bug求助 为什么这个代码输入超过20就错。。

greenery

为什么这个代码输入超过20就错。。
给定两个正整数m、n，问只能做加1、乘2和平方这三种变化，从m变化到n最少需要几次


输入：


输入两个10000以内的正整数m和n，且m小于n


输出：


输出从m变化到n的最少次数


输入样例：

1 16




输出样例：

3

1. #include <stdio.h>
   
2. void init(void);
   
3. void clean(void);
   
4. void addtoqueue(int);
   
5. int takeoutofqueue(void);
   
6. int emptyqueue(void);
   
7. int canmoveto(int pre,int *curr,int i);
   
8. int isaim(int);
   
9. int used(int);
   
10. void readdata(void);
    
11. int search(void);
    
12. 
    
13. int head,tail;
    
14. int a[1000];
    
15. int queue[1000],qlen=1000;
    
16. int s,t;
    
17. int xtmp,x[100];
    
18. 
    
19. int main(void)
    
20. {
    
21.         int i,n1;
    
22.         clean();
    
23.         readdata();
    
24.         xtmp=search();
    
25.         printf("%d\n",xtmp);
    
26.         return 0;
    
27. }
    
28. 
    
29. void init(void)
    
30. {
    
31.         head=0;
    
32.         tail=1;
    
33.         queue[0]=s;
    
34. }
    
35. void clean(void)
    
36. {
    
37.         int i;
    
38.         for(i=0;i<10000;i++)
    
39.         {
    
40.                 a[i]=0;
    
41.         }
    
42.         for(i=0;i<qlen;i++)
    
43.         {
    
44.                 queue[i]=0;
    
45.         }
    
46. }
    
47. void addtoqueue(int curr)
    
48. {
    
49.         queue[tail++]=curr;
    
50.         tail=tail%qlen;
    
51. }
    
52. int takeoutofqueue(void)
    
53. {
    
54.         int curr;
    
55.         curr=queue[head++];
    
56.         head=head%qlen;
    
57.         return curr;
    
58. }
    
59. int emptyqueue(void)
    
60. {
    
61.         if(head==tail)return 1;
    
62.         return 0;
    
63. }
    
64. int canmoveto(int pre,int*curr,int i)
    
65. {
    
66.         int p;
    
67.         p=pre;
    
68.        
    
69.         switch(i)
    
70.         {
    
71.                 case 0:p+=1;break;
    
72.                 case 1:p*=2;break;
    
73.                 case 2:p=p*p;break;
    
74.         }
    
75.         *curr=p;
    
76.         return 1;
    
77. }
    
78. int isaim(int curr)
    
79. {
    
80.         if(curr==t)return 1;
    
81.         return 0;
    
82. }
    
83. int used(int curr)
    
84. {
    
85.         if(a[curr]!=0)return 1;
    
86.         return 0;
    
87. }
    
88. void readdata(void)
    
89. {
    
90.         scanf("%d %d",&s,&t);
    
91. }
    
92. int search(void)
    
93. {
    
94.         int pre,curr,i,num;
    
95.         init();
    
96.         while(!emptyqueue())
    
97.         {
    
98.                 pre=takeoutofqueue();
    
99.                 num=a[pre];
    
100.                 printf("num_%d\n",num);
     
101.                 for(i=0;i<3;i++)
     
102.                 {
     
103.                         if(canmoveto(pre,&curr,i))///////
     
104.                         {
     
105.                                 if(isaim(curr))return num+1;
     
106.                                 if(!used(curr))
     
107.                                 {
     
108.                                         a[curr]=num+1;
     
109.                                         addtoqueue(curr);
     
110.                                 }
     
111.                         }
     
112.                 }
     
113.         }
     
114.         return 0;
     
115. }
     

复制代码

greenery

破案了破案了，要剪枝的，大几百的平方会溢出，半句话的事

1. #include <stdio.h>
   
2. void init(void);
   
3. void clean(void);
   
4. void addtoqueue(int);
   
5. int takeoutofqueue(void);
   
6. int emptyqueue(void);
   
7. int canmoveto(int pre,int *curr,int i);
   
8. int isaim(int);
   
9. int used(int);
   
10. void readdata(void);
    
11. int search(void);
    
12. 
    
13. int head,tail;
    
14. int a[10000];
    
15. int queue[10000],qlen=10000;
    
16. int s,t;
    
17. int x;
    
18. 
    
19. int main(void)
    
20. {
    
21.         readdata();
    
22.         x=search();
    
23.         printf("%d\n",x);
    
24.         return 0;
    
25. }
    
26. 
    
27. void init(void)
    
28. {
    
29.         head=0;
    
30.         tail=1;
    
31.         queue[0]=s;
    
32. }
    
33. void clean(void)
    
34. {
    
35.         int i;
    
36.         for(i=0;i<10000;i++)
    
37.         {
    
38.                 a[i]=0;
    
39.         }
    
40.         for(i=0;i<qlen;i++)
    
41.         {
    
42.                 queue[i]=0;
    
43.         }
    
44. }
    
45. void addtoqueue(int curr)
    
46. {
    
47.         queue[tail++]=curr;
    
48.         tail=tail%qlen;
    
49. }
    
50. int takeoutofqueue(void)
    
51. {
    
52.         int curr;
    
53.         curr=queue[head++];
    
54.         head=head%qlen;
    
55.         return curr;
    
56. }
    
57. int emptyqueue(void)
    
58. {
    
59.         if(head==tail)return 1;
    
60.         return 0;
    
61. }
    
62. int canmoveto(int pre,int*curr,int i)
    
63. {
    
64.         int p;
    
65.         p=pre;
    
66.        
    
67.         switch(i)
    
68.         {
    
69.                 case 0:p+=1;break;
    
70.                 case 1:p*=2;break;
    
71.                 case 2:p=p*p;break;
    
72.         }
    
73.         if(p<=t)*curr=p;
    
74.         return 1;
    
75. }
    
76. int isaim(int curr)
    
77. {
    
78.         if(curr==t)return 1;
    
79.         return 0;
    
80. }
    
81. int used(int curr)
    
82. {
    
83.         if(a[curr]!=0)return 1;//<------------------------论剪枝的重要性。草泥马
    
84.         return 0;
    
85. }
    
86. void readdata(void)
    
87. {
    
88.         scanf("%d %d",&s,&t);
    
89. }
    
90. int search(void)
    
91. {
    
92.         int pre,curr,i,num;
    
93.         init();
    
94.         while(!emptyqueue())
    
95.         {
    
96.                 pre=takeoutofqueue();
    
97.                 num=a[pre];
    
98.                 for(i=0;i<3;i++)
    
99.                 {
    
100.                         if(canmoveto(pre,&curr,i))///////
     
101.                         {
     
102.                                 if(isaim(curr))return num+1;
     
103.                                 if(!used(curr))
     
104.                                 {
     
105.                                         a[curr]=num+1;
     
106.                                         addtoqueue(curr);
     
107.                                 }
     
108.                         }
     
109.                 }
     
110.         }
     
111.         return 0;
     
112. }
     

复制代码