过桥问题(1)

过桥问题

一、课题内容与分析

题目：过桥问题

描述：有N（N≥）个人在晚上需要从X地到达Y地，中间要过一座桥，过桥需要手电筒（而他们只有个手电筒），每次最多两个人一起过桥（否则桥会垮）。N个人的过桥时间依次存入数组t[N]中，分别为：t[0], t[1], ??, t[N-1]。过桥的速度以慢的人为准！注意：手电筒不能丢过桥！问题是：编程求这N个人过桥所花的最短时间。

输入：有多组测试数据，每组数据先输入一个人数N，然后输入这N个人过桥所花的时间。输出：输出对应的最短时间。 样例输入： 4 1 2 5 10 4 5 2 10 1 样例输出： 17 17

二、题目分析

1、四个人的情况

假设这四人分别为A、B、C、D。很明显，开始两人拿着手电筒过桥后，手电筒就在桥的另一边了，此时需要已经过桥的那两人中的一个再把手电筒送回桥这边。送手电筒回来过桥也要化时间，所以要选一个跑得比较快的。一个很自然的想法就是，每次让跑得最快的A陪着另一个过桥，然后A快速地跑回来，再陪下一位过去，最后所有人就都可以过桥了。

让我们来算一下这要多长时间。为了方便起见，我们把旅行者出发的桥的这一边称为“此岸”，而把旅行者想要到达的那边叫“彼岸”。在表达一个过桥方案时，我们用“←”来表示从彼岸到此岸的移动，用“→”表示从此岸到彼岸的移动。前面“A护送大家过河”的方案就可以写成：（右边数字为完成此步骤所需时间）

A B → 2 A ← 1 A C → 5 A ← 1 A D → 8

一共就是2+1+5+1+8=17分钟。

但其实有更快的办法：

A B → 2 A ← 1 C D → 8 B ← 2 A 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(\, &n) != EOF)实现多组数据的输入。 依次调用函数即可。

四、详细设计

#include //选择排序法

void sort(int *a, int n) { int i=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; } }

int compare(int *a, int n) {

return (2*a[1] - a[0] - a[n-2]) > 0 ? 1 : 2;