最小无法表达的正整数

mathe

我只用过gdb,不过我是用ddd（提供的图形界面还可以），它封装的gdb.

无心人

要疯了
怎么也无法枚举每种状态
已解决加乘的左右交换问题
但对减除的左面是树，右面是叶子的
表达式树，怎么也无法枚举出来
枚举打印的都缺少叶子，哎

无心人

重新写的求值函数

1. #include <stdio.h>
   
2. #include <stdlib.h>
   
3. #include <sys/time.h>
   
4. 
   
5. #define max 16
   
6. #define nmax 64 * 1024 * 1024
   
7. 
   
8. int calc[2 * max - 1];
   
9. int operator[4] = { -1, -3, -2, -4 };        // + * - /
   
10. int mask[max + 1]; //代表数字是否被使用
    
11. int nmask[nmax]; //表示的数字
    
12. int n;
    
13. int leaf;                        //剩余数字  
    
14. int position;
    
15. int counter;
    
16. 
    
17. void
    
18. init (void)
    
19. {
    
20.         int i;
    
21.         for (i = 1; i <= max; i++)
    
22.                 mask[i] = 0;
    
23.         position = 0;
    
24.         counter = 0;
    
25.         leaf = n;
    
26.         memset(nmask, 0, nmax * sizeof(int));
    
27. }
    
28. 
    
29. void search(void)
    
30. {
    
31.         int i;
    
32.         for (i = 1; i < nmax; i ++)
    
33.                 if (nmask[i] == 0)
    
34.         {
    
35.                 printf("\nmin: %d\n", i);
    
36.                 break;
    
37.         }
    
38. }
    
39. 
    
40. //返回0代表表达式合法，－1代表除法不能除尽，－2代表除以0，－3代表结果为负
    
41. int print(void)
    
42. {
    
43.         int i;
    
44.         int opTop = 0, numTop = 0;
    
45.         long long temp;
    
46.         long long numBuffer[max];
    
47.         int itemp;
    
48.        
    
49.         for (i = 2 * n - 2; i >= 0; i --)
    
50.         {
    
51.                 if (calc[i] < 0)
    
52.                 {
    
53.                         switch (calc[i])
    
54.                         {
    
55.                                 case -1:
    
56.                                         temp = numBuffer[numTop - 1] + numBuffer[numTop - 2];
    
57.                                         break;
    
58.                                 case -2:
    
59.                                         temp = numBuffer[numTop - 1] - numBuffer[numTop - 2];
    
60.                                         break;
    
61.                                 case -3:
    
62.                                         temp = numBuffer[numTop - 1] * numBuffer[numTop - 2];
    
63.                                         break;
    
64.                                 case -4:
    
65.                                         if (numBuffer[numTop - 2] == 0)
    
66.                                                 return (-2);
    
67.                                         if (numBuffer[numTop - 1] % numBuffer[numTop - 2] > 0)
    
68.                                                 return (-1);
    
69.                                         temp = numBuffer[numTop - 1] / numBuffer[numTop - 2];
    
70.                                         break;
    
71.                         }
    
72.                         numTop -= 1;                                                                                                                                                                                                                                                                                                                                                                               
    
73.                         numBuffer[numTop - 1] = temp;
    
74.                 }
    
75.                 else
    
76.                         numBuffer[numTop ++] = calc[i];
    
77.         }
    
78.        
    
79.         temp = numBuffer[0];
    
80.         if (temp < 0) return (-3);
    
81.         if (temp < nmax)
    
82.         {
    
83.                 itemp = temp;
    
84.                 if (nmask[itemp] == 0)
    
85.                 {
    
86.                         counter++;
    
87.                         printf("%d: %d ", counter, itemp);
    
88.                         for (i = 0; i <= 2 * n - 2; i++)
    
89.                         {
    
90.                                 if (calc[i] < 0)
    
91.                                 {
    
92.                                         switch (calc[i])
    
93.                                         {
    
94.                                                 case -1:
    
95.                                                         printf ("+ ");
    
96.                                                         break;
    
97.                                                 case -2:
    
98.                                                         printf ("- ");
    
99.                                                         break;
    
100.                                                 case -3:
     
101.                                                         printf ("* ");
     
102.                                                         break;
     
103.                                                 case -4:
     
104.                                                         printf ("/ ");
     
105.                                                         break;
     
106.                                         }
     
107.                                 }
     
108.                                 else
     
109.                                         printf ("%d ", calc[i]);
     
110.                         }
     
111.                         printf ("\n");
     
112.                        
     
113.                         nmask[itemp] = 1;       
     
114.                 }
     
115.         }
     
116.        
     
117.         return (0);
     
118. }
     
119. 
     
120. int
     
121. printOnly (void)
     
122. {
     
123.         int i;
     
124.         for (i = 0; i <= 2 * n - 2; i++)
     
125.         {
     
126.                 if (calc[i] < 0)
     
127.                 {
     
128.                         switch (calc[i])
     
129.                         {
     
130.                                 case -1:
     
131.                                         printf ("+ ");
     
132.                                         break;
     
133.                                 case -2:
     
134.                                         printf ("- ");
     
135.                                         break;
     
136.                                 case -3:
     
137.                                         printf ("* ");
     
138.                                         break;
     
139.                                 case -4:
     
140.                                         printf ("/ ");
     
141.                                         break;
     
142.                         }
     
143.                 }
     
144.                 else
     
145.                         printf ("%d ", calc[i]);
     
146.         }
     
147.         printf ("\n");
     
148.         counter++;
     
149. }
     
150. 
     
151. void
     
152. printBlank (void)
     
153. {
     
154.         counter++;
     
155. }
     
156. 
     
157. int
     
158. top (int MaxNode)
     
159. {
     
160.         int i;
     
161.         if (MaxNode >= 1)
     
162.                 for (i = 0; i < 4; i++)
     
163.         {
     
164.                 calc[position++] = operator[i];
     
165.                 if (i < 2)
     
166.                         subNode (MaxNode - 1, 1);
     
167.                 else
     
168.                         subNode (MaxNode - 1, 0);
     
169.                 position--;
     
170.         }
     
171. }
     
172. 
     
173. void
     
174. addmul (void)
     
175. {
     
176.         int i, j;
     
177.         for (i = 1; i <= n - 1; i++)
     
178.                 if (mask[i] == 0)
     
179.         {
     
180.                 mask[i] = 1;
     
181.                 leaf--;
     
182.                 calc[position++] = i;
     
183.                 for (j = i + 1; j <= n; j++)
     
184.                         if (mask[j] == 0)
     
185.                 {
     
186.                         calc[position++] = j;
     
187.                         mask[j] = 1;
     
188.                         leaf--;
     
189.                         if (leaf == 0)
     
190.                         {
     
191.                                 // check();
     
192.                                 print ();
     
193.                         }
     
194.                         mask[j] = 0;
     
195.                         leaf++;
     
196.                         position--;
     
197.                 }
     
198.                 leaf++;
     
199.                 position--;
     
200.                 mask[i] = 0;
     
201.         }
     
202. }
     
203. 
     
204. void
     
205. subdiv (void)
     
206. {
     
207.         int i, j;
     
208.         for (i = 1; i <= n; i++)
     
209.                 if (mask[i] == 0)
     
210.         {
     
211.                 mask[i] = 1;
     
212.                 leaf--;
     
213.                 calc[position++] = i;
     
214.                 for (j = 1; j <= n; j++)
     
215.                         if (mask[j] == 0)
     
216.                 {
     
217.                         calc[position++] = j;
     
218.                         mask[j] = 1;
     
219.                         leaf--;
     
220.                         if (leaf == 0)
     
221.                         {
     
222.                                 // check();
     
223.                                 print ();
     
224.                         }
     
225.                         mask[j] = 0;
     
226.                         leaf++;
     
227.                         position--;
     
228.                 }
     
229.                 leaf++;
     
230.                 position--;
     
231.                 mask[i] = 0;
     
232.         }
     
233. }
     
234. 
     
235. void
     
236. leftFill (int MaxNode)
     
237. {
     
238.         int i;
     
239.         for (i = 1; i <= n; i++)
     
240.                 if (mask[i] == 0)
     
241.         {
     
242.                 calc[position++] = i;
     
243.                 leaf--;
     
244.                 mask[i] = 1;
     
245.                 top (MaxNode);
     
246.                 position--;
     
247.                 leaf++;
     
248.                 mask[i] = 0;
     
249.         }
     
250. }
     
251. 
     
252. void
     
253. rightFill (int MaxNode)
     
254. {
     
255.         int i;
     
256.         for (i = 1; i <= n; i++)
     
257.                 if (mask[i] == 0)
     
258.         {
     
259.                 mask[i] = 1;
     
260.                 calc[position + 2 * MaxNode + 1] = i;
     
261.                 leaf--;
     
262.                 top (MaxNode);
     
263.                 leaf++;
     
264.                 mask[i] = 0;
     
265.         }
     
266. }
     
267. 
     
268. int
     
269. subNode (int MaxNode, int exchange)
     
270. {
     
271.         int i, j;
     
272.         if (MaxNode == 0)
     
273.         {
     
274.                 if (exchange == 1)
     
275.                         addmul ();
     
276.                 else
     
277.                         subdiv ();
     
278.         }
     
279.        
     
280.         if (MaxNode >= 1)
     
281.         {
     
282.                 //1\fill left
     
283.                 leftFill (MaxNode);
     
284.                 //2\fill right
     
285.                 if (exchange == 0)
     
286.                         rightFill (MaxNode);
     
287.         }
     
288.        
     
289.         //3\top(left) top(right)
     
290.         if (MaxNode >= 2)
     
291.                 for (i = 1; i < MaxNode; i++)
     
292.         {
     
293.                 top (i);
     
294.                 top (MaxNode - i);
     
295.         }
     
296. }
     
297. 
     
298. int
     
299. main (void)
     
300. {
     
301.         struct timeval start, end;
     
302.         double timeuse;
     
303.         printf ("Input n value:");
     
304.         scanf ("%d", &n);
     
305.         printf ("\n\n");
     
306.         gettimeofday (&start, NULL);
     
307.         init ();
     
308.         top (n - 1);
     
309.         printf ("\nTotal: %d\n", counter);
     
310.         search();
     
311.         gettimeofday (&end, NULL);
     
312.         timeuse =
     
313.                 1000000 * (end.tv_sec - start.tv_sec) + end.tv_usec - start.tv_usec;
     
314.         timeuse /= 1000000;
     
315.         printf ("\n\nUsed Time:%8.6f\n\n", timeuse);
     
316.         return 0;
     
317. }
     

复制代码

n <=5和mathe的答案一致
从6开始就不对了
在查找原因

[ 本帖最后由 无心人 于 2008-8-4 21:48 编辑 ]

无心人

n = 7的算下
一会儿过来汇报
＝＝＝＝＝＝＝＝＝＝＝＝＝
Total: 2710

min: 1102


Used Time:105.265166
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
晕，似乎从6开始就和mathe的结果不同了啊
哎

[ 本帖最后由 无心人 于 2008-8-4 18:46 编辑 ]

mathe

1102=2*(5+7*6*(1+4*3))

无心人

有bug，从3开始就不对了
还没找到问题

我把7的都输出到文件，看是漏算还是计算函数有问题
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
已修正n到5
但从6开始还不对，有两个无法算出
279 281

[ 本帖最后由 无心人 于 2008-8-4 21:56 编辑 ]

mathe

279=(5+4)*(1+6*(3+2))

无心人

晕死
7的输出3G多
文本编辑器打不开阿
推荐个能处理这么大文件的文本编辑器
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
看n=3的结果
里面有7的结果 + 1 * 2 3
但不输出7
似乎是求值的问题

[ 本帖最后由 无心人 于 2008-8-4 19:28 编辑 ]

无心人

Input n value:  3

1: 6 + 1 + 2 3
2: 7 + 1 * 2 3
3: 0 + 1 - 2 3
4: 2 + 1 - 3 2
5: 5 + 2 * 1 3
6: 4 + 2 - 3 1
7: 1 * 1 - 3 2
8: 8 * 2 + 1 3
9: 9 * 3 + 1 2
10: 3 * 3 - 2 1

Total: 10

min: 10


Used Time:1.113455

[ 本帖最后由 无心人 于 2008-8-4 21:47 编辑 ]

无心人

mathe
6的还一个281没找到解
你的解是？