最小无法表达的正整数

无心人

失望了
刚去学校
才算到35万多个表达式
看来，越来越难出新的
冲突的概率在增大啊
所以估计至少需要10天甚至50天才能出结果
而这么多天不停电的概率太小了
这个程序很难保存当前状态以避免中断

暂时没停止
希望出现奇迹

无心人

我想至少如果实现了那个以文件存储且仅考虑加减乘的程序
应该能实现保存状态持续计算的

但似乎这个东西有点复杂哦

mathe能估算下对应10的文件存储需求么？

无心人

2008-10-02  15:12               416     0202.dat
2008-10-02  15:12             1,248     0302.dat
2008-10-02  15:12             4,992     0303.dat
2008-10-02  15:12             2,496     0402.dat
2008-10-02  15:12            19,968     0403.dat
2008-10-02  15:12           119,808     0404.dat
2008-10-02  15:12             4,160     0502.dat
2008-10-02  15:12            49,920     0503.dat
2008-10-02  15:12           599,040     0504.dat
2008-10-02  15:12         3,194,880     0505.dat
2008-10-02  15:12             6,240     0602.dat
2008-10-02  15:12            99,840     0603.dat
2008-10-02  15:12         1,797,120     0604.dat
2008-10-02  15:12        19,169,280     0605.dat
2008-10-02  15:13       124,600,320     0606.dat
2008-10-02  15:13             8,736     0702.dat
2008-10-02  15:13           174,720     0703.dat
2008-10-02  15:13         4,193,280     0704.dat
2008-10-02  15:14        67,092,480     0705.dat
2008-10-02  15:15       872,202,240     0706.dat
携带所有信息的记录，每个长度104字节，0707的出现错误，怀疑是文件太大了，在3.4G大小后异常结束

无心人

暂时用Delphi语言写的

1. program minn;
   
2. 
   
3. {$APPTYPE CONSOLE}
   
4. 
   
5. uses
   
6.   SysUtils, StrUtils, windows;
   
7. 
   
8. var
   
9.   EndNum: integer = 0;
   
10.   AddNum: integer = -1;
    
11.   SubNum: integer = -2;
    
12.   MulNum: integer = -3;
    
13. 
    
14. type
    
15.   sExpr = record
    
16.     mask: integer;
    
17.     result: integer; //可能为负数，只能计算到12
    
18.     Expr: array[0..23] of integer;  
    
19.   end;
    
20. 
    
21. var
    
22.   num: integer; //输入数字
    
23.   appPath: string;
    
24.   numStr: array[0..15] of string[2];
    
25.   mask: array[0..15] of integer;
    
26. 
    
27. procedure Init;
    
28. var
    
29.   i: integer;
    
30. begin
    
31.   numStr[0] := '00';
    
32.   numStr[1] := '01';
    
33.   numStr[2] := '02';
    
34.   numStr[3] := '03';
    
35.   numStr[4] := '04';
    
36.   numStr[5] := '05';
    
37.   numStr[6] := '06';
    
38.   numStr[7] := '07';
    
39.   numStr[8] := '08';
    
40.   numStr[9] := '09';
    
41.   numStr[10] := '10';
    
42.   numStr[11] := '11';
    
43.   numStr[12] := '12';
    
44.   numStr[13] := '13';
    
45.   numStr[14] := '14';
    
46.   numStr[15] := '15';
    
47.   mask[0] := 1;
    
48.   for I := 1 to 15 do
    
49.     mask[i] := mask[i-1] shl 1;  
    
50. end;
    
51. 
    
52. //两个都是单数字
    
53. procedure processTwoStep;
    
54. var
    
55.   sFile: File of sExpr;
    
56.   i, j, fs: integer;
    
57.   sSFile, prefix: string;
    
58.   sSExpr: sExpr;
    
59. begin
    
60.   prefix := appPath + numStr[num];
    
61.   sSFile := prefix + '02.dat';
    
62.   AssignFile(sFile, sSFile);
    
63.   Reset(sFile);
    
64.   fs := FileSize(sFile);
    
65.   Seek(sFile, fs);
    
66.   for i := 1 to num - 1 do
    
67.     for j := i + 1 to num do
    
68.       begin
    
69.         sSExpr.mask := mask[i] or mask[j];
    
70.         sSExpr.result := i + j;
    
71.         ssExpr.Expr[0] := AddNum;
    
72.         sSExpr.Expr[1] := i;
    
73.         sSExpr.Expr[2] := j;
    
74.         ssExpr.Expr[3] := EndNum;
    
75.         Write(sFile, sSExpr);
    
76. 
    
77.         sSExpr.Expr[0] := SubNum;
    
78.         sSExpr.result := i - j;
    
79.         Write(sFile, sSExpr);
    
80. 
    
81.         sSExpr.Expr[0] := MulNum;
    
82.         sSExpr.result := i * j;
    
83.         Write(sFile, sSExpr);
    
84. 
    
85.         sSExpr.result := j - i;
    
86.         sSExpr.Expr[0] := SubNum;
    
87.         sSExpr.Expr[1] := j;
    
88.         sSExpr.Expr[2] := i;
    
89.         sSExpr.Expr[3] := EndNum;
    
90.         Write(sFile, sSExpr);
    
91.       end;
    
92. 
    
93.   Close(sFile);
    
94. end;
    
95. 
    
96. //有一个是单数字
    
97. procedure processSingleStep(m: integer);
    
98. var
    
99.   mFile, sFile: File of sExpr;
    
100.   n, i, fs: integer;
     
101.   sMFile, sSFile, prefix: string;
     
102.   sMExpr, sSExpr: sExpr;
     
103. begin
     
104.   prefix := appPath + numStr[num];
     
105.   sMFile := prefix + numStr[m] + '.dat';
     
106.   sSFile := prefix + numStr[m + 1] + '.dat';
     
107.   AssignFile(mFile, sMFile);
     
108.   AssignFile(sFile, sSFile);
     
109.   Reset(sFile);
     
110.   fs := FileSize(sFile);
     
111.   Seek(sFile, fs);
     
112.   for n := 1 to num do
     
113.   begin
     
114.     reset(mFile);
     
115.     while not eof(mFile) do
     
116.     begin
     
117.       Read(mFile, sMExpr);
     
118.       if (mask[n] and sMExpr.mask = 0) then
     
119.       begin
     
120.         sSExpr.mask := mask[n] or sMExpr.mask;
     
121.         sSExpr.result := n + sMExpr.result;
     
122.         sSExpr.Expr[1] := n;
     
123.         for I := 0 to 2 * m - 2 do
     
124.           sSExpr.Expr[2 + i] := sMExpr.Expr[i];
     
125.         sSExpr.Expr[0] := AddNum;
     
126.         sSExpr.Expr[1 + 2 * m] := EndNum;
     
127.         Write(sFile, sSExpr);
     
128. 
     
129.         sSExpr.Expr[0] := SubNum;
     
130.         sSExpr.result := n - sMExpr.result;
     
131.         Write(sFile, sSExpr);
     
132. 
     
133.         sSExpr.Expr[0] := MulNum;
     
134.         sSExpr.result := n * sMExpr.result;
     
135.         Write(sFile, sSExpr);
     
136. 
     
137.         sSExpr.result := sMExpr.result - n;
     
138.         for I := 1 to 2 * m - 1 do
     
139.           sSExpr.Expr[i] := sMExpr.Expr[i - 1];
     
140.         sSExpr.Expr[2 * m] := n;
     
141.         sSExpr.Expr[0] := SubNum;
     
142.         Write(sFile, sSExpr);
     
143.       end;
     
144.     end;
     
145.   end;
     
146. 
     
147.   Close(mFile);
     
148.   Close(sFile);
     
149. end;
     
150. 
     
151. //两个都是序列表达式
     
152. procedure processDoubleStep(n, m: integer);
     
153. var
     
154.   nFile, mFile, sFile: File of sExpr;
     
155.   fs, i: integer;
     
156.   sNFile, sMFile, sSFile, prefix: string;
     
157.   sNExpr, sMExpr, sSExpr: sExpr;
     
158. begin
     
159.   prefix := appPath + numStr[num];
     
160.   sNFile := prefix + numStr[n] + '.dat';
     
161.   sMFile := prefix + numStr[m] + '.dat';
     
162.   sSFile := prefix + numStr[n + m] + '.dat';
     
163.   AssignFile(nFile, sNFile);
     
164.   AssignFile(mFile, sMFile);
     
165.   reset(nFile);
     
166.   AssignFile(sFile, sSFile);
     
167.   reset(sFile);
     
168.   fs := FileSize(sFile);
     
169.   Seek(sFile, fs);
     
170.   while not eof(nFile) do
     
171.   begin
     
172.     Read(nFile, sNExpr);
     
173.     reset(mFile);
     
174.     while not eof(mFile) do
     
175.     begin
     
176.       Read(mFile, sMExpr);
     
177.       if (sNExpr.mask and smExpr.mask = 0) then
     
178.       begin
     
179.         sSExpr.mask := sNExpr.mask or sMExpr.mask;
     
180.         sSExpr.result := sNExpr.result + sMExpr.result;
     
181.         for I := 1 to 2 * n - 1 do
     
182.           sSExpr.Expr[i] := sNExpr.Expr[i - 1];
     
183.         for I := 0 to 2 * m - 2 do
     
184.           sSExpr.Expr[2 * n + i] := sMExpr.Expr[i];
     
185.         sSExpr.Expr[0] := AddNum;
     
186.         sSExpr.Expr[2 * n + 2 * m - 1] := EndNum;
     
187.         Write(sFile, sSExpr);
     
188. 
     
189.         sSExpr.Expr[0] := SubNum;
     
190.         sSExpr.result := sNExpr.result - sMExpr.result;
     
191.         Write(sFile, sSExpr);
     
192. 
     
193.         sSExpr.Expr[0] := MulNum;
     
194.         sSExpr.result := sNExpr.result * sMExpr.result;
     
195.         Write(sFile, sSExpr);
     
196. 
     
197.         sSExpr.result := sMExpr.result - sNExpr.result;
     
198.         for I := 1 to 2 * m - 1 do
     
199.           sSExpr.Expr[i] := sMExpr.Expr[i - 1];
     
200.         for I := 0 to 2 * n - 2 do
     
201.           sSExpr.Expr[2 * m + i] := sNExpr.Expr[i];
     
202.         sSExpr.Expr[0] := SubNum;
     
203.         Write(sFile, sSExpr);
     
204.       end;
     
205.     end;
     
206.   end;
     
207. 
     
208.   Close(nFile);
     
209.   Close(mFile);
     
210.   Close(sFile);
     
211. end;
     
212. 
     
213. procedure processStep(l: integer);
     
214. var
     
215.   i: integer;
     
216.   sFile: File of sExpr;
     
217.   sSFile, prefix: string;
     
218. begin
     
219.   prefix := appPath + numStr[num];
     
220.   sSFile := prefix + numStr[l] + '.dat';
     
221.   AssignFile(sFile, sSFile);
     
222.   rewrite(sFile);
     
223.   Close(sFile);
     
224. 
     
225.   if (l = 2) then
     
226.     processTwoStep;
     
227.   if (l >= 3) then
     
228.     processSingleStep(l - 1);
     
229.   if (l >= 4) then
     
230.     for i := 2 to l div 2 do
     
231.       processDoubleStep(i, l - i);
     
232. end;
     
233. 
     
234. var
     
235.   i: integer;
     
236. begin
     
237.   { TODO -oUser -cConsole Main : Insert code here }
     
238.   appPath := ExtractFilePath(paramStr(0));
     
239.   writeln('请输入需要求出数据的num值: ');
     
240.   readln(num);
     
241.   Init;
     
242.   for i := 2 to num do
     
243.     processStep(i);  
     
244. end.
     
245. 
     

复制代码

mathe

我倾向于只保存小文件.

无心人

你的意思是只保存数值，不保存表达式？

mathe

这个自然,不然保存的信息太多了.
而如果对于一个数值,要计算对应的表达式,只要将匹配的数值逆向再计算一次就应该能够比较快速的找出表达式(可以用来检测程序运行的正确性),但是通常情况没有必要产生这些表达式

jiangbin00cn

28 = (2 * 3 + 1)  * 4

对n=4
(1+2)*3*4=36

//////////////////////////////////////////////////
对任意的n(n>2)能够表达的最大整数为
(1+2)*3*4*...*n
如果能够证明，其能够连续表达出1~(1+2)*3*4*...*n的数
那么(1+2)*3*4*...*n+1 就是这个最小正整数

jiangbin00cn

不过用1~n这n个数通过四则混合运算表达出来的正整数
最多只可能有 4的(n-1)次方的，在n较大的情况下是远小于 (1+2)*3*4*...*n的
所以，楼主的答案必在1~(1+2)*3*4*...*n之间
有难度

jiangbin00cn

不过用1~n这n个数通过四则混合运算表达出来的正整数
最多只可能有 4的(n-1)次方的，

/////////////////////////////////////
这个结论不对，还要考虑括号的情况
那么最大可能有 （4的(n-1)次方）*(n-1)! >(1+2)*3*4*...*n

（4的(n-1)次方）*(n-1)!  

/////////////////////////////////////////////////////
对任意的n(n>2)能够表达的最大整数为
(1+2)*3*4*...*n
如果能够证明，其能够连续表达出1~(1+2)*3*4*...*n的数
那么(1+2)*3*4*...*n+1 就是这个最小正整数

这条路可能才是王道阿，考虑一下