求助一段shell

luyi1983

有六只老虎，其中三只母老虎，每只母老虎分别带着一只小老虎。
有一条河，六只老虎都在河的东岸。
有一条船，每次只能载二只老虎。每只老虎（包括母老虎和小老虎）都会划船。
如果一只小老虎，其母亲不和它在一起，则会被其它母老虎吃掉（但不会被其它小老虎吃掉）。
问：如何才能把六只老虎平安地载到河的西岸？共有多少种不同的方法？

请用shell
有兴趣的来顶一下

ly5066113

写了一个，好象能用。
不过还有很多地方需要改进，并且没写注释。
其中A a B b C c表示6只老虎，大写字母是大老虎，小写字母是小老虎。

1. #! /bin/bash
   
2. 
   
3. tiger=(A a B b C c)
   
4. east=(1 1 1 1 1 1)
   
5. west=(0 0 0 0 0 0)
   
6. step=0
   
7. method=()
   
8. 
   
9. check()
   
10. {
    
11.         if echo "$*" | sed 's/ //g' | grep -Eq '(^01(..)?1)|(1.(..)?01$)|(^1.01)|(011.$)'
    
12.         then
    
13.                 return 1
    
14.         else
    
15.                 return 0
    
16.         fi
    
17. }
    
18. 
    
19. get1()
    
20. {
    
21.         tmparr=($*)
    
22.         for((i=0;i<=5;i++))
    
23.         do
    
24.                 [ "${tmparr[$i]}" -ne 0 ] && echo $i
    
25.         done
    
26. }
    
27. 
    
28. get2()
    
29. {
    
30.         tmpset="{"
    
31.         tmparr=($*)
    
32.         for((i=0;i<=5;i++))
    
33.         do
    
34.                 [ "${tmparr[$i]}" -ne 0 ] && tmpset="$tmpset$i,"
    
35.         done
    
36.         tmpset="${tmpset%,}}"
    
37.         { eval echo $tmpset$tmpset; } | tr ' ' '\n' | awk -F "" '$1<$2'
    
38. }
    
39. 
    
40. move()
    
41. {
    
42.         case "$1" in
    
43.         e)
    
44.                 for i in $(echo $2 | sed -r 's/(.)(.)/\1\n\2/')
    
45.                 do
    
46.                         east[$i]=0
    
47.                         west[$i]=1
    
48.                 done
    
49.         ;;
    
50.         w)
    
51.                 for i in $(echo $2 | sed -r 's/(.)(.)/\1\n\2/')
    
52.                 do
    
53.                         east[$i]=1
    
54.                         west[$i]=0
    
55.                 done
    
56.         ;;
    
57.         esac
    
58. }
    
59. 
    
60. printmethod()
    
61. {
    
62.         eval echo \"$(echo $* | sed 's/[0-9]/${tiger[&]}/g')\"
    
63. }
    
64. 
    
65. river()
    
66. {
    
67.         for ei in $(get2 "${east[@]}")
    
68.         do
    
69.                 [ "$ei" = "${method[$step]//[^0-9]/}" ] && continue
    
70.                 move e $ei
    
71.                 if check "${east[@]}" && check "${west[@]}"
    
72.                 then
    
73.                         ((step++))
    
74.                         method[$step]="$ei-->"
    
75.                         if [ $(echo "${west[@]}" | tr ' ' '+' | bc) -eq 6 ]
    
76.                         then
    
77.                                 printmethod "${method[@]}"
    
78.                                 move w $ei
    
79.                                 ((step--))
    
80.                                 return 0
    
81.                         elif [ $step -eq 5 ]
    
82.                         then
    
83.                                 ind=$(get2 "${west[@]}")
    
84.                         else
    
85.                                 ind=$(get1 "${west[@]}")
    
86.                         fi
    
87. 
    
88.                         for wi in $ind
    
89.                         do
    
90.                                 [ "x$ei" = "x$wi" ] && continue
    
91.                                 move w $wi
    
92.                                 if check "${east[@]}" && check "${west[@]}"
    
93.                                 then
    
94.                                         ((step++))
    
95.                                         method[$step]="$wi<--"
    
96.                                         river
    
97.                                         move e ${method[$step]//[^0-9]/}
    
98.                                         ((step--))
    
99.                                 else
    
100.                                         move e $wi
     
101.                                 fi
     
102.                         done
     
103.                         move w ${method[$step]//[^0-9]/}
     
104.                         ((step--))
     
105.                 else
     
106.                         move w $ei
     
107.                 fi
     
108.         done
     
109. }
     
110. 
     
111. river

复制代码

piaopiao131

顶一个，期待ing...

smallstar001

哇噻， 来考人来了

guorui913

是考算法的吧

ly5066113

占个地方先，代码慢慢想。

smallstar001

小虎在船上 其它的母老虎不吃它？？

我是DBA

直接晕了

welcome008

应该是排列组合吧？

我现在想到7种

luyi1983

给高手们摆好板凳 嘿嘿
我也努力去想啊。。。
关键是要出模型。。。