过桥问题1Word格式.docx
- 文档编号:4988414
- 上传时间:2023-05-04
- 格式:DOCX
- 页数:12
- 大小:18.83KB
过桥问题1Word格式.docx
《过桥问题1Word格式.docx》由会员分享,可在线阅读,更多相关《过桥问题1Word格式.docx(12页珍藏版)》请在冰点文库上搜索。
二、题目分析
1、四个人的情况
假设这四人分别为A、B、C、D。
很明显,开始两人拿着手电筒过桥后,手电筒就在桥的另一边了,此时需要已经过桥的那两人中的一个再把手电筒送回桥这边。
送手电筒回来过桥也要化时间,所以要选一个跑得比较快的。
一个很自然的想法就是,每次让跑得最快的A陪着另一个过桥,然后A快速地跑回来,再陪下一位过去,最后所有人就都可以过桥了。
让我们来算一下这要多长时间。
为了方便起见,我们把旅行者出发的桥的这一边称为“此岸”,而把旅行者想要到达的那边叫“彼岸”。
在表达一个过桥方案时,我们用“←”来表示从彼岸到此岸的移动,用“→”表示从此岸到彼岸的移动。
前面“A护送大家过河”的方案就可以写成:
(右边数字为完成此步骤所需时间)
A B → 2
A ← 1
A C → 5
A D → 8
一共就是2+1+5+1+8=17分钟。
但其实有更快的办法:
C D → 8
B ← 2
一共是2+1+8+2+2=15分钟。
这个办法的聪明之处在于让两个走得最慢的人同时过桥,这样花去的时间只是走得最慢的那个人花的时间,而走得次慢的那位就不用另花时间过桥了。
可以把所有可能的方案都列举一遍,就会发现这是最快的方案了。
现在我们把这个问题推广到N(N≥4)个人过桥的情况:
如果有N个旅行者,假设他们有各自所需的过桥时间(正实数)。
在只有一只手电筒的情况下,要过上述的一条桥,怎样才能找到最快的过桥方案?
假设最快地把N个旅行者从此岸移动到彼岸需要f分钟时间,那么我们把所有在f分钟时间内把N个旅行者从此岸移动到彼岸的方案称为“最佳方案”。
最佳方案很有可能不止一个,我们的目的是要找到一个最佳方案,但是并不需要把所有的最佳方案全都找出来。
2、一个合理的假设
假设A为最快,B为次快,而Z是任意一个其他旅行者
“由A护送最慢过桥,回来,然后继续护送最慢的过桥,再回来”,称作“模式一”。
”两个最快的过桥(A和B过桥),A回来,两个最慢的过桥,B回来”,称作“模式二”。
最佳方案构造法:
以下是构造N个人(N≥1)过桥最佳方案的方法:
1)如果N=1、2,所有人直接过桥。
2)如果N=3,由最快的人往返一次把其他两人送过河。
3)如果N≥4,设A、B为走得最快和次快的旅行者,过桥所需时间分别为a、b;
而Z、Y为走得最慢和次慢的旅行者,过桥所需时间分别为z、y。
那么
当2b>=a+y时,使用模式一将Z和Y移动过桥;
当2b<a+y时,使用模式二将Z和Y移动过桥;
这样就使问题转变为N-2个者的情形,从而递归解决之。
三、概要设计
1.设计函数sort运用选择排序法从大到小排序。
2.函数compare判断return(2*a[1]-a[0]-a[n-2])>
0?
1:
2;
使用模式一返回1,使用模式二返回2。
3.函数move计算结果,
若n=2则直接为第二个人的用时;
第一趟移动:
符合模式一*count=*count+modelone(a[0],a[n-1]);
符合模式二*count=*count+a[0]+2*a[1]+a[n-1];
此时将问题转化为移动n-2个人移动,运用递归思想。
4.main函数中while(scanf("
%d"
&
n)!
=EOF)实现多组数据的输入。
依次调用函数即可。
四、详细设计
#include<
stdio.h>
//选择排序法
voidsort(int*a,intn){
inti=0,j,temp,last;
while(i<
n-1){
last=n-1;
for(j=n-1;
j>
i;
j--)
if(a[j]<
a[j-1]){
temp=a[j-1];
a[j-1]=a[j];
a[j]=temp;
last=j;
}
i=last;
}
intcompare(int*a,intn){
return(2*a[1]-a[0]-a[n-2])>
intprint(intfast,intslow){
returnfast+slow;
voidmove(int*a,intn,int*count){
intcom;
if(n==2){
*count=*count+a[1];
else{
com=compare(a,n);
switch(com){
case1:
*count=*count+print(a[0],a[n-1]);
n=n-1;
move(a,n,count);
break;
case2:
*count=*count+a[0]+2*a[1]+a[n-1];
n=n-2;
intmain()
{
intn;
while(scanf("
=EOF)
{
intt[100],i=0,com,count=0;
for(i=0;
i<
n;
i++){
scanf("
t[i]);
sort(t,n);
move(t,n,&
count);
printf("
%d\n"
count);
return0;
五、测试数据及结果分析
不管换什么数据都能准确输出结果
,但是输出格式与结果略有不同只能输入一组然后回车,再继续输入,当输入结束时ctrl+c即可。
六、调试过程中的问题
问题一、无法输入多组数据,通过while(scanf("
=EOF)完成了这一功能。
问题二、没有考虑到n=2时的情况。
问题三、return(2*a[1]-a[0]-a[n-2])>
算法的思想核心。
问题四、递归的思想难以把握,费事。
问题五、intt[100],i=0,com,count=0;
必须出现在while(scanf("
=EOF)里面,否则当输入多组数据时出现count为多个结果相加的情况,因为指针count是为了存储每次递归的结果的,所以必须定义在里面。
七、课程设计总结
过桥问题的算法思想让我领悟到了算法的神奇,通过大量的计算与总结才能得出具有模式一模式二的形式,然后就是程序的编写,首先必须实现排序,再实现最慢次慢,最快次快临界条件的判断以及递归的计算。
在写程序的过程中,每个功能的实现都需要写,思虑必须周全,
选择排序法以及数组指针的使用都需要熟练地掌握,递归更是一个难点,相当于又学习了一遍。
通过过桥问题从分析到解决使我的知识更加丰富了,比如while(scanf("
=EOF)可以输入多组数据。
附加题2.学生成绩排名
一、课题内容和要求
期末考试时老师发飙出了1000道题目,每道题目1分。
最终课程的及格分数由老师指定。
现在班上的学生成绩已经批改好并按学号列出,要求你根据及格线将学生分为两个部分,分数低于及格线的同学要重修不参加排名,及格的同学从高到低排出名次。
三行数据,第一行为班级人数(小于1000),第二行按学号从低到高给出成绩,第三行给出及格分数线。
两行:
第一行将同学的分数按是否及格输出,低于及格线的部分、大于等于及格线的部分内部先后顺序不变。
第二行输出及格同学的成绩,从高到低排列。
6
22010980490401600
490
22010401980490600
980600490
应题目要求,数组的长度是小于1000的,要按题目说明的输出结果例如题中给的例子,
输出要求将大于490的置于后面并且顺序不变,然后就是排序后面的数并且输出
此时就可定义数组然后排序输出即可。
参考资料为c语言书
1、sort函数的定义
排序函数与过桥问题略有不同,用的是冒泡排序。
2、main函数
定义了两个数组a[size]与s[size],分别用于存储大于及格线与小于及格线的学生成绩。
然后定义k是为了记录a[size]中的数的个数。
#definesize1000
intsort(inta[],intn)
inti,j,t;
i<
n-1;
i++)
for(j=n-1;
j>
j--)
{
if(a[j]>
a[j-1])
{
t=a[j-1];
a[j-1]=a[j];
a[j]=t;
}
}
intmain()
inta[size],n,x,i,s[size],k;
&
n);
scanf("
a[i]);
x);
k=0;
if(a[i]<
x)
printf("
a[i]);
"
);
if(a[i]>
=x)
s[k]=a[i];
k++;
\n"
sort(s,k);
k;
printf("
%d"
s[i]);
五、测试数据及其结果分析
8
10026050041090530980490
400
10026090500410530980490
410490500530980
已经试用多组数组均可得到理想的结果
六、调试过程中的问题
1、在写函数sort冒泡排序时,交换位置出现问题,编译没问题,但第二行输出结果出现问题一直都有数重复,而有的数没有在结果行出现。
经过调试,发现排序时交换的问题,修改后可以得出正确答案。
八、课程设计总结
在开始时并没有这样来写,在实现第一行输出及格线分差时而是选择了二维数
组,后面的统一用的冒泡排序,但是输出及格线分差时,出现了间隔数字没法交换的问题,尽管多次修改依然错误百出,经过一段时间的休整决定推倒重做。
从这里我发现有的时候选择的算法未必可行,不能太钻牛角尖了,否则就造成时间的白白浪费。
后来的程序就思路简单清晰多了。
这样的改变也是有意义的,毕竟编程比的不是算法所谓的高端,而是简单易行、好懂。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 过桥 问题