由每個(gè)最末的狀態(tài)（n,n,n）推得所有可行的狀態(tài)，并記錄被推得狀態(tài)的來(lái)源和步長(zhǎng)，類(lèi)似篩法的方式，沒(méi)有被擴(kuò)展到的情況即無(wú)法到達(dá)的情況，標(biāo)記其步長(zhǎng)仍為0.
1
#include<stdio.h>
2#include<string.h>
3
4
struct Q
{
5
int flag;
6 int a;
7 int b;
8 int c;
9
};
10Q f[61][61][61];
11
12 int chang1(Q t);
13 int chang2(Q t);
14 int chang3(Q t);
15 int chang4(Q t);
16 int chang5(Q t);
17 int chang6(Q t);
18
19int chang1(Q t){
20 Q ne;
21 if(t.a%2 !=0 ) return 0 ;
22 ne.a = t.a /2;
23 ne.b = t.b+ne.a;
24 ne.c = t.c;
25
26 if(ne.a == ne.b && ne.b == ne.c) return 0 ;
27 if(f[ne.a][ne.b][ne.c].flag != 0 && f[ne.a][ne.b][ne.c].flag<t.flag+1) return 0 ;
28 f[ne.a][ne.b][ne.c].flag = t.flag+1;
29 f[ne.a][ne.b][ne.c].a=t.a;
30 f[ne.a][ne.b][ne.c].b=t.b;
31 f[ne.a][ne.b][ne.c].c=t.c; ne.flag = t.flag+1;
32 return chang1(ne)+chang2(ne)+chang3(ne)+chang4(ne)+chang5(ne)+chang6(ne);
33}
34int chang2(Q t){
35 Q ne;
36 if(t.a%2 !=0 ) return 0 ;
37 ne.a = t.a /2;
38 ne.c = t.c+ne.a;
39 ne.b = t.b;
40
41 if(ne.a == ne.b && ne.b == ne.c) return 0 ;
42 if(f[ne.a][ne.b][ne.c].flag != 0 && f[ne.a][ne.b][ne.c].flag<t.flag+1) return 0 ;
43 f[ne.a][ne.b][ne.c].flag = t.flag+1;
44 f[ne.a][ne.b][ne.c].a=t.a;
45 f[ne.a][ne.b][ne.c].b=t.b;
46 f[ne.a][ne.b][ne.c].c=t.c; ne.flag = t.flag+1;
47 return chang1(ne)+chang2(ne)+chang3(ne)+chang4(ne)+chang5(ne)+chang6(ne);
48}
49int chang3(Q t){
50 Q ne;
51 if(t.b%2 !=0 ) return 0 ;
52 ne.b = t.b /2;
53 ne.a = t.a+ne.b;
54 ne.c = t.c;
55
56 if(ne.a == ne.b && ne.b == ne.c) return 0 ;
57 if(f[ne.a][ne.b][ne.c].flag != 0 && f[ne.a][ne.b][ne.c].flag<t.flag+1) return 0 ;
58 f[ne.a][ne.b][ne.c].flag = t.flag+1;
59 f[ne.a][ne.b][ne.c].a=t.a;
60 f[ne.a][ne.b][ne.c].b=t.b;
61 f[ne.a][ne.b][ne.c].c=t.c; ne.flag = t.flag+1;
62 return chang1(ne)+chang2(ne)+chang3(ne)+chang4(ne)+chang5(ne)+chang6(ne);
63}
64int chang4(Q t){
65 Q ne;
66 if(t.b%2 !=0 ) return 0 ;
67 ne.b = t.b /2;
68 ne.c = t.c+ne.b;
69 ne.a = t.a;
70
71 if(ne.a == ne.b && ne.b == ne.c) return 0 ;
72 if(f[ne.a][ne.b][ne.c].flag != 0 && f[ne.a][ne.b][ne.c].flag<t.flag+1) return 0 ;
73 f[ne.a][ne.b][ne.c].flag = t.flag+1;
74 f[ne.a][ne.b][ne.c].a=t.a;
75 f[ne.a][ne.b][ne.c].b=t.b;
76 f[ne.a][ne.b][ne.c].c=t.c; ne.flag = t.flag+1;
77 return chang1(ne)+chang2(ne)+chang3(ne)+chang4(ne)+chang5(ne)+chang6(ne);
78}
79
80int chang5(Q t){
81 Q ne;
82 if(t.c%2 !=0 ) return 0 ;
83 ne.c = t.c /2;
84 ne.a = t.a+ne.c;
85 ne.b = t.b;
86
87 if(ne.a == ne.b && ne.b == ne.c) return 0 ;
88 if(f[ne.a][ne.b][ne.c].flag != 0 && f[ne.a][ne.b][ne.c].flag<t.flag+1) return 0 ;
89 f[ne.a][ne.b][ne.c].flag = t.flag+1;
90 f[ne.a][ne.b][ne.c].a=t.a;
91 f[ne.a][ne.b][ne.c].b=t.b;
92 f[ne.a][ne.b][ne.c].c=t.c; ne.flag = t.flag+1;
93 return chang1(ne)+chang2(ne)+chang3(ne)+chang4(ne)+chang5(ne)+chang6(ne);
94}
95int chang6(Q t){
96 Q ne;
97 if(t.c%2 !=0 ) return 0 ;
98 ne.c = t.c /2;
99 ne.b = t.b+ne.c;
100 ne.a = t.a;
101
102 if(ne.a == ne.b && ne.b == ne.c) return 0 ;
103 if(f[ne.a][ne.b][ne.c].flag != 0 && f[ne.a][ne.b][ne.c].flag<t.flag+1) return 0 ;
104 f[ne.a][ne.b][ne.c].flag = t.flag+1;
105 f[ne.a][ne.b][ne.c].a=t.a;
106 f[ne.a][ne.b][ne.c].b=t.b;
107 f[ne.a][ne.b][ne.c].c=t.c; ne.flag = t.flag+1;
108 return chang1(ne)+chang2(ne)+chang3(ne)+chang4(ne)+chang5(ne)+chang6(ne);
109}
110void init(){
111 Q temp ;
112
for(int i = 1 ; i <= 20 ; i++ ){
113 f[i][i][i].a = i;
114 f[i][i][i].b = i;
115 f[i][i][i].c = i;
116 f[i][i][i].flag = 0;
117 temp = f[i][i][i];
118 if (i % 2 != 0 )continue;
119 chang1(temp)+chang2(temp)+chang3(temp)+chang4(temp)+chang5(temp)+chang6(temp);
120
}
121}
122int main(){
123 init();
124 Q f2;
125 while(scanf("%d%d%d",&f2.a,&f2.b,&f2.c)!=EOF){
126 printf("%4d%4d%4d\n",f2.a,f2.b,f2.c);
127 while(f[f2.a][f2.b][f2.c].flag){
128 printf("%4d%4d%4d\n",f[f2.a][f2.b][f2.c].a,f[f2.a][f2.b][f2.c].b,f[f2.a][f2.b][f2.c].c);
129 f2 = f[f2.a][f2.b][f2.c];
130 }
131 printf("============\n");
132 }
133return 0 ;
134}
135