最小无法表达的正整数

无心人

出去乘凉
似乎找到了方法
用线性序列表示栈
首先压入运算符号，再压入数字
得到全部组合，则会得到所有的可能解
现在问题是，似乎要限定解的上限，否则太大
我想，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>
   
3. 
   
4. #define max 16
   
5. 
   
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;
    
14. 
    
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. }
    
23. 
    
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.   }
    
49. 
    
50. }
    
51. 
    
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. }
    
73. 
    
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. }
    
85. 
    
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. }
     
103. 
     
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. }
     
123. 
     
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$个，比上面表达式好一些