过桥问题c语言程序,盏灯过桥游戏
本站寻求有缘人接手，详细了解请联系站长QQ1493399855
博客里面好像没办法嵌入flash，加入之后，flash并不显示，只显示一片空白，不知道是博客等级缘故还是本身的限制
下面给出地址，有兴趣自己去试试
建议玩过了这个游戏后，再看下面的思路
问题描述
有n个人要在晚上过一座独木桥，他们过桥速度有快有慢，每次最多只能有两个人过桥，而且他们只有一盏灯，他们必须在规定时间内全部通过，否则灯会灭掉。
玩过这个游戏的人会得出两个简单逻辑，一灯必须靠快的人传递，二，两个人的过桥时间取决于慢的人。有了这两个基本信息，我们先将问题缩小为两个人A和B的情形，假定速度是从快到慢，下同
A，B的过桥时间为B
三个人的情况
A，B，C，简单想一下可以得出，为了使得传递速度够快，需要A作为传递的人，所以过桥方案为
1.A，C过桥
2，A返回
3 A，B过桥
总计时间 C+A+B
下面要考虑四个人的情形ABCD
这里有两种作法
方案S1
由A当传递，根据上述分析，我们很快可以得到最终时间为D+C+B+2*A
方案S2
由A，B当做传递，过桥方案为
1，A，B先过
3，D,C过(最慢的要一起过，这样可以节省时间)
4，B返回
5，A,B过桥
总计时间 B+A+D+B+B
将两个方案比较一下，S1的总时间T1-S2的总时间T2 = A+C-2*B
A+C-2*B >0则用方案2，否则用方案1
由此，我们将思路整理一下
首先将N个人按照速度从快到慢排成一个队列q[]
当n>3的时候，取队列的最后两位(最慢)和最前两位(最快)，组合成ABCD，根据A+C-2*B的情况，采用某个过桥方案。n-=2，重复该过程直到n<=3为止。
当n==3
过桥时间为A+B+C
当n==2，过桥时间为B
当n==1，过桥为A
程序清单
#include
#define PERSON_NUM 5
#define TIME_LIMITS 30
#define A speed[0]
#define B speed[1]
#define C speed[n-2]
#define D speed[n-1]
#define LAST speed[n-1]
int speed[PERSON_NUM] = {1,3,6,8,12};//已经按照升序输入，若没有，
//可以使用sort或者qsort排序
void print_solution1(int n)
{
printf("1th,%dth
printf("1th --> times need %d ",speed[0]);
printf("1th --> times need %d ",speed[0]);
}
void print_solution2(int n)
printf("1th,2th
printf("%dth,%dth
printf("2th --> times need %d ",speed[1]);
void main()
int times = 0;
int n = PERSON_NUM;
while(n>0)
if(n>3)
if((A+C)>2*B) //采用方案2
times+=(D+A+2*B);
print_solution2(n);
else
times+=(D+C+2*A);
print_solution1(n);
n-=2;
else if(n==3)
times += (A+B+LAST);
printf("LAST_A,B,C times need %d ",(A+B+LAST));
break;
else if(n==2)
times+=(B);
printf("LAST_A,B times need %d ",(B));
else if(n==1) //只有一个人的情况
times+=A;
printf("min time: %d ",times);
测试输入
1,3,6,8,12
1,5,6,8,12
1,8,9,11,12,13,15,20,100
下一期预告
泰坦尼克号赌船
