博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
英特尔线程挑战赛试题--房间分配
阅读量:5168 次
发布时间:2019-06-13

本文共 1472 字,大约阅读时间需要 4 分钟。

问题描述:假定有若干间宿舍,每个房间住两名学生,要对学生兴趣进行调查,根据学生兴趣来安排志趣相投的学生同住,以尽量使所有学生能够和睦相处。

对学生进行一次包含 50 个问题的调查。每个问题的答案都有五种同意程度,其分值范围从强烈反对(0 分)到强烈同意(4 分)。评估任意一对学生间不和谐程度的计算方法是:比较两人对 50 个调查问题的答案,并汇总不同答案所对应的同意程度分值差的绝对值。然后将得到的总和统一除以 200.0(即可能的最大差异分值总和)。所有假定房间分配的总不和谐程度(TD)值是所有学生对之间的不和谐程度值总和。因此,这个程序的目的就是通过测试宿舍中学生的不同配对来最小化 TD 值。

这个问题的输入内容将是一个文本文件。这个文件的第一行将是要分配宿舍的学生总数(N),后面跟有 N 个学生行。文件中的学生数N将是一个小于 2^28 - 1 的偶数,并且所有输入数据将装入目标平台的主内存中。文件中学生行的格式将是:由 10 个字符组成的标识字符串,1 个空格,再加一个 50 位的调查字符串。调查字符串的元素值范围为 0 到 4。

这些行的初始排列将决定初始的室友配对。最前面的两名学生将被视为分配到同一个房间,接下来的两名学生也分配到另一个房间,依此类推。

输入文件示例:

2

ChukECheez 01230230420314203422301230230420332023410123023042
Clyde Ruth 20342230123023042031420342230123042031420342233042

此示例文件的总不和谐程度(TD)临界值为 0.305。

代码限制:主程序必须采用以下结构:

InputDataFromFile(Rooms, N);

first = EvaluateRooms(Rooms, N);
print("The initial Disharmony is", first);
start = GetTime;
ComputeRoomAssignments(Rooms, N);
end = GetTime;
print("Time to compute room assignments is ", end - start, "seconds");
final = EvaluateRooms(Rooms, N);
print("Final Disharmony is", final);
PrintRoomAssignmentToFile(Rooms, N);
亦即:输入数据,计算并打印初始总不和谐程度(TD)评估值,开始计时,计算 TD 评估值较低的房间分配,停止计时,打印计算所用的时间,计算并打印最终分配所对应的 TD 评估值,然后将最终分配的标识字符串(一行一个标识)打印到输出文件。此处显示的具体函数名或变量名并非必需。

算法限制:由于解决此类问题的直接方法可能不可靠,并且随着学生人数的增加,各种分配组合的数量将呈几何级剧增,因此程序代码必须使用一些迭代的全局优化技巧,例如模拟退火算法(Simulated Annealing)。

时间限制:运行时的执行时间将限制在 2 分钟以内。亦即:假如运行时间超过120秒,应用程序无法向接收点报告。

输入文件:Students.in

输出文件:Assignments.out

转载于:https://www.cnblogs.com/MaxWoods/archive/2007/12/20/1007834.html

你可能感兴趣的文章
【BZOJ3295】[Cqoi2011]动态逆序对 cdq分治
查看>>
【CF799E】Aquarium decoration 线段树
查看>>
大运飞天 鲲鹏展翅
查看>>
从ECMA到W3C
查看>>
软件工程--第十六周学习进度
查看>>
yii2 ActiveRecord多表关联以及多表关联搜索的实现
查看>>
搜狗输入法安装--ubuntu
查看>>
ps/2接口键盘的输入及显示
查看>>
Swift———a Glance(极客学院)笔记
查看>>
【poj3294-不小于k个字符串中最长公共子串】后缀数组
查看>>
java如何获取其它用户登录的真是IP地址
查看>>
Jquery通过指定层次关系获取元素
查看>>
c# for 和 foreach 的区别
查看>>
docfx (一)
查看>>
HashMap底层实现原理/HashMap与HashTable区别/HashMap与HashSet区别
查看>>
深度学习之前馈神经网络(前向传播和误差反向传播)
查看>>
IEnumerable<T>和IQueryable<T>区别
查看>>
(转)MFC界面风格
查看>>
Centos7 tmux1.6 安装
查看>>
二叉树(三)
查看>>