|
若N人过桥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移动过桥； 当2b＝a+y时，使用模式一将Z和Y移动过桥。这样就使问题转变为N-2个旅行者的情形，从而递归解决之。 …… AZ→ A← ……也就是“由A护送到对岸，A返回”，称作“模式一”。…… …… 第n-2步： AB→ 第n-1步： A← 第n步： YZ→ 第n+1步： B← ……这个模式是“由A和B护送到对岸，A和B返回”，称作“模式二”。C++代码：#include#includeusingnamespacestd;intmain(){intn=4;inti,fast1,fast2,slow1,slow2,sum,l;sum=0;int*a=newint[n];for(i=1;i>a;sort(a+1,a+n+1);fast1=a[1];fast2=a[2];slow1=a[n-1];slow2=a[n];l=1;while(n!=0){if(n==1||n==2){sum+=slow2;break;}if(n==3){sum+=(slow2+slow1+fast1);break;}if(2*fast2>=fast1+slow1){sum+=(slow1+slow2+2*fast1);n-=2;slow2=a[n];slow1=a[n-1];}else{sum+=2*fast2+fast1+slow2;n-=2;slow2=a[n];slow1=a[n-1];}}cout |
