最小无法表达的正整数

无心人

出去乘凉 似乎找到了方法 用线性序列表示栈 首先压入运算符号，再压入数字 得到全部组合，则会得到所有的可能解 现在问题是，似乎要限定解的上限，否则太大 我想，2*n^2是否足够大？

无心人

还要实现一个基于栈的表达式计算函数

kenmark

昨天想了一会儿没脸把如此显然的结论贴上来，今天来丢一下脸 还可以剪枝，设a[n]是长度n的数列第一个无法表示的数值 a[1]=2 a[2]=4 a[3]=10 ... 则对于a[n]必有a[n]>n(n+1)/2，可以减少检测范围 证明： 对于n的情况，由数归证得的a[n-1]>=n 通过构造n+(p[n-1]) 可以表示n+1...n+a[n-1]-1 通过构造n+n-1+(p[n-2])可以表示n+n-1+1...n+n-1+a[n-2]-1 ... 得n+1...n(n+1)/2都可以表示 通过构造n-(p[n-1])可以表示1到n-1的数 而n可以由n*(1)表示(1)由1...n-1表示 得证 后来在车上想到下界还能更好，没来的及好好想，楼下继续 mathe能把1...10的结果爆料一下吗？寻找一下更好的思路 [ 本帖最后由 kenmark 于 2008-8-2 14:04 编辑 ]

mathe

游客，如果您要查看本帖隐藏内容请回复

无心人

mathe 能否证明 a[n] <= n * [n-1] ==================== PS: 还可以构造 n * a[n-1] n * (n-1) * a[n - 1]等 用构造法应该能得到非显然的下界 但无法得到准确下界 只能暴力搜索么？

无心人

对于 + * 2 3 - 4 1 表示(2 * 3) + (4 - 1) 类型的表达式树 如何计算比较好？

无心人

1. #include <stdio.h>
2. #include <stdlib.h>
4. #define max 16
6. int calc[max * max];
7. int maxlevel;
8. int operator[4] = {-1, -2, -3, -4}; // + - * /
9. int mask[max + 1];
10. int n;
11. int le; //剩余数字
12. int position;
13. int counter;
15. void init(void)
16. {
17. int i;
18. for (i = 1; i <= max; i ++)
19. mask[i] = 0;
20. position = 0;
21. counter = 0;
22. }
24. //返回0代表表达式合法，－1代表除法不能除尽，－2代表除以0，－3代表结果为负
25. int check(void)
26. {
27. int i;
28. int op;
29. int leftNum, rightNum;
30. long long Result;
31. leftNum = 0;
32. rightNum = 0;
33. //检测得到的数字序列是否合法表达式，如果是，则计算出结果
34. for (i = position - 1; i >= 0; i --)
35. {
36. if (calc[i] < 0)
37. switch (calc[i])
38. {
39. case -1:// +
40. break;
41. case -2:// -
42. break;
43. case -3:// *
44. break;
45. case -4:// /
46. break;
47. }
48. }
50. }
52. void print(void)
53. {
54. int i;
55. for (i = 0; i <= position - 1; i ++)
56. {
57. if (calc[i] < 0)
58. {
59. switch (calc[i])
60. {
61. case -1: printf("+ "); break;
62. case -2: printf("- "); break;
63. case -3: printf("* "); break;
64. case -4: printf("/ "); break;
65. }
66. }
67. else
68. printf("%d ", calc[i]);
69. }
70. printf("\n");
71. counter ++;
72. }
74. int top(int level)
75. {
76. int i, j;
77. if (level < n - 1)
78. for (i = 0; i < 4; i ++)
79. {
80. calc[position++] = operator[i];
81. left(level);
82. position --;
83. }
84. }
86. //左的长度要不大于右
87. int left(int level)
88. {
89. int i;
90. for (i = 1; i <= n; i ++)
91. if (mask[i] == 0)
92. {
93. calc[position++] = i;
94. mask[i] = 1;
95. le --;
96. right(level);
97. le ++;
98. mask[i] = 0;
99. position --;
100. }
101. top(level + 1);
102. }
104. int right(int level)
105. {
106. int i;
107. if (le == 1)
108. {
109. for (i = 1; i <= n; i ++)
110. if (mask[i] == 0)
111. {
112. calc[position++] = i;
113. mask[i] = 1;
114. // check();
115. print();
116. position --;
117. mask[i] = 0;
118. }
119. }
120. else
121. top(level + 1);
122. }
124. int main(void)
125. {
126. printf("Input n value:");
127. scanf("%d", &n);
128. printf("\n\n");
129. init();
130. le = n;
131. top(0);
132. printf("Total: %d\n", counter);
133. return 0;
134. }

复制代码

无心人

n = 2得到8个式子 n = 3 96 n = 4 1536 n=4应该是错误的， 呵呵 / 4 * 1 + 2 3 / 4 * 1 + 3 2 / 4 * 1 - 2 3 / 4 * 1 - 3 2 / 4 * 1 * 2 3 / 4 * 1 * 3 2 就这种式子 少了 * + 2 3 - 4 1 类型的

无心人

对每个n 不考虑唯一 不考虑结果的合理性 所有可能的式子是 $2^(n-2)*4^(n-1)*n!$ 所以随n增大，搜索时间迅速变大 n=10的可能是$2^8*4^9*10! = 243,524,645,683,200$

mathe

这个可以通过 http://bbs.emath.ac.cn/thread-461-1-1.html 中的统计数据，只计算不等价的表达式，还有$2,894,532,443,154$个，比上面表达式好一些