求助一段shell

flyrip

类型1大老虎A B C
类型2小老虎a b c
转换大小写相等并且类型相同才正确，提供种思路，让高手写吧。俺菜，不会写。

我是DBA

方法应该有很多种。。。
想想。

lingonlei

我很赞同！

cjaizss

占位，听说偶还有机会拿到这一帖的赏分

爱知

有些地方可能不对，抛砖引玉

把 东西两岸 写为 此岸，彼岸
渡船中，此岸 最短渡船序列为：
>>>最短渡船序列证明见 30 楼<<<

1. 
   
2. //相似的不再列出
   
3. //其中，A、B、C代表母老虎，1、2、3代表小老虎）
   
4. //程序中4、5、6代表母老虎，1、2、3代表小老虎)   //上下一一对应
   
5. 
   
6. 序列>
   
7. 00:  ABC123
   
8. 01:  BC23
   
9. 02:  ABC23
   
10. 03:  ABC
    
11. 04:  ABC1
    
12. 05:  A1
    
13. 06:  AB12
    
14. 07:  12
    
15. 08:  123
    
16. 09:  1
    
17. 10:  12
    

复制代码

每次组合变化数序列：

1. 
   
2. 00:  -2
   
3. 01:   1
   
4. 02:  -2
   
5. 03:   1
   
6. 04:  -2
   
7. 05:  +2
   
8. 06:  -2
   
9. 07:   1
   
10. 08:  -2
    
11. 09:   1
    
12. 10:  -2
    

复制代码

可见每次变化的规律:此岸组合交替 减2/加1 个元素 (除 05 步加 2，即组合中只有一对母子老虎是加 2)

算法：

>>>主函数<<<：

1. 
   
2. i = 0            //全局变量：渡船方法数
   
3. set = "456123"   //最初组合
   
4. 
   
5. 递归函数(set)
   
6. 
   
7. print  i  　　　　//打印渡船方法总数
   

复制代码

>>>递归函数<<<
(
当组合元素个数为 0 时，渡船方法数自加 1（计数），返回；
当组合为安全组合时，调用递归函数；
当组合为非安全组合时，不计数，返回；
)

1. 
   
2. //彼岸和此岸互为补集
   
3. f = 0   //变量(标志渡船来回)  0: 渡向彼岸　1:渡向此岸
   
4. set     //递归函数形参
   
5. 
   
6. while(组合元素个数不为0)
   
7. do
   
8.       if(f == 0)                                      //渡向彼岸,减去两个元素
   
9.                for T1, T2 in set
   
10.                       fun(set, T1, T2, 0)             //见下定义
    
11.                       f = 1
    
12.       else                                            //f == 1  渡向此岸，加上一个元素（有特殊情况:组合中只有一对母子老虎加两个元素）
    
13. 
    
14.                 if(组合中只有一对母子老虎)
    
15.                        for T1, T2 in mod(set)         //set 的补集
    
16.                                   fun(set, T1, T2, 1) //见下定义
    
17.                                   f = 0
    
18.                 else
    
19.                        for T in mod(set)              //set 的补集
    
20.                                    add(set, T)        //与 fun 函数类似，见下定义
    
21.                                    f = 0
    
22. done
    
23. 
    
24. def fun(set, T1, T2, f)
    
25.         // when add2 or dev2
    
26.         // f 为局部标志  0:dev 2 elements,  1:add 2 elements
    
27.         if(f == 0)
    
28.                    从组合中减去 T1,T2
    
29.         else              // f == 1
    
30.                   在组合中加上 T1,T2
    
31. 　　　   if(组合长度为0）
    
32.                 i++
    
33.                 return
    
34.         if(此岸非安全组合 || 彼岸非安全组合）                  // call 安检函数    (见下)
    
35. 　　　　　　      return
    
36. 　　     else　　　　　　　                                  //安全组合
    
37.                 call  递归函数(set)
    
38. 
    
39. def add(set, T)
    
40.          //when add1
    
41.          if(此岸非安全组合 || 彼岸非安全组合）                 // call 安检函数    (见下)
    
42. 　　　　　　      return
    
43. 　　     else　　　　　　　                                  //安全组合
    
44.                 call  递归函数(set)
    

复制代码

>>>安检函数<<<
(检测组合是否为安全组合
：
如果有一个子老虎且没有其对应的母老虎，但有其他母老虎
则为非安全组合
)

1. 
   
2. d = 0  //标志变量　0:表示 无 母子老虎   n(>0):表示 母子老虎对数  
   
3. T      //临时变量
   
4. 
   
5. while (组合长度 != 0)
   
6. do
   
7. 　　　if(组合元素 有 母子老虎对）　　//优先 删除 母子老虎对
   
8. 　　　　　　　 d++
   
9.              从组合中 删除 母子老虎对
   
10. 　　　　elif(组合中都为母老虎)
    
11.               return "安全组合"
    
12.        elif(组合中都为子老虎 && d == 0)
    
13.               return "安全组合"
    
14.      　else
    
15.               return "非安全组合"
    
16. done
    

复制代码

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

luyi1983

期待啊，，，
谢谢各位

看着爱知的improve思路

[ 本帖最后由 luyi1983 于 2009-1-2 11:51 编辑 ]

ly5066113

原帖由 爱知 于 2009-1-1 22:55 发表
00:  -2
01:   1
02:  -2
03:   1
04:  -2
05:  +2
06:  -2
07:   1
08:  -2
09:   1
10:  -2

怎样才能证明这个是最短的呢？

不知道楼主是想写程序证明这个是最短的，还是在已知这个是最短的情况下列出所有的可能？

luyi1983

tim
我只希望能看到用程序解出答案
程序能告诉我 怎么渡河 可以成功
并且 可以列出可能的方法

ly5066113

原帖由 luyi1983 于 2009-1-2 12:34 发表
可以列出可能的方法

这个范围太广了，比如只有A老虎过去，然后自己又划回来，这样就做了一次无用功，在任何一种方法里添加这样一次，都可以成为另一种方法，因此，还是要列出最短的所有情况。

luyi1983

嗯 同意 无意义的 肯定不要