精华内容
下载资源
问答
  • 银行排队算法: 行家算法是一种最有代表性的避免死锁的算法。在避免死锁方法中允许进程动态地申请资源,但是银行家算法系统在进行资源分配之前,应先计算此次分配资源的安全性,若分配不会导致系统进入不安全状态,...
  • 这个是借鉴了一下别人的代码的。原文:...这个问题综合性很高,把队列和链表的知识都照顾到了诶。 学习一下~ 还是先放截图吧 3.6.h #ifndef _3_6_H ...stdlib...

    这个是借鉴了一下别人的代码的。原文:https://www.cnblogs.com/kangjianwei101/p/5225738.html(膜大佬)
    这个问题综合性很高,把队列和链表的知识都照顾到了诶。
    学习一下~

    还是先放截图吧
    在这里插入图片描述


    3.6.h


    #ifndef _3_6_H
    #define _3_6_H
    
    #include<stdio.h>
    #include<stdlib.h>
    #include<unistd.h>
    #include<time.h> //provide seed
    
    #define TRUE 1
    #define FALSE 0
    #define OK 1
    #define ERROR 0
    #define OVERFLOW -2
    #define INDEFINE -3
    
    
    #define SleepTime 1
    #define DurationTime 20 // business time in a row 
    #define IntervalTime 10 // last customer come 
    
    typedef int Status;
    
    //when a variable value is certain,could use enum
    typedef enum 
    {
    	Arrive,Leave_1,Leave_2,Leave_3,Leave_4
    
    }EventType;
    
    typedef struct 
    {
    	int OccurTime;
    	EventType NType;
    	
    }Event;
    
    typedef Event LElemType_L;
    
    typedef struct LNode
    {
    	LElemType_L data;
    	struct LNode * next;
    }LNode;
    
    typedef LNode* LinkList;
    typedef LinkList EventList;
    
    typedef struct 
    {
    	int ArrivedTime;
    	int Duration;
    	int Count;
    	
    }QElemType_L;
    
    typedef struct QNode //队列也是要有下一个的
    {
    	QElemType_L data;
    	struct QNode *next;
    }QNode;
    
    typedef QNode* QueuePtr;
    
    typedef struct 
    {
    	QueuePtr front;
    	QueuePtr rear;
    	
    }LinkQueue;
    
    //global variable
    
    int gTotalTime,gCustomerNum;
    int gCloseTime = 10;
    EventList gEv;
    Event gEn;
    LinkQueue gQ[5];
    QElemType_L gCustomerRcd;
    
    //functions
    
    void Bank_Simulation_1();
    
    void OpenForDay();
    
    Status MoreEvent();
    
    void EventDrived(char * event);
    
    void CustomerArrived();
    
    void CustomerDeparture();
    
    void Invalid();
    
    void CloseForDay();
    
    int cmp(Event a,Event b);
    
    void Random(int *durtime,int *intertime);
    
    Status OrderInsert(EventList gEv,Event gEn,int(cmp)(Event,Event));
    
    int Minimum();
    
    void Show();
    
    void Bank_Simulation_2();
    
    
    #endif
    
    

    3.6.c


    #include "3_6.h"
    
    void
    Show()
    {
    	int i ;
    	QueuePtr p;
    	for(i = 1;i<=4;i++)
    	{
    		for(p = gQ[i].front; p ; p = p->next)
    		{
    			if(p == gQ[i].front)
    			{
    				if(i == 1)
    					printf("first: ⭕️");
    				if(i == 2)
    					printf("second:⭕️");
    				if(i == 3)
    					printf("third: ⭕️");
    				if(i == 4)
    					printf("forth: ⭕️");
    			}
    			else
    				printf(" (%03d) ",p->data.Count);
    
    			if(p == gQ[i].rear)
    				printf("\n");
    		}
    
    	}
    
    	sleep(SleepTime);
    	printf("\n");
    
    }
    
    void
    Random(int *durtime,int *intertime)
    {
    	srand((unsigned)time(NULL));
    	*durtime = rand()%DurationTime+1;
    	*intertime = rand()%IntervalTime+1;
    }
    
    
    int
    cmp(Event a,Event b)
    {
    	if(a.OccurTime < b.OccurTime)
    		return -1;
    	if(a.OccurTime == b.OccurTime)
    		return 0;
    	if(a.OccurTime > b.OccurTime)
    		return 1;
    	return INDEFINE;
    }
    
    
    Status
    InitList_L(LinkList *L)
    {
    	(*L) = (LinkList)malloc(sizeof(LNode));
    	if(!(*L))
    		exit(OVERFLOW);
    	(*L)->next = NULL;
    
    	return OK;
    }
    
    
    Status
    ListEmpty_L(LinkList L)
    {
    	if( L != NULL && L->next == NULL)
    		return TRUE;
    	else
    		return FALSE;
    
    }
    
    Status
    ListDelete_L(LinkList L,int i,LElemType_L *e)
    {
    	LinkList pre,p;
    	int j;
    
    	pre = L;
    	j = 1;
    
    	while(pre->next && j<i)
    	{
    		pre = pre->next;
    		++j;
    	}
    
    	if(!pre->next || j > i)
    		return ERROR;
    
    	p = pre->next;
    	pre->next = p->next;
    	*e = p->data;
    
    	free(p);
    
    	return OK;
    }
    
    Status
    InitQueue_L(LinkQueue *Q)
    {
    	(*Q).front = (*Q).rear = (QueuePtr)malloc(sizeof(QNode));
    	if(!(*Q).front)
    		exit(OVERFLOW); 
    
    	(*Q).front->next = NULL;
    
    	return OK;
    
    }
    
    int
    QueueLength_L(LinkQueue Q)
    {
    	int count = 0;
    	QueuePtr p = Q.front;
    
    	while(p != Q.rear)
    	{
    		count++;
    		p = p->next;
    	}
    
    	return count;
    }
    
    Status
    EnQueue_L(LinkQueue *Q,QElemType_L e)
    {
    	QueuePtr p;
    
    	p = (QueuePtr)malloc(sizeof(QNode));
    	if(!p)
    		exit(OVERFLOW);
    
    	p->data = e;
    	p->next = NULL;
    
    	(*Q).rear->next = p;
    	(*Q).rear = p;
    
    	return OK;
    }
    
    Status
    DeQueue_L(LinkQueue *Q,QElemType_L *e)
    {
    	QueuePtr p;
    
    	if( (*Q).front == (*Q).rear )
    		return ERROR;
    
    	p = (*Q).front->next;
    	*e = p->data;
    
    	(*Q).front->next = p->next;
    	if((*Q).rear == p)
    		(*Q).rear = (*Q).front;
    
    	free(p);
    
    	return OK; 
    
    }
    
    Status
    QueueEmpty_L(LinkQueue Q)
    {
    	if(Q.front == Q.rear)
    		return TRUE;
    	else
    		return FALSE;
    }
    
    Status
    GetHead_L(LinkQueue Q,QElemType_L *e)
    {
    	QueuePtr p;
    	if(Q.front == Q.rear)
    		return ERROR;
    	p = Q.front->next;
    	*e = p->data;
    
    	return OK;
    
    }
    
    int 
    Minimum()
    {
    	int i1 = QueueLength_L(gQ[1]);
    	int i2 = QueueLength_L(gQ[2]);
    	int i3 = QueueLength_L(gQ[3]);
    	int i4 = QueueLength_L(gQ[4]);
    
    	if( i1<=i2 && i1<=i3 && i1<=i4 )
    		return 1;
    	if( i2<i1 && i2<=i3 && i2<=i4 )
    		return 2;
    	if( i3<i1 && i3<i2 && i3<=i4 )
    		return 3;
    	if( i4<i1 && i4<i2 && i4<i3 )
    		return 4; 
    	return INDEFINE;
    }
    
    
    Status
    OrderInsert(EventList gEv,Event gEn,int(cmp)(Event,Event)) 
    {
    	int i;
    	EventList p,pre,s;
    
    	pre = gEv;
    	p = gEv->next; // 因为链表带头节点,所以p指向第一个事件
    
    	while(p && cmp(gEn,p->data) == 1) //查找事件gEn在时间表中插入的位置
    	{
    		pre = p;
    		p = p->next;
    	}
    
    	s = (LinkList)malloc(sizeof(LNode));
    	if(!s)
    		exit(OVERFLOW);
    
    	s->data = gEn;
    	s->next = pre->next;
    	pre->next = s;
    
    	return OK;
    
    }
    
    void
    OpenForDay()
    {
    	int i;
    
    	gTotalTime = 0;
    	gCustomerNum = 0;
    
    	InitList_L(&gEv);//为什么要用struct LNode ** 呀
    	//这里用的都是指向指针的指针!!!
    	//用二级指针的原因:
    	//一级指针作为函数参数可以交换两个数的值,
    	//二级指针作为函数参数可以改变一级指针的值,也就是改变地址。
     
    	gEn.OccurTime = 0;
    	gEn.NType = Arrive;
    
    	OrderInsert(gEv,gEn,cmp);
    
    	for(i = 1;i <= 4;i++)
    	{
    		InitQueue_L(&gQ[i]); // 同样的疑问
    	}
    
    	Show();       //最后再写
    } 
    
    
    Status
    MoreEvent()
    {
    	if(!ListEmpty_L(gEv))
    		return TRUE;
    	else
    		return FALSE;
    }
    
    void
    EventDrived(char *event)
    {
    	ListDelete_L(gEv,1,&gEn);
    
    	if(gEn.NType == Arrive)
    		*event = 'A';
    	else
    		*event = 'D';
    }
    
    void
    CustomerArrived()
    {
    	int durtime,intertime;
    	int cur_LeftTime,suc_ArrivalTime;
    	int i;
    
    	++gCustomerNum;
    
    	Random(&durtime,&intertime);
    
    	cur_LeftTime = gEn.OccurTime + durtime;
    	suc_ArrivalTime = gEn.OccurTime + intertime;
    
    	gCustomerRcd.ArrivedTime = gEn.OccurTime;
    	gCustomerRcd.Duration = durtime;
    	gCustomerRcd.Count = gCustomerNum;
    
    	i = Minimum(); 
    	EnQueue_L(&gQ[i],gCustomerRcd); //用户加入最短的队列
    
    	Show();
    
    	if(suc_ArrivalTime < gCloseTime)
    	{
    		gEn.OccurTime = suc_ArrivalTime;
    		gEn.NType = Arrive;
    		OrderInsert(gEv,gEn,cmp);
    	}
    
    	if(QueueLength_L(gQ[i]) == 1)
    	{
    		gEn.OccurTime = cur_LeftTime;
    		gEn.NType = i;
    		OrderInsert(gEv,gEn,cmp);
    	}
    
    
    }
    
    
    void
    CustomerDeparture()
    {
    	int i = gEn.NType;
    
    	DeQueue_L(&gQ[i],&gCustomerRcd);
    
    	Show();
    
    	gTotalTime = gEn.OccurTime - gCustomerRcd.ArrivedTime;
    
    	if(!QueueEmpty_L(gQ[i]))
    	{
    		GetHead_L(gQ[i],&gCustomerRcd);
    		gEn.OccurTime += gCustomerRcd.Duration; 
    		gEn.NType = i;
    		OrderInsert(gEv,gEn,cmp); 
    	}
    }
    
    void
    Invalid()
    {
    	printf("wrong!\n");
    	exit(OVERFLOW);
    }
    
    void
    CloseForDay()
    {
    	printf("Today have %d customers,The Average Time is %f\n",
    		gCustomerNum, (float)gTotalTime / gCustomerNum);
    }
    
    
    
    
    void 
    Bank_Simulation_1()
    {
    	char eventType;
    
    	OpenForDay();
    
    	while(MoreEvent())
    	{
    		EventDrived(&eventType);
    
    		switch(eventType)
    		{
    			case 'A':
    				CustomerArrived();
    				break;
    			case 'D':
    				CustomerDeparture();
    				break;
    			default:
    				Invalid(); 
    		}
    	}
    
    	CloseForDay();
    }
    
    
    
    
    
    void Bank_Simulation_2()
    {
    	OpenForDay();
    	while(!ListEmpty_L(gEv))
    	{
    		ListDelete_L(gEv,1,&gEn);
    
    		if(gEn.NType == Arrive)
    			CustomerArrived();
    		else
    			CustomerDeparture();
    	}
    }
    
    
    
    
    int main(int argc, char const *argv[])
    {
    	Bank_Simulation_1();
    
    	return 0;
    }
    
    
    展开全文
  • 解决选择两个队列中时间比较短的那个队列排队,选择花费时间最短的队列进行排队
  • 算法3-7:银行排队

    千次阅读 2018-10-25 15:09:52
    我们大多都有在银行排队的经历,唉,那坑爹的排队啊!现在就让我们来算算我们这些客户平均需要等多久吧。 每天刚开始时银行会开m个窗口来为我们total个客户办理业务,当有客户需要办理业务时,先选择可以办理业务的...

    题目描述

    我们大多都有在银行排队的经历,唉,那坑爹的排队啊!现在就让我们来算算我们这些客户平均需要等多久吧。
    每天刚开始时银行会开m个窗口来为我们total个客户办理业务,当有客户需要办理业务时,先选择可以办理业务的窗口,如果有多个窗口可以办理业务就选择空闲时间最长的窗口,如果有多个窗口空闲的时间一样长,则选择序号小的窗口办理业务。假设我们每个人来到的时间和办理业务所需要的时间(为了简化问题,采用整数表示时间)都知道了。现在请你算算我们平均需要等待多久呢?

    输入描述

    有多组测试数据,每组数据开始有两个正整数m(<20)和total(<200),后面有total对整数,对应客户先后到来的时间以及办理业务所需的时间。

    输出描述

    平均等待的时间,保留两位小数。

    输入样例

    2 6 1 3 4 1 5 3 9 2 13 4 13 3
    3 14 0 3 2 2 2 4 5 4 7 2 11 3 12 3 12 4 12 1 13 3 15 4 19 1 22 3 23 2
    2 5 0 6 0 5 0 6 7 1 7 2

    输出样例

    0.00
    0.29
    1.20

    提示

    提示:

    题目中选择办理的窗口有三个状态,实际上从序号自小到大查找可以最早办理业务的窗口就已经满足上述三个状态了。可以使用数组来模拟列表。

    总结:

    实际上数组既可以模拟堆栈又可以模拟队列。

     

    #include<stdio.h>
    #include<string.h>
    
    
    //ÓÃһάÊý×é µÄÿһλ±íʾ¸Ã´°¿ÚÀ뿪µÄʱ¼ä 
    int main()
    {
    	int a[100]; 
    	int n,m,j,k,i,T,x,y,total,current;
    	double sum;
    	while (scanf("%d%d",&m,&total)!=EOF)
    	{
    		
    		sum=0;
    		current=0;
    		memset(a,0,sizeof(a));
    		for (i=0;i<total;i++)
    		{
    			scanf("%d%d",&x,&y);
    			int min = 1000000;
    			for (j=0;j<m;j++)
    			{
    				if (a[j]<a[current])//
    				{
    					min = a[j];
    					current = j;
    				}
    			}
    			if (x<=a[current])//ÐèÒªÅÅ¶Ó 
    			{
    				sum += (a[current] - x) ;
    				a[current] += y;
    			}
    			else//²»ÐèÒªÅÅ¶Ó 
    			{
    				a[current] = x+y;
    			}
    			
    		}
    		
    		printf("%.2lf\n",sum/(1.0*total) );
    	}
    	
    		
    	return 0;
     } 

     

    展开全文
  • 【数据结构】(五)队列,链式队列(银行排队算法) (一)队列:(如果用循环将使算法时间变得复杂,所以为了提高运算效率,引入队列) (1)假溢出:(为了解决假溢出,引入循环队列) (2)循环队列:(判断空...

    【数据结构】(五)队列,链式队列(银行排队算法)

    (一)队列:(如果用循环将使算法时间变得复杂,所以为了提高运算效率,引入队列
    在这里插入图片描述
    (1)假溢出:(为了解决假溢出,引入循环队列
    在这里插入图片描述
    (2)循环队列:(判断空满条件
    在这里插入图片描述
    其中方法二:
    在这里插入图片描述

    (3)队列的创建:(所有的引用修改都是为了可以传出去而使用的)
    C++:
    在这里插入图片描述
    C语言:
    在这里插入图片描述
    (4)操作:
    入队:
    在这里插入图片描述
    出队:
    在这里插入图片描述
    在主函数中输出item:
    在这里插入图片描述
    改为C++中语句:
    在这里插入图片描述
    读取对头元素:
    在这里插入图片描述
    (二)链式队列:
    C++:
    在这里插入图片描述

    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    (2)区别:
    在这里插入图片描述
    (三)银行排队(离散事件模拟)问题:
    在这里插入图片描述
    表示:
    如16,19,23都表示客户所用时间;
    例如:16 2 -->表示在第二个窗口花了16分钟,对应5 11(排队5分钟,业务11分钟)
    在这里插入图片描述
    算法:(先图解,最后会有对应代码块)
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    还需要一个链表来存储和处理事件:
    在这里插入图片描述
    在这里插入图片描述
    操作:cpp
    在这里插入图片描述
    在这里插入图片描述
    代码:
    List.h文件

    #pragma once
    #include <iostream>
    using namespace std;
    #include <string>
    
    
    //*************----《链表初始化定义》----***********//
    
    typedef struct evNode
    {
    	int occurtime;   //事件发生时间
    	int nType;       //事件类型:-1表示到达,0~3表示四个窗口
    	struct evNode* next;
    }evNode;
    
    class EventList
    {
    private:
    	evNode* head;   //头指针
    	int length;
    public:
    	EventList()   //构造函数
    	{
    		head = new evNode;
    		head->next = NULL;
    		length = 0;
    	}
    	~EventList()  //析构函数,删除节点,清空
    	{
    		//释放再堆区开辟的所有节点
    		//保存释放的下一个节点
    		while (head->next)
    		{
    			evNode* p = head->next->next;
    			delete(head->next);
    			head->next = p;
    		}
    		length = 0;
    	}
    	bool isEmpty()  //判断是否为空
    	{
    		if (length == 0)
    		{
    			return true;
    		}
    		else
    		{
    			return false;
    		}
    	}
    	void addNode(EventList List, evNode* eventItem)   //向链表插入数据
    	{
    		//插入是要按离开或者到达的时间顺序进行插入
    		evNode* p = new evNode;
    		p = eventItem;
    		//对链表进行遍历,找到新用户该插入的位置
    		evNode* qi, * hou;    //前后指针,用于查找插入排序
    		qi = List.head;
    		hou = List.head->next;
    		while (hou != NULL)
    		{
    			if (p->occurtime <= hou->occurtime)
    			{
    				//将新用户节点插在该节点前面
    				p->next = hou;
    				qi->next = p;
    				qi->next->next = hou;
    				break;
    			}
    			qi = hou;
    			hou = hou->next;
    		}
    		qi->next = p;
    		length++;
    	}
    	void deleteNode(EventList List, evNode* firstNode)   //对链表删除数据
    	{
    		evNode* p = new evNode;
    		p = List.head->next;
    		firstNode = p;
    		List.head = p->next;
    		delete(p);
    		p = NULL;
    		length--;
    	}
    	void displayNode()  //遍历数据
    	{
    		evNode* p = head->next;
    		while (p)
    		{
    			if (p->nType == -1)
    			{
    				cout << "新用户到达时间为:" << p->occurtime << endl;
    			}
    			else
    			{
    				cout << p->nType << "号窗口的用户离开时间为:" << p->occurtime << endl;
    			}
    			p = p->next;
    		}
    	}
    };
    

    Queue.h文件:

    #pragma once
    #include <iostream>
    using namespace std;
    #include <string>
    
                               //************----《队列初始化定义》----************//
    
    //定义银行客户,Client作为队列的data域
    typedef struct Client
    {
    	int arrivetime;   //客户到达银行时间
    	int duration;     //客户办理业务时间
    }Client;
    
    struct Node
    {
    	Client data;   //包含客户信息
    	struct Node* next; 
    };
    
    class Queue       //银行窗口队列类
    {
    private:
    	Node* front;   //头尾指针
    	Node* rear;
    	int length;   //队列长度,因为插入时会标记不同的窗口队列,所以不必担心length加重的问题
    public:
    	Queue()     //建立头节点,初始化属性
    	{
    		front = new Node;
    		rear = front;
    		front->next = NULL;
    		length = 0;
    	}
    	~Queue()     //释放队列空间
    	{
    		if (front == rear)
    		{
    			return;
    		}
    		else
    		{
    			while (front)   //直到删完为止
    			{
    				rear = front->next;
    				delete(front);
    				front = rear;
    			}
    			length = 0;
    		}
    	}
    	void enQueue(Client person)   //入队
    	{
    		//不用判断队列是否为满,因为是链式存储
    		//头插
    		Node* p=new Node;
    		p->data = person;
    		p->next = NULL;
    
    		rear->next = p;
    		rear = p;
    		length++;
    	}
    	bool deQueue()  //出队
    	{
    		//队列为空,返回假
    		if (front == rear)
    		{
    			return false;
    		}
    		//进行头删
    		Node* p = front->next;
    		front->next = p->next;
    		//判断删除的是否是最后一个节点,是的话把rear指向头结点
    		if (p == rear)
    		{
    			rear = front;
    		}
    		delete(p);
    		p = NULL;
    		length--;
    		return true;
    	}
    	bool getQueue(Client* item)  //获取队头元素到item所☞单元
    	{
    		if (length == 0)
    		{
    			cout << "无对头元素" << endl;
    			system("pause");
    			exit(0);
    		}
    		else
    		{
    			Node* p ;
    			p = front->next;
    			*item = p->data;
    			delete(p);
    			return true;
    		}
    	}
    	bool isEmpty()     //判断是否为空
    	{
    		if (length == 0)
    		{
    			return true;
    		}
    		else
    			return false;
    	}
    	void clearQueue()   //清空队列
    	{
    		//清空除头结点以外的节点
    		Node* p;
    		p = front->next;
    		while (p)
    		{
    			Node* nextNode = p;
    			p = p->next;
    			delete(nextNode);
    		}
    		p = NULL;
    		//尾指针更新到头指针处
    		front->next = NULL;
    		rear = front;
    		length = 0;
    	}
    	int queueLength()    //获取元素个数
    	{
    		return length;
    	}
    };
    
    

    cpp文件:

    #include "Queue.h"
    #include "List.h"
    #include<time.h>
    #define Closetime 40 //银行关门时间
    int findMin(Queue queue[], int len);
    
    //现写出银行业务活动如下:
    //模仿
    double  simulation()
    {
    	//为客户服务的总时长
    	int totalTime = 0;
    	//客户人数
    	int customerNum = 0;
    	//初始化四个窗口队列
    	Queue queue[4];
    	//初始化事件链表对象
    	EventList List;
    	//初始化一个客户结构体
    	Client person;
    	//设定第一个客户到达的事件
    	evNode eventItem = { 0, -1, NULL };
    	//将第一个客户放到事件链表中
    	List.addNode(List,&eventItem);
    	//判断事件链表是否为空,不为空取出事件链表中第一个事件节点,判断是用户到达事件还是用户离开事件
    	while (!List.isEmpty())
    	{
    		evNode firstNode;
    		List.deleteNode(List,&firstNode);    //弹出(读取)链表第一个数同时在链表中删除第一个数
    		cout << "第一个事件类型:" << firstNode.nType<<"  ";
    
    		if (firstNode.nType == -1)  //-1表示客户刚到
    		{
    			customerNum++;   //客户人数加一
    
    			//生成随机函数-->服务时间,-->下一位顾客到来时间
    			int duringTime = rand() % 30 + 1;   //接受服务时间范围是1到30
    			int nextcustomertime = rand() % 20 + 1; //下一个用户到来的间隔时间范围是1到20
    			cout << "当前客户接受服务所用时间: " << duringTime << endl;
    			//下一个新用户到来的时间---下一个到来事件发生的时间
    			 //要判断下一个用户到来的时候,银行有没有关门
    			//当前新用户到达时间+间隔时间
    			if (firstNode.occurtime < Closetime)
    			{
    				//设定下一个用户的到达事件插入事件表
    				evNode nextPerson;
    				//表示下一个顾客到达时间,方式
    				nextPerson = { firstNode.occurtime + nextcustomertime,-1,NULL };
    
    				cout << "下一个用户到达时间: " << nextPerson.occurtime << "  ";
    				List.addNode(List,&nextPerson);
    			}
    			//把当前到达的用户,放到当前排队人数最少的队列中
    			//若四个队列排队人数相同,就按队列的顺序从下标小的先插入
    			int min = findMin(queue, 4);
    
    			cout << "去" << min << "窗口排队最好" << endl;
    
    			//当前客户进入人数最少的队列
    			//先对客户结构体进行赋值
    			person = { firstNode.occurtime , duringTime };  
    
    			//入队
    			queue[min].enQueue(person);
    
    			//入队完了之后,判断当前客户是不是窗口的第一个人,如果是就要把他的离开事件放入事件表中
    			if (queue[min].queueLength() == 1)
    			{
    				evNode Putincust = { firstNode.occurtime + duringTime, min, NULL };
    				cout << "用户离开时间为: " << Putincust.occurtime << "  ";
    				cout << "离开窗口: " << min <<"\n\n"<< endl;
    				//将离开事件插入事件链表中
    				List.addNode(List,&Putincust);
    			}
    		}
    		else     //表示处理的是用户离开事件
    		{
    			//记录该用户从几号窗口离开
    			int index = firstNode.nType;
    			//获取队头元素
    			Client leaver;
    			queue[index].getQueue(&leaver);
    			//客户离开的时候,要累积客户的逗留时长
    			totalTime = leaver.duration;
    			//出队
    			queue[index].deQueue();
    
    			//判断出完队后,当前队列是否为空,如果为空,就不管
    			//如果还有下一个用户,就要把下一个用户的离开事件放入事件表中
    			if (queue[index].queueLength() != 0)
    			{
    				Client nextPer;
    				queue[index].getQueue(&nextPer);
    				//离开的时间等于到达的时间加上逗留的时间
    				evNode tempNode = { nextPer.arrivetime + nextPer.duration,index,NULL };
    				List.addNode(List,&tempNode);
    			}
    		}
    		cout << "当前正在处理的事件" << endl;
    		cout << endl;
    	}
    	//计算客户的平均逗留时间
    	cout << "\n\n用户访问总数: " << customerNum << "  ";
    	cout << "总时间" << totalTime << endl;
    	return totalTime / customerNum;
    }
    
    
    int findMin(Queue queue[], int len)      //找出排队人数最少的窗口下标
    {
    	int min = queue[0].queueLength();
    	int Index = 0;
    	for (int i = 0; i < len; i++)
    	{
    		if (min < queue[i].queueLength())
    		{
    			min = queue[i].queueLength();   //多长
    			Index = i;  //那个窗口
    		}
    		else
    		{
    			continue;
    		}
    	}
    	return Index;
    }
    
    
    int main()
    {
    	srand(unsigned int((time(NULL))));   //随机函数
    	double num = simulation();
    	cout << "用户平均服务时间: " << num << endl;
    	system("pause");
    	return 0;
    }
    

    结果:
    在这里插入图片描述

    展开全文
  • 排队论与银行排队系统,详细讲解了一些常见的排队算法
  • 基本算法为,输入用户信息特征因素向量B[1,n]优化因素特征矩阵C[n,m] n为特征类型的得分数 m为窗口号,特征包括该时段内历史业务办理情况,员工熟练度,当前排队情况等…D=B*C得到D向量...
  • 银行排队

    千次阅读 2016-04-14 23:25:44
    问题 H 算法3-7:银行排队 时间限制: 1 Sec 内存限制: 128 MB [提交] 题目描述 我们大多都有在银行排队的经历,唉,那坑爹的排队啊!现在就让我们来算算我们这些客户平均需要等多久吧。 每天刚开始时...

    问题 H 算法3-7:银行排队

    时间限制: 1 Sec  内存限制: 128 MB
    [提交]

    题目描述

    我们大多都有在银行排队的经历,唉,那坑爹的排队啊!现在就让我们来算算我们这些客户平均需要等多久吧。
    每天刚开始时银行会开m个窗口来为我们total个客户办理业务,当有客户需要办理业务时,先选择可以办理业务的窗口,如果有多个窗口可以办理业务就选择空闲时间最长的窗口,如果有多个窗口空闲的时间一样长,则选择序号小的窗口办理业务。假设我们每个人来到的时间和办理业务所需要的时间(为了简化问题,采用整数表示时间)都知道了。现在请你算算我们平均需要等待多久呢?

    输入

    有多组测试数据,每组数据开始有两个正整数m(<20)和total(<200),后面有total对整数,对应客户先后到来的时间以及办理业务所需的时间。

    输出

    平均等待的时间,保留两位小数。

    样例输入

    2 6 1 3 4 1 5 3 9 2 13 4 13 33 14 0 3 2 2 2 4 5 4 7 2 11 3 12 3 12 4 12 1 13 3 15 4 19 1 22 3 23 22 5 0 6 0 5 0 6 7 1 7 2

    样例输出

    0.000.291.20

    #include<stdio.h>
    #include<string.h>
    #include<stdlib.h>
    #include<malloc.h>
    #include<math.h>
    int top[22];
    int time[22];
    int qu[22][202];
    int m,tol;
    float tc=0;
    void pu(int a,int b){
        int k;
        int t=cho(a,b);
        //printf("%d\n",t);
        top[t]++;
        qu[t][top[t]]=a+b;
    }
    int cho(int a,int b){
        int i=0;
        for(i=0;i<m;i++){
            if(time[i]+qu[i][top[i]]<=a){
                time[i]=0;
                return i;
            }
        }
        int min=999999;
        int t=0;
        for(i=0;i<m;i++){
            if((time[i]+qu[i][top[i]]-a)<min){
                min=time[i]+qu[i][top[i]]-a;
                //printf("%d\n",min);
                t=i;
            }
        }
        time[t]=min;
        tc+=min;
        return t;
    }
    int main(){
        int i,j;
        int a,b;
        while(~scanf("%d",&m)){
            scanf("%d",&tol);
            for(i=0;i<tol;i++){
                scanf("%d %d",&a,&b);
                    pu(a,b);
            }
            printf("%1.2f\n",tc/tol);
            memset(time,0,sizeof(time));
            memset(top,0,sizeof(top));
            tc=0;
        }
        return 0;
    }
    


    展开全文
  • 就是类似那个银行的业务排号系统,正常情况应该是从四个线程各自取号,但是四个线程取出来的都是1,后面的号都取不出来,不知道问题出在哪里。。。求大神指教。。。 代码: CS.java import java.util....
  • 银行的单窗口排队问题中,假设银行只有1个窗口提供服务,所有顾客按到达时间排成一条长龙。当窗口空闲时,下一位顾客即去该窗口处理事务。此时如果已知第i位顾客与排在后面的第j位顾客是好朋友,并且愿意替朋友...
  • 我的数据结构与算法题目集代码仓:https://github.com/617076674/Data-structure-and-algorithm-topic-set ...思路:模拟银行排队问题 (1)用一个unordered_map&lt;string, int&gt;类型...
  • 谁能用C#设计一个银行排队叫号系统,简单的就行。需要帮我写一段代码,谢谢!!或者实现原理。
  • 银行排队模拟程序功能 假设某银行有四个窗口对外接待客户,从早晨银行开门起不断有客户进入银行。由于每个窗口只能接待一个客户,因此在客户人数众多时需在每个窗口前顺次排队,对于刚进入银行的客户,如果某个窗口的...
  • 数据结构简单模拟银行排队系统

    千次阅读 多人点赞 2020-06-12 02:06:17
    银行排队系统实现 功能要求: (1) 客户进入排队系统; (2) 客户离开; (3) 查询当前客户前面还有几人; (4) 查询截至目前总共办理多少客户。 输出要求:每进行一次操作后,输出当前排队成员情况。 算法实现 ...
  • 1.银行排队模拟程序简介: 2.算法所需要的数据结构和相当解释说明 3.事件算法运行时的某个状态 初始化 生成随机数后要做的事情
  • 算法就相当于是现在银行实行的叫号制度。每个窗口只有一个客户正在办理手续,其它客户都在等待区等待且根据到达事件进行排序,当某个窗口的客户办完业务时,将等待区的最先到达的客户安排到刚空闲下来的窗口去办理...
  • 银行的单窗口排队问题中,假设银行只有1个窗口提供服务,所有顾客按到达时间排成一条长龙。当窗口空闲时,下一位顾客即去该窗口处理事务。此时如果已知第i位顾客与排在后面的第j位顾客是好朋友,并且愿意替朋友...
  • 数据结构与算法题目集7-48——银行排队问题之单窗口“夹塞”版 #include<bits/stdc++.h> using namespace std; struct people { string name; int arrive; int cost; }; queue<people>
  • 优先队列保存窗口时间,每次选出最小时间处理讲解算法思路代码部分pat运行结果复杂度分析 讲解 设置一个将题干hh:mm:ss时间转化为秒为单位的时间的函数 利用一个优先队列(这里是一个小根堆,每次top为时间最小的...
  • 用程序简单模拟一个单队列多窗口的排队模式: 设某银行有一个固定能容纳N个顾客的等候区,顾客想进银行,若等候区有空则可进,否则被拒绝进入。 每当银行柜员叫号时,等候区中最先进入的顾客离开等候区前往柜台办理...
  • 利用的算法类似于买票排队,你总会到队列最短的窗口去排队,但往往会有其他队列办事速度快,队列长度很快变得比你所在队列的还短,但你改变自己的队列去当前较短的队列时,可能没过多久刚刚你在的队列又比你现在所处...
  • 建立了银行柜台设置的优化模型,应用排队论理论,提出了随机环境下具有可变输入率的适时调整窗口数量的算法,给出了改善整个柜台系统服务效率的设想.

空空如也

空空如也

1 2 3 4 5 ... 11
收藏数 218
精华内容 87
关键字:

银行排队算法