实验项目:ACM程序设计基础(6)
实验目的:掌握C++程序设计基础。
实验要求:使用VC++6.0实现实验要求。
实验内容:
1.猜牌游戏问题,请看简单回溯——猜牌游戏(提示:可以参考实验六的最后一题Crashing
Balloon)。
2. 给定n个作业的集合Jn,每一个作业Ji都有两项任务分别在2台机器上完成。每个作业必须先由机器1处理,然后再由机器2处理。求所有作业在机器2上完成处理的时间和最少,并输出最佳调度方案。如:
|
机器1 |
机器2 |
作业1 |
2 |
1 |
作业2 |
3 |
1 |
作业3 |
2 |
3 |
最佳调度方案为:1 3 2,其完成时间为18。
3. 电路布线问题,请看简单动态规划——电路布线。
1.猜牌游戏问题,请看简单回溯——猜牌游戏。
2.最佳调度方案
思路是通过全排列搜索所有排序情况,并计算出结果,与当前最小值比较,最终得出答案。
难点是完成时间的计算,注意题目要求计算的是在机器二上的完成时间之和,而非所用时间之和,以上述数据为例:
|
机器1 |
机器2 |
1 |
作业1(2小时) |
|
2 |
|
3 |
作业3(2小时) |
作业1(1小时) |
4 |
|
5 |
作业2(3小时) |
作业3(3小时) |
6 |
7 |
8 |
|
作业2(1小时) |
可以看出3个作业的完成时间分别是3,7,8,因此完成时间之和为3 + 7 + 8 = 18。
而代码我是这么实现的:设两个变量t1与t2,分别表示当前作业在机器1与机器2上的完成时间,则:
- 当前作业在机器1上的处理只需等上一作业在机器1上完成,即t1 += 当前作业在机器1上所需的处理时间
- 当前作业在机器2上的处理必须等当前作业在机器1上完成且上一作业在机器2上完成之后开始,即:t2 = max(t1, t2) + 当前作业在机器2上所需的处理时间
代码如下:
3. 电路布线问题,请看简单动态规划——电路布线。
=======================签 名 档=======================
原文地址(我的博客):http://lanfei.sinaapp.com/2012/06/1347.html
欢迎访问交流,至于我为什么要多弄一个博客,因为我热爱前端,热爱网页,我更希望有一个更加自由、真正属于我自己的小站,或许并不是那么有名气,但至少能够让我为了它而加倍努力。。
=======================签 名 档=======================
分享到:
相关推荐
ACM国际大学生程序设计竞赛基础知识
本资料含 ACM国际大学生程序设计竞赛简介、 程序设计基础、 程序设计简单问题以及 组合数学中的程序设计算法的分析,资料比较全面,为大学生程序竞赛提供了很好的资源
本课件是沈云付老师写的《ACM程序设计竞赛辅导》这本教材的配套课件包括ACM程序设计竞赛简介和程序设计基础、 高精度计算 、数论、 组合数学 、动态规划 、计算几何等
ACM国际大学生程序设计竞赛:知识与入门,是你提高算法思想,锻炼算法实践能力的不二之选!你值得拥有!!
《ACM程序设计》详细讲解了ACM国际大学生程序设计竞赛(ACM/ICPC)编程、调试方法,以及提高时间、空间性能的策略,并充分利用了c++泛型编程的高效率、规范化的特性,全部采用c++泛型编程。 第1章讲解了ACM程序设计...
国际程序大学生程序设计竞赛教程和程序设计基础课程设计
ACM国际大学生 程序设计竞赛基础知识
主要用于ACM竞赛,书里面包含了基础算法和较为高级的算法,无论是小白还是大神都者的一看~
推选文档ACM程序设计基础之贪心法PPT.ppt
ACM程序设计基础之贪心法PPT课件.pptx
ACM程序设计基础之贪心法学习教案.pptx
ACM程序设计竞赛基础教程_俞经善等编.pdf,算法竞赛题解
ACM程序设计基础之贪心法PPT学习教案.pptx
ACM程序设计基础之贪心法PPT教学课件.pptx
ACM竞赛,程序设计资料包,包含ppt,经典题目,常用算法,已经一套基础训练题
最新的ACM培新计划和培训内容,包含代码和解析,培养最出色的ACMer
ACM程序设计-基础ACM课件(与“问题”有关文档共30张).pptx
UTF-8''ACM程序设计竞赛基础教程_俞经善等编,算法入门经典完整版,算法入门经典训练版。
《ACM国际大学生程序设计竞赛题解Ⅰ》——基础编程题