C语言的题目

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,

这个应该不困难

当然,

如果楼主需要的话,

也可以给出程序

1、1分钟和2分钟过河，（2分钟）

2、然后2分钟回头，（孙睁2分钟）

3、腔凯逗5分钟和10分钟过河（10分伍卖钟）

4、1分钟回头（1分钟）

5、1分钟和2分钟过河，（2分钟）

2+2+10+1+2=17

假设商人和随从分别叫A和B，现在有AAAA+BBBB：

开始只能AB过去或者BB过去：

1.若是AB过去，只能A回来，BB过去，B回来，只能BB过去或者AA过去：

1.1若是BB过去，只能B回来，对面三个B，A不能过去，无解。

2.2若是AA过去，只能AB回来渣滚，重复开始的AB过去，死循环，无解。

2.若是BB过去，只能B回来，BB过去，B回来，BB过去，答搭无解。

所以，这个破题清梁拿无解。

---