「数据结构」第四次作业(2023春 - 银行排队模拟)

这篇具有很好参考价值的文章主要介绍了「数据结构」第四次作业(2023春 - 银行排队模拟)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

第四次作业(银行排队模拟)

5. 银行排队模拟(生产者-消费者模拟) - 分类别

这道题比较难,单独拿出来说。

先再看一遍题目:

题干描述:

【问题描述】

一个系统模仿另一个系统行为的技术称为模拟,如飞行模拟器。模拟可以用来进行方案论证、人员培训和改进服务。计算机技术常用于模拟系统中。

生产者-消费者(Server-Custom)是常见的应用模式,见于银行、食堂、打印机、医院、超等提供服务和使用服务的应用中。这类应用的主要问题是消费者如果等待(排队)时间过长,会引发用户抱怨,影响服务质量;如果提供服务者(服务窗口)过多,将提高运管商成本。(经济学中排队论)

假设某银行网点有五个服务窗口,分别为三个对私、一个对公和一个外币窗口。银行服务的原则是先来先服务。通常对私业务人很多,其它窗口人则较少,可临时改为对私服务。假设当对私窗口等待服务的客户(按实际服务窗口)平均排队人数超过(大于或等于)7人时,等待客户将可能有抱怨,影响服务质量,此时银行可临时将其它窗口中一个或两个改为对私服务,当平均排队客户少于7人时,将立即恢复原有业务。设计一个程序用来模拟银行服务。

说明:

  1. 增加服务窗口将会增加成本或影响其它业务,因此,以成本增加或影响最小为原则来增加服务窗口,即如果增加一个窗口就能使得按窗口平均等待服务人数小于7人,则只增加一个窗口。一旦按窗口平均等待服务人数小于7人,就减少一个所增加的窗口。

  2. 为了简化问题,假设新到客户是在每个服务周期开始时到达。

  3. 根据客户业务服务时间将客户分为3类:1(简单业务)、2(普通业务)、3(复杂业务),分别对应花费1-3个时间周期。

  4. 当等待服务人数发生变化时(新客户到达或有客户已接受服务),则及时计算按实际服务窗口平均等待服务人数,并按相应策略调整服务窗口数(增加或减少额外的服务窗口,但对私窗口不能减少)。

注意:只在获取新客户(不管到达新客户数是否为0)时,才按策略调整服务窗口数。进一步讲,增加服务窗口只在有客户到达的周期内进行(也就是说增加窗口是基于客户的感受,银行对增加窗口是不情愿的,因为要增加成本,一旦不再有新客户来,银行是不会再增加服务窗口的);一旦有客户去接受服务(即等待客户减少),银行将根据策略及时减少服务窗口,因此,在每个周期内,有客户去接受服务后要马上判断是否减少服务窗口(因为能减少成本,银行是积极的)。

本问题中假设对公和对外币服务窗口在改为对私服务时及服务期间没有相应因公或外币服务新客户到达(即正好空闲),同时要求以增加成本或影响最小为前提,来尽最大可能减少对私服务客户等待时间。

【输入形式】

首先输入一个整数表示时间周期数,然后下一行输入每个时间周期到达的客户人数;再依次分行输入每个时间周期到达的因私业务的客户类别。注:一个时间周期指的是银行处理一笔业务的平均处理时间,可以是一分钟、三分钟或其它。每行中的整数之间以一个空格分隔。

例如:

6

2 5 8 11 15 6

1 3

2 2 1 3 2

说明:共有6个时间周期,第1个周期来了2个客户(序号分别为1、2,业务分别为简单业务和复杂业务),第2个时钟周期来了5人(序号分别为3、4、5、6、7,业务分别为普通业务、普通业务、简单业务、复杂业务和普通业务),以此类推。

【输出形式】

每个客户等待服务的时间周期数。输出形式如下:

用户序号 : 等待周期数

说明:客户序号与等待周期数之间用英文冒号:分隔,冒号(:)两边各有一个空格,等待周期数后直接为回车。

【样例输入】

4

2 5 13 11

1 3

2 2 1 3 2

1 1 1 1 3 3 2 2 1 2 3 1 1

3 3 2 1 3 1 1 3 1 3 3

【样例输出】

1 : 0

2 : 0

3 : 0

4 : 0

5 : 2

6 : 2

7 : 2

8 : 1

9 : 2

10 : 3

11 : 3

12 : 4

13 : 4

14 : 4

15 : 6

16 : 7

17 : 7

18 : 8

19 : 8

20 : 9

21 : 8

22 : 9

23 : 10

24 : 11

25 : 12

26 : 12

27 : 12

28 : 13

29 : 13

30 : 14

31 : 15

【样例说明】

样例输入表明有四个时间周期,第一个周期来了2人(序号1-2);第二个周期来了5人(序号3-7);第三个周期来了13人(序号8-20);第四个周期来了11人(序号21-31)。由于第一个时间周期内只来了2人,银行(有三个服务窗口)能及时提供服务,因此客户等待时间为0;第二个时间周期内来了5人,银行一个周期内一次只能服务3人,而且第一个周期内有一位办理复杂业务的客户,所以这时只有两个空闲窗口可以提供服务,前2人等待时间为0,另外3人需要等待;其它类推。

【评分标准】

通过所有测试点得满分。

参考解答:

笑死,助教也被这道题恶心到了,交了两遍总算过了。这题今年(2023春)有修改过,然后原本就模糊的描述更加不明所以了。

这题最难的地方在于理解题目,或者直白点说:什么时候增加窗口什么时候减少窗口

从我的代码里可以看到:

  • 队列人数增加,也就是有新的客户入队时,判断是否应该增加窗口。
  • 队列人数减少,也就是有些人进入窗口后,判断是否应该减少窗口。

从上面两点我们可以知道,当后续不再有客户进入银行后,队列只增不减。

还有一个误区:

题目并未要求每次服务过程中平均等待人数均少于7人。

而且,引用另一个助教的话:如果当前需要减少的这个窗口,正在服务复杂业务,可能还需要1~2个周期才能服务完,那这个窗口在计算时候是要减少(即不能给它分配新的客户),但原先的客户是要继续服务的

如果你还是不能理解,下面我换一种说法:

  1. 这题的队列不是你们传统认知上,比如你一进食堂就决定排哪条队伍,然后就呆在一条队伍直到轮到你的过程。这道题的背景是银行,其实想象成银行的叫号更加准确,即客户一进银行就领取一个号码,然后等待窗口”叫到你“再去接受服务。

  2. 然后就是我在上面提到的队列人数变化。当这一轮有新的客户进入(哪怕是0人),处于”等待区“的人数过多时,就多开窗口,尽量满足平均等待人数小于7人;当一部分等待区中的人到窗口去服务时,等待区人数减少,就判断是否需要减少窗口,这个减少窗口实际上指的是减少“预分配的窗口”,已经在窗口接受服务的用户是不受影响的。

  3. 按照这种理解,如果客户服务尚未完成(是普通或者复杂服务),他仍需在窗口接受服务,但是等待区不包含该用户,在窗口减少的过程中,也不需要影响或者变化该用户的服务情况。

具体的实现看代码吧,思路还是比较清晰的。文章来源地址https://www.toymoban.com/news/detail-427546.html

#include <stdio.h>
#include <stdlib.h>

typedef struct node
{
	int num;
	int val;
	int wait;
	struct node *next;
} node, *nodeptr;

int main()
{
	int t;
	int nums[20];
	
	int res[200];

	scanf("%d", &t);
	for (int i = 0; i < t; i++)
	{
		scanf("%d", nums + i);
	}

	nodeptr head = (nodeptr)malloc(sizeof(node));
	head->next = NULL;
	nodeptr tail = head;

	int num_cnt = 1;
	int wait_cnt = 0;
	int window_cnt = 3;

	for (int i = 0; i < t; i++)
	{
		// 先把所有新用户加入等待队列
		for (int j = 0; j < nums[i]; j++)
		{
			tail->next = (nodeptr)malloc(sizeof(node));
			tail = tail->next;
			tail->num = num_cnt++;
			scanf("%d", &(tail->val));
			tail->wait = 0;
			tail->next = NULL;
		}

		// 队列人数增加->判断是否应该增加窗口
		wait_cnt += nums[i];
		if (wait_cnt / window_cnt >= 7 && window_cnt < 5)
		{
			window_cnt = (wait_cnt / 7 + 1) <= 5 ? (wait_cnt / 7 + 1) : 5;
		}

		// 窗口处理用户服务
		nodeptr q = head;
		nodeptr p = head->next;
		for (int j = 0; j < window_cnt && p != NULL; j++)
		{
			(p->val)--;
			if (!(p->val))
			{
				res[p->num] = p->wait;
				q->next = p->next;
				free(p);
				p = q->next;
				if (p == NULL)
				{
					tail = q;
				}
			}
			else
			{
				q = p;
				p = p->next;
			}
		}

		// 增加还在等待中的所有客户的等待时间
		wait_cnt = 0;
		while (p != NULL)
		{
			(p->wait)++;
			p = p->next;
			wait_cnt++;
		}

		// 队列人数减少->判断是否应该减少窗口
		if (wait_cnt / window_cnt < 7 && window_cnt > 3)
		{
			window_cnt = (wait_cnt / 7) >= 3 ? wait_cnt / 7 : 3;
		}
	}

	while (head != tail)
	{
		// 窗口处理用户服务
		nodeptr q = head;
		nodeptr p = head->next;
		for (int j = 0; j < window_cnt && p != NULL; j++)
		{
			(p->val)--;
			if (!(p->val))
			{
				res[p->num] = p->wait;
				q->next = p->next;
				free(p);
				p = q->next;
				if (p == NULL)
				{
					tail = q;
				}
			}
			else
			{
				q = p;
				p = p->next;
			}
		}

		// 增加还在等待中的所有客户的等待时间
		wait_cnt = 0;
		while (p != NULL)
		{
			(p->wait)++;
			p = p->next;
			wait_cnt++;
		}

		// 队列人数减少->判断是否应该减少窗口
		if (wait_cnt / window_cnt < 7 && window_cnt > 3)
		{
			window_cnt = (wait_cnt / 7) >= 3 ? (wait_cnt / 7) : 3;
		}
	}

	// 输出结果
	for (int i = 1; i <= num_cnt - 1; i++)
	{
		printf("%d : %d\n", i, res[i]);
	}

	return 0;
}

到了这里,关于「数据结构」第四次作业(2023春 - 银行排队模拟)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 运维第四次作业

    1. 简述静态网页和动态网页的区别。 静态网页和动态网页的区别在于内容的生成方式。静态网页的内容在服务器上预先创建好,并在用户访问时直接传送给浏览器,内容不会改变。而动态网页的内容是在用户访问时才在服务器上生成,可以根据用户的请求和其他参数动态地生

    2024年02月14日
    浏览(42)
  • Python第四次作业

    周六: 1. 找出10000以内能被5或6整除,但不能被两者同时整除的数(函数) 2. 写一个方法,计算列表所有偶数下标元素的和(注意返回值)  3. 根据完整的路径从路径中分离文件路径、文件名及扩展名   4. 根据标点符号对字符串进行分行  5. 去掉字符串数组中每个字符串的空格

    2024年04月11日
    浏览(31)
  • 合肥工业大学机器人技术第四次作业:生成决策树

    样本数据 ID3生成决策树基本算法 计算数据整体的香农信息熵 对每个属性,分别计算条件熵 计算条件增益 选择最有条件增益作为决策树的根节点 重复上述步骤,直到信息熵降为0.达到根节点 使用sklearn生成ID3决策树 Python第三方库 sklearn 提供了决策树生成算法,此次作业便是用

    2024年02月06日
    浏览(50)
  • 银行排队模拟(数据结构--队列)

    既然你点进了这篇博客,想必大概是大一 ,而且学到了队列,刚好严蔚敏老师的数据结构在讲队列的那章讲了银行排队的模拟,为什么我知道呢?因为我就是,好了谢谢你有耐心地看完我说的“废话”,下面我就简述一下,队列的实现就不讲了,很简单就是一个先进先出。

    2024年02月03日
    浏览(32)
  • 【NJUPT】 数据结构与算法分析_银行排队系统

    银行排队系统 【问题描述】 试设计一个银行排队系统,模拟一般银行的日常对外营业服务,包括顾客到达、等待、办理业务及离开等事件。要求体现“先来先服务”的原则,将传统物理的多个顾客排队队列变为一个逻辑队列处理,顾客只需取票(即刻进队,排队),等待叫

    2024年02月04日
    浏览(53)
  • 408数据结构第四章

    小题形式考,比较简单,拿两个题来练手就会了 字符串简称串 由零个或多个字符组成的有限序列 S是串名n称为串的长度,n=0称为空串 串中多个连续的字符组成的子序列称为该串的子串 串的逻辑结构和线性表极为相似,区别仅在于串的数据结构对象限定为字符集 线性表的基

    2024年02月11日
    浏览(34)
  • 数据结构 第四章:串

    所谓串其实就是字符串,该小节我们会先学习串的定义和相关基本操作。也就是要探讨它的逻辑结构和基本运算(数据结构三要素:逻辑结构、存储结构、数据的运算) 1.1.1串的定义 串 ,即字符串(String)是由零个或多个 字符 组成的有序序列。 一般记为S=‘a1a2…an’(n=0)

    2024年02月06日
    浏览(40)
  • 数据结构 第四章 栈

    🚀 写在最前 :这篇文章将学习栈这种结构,以及该结构的一些基本操作的实现,包括顺序存储栈和链式存储栈的基本操作的实现。 🚀:点求个关注,让我们一起探索计算机的奥秘! 所谓的 栈就是一种特殊的线性表 ,对于栈这种逻辑结构来说他和线性表最大的区别就是 栈

    2024年04月15日
    浏览(40)
  • 《数据结构》_PTA_数据结构作业6:图

    1-1 无向连通图所有顶点的度之和为偶数。 T 1-2 无向连通图边数一定大于顶点个数减1 F 1-3 无向连通图至少有一个顶点的度为1。 F 1-4 用邻接表法存储图,占用的存储空间数只与图中结点个数有关,而与边数无关. F 1-5 用邻接矩阵法存储图,占用的存储空间数只与图中结点个数

    2024年02月04日
    浏览(55)
  • 数据结构复盘——第四章:数组和矩阵

    矩阵在线性代数中已经有过详细了解,在考研中矩阵部分常常考察 数组下标 k 与 矩阵行 i 和列 j 的关系。 需要注意的是矩阵下标 i、j 通常是: 1 到 n 1到n 1 到 n ,而数组下标 k 通常是: 0 到 n 2 − 1 0到n^2-1 0 到 n 2 − 1 。 k 与 i、j 的关系就是: k = n ∗ ( i − 1 ) + j − 1 k=n*

    2024年02月07日
    浏览(39)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包