渡河问题，尚有小问题，求教！

stone_shelly

#include <stdio.h>

typedef struct node {
int A, B, C, no, prec;
}QU;

typedef struct pair {
int np, pp;
}PA;

QU stack[100];

int top = -1;
int n, c;

void push(QU* pstatus) {
stack[++top]= *pstatus;
return;
}

void pop() {
if (top>=0) top--;
return;
}

/*
这里的 pair是指船上正常人和病人的数量(x,y)，前面指正常人后面是病人
*/
int nextpair(PA* ppair) {
int i,j;

i = ppair->np;j = ppair->pp;

if ((i==-1)&&(j==-1)) {
i = 0;j = 0;
}else{
if (j<c-i) {
j++;
}else if (i<c) {
i++;j = 0;
}else return 0;
}
ppair->np = i;ppair->pp = j;
return 1;
}

/*
符合条件的正常人、病人数量对
*/
int nextvalidpair(PA* ppair) {
do {
if (nextpair(ppair)) {
if ((ppair->np+ppair->pp)<=0) continue;
if ((ppair->np<ppair->pp)&&(ppair->np!=0)) continue;
return 1;
}else return 0;
}while(1);
}

/*
检查起始岸的状态
*/
int startbank(PA* ppair) {
QU status;
int i, j;
status = stack[top];
i = status.A-ppair->np;
j = status.B-ppair->pp;
if ((i<0)||(i>n)) return 0;
if ((j<0)||(j>n)) return 0;
if ((i<j)&&(i>0)) return 0;
return 1;
}

/*
检查终点岸的状态
*/
int endbank(PA* ppair) {
QU status;
int i, j;
status = stack[top];
i = n-status.A+ppair->np;
j = n-status.B+ppair->pp;
if ((i<0)||(i>n)) return 0;
if ((j<0)||(j>n)) return 0;
if ((i<j)&&(i>0)) return 0;
return 1;
}

/*
检查是否出现重复状态，也就是回路。
*/
int duplicatestatus(PA* ppair) {
QU status;
int i, j, k, t;
status = stack[top];
i = status.A-ppair->np;
j = status.B-ppair->pp;
k = status.C;
for (t=0;t<top;t++) {
status = stack[t];
if ((k== status.C)&&(i==status.A)&&(j==status.B)) return 1;
if ((k==!status.C)&&(i==n-status.A)&&(j==n-status.B)) return 1;
}
return 0;
}
/*起点和终点都正常，又不产生重复状态，是期望的状态*/
int isvalidstatus(PA* ppair) {
if (!startbank(ppair)) return 0;
if (!endbank(ppair)) return 0;
if (duplicatestatus(ppair)) return 0;

return 1;
}

/*推算下一状态*/
int nextstep() {
QU status;
PA pair;
pair.np=-1;pair.pp=-1;
status = stack[top];
do {
if (nextvalidpair(&pair)) {
if (isvalidstatus(&pair)) {
status.A=n-status.A+pair.np;
status.B=n-status.B+pair.pp;
status.C=!(status.C);
push(&status);
return 1;
}
}else return 0;
}while(1);
}

/*回溯时尝试下一个有可能的状态*/
int nextstatus() {
QU status,prevstatus;
PA pair;
if (top>0) {
status = stack[top];
prevstatus = stack[top-1];
pair.np = status.A+prevstatus.A-n;
pair.pp = status.B+prevstatus.B-n;

pop(); status = stack[top];
do {
if (nextvalidpair(&pair)) {
if (isvalidstatus(&pair)) {
status.A=n-status.A+pair.np;
status.B=n-status.B+pair.pp;
status.C=!(status.C);
push(&status);
return 1;
}
}else return 0;
}while (1);
}else return 0;
}

main() {
QU status;
int outflag,i;

scanf("%d,%d",&n,&c);
status.A = n;
status.B = n;
status.C = 1;

/*n=2;c=2;*/

push(&status);
do {
if (nextstep()) {
status = stack[top];
if ((status.A==n)&&(status.B==n)&&(status.C==0)) {
for(i=0;i<=top;i++) {
status = stack;
printf("(%d,%d,%d);",status.A,status.B,status.C);
}
return;
}
}else {
outflag = 1;
do {
if (nextstatus()) {
outflag=0;
}else {
pop();
if (top<0) {
printf("no result!\n");
return;
}
}
}while(outflag);
}
}while(1);
return;
}



kj501

粘贴代码时要保持缩进，请按置顶贴子的要求做。不然，读起来太费劲。

scream

我靠
兄弟是哪位啊？
我是林！！！
我早上就说过了你这个风格写得太差
这回被kj兄批评了吧

scream

我帮你重新把格式搞了一下
形式美也很重要！

1. 
   
2. #include <stdio.h>
   
3. 
   
4. typedef
   
5. struct node
   
6. {
   
7.     int A, B, C, no, prec;
   
8. }
   
9. QU;
   
10. 
    
11. typedef
    
12. struct pair
    
13. {
    
14.     int np, pp;
    
15. }
    
16. PA;
    
17. 
    
18. QU stack[100];
    
19. 
    
20. int top = -1;
    
21. int n, c;
    
22. 
    
23. void push(QU* pstatus)
    
24. {
    
25.    stack[++top]= *pstatus;
    
26.    return;
    
27. }
    
28. 
    
29. void pop()
    
30. {
    
31.    if (top>=0) top--;
    
32.    return;
    
33. }
    
34. 
    
35. /*
    
36. 这里的 pair是指船上正常人和病人的数量(x,y)，前面指正常人后面是病人
    
37. */
    
38. int nextpair(PA* ppair)
    
39. {
    
40.    int i,j;
    
41. 
    
42.    i = ppair->np;
    
43.    j = ppair->pp;
    
44. 
    
45.    if ((i==-1)&&(j==-1))
    
46.    {
    
47.       i = 0;j = 0;
    
48.    }
    
49.    else
    
50.    {  
    
51.       if (j<c-i)
    
52.       {
    
53.           j++;
    
54.       }
    
55.       else
    
56.       if (i<c)
    
57.       {
    
58.          i++;
    
59.          j = 0;
    
60.       }
    
61.       else
    
62.       return 0;
    
63.    }
    
64.    
    
65.    ppair->np = i;
    
66.    ppair->pp = j;
    
67.    
    
68.    return 1;
    
69. }
    
70. 
    
71. /*
    
72. 符合条件的正常人、病人数量对
    
73. */
    
74. int nextvalidpair(PA* ppair)
    
75. {
    
76.     do
    
77.     {
    
78.       if (nextpair(ppair))
    
79.       {
    
80.          if ((ppair->np+ppair->pp)<=0)
    
81.          continue;
    
82.          if ((ppair->np<ppair->pp)&&(ppair->np!=0))
    
83.          continue;
    
84.          return 1;
    
85.       }
    
86.       else
    
87.       return 0;
    
88.     }
    
89.     while(1);
    
90. }
    
91. 
    
92. /*
    
93. 检查起始岸的状态
    
94. */
    
95. int startbank(PA* ppair)
    
96. {
    
97.     QU status;
    
98.     int i, j;
    
99.    
    
100.     status = stack[top];
     
101.     i = status.A-ppair->np;
     
102.     j = status.B-ppair->pp;
     
103. 
     
104.     if ((i<0)||(i>n)) return 0;
     
105.     if ((j<0)||(j>n)) return 0;
     
106.     if ((i<j)&&(i>0)) return 0;
     
107.     return 1;
     
108. }
     
109. 
     
110. /*
     
111. 检查终点岸的状态
     
112. */
     
113. int endbank(PA* ppair)
     
114. {
     
115.     QU status;
     
116.     int i, j;
     
117.    
     
118.     status = stack[top];
     
119.     i = n-status.A+ppair->np;
     
120.     j = n-status.B+ppair->pp;
     
121.    
     
122.     if ((i<0)||(i>n)) return 0;
     
123.     if ((j<0)||(j>n)) return 0;
     
124.     if ((i<j)&&(i>0)) return 0;
     
125. 
     
126.     return 1;
     
127. }
     
128. 
     
129. /*
     
130. 检查是否出现重复状态，也就是回路。
     
131. */
     
132. int duplicatestatus(PA* ppair)
     
133. {
     
134.     QU status;
     
135.     int i, j, k, t;
     
136. 
     
137.     status = stack[top];
     
138.     i = status.A-ppair->np;
     
139.     j = status.B-ppair->pp;
     
140.     k = status.C;
     
141. 
     
142.     for (t=0;t<top;t++)
     
143.     {
     
144.        status = stack[t];
     
145.       
     
146.        if ((k== status.C)&&(i==status.A)&&(j==status.B)) return 1;
     
147.        if ((k==!status.C)&&(i==n-status.A)&&(j==n-status.B)) return 1;
     
148.     }
     
149.    
     
150.     return 0;
     
151. }
     
152. 
     
153. 
     
154. /*起点和终点都正常，又不产生重复状态，是期望的状态*/
     
155. int isvalidstatus(PA* ppair)
     
156. {
     
157.      if (!startbank(ppair))
     
158.      return 0;
     
159.      if (!endbank(ppair))
     
160.      return 0;
     
161.      if (duplicatestatus(ppair))
     
162.      return 0;
     
163. 
     
164.      return 1;
     
165. }
     
166. 
     
167. /*推算下一状态*/
     
168. int nextstep()
     
169. {
     
170.    QU status;
     
171.    PA pair;
     
172.    
     
173.    pair.np=-1;
     
174.    pair.pp=-1;
     
175.    status = stack[top];
     
176.    
     
177.    do {
     
178.          if (nextvalidpair(&pair))
     
179.          {
     
180.              if (isvalidstatus(&pair))
     
181.              {
     
182.                   status.A=n-status.A+pair.np;
     
183.                   status.B=n-status.B+pair.pp;
     
184.                   status.C=!(status.C);
     
185.                   push(&status);
     
186.                   return 1;
     
187.              }
     
188.          }
     
189.          else
     
190.          return 0;
     
191.       }
     
192.       while(1);
     
193. }
     
194. 
     
195. /*回溯时尝试下一个有可能的状态*/
     
196. int nextstatus()
     
197. {
     
198.       QU status,prevstatus;
     
199.       PA pair;
     
200.       
     
201.       if (top>0)
     
202.       {
     
203.          status = stack[top];
     
204.          prevstatus = stack[top-1];
     
205.          pair.np = status.A+prevstatus.A-n;
     
206.          pair.pp = status.B+prevstatus.B-n;
     
207. 
     
208.          pop();
     
209.          status = stack[top];
     
210.          
     
211.          do {
     
212.                if (nextvalidpair(&pair))
     
213.                {
     
214.                     if (isvalidstatus(&pair))
     
215.                     {
     
216.                         status.A=n-status.A+pair.np;
     
217.                         status.B=n-status.B+pair.pp;
     
218.                         status.C=!(status.C);
     
219.                         push(&status);
     
220.                         return 1;
     
221.                     }
     
222.                }
     
223.                else
     
224.                return 0;
     
225.             }
     
226.             while (1);
     
227.       }
     
228.       else
     
229.       return 0;
     
230. }
     
231. 
     
232. 
     
233. 
     
234. 
     
235. 
     
236. main()
     
237. {
     
238.      QU status;
     
239.      int outflag,i;
     
240. 
     
241.      scanf("%d,%d",&n,&c);
     
242.      status.A = n;
     
243.      status.B = n;
     
244.      status.C = 1;
     
245. 
     
246.      /*n=2;c=2;*/
     
247. 
     
248.      push(&status);
     
249.      do
     
250.      {
     
251.          if (nextstep())
     
252.          {
     
253.               status = stack[top];
     
254.               if ((status.A==n)&&(status.B==n)&&(status.C==0))
     
255.               {
     
256.                    for(i=0;i<=top;i++)
     
257.                    {
     
258.                        status = stack[i];
     
259.                        printf("(%d,%d,%d);",status.A,status.B,status.C);
     
260.                    }
     
261.                    return;
     
262.                }
     
263.           }
     
264.           else
     
265.           {
     
266.               outflag = 1;
     
267.               do
     
268.               {  
     
269.                     if (nextstatus())
     
270.                     {
     
271.                          outflag=0;
     
272.                     }
     
273.                     else
     
274.                     {
     
275.                          pop();
     
276.                          if (top<0)
     
277.                          {
     
278.                              printf("no result!\n");
     
279.                              return;
     
280.                          }
     
281.                     }
     
282.               }
     
283.               while(outflag);
     
284.           }
     
285.      }
     
286.      while(1);
     
287.      
     
288.      return;
     
289. }
     

复制代码

scream

你最好先阅读一下置顶的帖子吧
把你的问题和要求说说清楚
这样莫名其妙的提问
是很摧残人的啊~~~~~~~~~

kj501

最初由 scream 发表
我靠
兄弟是哪位啊？
我是林！！！
我早上就说过了你这个风格写得太差
这回被kj兄批评了吧

你们两个认识？

scream

哈哈，是我认识这个程序
我估计他是我们班上同学
因为我上午刚被人要求讲解这个程序
不过不是我写的