1.正确的算法:
如果n=3,
过河时间为A+B+C
如果n<=2,
好算,
不费口舌了
如果n>=4,
这个是重点:
每次优先考虑把最慢两人送过河
把n人中最快两人记为A,B,
最慢两人记为C,D(过河时间A<B<C<D),
n人问题实质上转换为4人过河问题,
参考到4人过河时的优化,
记AB过河,
A回,
CD过河,
B回,
为方法X,
实质是利用最快两人进行优化,
耗时A+2B+D
记AD过河,
A回,
AC过河,
A回,
为方法y,
实质是利用最快一人来过河,
耗时2A+C+D
每次比较这两个方法,
如果x快,
使用x方法,
如果y快,
则用y,
并且,
一旦某次使用y方法后,
以后都不用比较了,
全部使用y方法过河
2.算法正确性证明:
为什么每次先让最慢两人过河?
因为他们迟早要过河...早过晚过一样,
而晚过的话,
有可能时间不能被优化,
所以选择最先过
为什么是两人,
不是三人?
因为这船一次只能两人,
三人问题和两人问题的优化一样,
所以一次考虑三人毫无意义,
同理,
三人以上不加考虑
为什么某次用y过河后不用再比较xy了?
先看这个例子:
1
99
100
101
用x方法是99+1+101+99=
300
y方法是
101+1+100+1
=
203
y比x快的原因是2A+C+D
<
A+2B+D,
即
A+C<2B
容易想到,
从此以后A+C都会小于2B了(因为C越来越小)
3.补充:
算法分析就到这里了,
至于具体的程序...楼主既然是ACMer,
这个应该不困难
当然,
如果楼主需要的话,
也可以给出程序
温馨提示：答案为网友推荐，仅供参考