最小无法表达的正整数

jiangbin00cn

所谓不用考虑括号不过是针对程序处理而言 而我说的是针对推理证明 这一题如果不能证明1~n的数能够连续表示出1~（1+2）*3*...n的正整数 即时你能够做出11，还有12，13... 而且不考虑除的话结果肯定不对

zed

原帖由 jiangbin00cn 于 2008-10-4 00:13 发表 所谓不用考虑括号不过是针对程序处理而言 而我说的是针对推理证明 这一题如果不能证明1~n的数能够连续表示出1~（1+2）*3*...n的正整数 即时你能够做出11，还有12，13... 而且不考虑除的话结果肯定不对

你应该先查看一下前面已经得出的一些结果。在做猜想时起码得检验一下是否成立

无心人

我来回答吧 1、没有括号是针对程序设计的 你仔细研究下我说的中序遍历下的表达式树序列 只要考虑从右边连续取数字压栈 碰到计算符号，弹出两个数字，计算后压栈 直到序列空，就会得到表达式值，当然也能得到带括号的原始表达式的 2、并不能表示1到n! * 3 / 2的所有连续数字 比如1-4，就不可以的 3、不考虑除法是因为除法有点复杂，这个问题一个数字有很多表示方法 不考虑除法会减少一些数字被成功解析的机会，但会大大增加速度 有除法参与的运算，需要考虑6种可能，没有除法仅考虑4种就可以了 而且加减乘运算，只需要运算，除法需要判定0做除数和是否除尽的 我们只是研究如果去掉除法，是否会对整体没有影响，我想可能在大数字下有影响 [ 本帖最后由 无心人 于 2008-10-4 08:50 编辑 ]

mathe

好像我这个最新的将中间结果保存到文件的程序比上一个版本(不保存到文件的)速度还要慢很多 实在没有想到,可能是文件访问太慢了.早知道原先版本就不应该停小来了. 不过这个程序现在已经完全产生了使用11个数中不超过8个数的所有可能结果(只保存结果值),所有数据才133M(看来都可以直接保存在内存中)

无心人

这么低啊？？？？ 我的可没这么低 11的我估计是现有硬盘空间无法承受的

mathe

是不是结果相等的表达式你重复保存了。

无心人

是啊 可是结果相同的，使用的数字不一定相同啊 你觉得没有必要么?

mathe

下面程序你可以运行一下看，Windows下面运行

2. #include "stdafx.h"
3. #define N 12
4. #include <set>
5. using namespace std;
7. bool has_set(int x[],int size)
8. {
9. int mask=0;
10. int i;
11. char fName[20];
12. for(i=0;i<size;i++){
13. mask|=1<<(x[i]-1);
14. }
15. sprintf(fName,"data\\%d",mask);
16. FILE *pFile=fopen(fName,"rb");
17. if(pFile==NULL)
18. return false;
19. fclose(pFile);
20. return true;
21. }
23. #define BUFF_LEN 4096
24. int buff[BUFF_LEN];
25. int buff2[BUFF_LEN];
27. void output_r(int i)
28. {
29. int s=(1<<i)-1;
30. char fName[20];
31. sprintf(fName,"data\\%d",s);
32. FILE *pFile=fopen(fName,"rb");
33. if(pFile==NULL){
34. fprintf(stderr,"Cannot read file %s\n",fName);
35. exit(-1);
36. }
37. int yu=fread(buff,sizeof(int),BUFF_LEN,pFile);
38. int x=1,start;
39. if(buff[0]==0)start=1;else start=0;
40. while(buff[start]==x){
41. x++;
42. start++;
43. if(start>=yu){
44. if(yu==BUFF_LEN){
45. yu=fread(buff,sizeof(int),BUFF_LEN,pFile);
46. start=0;
47. if(yu==0)break;
48. }else break;
49. }
50. }
51. printf("r[%d]=%d\n",i,x);
52. fclose(pFile);
53. }
55. void save_set(const set<int>& result, int x[],int size)
56. {
57. int mask=0;
58. int i;
59. char fName[20];
60. for(i=0;i<size;i++){
61. mask|=1<<(x[i]-1);
62. }
63. sprintf(fName,"data\\%d",mask);
64. FILE *pFile=fopen(fName,"wb");
65. if(pFile==NULL){
66. fprintf(stderr,"Cannot write file %s\n",fName);
67. exit(-1);
68. }
69. int j;
70. set<int>::const_iterator cit;
71. i=j=0;
72. for(cit=result.begin();cit!=result.end();++cit){
73. buff[j++]=*cit;
74. i++;
75. if(j==BUFF_LEN){
76. j=0;
77. fwrite(buff,sizeof(int),BUFF_LEN,pFile);
78. }
79. }
80. if(j>0){
81. fwrite(buff,sizeof(int),j,pFile);
82. }
83. fclose(pFile);
85. if((mask&(mask+1))==0){
86. output_r(size);
87. }
88. }
91. void add_result(set<int>& result, int y[],int yc,int z[],int zc)
92. {
93. int mask=0;
94. int i,j;
95. char fName[20];
96. FILE *yFile,*zFile;
97. int yu,zu;
98. if(yc<=2){
99. if(yc==1){
100. yu=1;
101. buff[0]=y[0];
102. }else{
103. yu=3;
104. buff[0]=y[0]+y[1];
105. buff[1]=abs(y[0]-y[1]);
106. buff[2]=y[0]*y[1];
107. }
108. yFile=NULL;
109. }else{
110. mask=0;
111. for(i=0;i<yc;i++){
112. mask|=1<<(y[i]-1);
113. }
114. sprintf(fName,"data\\%d",mask);
115. yFile=fopen(fName,"rb");
116. if(yFile==NULL){
117. fprintf(stderr,"Cannot read file %s\n",fName);
118. exit(-1);
119. }
120. yu=fread(buff,sizeof(int),BUFF_LEN,yFile);
121. }
122. if(zc<=2){
123. if(zc==1){
124. zu=1;
125. buff2[0]=z[0];
126. }else{
127. zu=3;
128. buff2[0]=z[0]+z[1];
129. buff2[1]=abs(z[0]-z[1]);
130. buff2[2]=z[0]*z[1];
131. }
132. zFile=NULL;
133. }else{
134. mask=0;
135. for(i=0;i<zc;i++){
136. mask|=1<<(z[i]-1);
137. }
138. sprintf(fName,"data\\%d",mask);
139. zFile=fopen(fName,"rb");
140. if(zFile==NULL){
141. fprintf(stderr,"Cannot read file %s\n",fName);
142. exit(-1);
143. }
144. zu=fread(buff2,sizeof(int),BUFF_LEN,zFile);
145. }
146. if(zu<BUFF_LEN){
147. do{
148. for(i=0;i<zu;i++)for(j=0;j<yu;j++){
149. result.insert(buff2[i]+buff[j]);
150. result.insert(buff2[i]*buff[j]);
151. result.insert(abs(buff2[i]-buff[j]));
152. }
153. if(yu<BUFF_LEN)break;
154. yu=fread(buff,sizeof(int),BUFF_LEN,yFile);
155. }while(1);
156. }else if(yu<BUFF_LEN){
157. do{
158. for(i=0;i<zu;i++)for(j=0;j<yu;j++){
159. result.insert(buff2[i]+buff[j]);
160. result.insert(buff2[i]*buff[j]);
161. result.insert(abs(buff2[i]-buff[j]));
162. }
163. if(zu<BUFF_LEN)break;
164. zu=fread(buff2,sizeof(int),BUFF_LEN,zFile);
165. }while(1);
166. }else{
167. do{
168. do{
169. for(i=0;i<zu;i++)for(j=0;j<yu;j++){
170. result.insert(buff2[i]+buff[j]);
171. result.insert(buff2[i]*buff[j]);
172. result.insert(abs(buff2[i]-buff[j]));
173. }
174. if(yu<BUFF_LEN)break;
175. yu=fread(buff,sizeof(int),BUFF_LEN,yFile);
176. }while(1);
177. if(zu<BUFF_LEN)break;
178. zu=fread(buff2,sizeof(int),BUFF_LEN,zFile);
179. if(zu==0)break;
180. fseek(yFile,0,SEEK_SET);
181. yu=fread(buff,sizeof(int),BUFF_LEN,yFile);
182. }while(1);
183. }
184. if(yFile)fclose(yFile);
185. if(zFile)fclose(zFile);
186. }
189. void gen_set(int x[],int size)
190. {
191. int y[N],z[N];
192. int i,j,yc,zc;
193. if(size<=2)return;
194. if(has_set(x,size))return;
195. set<int> result;
196. for(i=1;i<(1<<size)-1;i+=2){
197. yc=zc=0;
198. for(j=0;j<size;j++){
199. if(i&(1<<j)){
200. y[yc++]=x[j];
201. }else{
202. z[zc++]=x[j];
203. }
204. }
205. gen_set(y,yc);
206. gen_set(z,zc);
207. add_result(result,y,yc,z,zc);
208. }
209. save_set(result,x,size);
210. }
213. int _tmain(int argc, _TCHAR* argv[])
214. {
215. int x[]={1,2,3,4,5,6,7,8,9,10,11,12};
216. system("mkdir data");
217. gen_set(x,N);
218. return 0;
219. }

复制代码

mathe

上面程序我在笔记本上用N=10运行了一下，花费时间还不算长，几分钟。但是N=11时间就受不了了。今天只有笔记本可以用，不能长时间运行程序。

无心人

N=10你得到的输出和前面你原始的程序结果一致么？ 另外，你估计下N=11可以改成持续运行的程序么？ 或者说N=11需要不可中断的运行时间是多少？ 假设在24小时内，甚至在72小时我想也可接受 如果是超过72小时，则可能不能保证停电后能继续