最小无法表达的正整数

无心人

任何一个瞬间的递归函数有两个状态 第一个状态是当前左子节点的所有情况 局部保存，第二个状态是所有右子节点的状态 压栈保存 ＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝ 呵呵 实际代码 说简单也不简单 说复杂也不复杂 等我想好了 等我写好了 等我调试了 发上来

无心人

呵呵 光说原理，到现在程序还没写呢 学校有点忙 已经想明白如何做了 等写完检验吧 ＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝ PS: 更直接的方法也得到了 我想到 由表达式树中序遍历的序列 其特点是， 1、操作符和数字共2n-1个，操作符n-1个，数字n个 2、操作符可以任意多个并在一起， 3、如果一个从开始起的部分序列，已经有操作符k个，那么接下来，从开始算的操作数字必须也有k个，才能出现新的操作符 4、2n-1最后两个位置不得是操作符 所以如果按照上面规则，可以递归产生出合法的序列，而不用树 从而简化程序

无心人

补充上面的叙述 有多少连续操作符 后面就要跟多少操作数 而且最后结束的两个必须是数字 满足这两个条件的序列将为合法且为某个表达式树中序遍历序列 ＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝ PS 使用栈的递归方式还是没调试好 希望两天内能调试好 否则，将直接实现本帖子的算法 （还是希望能现实现栈算法，某些题目可能有用处）

无心人

发上当前使用栈递归的代码 但提前声明，存在错误 未调试好

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

复制代码

无心人

栈似乎可以工作了 但3的对 4的不对 存在重复的数字

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

复制代码

[ 本帖最后由 无心人 于 2008-8-16 20:38 编辑 ]

无心人

mathe： 有现成程序快速的对具体的数字m求连续n个数字的四则表示么？？ 我想，我不完整程序版本33＃的速度似乎快很多 可修改之使输出连续32个无法表示的 我们可从最小的一个个排除 修改下面的函数

2. #define SearchMax 32
4. void
5. search (void)
6. {
7. printf ("\nmin:");
8. int i, j = 0;
9. for (i = 1; i < nmax; i++)
10. if (nmask[i] == 0)
11. {
12. j++;
13. printf ("%d ", i);
14. if (j == SearchMax)
15. break;
16. }
17. printf ("\n");
18. }

复制代码

刚对11的测试，输出到48733项 48730: 20994 + 1 + 2 + 3 + 8 + 10 * 5 * 9 + 4 * 6 * 7 11 48731: 20634 + 1 + 2 + 3 + 8 + 10 * 5 * 9 - * 6 * 7 11 4 48732: 13614 + 1 + 2 + 3 + 8 + 10 * 5 * 9 - * 4 * 7 11 6 48733: 16686 + 1 + 2 + 3 + 8 + 10 * 6 + 5 * 4 * 7 * 9 11 real 4m57.256s user 3m35.929s sys 0m2.212s 估计11的要输出500万项以上吧 最小无法表示的当在200万－400万之间 这么作唯一的担心是输出32个连续最小无法表示的是否足够 或者干脆是把无法表示的输出个10000个到文件？ [ 本帖最后由 无心人 于 2008-8-16 22:18 编辑 ]

mathe

也许可以快速构造部分表达式。 不过这种方法最大的问题在于后面构造失败以后，如何去证明后面那个数不存在合法的表达式（而且如果实际上合法表达式存在，那么更加麻烦）

无心人

我有点不明白你的意思 你是否说这个意思 假设对于小于等于 $f(n)=3 / 2 n!$（1－n构造的四则运算结果所有可能数字中最大的）的正整数 用不完全构造的方法没构造出表达式的 数字组成集合 $Fa$ 对集合中的数字 有没有确定方法证明存在构造表达式？ [ 本帖最后由 无心人 于 2008-8-18 12:56 编辑 ]

无心人

我想这个问题可以提出 另外一个问题 对于确定的正整数$N$ 是否存在$1..n$的$n$个数字 构造的四则运算式 使得结果是$N$ 我觉得这个问题比本帖子讨论的问题简单的多

无心人

以n = 11为例 可证明最大可构造表达式值是59875200 最小不可构造数字大于n=10的不可构造数字 假设不完全构造后 得到无法构造的数字序列 其最小值应该大于n=10的确定的最小值a 即使小于 也应该能证明小于11a且大于a的数字应该绝大部分能构造 呵呵，所以我想问你是否存在程序能构造具体数字的表达式