求助一段shell

爱知

最短渡船序列>

1. 
   
2. //相似的不再列出
   
3. 00:  ABC123
   
4. 01:  BC23
   
5. 02:  ABC23
   
6. 03:  ABC
   
7. 04:  ABC1
   
8. 05:  A1
   
9. 06:  AB12
   
10. 07:  12
    
11. 08:  123
    
12. 09:  1
    
13. 10:  12
    

复制代码

证明：
枚举出一个 B 序列
找出一个比 B 更短的 A 序列
再证明 A 序列不能再压缩，则 A 序列最短

>枚举出一个 B 序列，再找出一个比 B 更短的 A 序列
来源于： 11 和 14 楼

1. 
   
2.                                 >>>06 之前， A,B 序列相同<<<
   
3. 00:  ABC123
   
4. 01:  BC23
   
5. 02:  ABC23
   
6. 03:  ABC
   
7. 04:  ABC1         
   
8. 05:  A1
   
9. 06:  AB12   <<--B          A-->>    07:  12
   
10. 07:  A1                             08:  123
    
11. 08:  AC13                           09:  1
    
12. 09:  13                             10:  12
    
13. 10:  123         
    
14. 11:  1
    
15. 12:  12
    

复制代码

从以上可以看出：A 有可能最短

>证明 A 序列不能再压缩：

A 序列中：
00 ～ 06 行
如果改变为其他类型流程，就会出现小老虎被吃的情况
不符合要求
因此00 ～ 06 行类型不能改变，不能再压缩

（次序是一定的，不会出现其他不同类型的渡船方法分支）
（一定是说：不这样类似走，小老虎将会被吃）

06 ～ 07 行
同上：类型不能改变，不能再压缩

可以看出：
    >当 偶数行 为：AB12,BC23,AC13时，以后有可能还会在偶数行产生 AB12,BC23,AC13这样的组合
    >也就是说当 偶数行 为 AB12 类型，一对母子老虎渡船到彼岸，从彼岸又有一对母子老虎再渡回来，此时，类型又与 AB12 相同，从此，循环往复

A 中一开始就避免循环，无多余步骤，A 最短

[ 本帖最后由 爱知 于 2009-1-2 14:50 编辑 ]

ly5066113

关键是要证明05为何要+2，如果是+1，那么会不会出现更短的算法。

爱知

原帖由 ly5066113 于 2009-1-2 13:08 发表
关键是要证明05为何要+2，如果是+1，那么会不会出现更短的算法。

05 一定得 +2（加的是一对老虎）
如果 +1 的话，不管渡船上是母老虎还是子老虎，都会出现子老虎被吃的情况

ly5066113

这种不能算做证明，你已经固定了这个流程，因此你的05才是必须+2。
证明是要给出数学上的证明，不是文字随便描述一下就可以的。

爱知

你已经固定了这个流程，因此你的05才是必须+2。

不是我固定了这个流程，而是必须这样走

不然，就会出现小老虎被吃的情况！

证明是要给出数学上的证明，不是文字随便描述一下就可以的。

数学功力不强
这种逻辑的推理我不会用数学方式表达的出来

[ 本帖最后由 爱知 于 2009-1-2 13:48 编辑 ]

我是DBA

知道了要这样做，不知道为什么要这样做。。。
太深了，暂时理解不了。。
继续学习

biglazybug

这玩意得慢慢消化

li831

么么.复杂了一点吧

delpiero_008

应该是9种可能.

我是DBA

原帖由 delpiero_008 于 2009-1-4 09:30 发表
应该是9种可能.

哪九种，能求证出来？还是怎么算出来的。