最小无法表达的正整数

无心人

为什么啊？

喜欢玩变态？

mathe

1-11中任意多个数采用+,-,*,/不能达到1765186得到证明了.
不过要验证12个数看来很难,估计要花费很长时间.

无心人

能给出验证程序么？

mathe

代码挺慢,分两部分.
第一部分将所有1~n之间不超过8个数字通过+,-,*,/所能得到的结果全部计算出来并且保存在文件中,其中1~11所有结果产生需要10个多小时,总共数据15.6G.
而计算1~12所产生的结果运行了37个多小时,总共数据量54G

1. 
   
2. #include "stdafx.h"
   
3. #define N 8
   
4. #include <set>
   
5. using namespace std;
   
6. 
   
7. class number{
   
8.     int up;
   
9.     int down;
   
10. public:
    
11.     number(const number& n):up(n.up),down(n.down){}
    
12.     number(int n=0):up(n),down(1){}
    
13.     number& operator+=(const number& n);
    
14.     number& operator-=(const number& n);
    
15.     number& operator*=(const number& n);
    
16.     number& operator/=(const number& n);
    
17.     bool is_zero()const{return down!=0&&up==0;}
    
18.     bool is_valid()const{return down!=0;}
    
19.     bool is_one()const{return down!=0&&up==down;}
    
20.     bool operator==(const number& n)const{return
    
21.         is_valid()&&n.is_valid()&&n.down*(long long)up==n.up*(long long)down;}
    
22.     bool operator<(const number& n)const;
    
23.     bool operator>(const number& n)const{return n<*this;}
    
24.     bool operator<=(const number& n)const{return !(*this>n);}
    
25.     bool operator!=(const number& n)const{return !(n==*this);}
    
26.     bool operator>=(const number& n)const{return !(*this<n);}
    
27.     number operator+(const number& n)const{number m(*this);return m+=n;}
    
28.     number operator-(const number& n)const{number m(*this);return m-=n;}
    
29.     number operator*(const number& n)const{number m(*this);return m*=n;}
    
30.     number operator/(const number& n)const{number m(*this);return m/=n;}
    
31.     bool is_integer()const{return down!=0&&up%down==0;}
    
32.     int get_integer()const{if(is_integer())return up/down;else return -1;}
    
33.     number& operator=(int n){up=n;down=1;return *this;}
    
34.     int get_up()const{return up;}
    
35.     int get_down()const{return down;}
    
36.         number abs()const{number x;x.up=up>=0?up:-up;x.down=down>=0?down:-down;return x;}
    
37. };
    
38. 
    
39. number& number::operator +=(const number& n)
    
40. {
    
41.     up=up*n.down+down*n.up;
    
42.     down*=n.down;
    
43.     return *this;
    
44. }
    
45. 
    
46. number& number::operator -=(const number& n)
    
47. {
    
48.     up=up*n.down-down*n.up;
    
49.     if(up<0)up=-up;
    
50.     down*=n.down;
    
51.     return *this;
    
52. }
    
53. 
    
54. number& number::operator *=(const number& n)
    
55. {
    
56.     up*=n.up;
    
57.     down*=n.down;
    
58.     return *this;
    
59. }
    
60. 
    
61. number& number::operator /=(const number& n)
    
62. {
    
63.     down*=n.up;
    
64.     up*=n.down;
    
65.     return *this;
    
66. }
    
67. 
    
68. bool number::operator <(const number &n)const
    
69. {
    
70.     return (long long)up*n.down<n.up*(long long)down;
    
71. }
    
72. 
    
73. bool has_set(int x[],int size)
    
74. {
    
75.     int mask=0;
    
76.     int i;
    
77.     char fName[20];
    
78.     for(i=0;i<size;i++){
    
79.         mask|=1<<(x[i]-1);
    
80.     }
    
81.     sprintf(fName,"data\\%d",mask);
    
82.     FILE *pFile=fopen(fName,"rb");
    
83.     if(pFile==NULL)
    
84.         return false;
    
85.     fclose(pFile);
    
86.     return true;
    
87. }
    
88. 
    
89. #define BUFF_LEN 4096
    
90. number buff[BUFF_LEN];
    
91. number buff2[BUFF_LEN];
    
92. 
    
93. void output_r(int i)
    
94. {
    
95.     int s=(1<<i)-1;
    
96.     char fName[20];
    
97.     sprintf(fName,"data\\%d",s);
    
98.     FILE *pFile=fopen(fName,"rb");
    
99.     if(pFile==NULL){
    
100.         fprintf(stderr,"Cannot read file %s\n",fName);
     
101.         exit(-1);
     
102.     }
     
103.     int yu=fread(buff,sizeof(number),BUFF_LEN,pFile);
     
104.     int x=1,start;
     
105.     if(buff[0]==0)start=1;else start=0;
     
106.     while(buff[start]<=x){
     
107.                 if(buff[start]<x){
     
108.                         start++;
     
109.                 }else{
     
110.                         x++;
     
111.                         start++;
     
112.                 }
     
113.         if(start>=yu){
     
114.             if(yu==BUFF_LEN){
     
115.                 yu=fread(buff,sizeof(number),BUFF_LEN,pFile);
     
116.                 start=0;
     
117.                 if(yu==0)break;
     
118.             }else break;
     
119.         }
     
120.     }
     
121.     printf("r[%d]=%d\n",i,x);
     
122.     fclose(pFile);
     
123. }
     
124. 
     
125. void save_set(const set<number>& result, int x[],int size)
     
126. {
     
127.     int mask=0;
     
128.     int i;
     
129.     char fName[20];
     
130.     for(i=0;i<size;i++){
     
131.         mask|=1<<(x[i]-1);
     
132.     }
     
133.     sprintf(fName,"data\\%d",mask);
     
134.     FILE *pFile=fopen(fName,"wb");
     
135.     if(pFile==NULL){
     
136.         fprintf(stderr,"Cannot write file %s\n",fName);
     
137.         exit(-1);
     
138.     }
     
139.     int j;
     
140.     set<number>::const_iterator cit;
     
141.     i=j=0;
     
142.     for(cit=result.begin();cit!=result.end();++cit){
     
143.         buff[j++]=*cit;
     
144.         i++;
     
145.         if(j==BUFF_LEN){
     
146.             j=0;
     
147.             fwrite(buff,sizeof(number),BUFF_LEN,pFile);
     
148.         }
     
149.     }
     
150.     if(j>0){
     
151.         fwrite(buff,sizeof(number),j,pFile);
     
152.     }
     
153.     fclose(pFile);
     
154. 
     
155.     if((mask&(mask+1))==0){
     
156.         output_r(size);
     
157.     }
     
158. }
     
159. 
     
160. 
     
161. void add_result(set<number>& result, int y[],int yc,int z[],int zc)
     
162. {
     
163.     int mask=0;
     
164.     int i,j;
     
165.     char fName[20];
     
166.     FILE *yFile,*zFile;
     
167.     int yu,zu;
     
168.     if(yc<=2){
     
169.         if(yc==1){
     
170.             yu=1;
     
171.             buff[0]=y[0];
     
172.         }else{
     
173.             yu=5;
     
174.             buff[0]=y[0]+y[1];
     
175.             buff[1]=abs(y[0]-y[1]);
     
176.             buff[2]=y[0]*y[1];
     
177.                         buff[3]=number(y[0])/y[1];
     
178.                         buff[4]=number(y[1])/y[0];
     
179.         }
     
180.         yFile=NULL;
     
181.     }else{
     
182.         mask=0;
     
183.         for(i=0;i<yc;i++){
     
184.             mask|=1<<(y[i]-1);
     
185.         }
     
186.         sprintf(fName,"data\\%d",mask);
     
187.         yFile=fopen(fName,"rb");
     
188.         if(yFile==NULL){
     
189.             fprintf(stderr,"Cannot read file %s\n",fName);
     
190.             exit(-1);
     
191.         }
     
192.         yu=fread(buff,sizeof(number),BUFF_LEN,yFile);
     
193.     }
     
194.     if(zc<=2){
     
195.         if(zc==1){
     
196.             zu=1;
     
197.             buff2[0]=z[0];
     
198.         }else{
     
199.             zu=5;
     
200.             buff2[0]=z[0]+z[1];
     
201.             buff2[1]=abs(z[0]-z[1]);
     
202.             buff2[2]=z[0]*z[1];
     
203.                         buff2[3]=number(z[0])/z[1];
     
204.                         buff2[4]=number(z[1])/z[0];
     
205.         }
     
206.         zFile=NULL;
     
207.     }else{
     
208.         mask=0;
     
209.         for(i=0;i<zc;i++){
     
210.             mask|=1<<(z[i]-1);
     
211.         }
     
212.         sprintf(fName,"data\\%d",mask);
     
213.         zFile=fopen(fName,"rb");
     
214.         if(zFile==NULL){
     
215.             fprintf(stderr,"Cannot read file %s\n",fName);
     
216.             exit(-1);
     
217.         }
     
218.         zu=fread(buff2,sizeof(number),BUFF_LEN,zFile);
     
219.     }
     
220.     if(zu<BUFF_LEN){
     
221.         do{
     
222.             for(i=0;i<zu;i++)for(j=0;j<yu;j++){
     
223.                 result.insert(buff2[i]+buff[j]);
     
224.                 result.insert(buff2[i]*buff[j]);
     
225.                 result.insert((buff2[i]-buff[j]).abs());
     
226.                                 number x=buff2[i]/buff[j];
     
227.                                 if(x.is_valid()){
     
228.                                         result.insert(x);
     
229.                                 }
     
230.                                 x=buff[j]/buff2[i];
     
231.                                 if(x.is_valid()){
     
232.                                         result.insert(x);
     
233.                                 }
     
234.             }
     
235.             if(yu<BUFF_LEN)break;
     
236.             yu=fread(buff,sizeof(number),BUFF_LEN,yFile);
     
237.         }while(1);
     
238.     }else if(yu<BUFF_LEN){
     
239.         do{
     
240.             for(i=0;i<zu;i++)for(j=0;j<yu;j++){
     
241.                 result.insert(buff2[i]+buff[j]);
     
242.                 result.insert(buff2[i]*buff[j]);
     
243.                 result.insert((buff2[i]-buff[j]).abs());
     
244.                                 number x=buff2[i]/buff[j];
     
245.                                 if(x.is_valid()){
     
246.                                         result.insert(x);
     
247.                                 }
     
248.                                 x=buff[j]/buff2[i];
     
249.                                 if(x.is_valid()){
     
250.                                         result.insert(x);
     
251.                                 }
     
252.             }
     
253.             if(zu<BUFF_LEN)break;
     
254.             zu=fread(buff2,sizeof(number),BUFF_LEN,zFile);
     
255.         }while(1);
     
256.     }else{
     
257.         do{
     
258.             do{
     
259.                 for(i=0;i<zu;i++)for(j=0;j<yu;j++){
     
260.                     result.insert(buff2[i]+buff[j]);
     
261.                     result.insert(buff2[i]*buff[j]);
     
262.                     result.insert((buff2[i]-buff[j]).abs());
     
263.                                         number x=buff2[i]/buff[j];
     
264.                                         if(x.is_valid()){
     
265.                                                 result.insert(x);
     
266.                                         }
     
267.                                         x=buff[j]/buff2[i];
     
268.                                         if(x.is_valid()){
     
269.                                                 result.insert(x);
     
270.                                         }
     
271.                 }
     
272.                 if(yu<BUFF_LEN)break;
     
273.                 yu=fread(buff,sizeof(number),BUFF_LEN,yFile);
     
274.             }while(1);
     
275.             if(zu<BUFF_LEN)break;
     
276.             zu=fread(buff2,sizeof(number),BUFF_LEN,zFile);
     
277.             if(zu==0)break;
     
278.             fseek(yFile,0,SEEK_SET);
     
279.             yu=fread(buff,sizeof(number),BUFF_LEN,yFile);
     
280.         }while(1);
     
281.     }
     
282.     if(yFile)fclose(yFile);
     
283.     if(zFile)fclose(zFile);
     
284. }
     
285. 
     
286. 
     
287. void gen_set(int x[],int size)
     
288. {
     
289.     int y[N],z[N];
     
290.     int i,j,yc,zc;
     
291.     if(size<=2)return;
     
292.     if(has_set(x,size))return;
     
293.     set<number> result;
     
294.     for(i=1;i<(1<<size)-1;i+=2){
     
295.         yc=zc=0;
     
296.         for(j=0;j<size;j++){
     
297.             if(i&(1<<j)){
     
298.                 y[yc++]=x[j];
     
299.             }else{
     
300.                 z[zc++]=x[j];
     
301.             }
     
302.         }
     
303.         gen_set(y,yc);
     
304.         gen_set(z,zc);
     
305.         add_result(result,y,yc,z,zc);
     
306.     }
     
307.     save_set(result,x,size);
     
308. }
     
309. 
     
310. int bc(int x){
     
311.         int c=0;
     
312.         while(x>0){
     
313.                 if(x&1)c++;
     
314.                 x>>=1;
     
315.         }
     
316.         return c;
     
317. }
     
318. 
     
319. int _tmain(int argc, _TCHAR* argv[])
     
320. {
     
321.     system("mkdir data");
     
322.     int x[]={1,2,3,4,5,6,7,8};
     
323.         int i;
     
324.         for(i=7;i<1<<12;i++){
     
325.                 if(bc(i)<=8){
     
326.                         int j=0,k;
     
327.                         for(k=0;k<12;k++){
     
328.                                 if(i&(1<<k)){
     
329.                                         x[j++]=k+1;
     
330.                                 }
     
331.                         }
     
332.                         gen_set(x,j);
     
333.                 }
     
334.         }
     
335.         return 0;
     
336. }
     

复制代码

mathe

第二部分代码是有了前面的结果,那么我们就可以将表达式拆分成两部分来求解,不过现在代码写的很简单,没有什么优化,即使N=11也运行了近一个晚上,这个代码应该可以改写的好看写,当然效率也可以改善一些.但是我觉得再怎么改,验证到N=12也已经是极限了.

1. 
   
2. // checker.cpp : Defines the entry point for the console application.
   
3. //
   
4. 
   
5. #include "stdafx.h"
   
6. #include <algorithm>
   
7. using namespace std;
   
8. #include <stdio.h>
   
9. #include <stdlib.h>
   
10. 
    
11. class number{
    
12.     int up;
    
13.     int down;
    
14. public:
    
15.     number(int u,int d):up(u),down(d){}
    
16.     number(const number& n):up(n.up),down(n.down){}
    
17.     number(int n=0):up(n),down(1){}
    
18.     number& operator+=(const number& n);
    
19.     number& operator-=(const number& n);
    
20.     number& operator*=(const number& n);
    
21.     number& operator/=(const number& n);
    
22.     bool is_zero()const{return down!=0&&up==0;}
    
23.     bool is_valid()const{return down!=0;}
    
24.     bool is_one()const{return down!=0&&up==down;}
    
25.     bool operator==(const number& n)const{return
    
26.         is_valid()&&n.is_valid()&&n.down*(long long)up==n.up*(long long)down;}
    
27.     bool operator<(const number& n)const;
    
28.     bool operator>(const number& n)const{return n<*this;}
    
29.     bool operator<=(const number& n)const{return !(*this>n);}
    
30.     bool operator!=(const number& n)const{return !(n==*this);}
    
31.     bool operator>=(const number& n)const{return !(*this<n);}
    
32.     number operator+(const number& n)const{number m(*this);return m+=n;}
    
33.     number operator-(const number& n)const{number m(*this);return m-=n;}
    
34.     number operator*(const number& n)const{number m(*this);return m*=n;}
    
35.     number operator/(const number& n)const{number m(*this);return m/=n;}
    
36.     bool is_integer()const{return down!=0&&up%down==0;}
    
37.     int get_integer()const{if(is_integer())return up/down;else return -1;}
    
38.     number& operator=(int n){up=n;down=1;return *this;}
    
39.     int get_up()const{return up;}
    
40.     int get_down()const{return down;}
    
41. };
    
42. 
    
43. number& number::operator +=(const number& n)
    
44. {
    
45.     up=up*n.down+down*n.up;
    
46.     down*=n.down;
    
47.     return *this;
    
48. }
    
49. 
    
50. number& number::operator -=(const number& n)
    
51. {
    
52.     up=up*n.down-down*n.up;
    
53.     if(up<0)up=-up;
    
54.     down*=n.down;
    
55.     return *this;
    
56. }
    
57. 
    
58. number& number::operator *=(const number& n)
    
59. {
    
60.     up*=n.up;
    
61.     down*=n.down;
    
62.     return *this;
    
63. }
    
64. 
    
65. number& number::operator /=(const number& n)
    
66. {
    
67.     down*=n.up;
    
68.     up*=n.down;
    
69.     return *this;
    
70. }
    
71. 
    
72. bool number::operator <(const number &n)const
    
73. {
    
74.     return (long long)up*n.down<n.up*(long long)down;
    
75. }
    
76. 
    
77. long long gcd(long long x,long long y)
    
78. {
    
79.     if(x==0)return y;
    
80.     return gcd(y%x,x);
    
81. }
    
82. 
    
83. class lnumber{
    
84.     long long up;
    
85.     long long down;
    
86. public:
    
87.     lnumber(const lnumber& n):up(n.up),down(n.down){}
    
88.     lnumber(const number& n):up(n.get_up()),down(n.get_down()){}
    
89.     lnumber(long long n=0):up(n),down(1LL){}
    
90.     lnumber& operator+=(const lnumber& n);
    
91.     lnumber& operator-=(const lnumber& n);
    
92.     lnumber& operator*=(const lnumber& n);
    
93.     lnumber& operator/=(const lnumber& n);
    
94.     bool is_zero()const{return down!=0&&up==0;}
    
95.     bool is_valid()const{return down!=0;}
    
96.     bool is_one()const{return down!=0&&up==down;}
    
97.     void normalize(){
    
98.         long long g=gcd(up,down);
    
99.         up/=g;down/=g;
    
100.     }
     
101.     bool operator==(const lnumber& n)const{
     
102.         if(!is_valid()||!n.is_valid())
     
103.             return false;
     
104.         if(n.down*up!=n.up*down)
     
105.             return false;
     
106.         ///check for overflow
     
107.         long long d1=n.down%0x7FFFFFFF;
     
108.         long long u1=n.up%0x7FFFFFFF;
     
109.         long long d2=down%0x7FFFFFFF;
     
110.         long long u2=up%0x7FFFFFFF;
     
111.         if((d1*u2)%0x7FFFFFFF!=(d2*u1)%0x7FFFFFFF)
     
112.             return false;
     
113.         return true;
     
114.     }
     
115.     bool operator<(const lnumber& n)const;
     
116.     bool operator>(const lnumber& n)const{return n<*this;}
     
117.     bool operator<=(const lnumber& n)const{return !(*this>n);}
     
118.     bool operator!=(const lnumber& n)const{return !(n==*this);}
     
119.     bool operator>=(const lnumber& n)const{return !(*this<n);}
     
120.     lnumber operator+(const lnumber& n)const{lnumber m(*this);return m+=n;}
     
121.     lnumber operator-(const lnumber& n)const{lnumber m(*this);return m-=n;}
     
122.     lnumber operator*(const lnumber& n)const{lnumber m(*this);return m*=n;}
     
123.     lnumber operator/(const lnumber& n)const{lnumber m(*this);return m/=n;}
     
124.     bool is_integer()const{return down!=0&&up%down==0;}
     
125.     long long get_integer()const{if(is_integer())return up/down;else return -1LL;}
     
126.     lnumber& operator=(long long n){up=n;down=1LL;return *this;}
     
127.     long long get_up()const{return up;}
     
128.     long long get_down()const{return down;}
     
129. };
     
130. 
     
131. lnumber& lnumber::operator +=(const lnumber& n)
     
132. {
     
133.     up=up*n.down+down*n.up;
     
134.     down*=n.down;
     
135.     return *this;
     
136. }
     
137. 
     
138. lnumber& lnumber::operator -=(const lnumber& n)
     
139. {
     
140.     up=up*n.down-down*n.up;
     
141.     if(up<0)up=-up;
     
142.     down*=n.down;
     
143.     return *this;
     
144. }
     
145. 
     
146. lnumber& lnumber::operator *=(const lnumber& n)
     
147. {
     
148.     up*=n.up;
     
149.     down*=n.down;
     
150.     return *this;
     
151. }
     
152. 
     
153. lnumber& lnumber::operator /=(const lnumber& n)
     
154. {
     
155.     down*=n.up;
     
156.     up*=n.down;
     
157.     return *this;
     
158. }
     
159. 
     
160. #define M32 0xFFFFFFFF
     
161. void mult128(unsigned int out[4],long long in1, long long in2)
     
162. {
     
163.     unsigned high1,low1,high2,low2;
     
164.     high1=(in1>>32)&M32;
     
165.     low1=in1&M32;
     
166.     high2=(in2>>32)&M32;
     
167.     low2=in2&M32;
     
168.     unsigned long long r1,r2,r3,r4;
     
169.     r1=low1*low2;
     
170.     r2=low1*high2;
     
171.     r3=high1*low2;
     
172.     r4=high1*high2;
     
173.     out[0]=(unsigned)(r1&M32);
     
174.     unsigned long long u=(r1>>32)&M32;
     
175.     u+=(r2&M32)+(r3&M32);
     
176.     out[1]=(unsigned)(u&M32);
     
177.     u=u>>32;
     
178.     u+=(r2>>32)+(r3>>32);
     
179.     u+=r4&M32;
     
180.     out[2]=(unsigned)(u&M32);
     
181.     u=u>>32;
     
182.     u+=(r4>>32);
     
183.     out[3]=(unsigned)u;
     
184. }
     
185. 
     
186. bool lnumber::operator <(const lnumber &n)const
     
187. {
     
188.     unsigned int r1[4],r2[4];
     
189.     int i;
     
190.     mult128(r1,up,n.down);
     
191.     mult128(r2,n.up,down);
     
192.     for(i=3;i>=0;i--){
     
193.         if(r1[i]<r2[i])
     
194.             return true;
     
195.         if(r1[i]>r2[i])
     
196.             return false;
     
197.     }
     
198. }
     
199. 
     
200. #define DATA_PATH "..\\..\\unr2\\unr2\\data\"
     
201. #define FILT_PATH "..\\..\\unr2\\unr2\\idata\"
     
202. #define T 38103
     
203. 
     
204. int bc(int x){
     
205.         int c=0;
     
206.         while(x>0){
     
207.                 if(x&1)c++;
     
208.                 x>>=1;
     
209.         }
     
210.         return c;
     
211. }
     
212. 
     
213. #define BUFF_LEN 4096
     
214. #define MAX_BUFF_SIZE (40*1024*1024)
     
215. number buff[BUFF_LEN];
     
216. number buff2[MAX_BUFF_SIZE];
     
217. 
     
218. bool test(number buff2[],int zu, const lnumber& r)
     
219. {
     
220.     lnumber rr=r;rr.normalize();
     
221.     if(rr.get_up()>0x7FFFFFFF||rr.get_down()>0x7FFFFFFF)
     
222.         return false;
     
223.     number sr((int)rr.get_up(),(int)rr.get_down());
     
224.     return binary_search(buff2,buff2+zu,sr);
     
225. }
     
226. 
     
227. 
     
228. ///x is small set, y is large set
     
229. bool verify(int x[],int xc, int y[],int yc, const lnumber& result)
     
230. {
     
231.     int mask1,mask2;
     
232.     char f1Name[100],f2Name[100];
     
233.     int i;
     
234.     mask1=mask2=0;
     
235.     for(i=0;i<xc;i++){
     
236.         mask1|=1<<(x[i]-1);
     
237.     }
     
238.     for(i=0;i<yc;i++){
     
239.         mask2|=1<<(y[i]-1);
     
240.     }
     
241.     sprintf(f1Name,DATA_PATH "%d",mask1);
     
242.     sprintf(f2Name,DATA_PATH "%d",mask2);
     
243.     FILE *f1,*f2;
     
244.     f1=f2=NULL;
     
245.     int yu,zu;
     
246.     if(xc>2){
     
247.         f1=fopen(f1Name,"rb");
     
248.         if(f1==NULL){
     
249.             fprintf(stderr,"Cannot open file %s\n",f1Name);
     
250.             exit(-1);
     
251.         }
     
252.         yu=fread(buff,sizeof(number),BUFF_LEN,f1);
     
253.     }else{
     
254.         if(xc==1){
     
255.             yu=1;
     
256.             buff[0]=x[0];
     
257.         }else{
     
258.             yu=5;
     
259.             buff[0]=x[0]+x[1];
     
260.             buff[1]=abs(x[0]-x[1]);
     
261.             buff[2]=x[0]*x[1];
     
262.             buff[3]=number(x[0])/x[1];
     
263.             buff[4]=number(x[1])/x[0];
     
264.         }
     
265.     }
     
266.     f2=fopen(f2Name,"rb");
     
267.     if(f2==NULL){
     
268.         fprintf(stderr,"Cannot open file %s\n",f2Name);
     
269.         exit(-1);
     
270.     }
     
271.     zu=fread(buff2,sizeof(number),MAX_BUFF_SIZE,f2);
     
272.     fclose(f2);
     
273. 
     
274.     do{
     
275.         for(i=0;i<yu;i++){
     
276.             lnumber lx=buff[i];
     
277.             lnumber s=lx+result;
     
278.             if(test(buff2,zu,s)){
     
279.                 if(f1)fclose(f1);
     
280.                 return true;
     
281.             }
     
282.             s=lx-result;
     
283.             if(test(buff2,zu,s)){
     
284.                 if(f1)fclose(f1);
     
285.                 return true;
     
286.             }
     
287.             if(!lx.is_zero()){
     
288.                 s=lx*result;
     
289.                 if(test(buff2,zu,s)){
     
290.                     if(f1)fclose(f1);
     
291.                     return true;
     
292.                 }
     
293.             }
     
294.             if(result.is_zero()&&lx.is_zero()){
     
295.                 if(f1)fclose(f1);
     
296.                 return true;
     
297.             }
     
298.             if(!lx.is_zero()){
     
299.                 s=result/lx;
     
300.                 if(test(buff2,zu,s)){
     
301.                     if(f1)fclose(f1);
     
302.                     return true;
     
303.                 }
     
304.             }
     
305.             if(!lx.is_zero()&&!result.is_zero()){
     
306.                 s=lx/result;
     
307.                 if(test(buff2,zu,s)){
     
308.                     if(f1)fclose(f1);
     
309.                     return true;
     
310.                 }
     
311.             }
     
312.         }
     
313.         if(yu<BUFF_LEN)break;
     
314.         yu=fread(buff,sizeof(number),BUFF_LEN,f1);
     
315.     }while(1);
     
316. 
     
317.     if(f1)fclose(f1);
     
318.     return false;
     
319. }
     
320. 
     
321. bool vs(int x[],int c, lnumber result)
     
322. {
     
323.         result.normalize();
     
324.         if(result.get_up()>=0x7FFFFFFF||result.get_down()>=0x7FFFFFFF)
     
325.                 return false;
     
326.         number sr((int)result.get_up(),(int)result.get_down());
     
327.     int mask;
     
328.     char fName[100];
     
329.     int i;
     
330.     mask=0;
     
331.     for(i=0;i<c;i++){
     
332.         mask|=1<<(x[i]-1);
     
333.     }
     
334.     sprintf(fName,DATA_PATH "%d",mask);
     
335.     FILE *f;
     
336.     f=NULL;
     
337.     int yu;
     
338.     if(c>2){
     
339.         f=fopen(fName,"rb");
     
340.         if(f==NULL){
     
341.             fprintf(stderr,"Cannot open file %s\n",fName);
     
342.             exit(-1);
     
343.         }
     
344.         yu=fread(buff,sizeof(number),BUFF_LEN,f);
     
345.     }else{
     
346.         if(c==1){
     
347.             yu=1;
     
348.             buff[0]=x[0];
     
349.         }else{
     
350.             yu=5;
     
351.             buff[0]=x[0]+x[1];
     
352.             buff[1]=abs(x[0]-x[1]);
     
353.             buff[2]=x[0]*x[1];
     
354.             buff[3]=number(x[0])/x[1];
     
355.             buff[4]=number(x[1])/x[0];
     
356.         }
     
357.     }
     
358. 
     
359.         do{
     
360.                 for(i=0;i<yu;i++){
     
361.                         if(buff[i]==sr){
     
362.                                 if(f)fclose(f);
     
363.                                 return true;
     
364.                         }
     
365.                 }
     
366.         if(yu<BUFF_LEN)break;
     
367.         yu=fread(buff,sizeof(number),BUFF_LEN,f);
     
368.     }while(1);
     
369.         if(f)fclose(f);
     
370.         return false;
     
371. }
     
372. 
     
373. bool v9(int x[],lnumber result)
     
374. {///verify 9 elements in x could get 'result'
     
375.     int u;
     
376.     int i,j;
     
377.     int N=9;
     
378.     int uc,vc;
     
379.     int au[9],av[9];
     
380.     for(u=(N+1)/2;u<=8;u++){
     
381.         int v=N-u;
     
382.         for(i=1;i<(1<<N)-1;i++){
     
383.             if(bc(i)==v){
     
384.                 uc=vc=0;
     
385.                 for(j=0;j<N;j++){
     
386.                     if(i&(1<<j)){
     
387.                         av[vc++]=j+1;
     
388.                     }else{
     
389.                         au[uc++]=j+1;
     
390.                     }
     
391.                 }
     
392.                 if(verify(av,vc,au,uc,result))
     
393.                     return true;
     
394.             }
     
395.         }
     
396.     }
     
397.     return false;
     
398. }
     
399. 
     
400. bool v10(int x[],lnumber result)
     
401. {
     
402.     int u;
     
403.     int i,j;
     
404.     int N=10;
     
405.     int uc,vc;
     
406.     int au[10],av[10];
     
407.     for(u=(N+1)/2;u<=8;u++){
     
408.         int v=N-u;
     
409.         for(i=1;i<(1<<N)-1;i++){
     
410.             if(bc(i)==v){
     
411.                 uc=vc=0;
     
412.                 for(j=0;j<N;j++){
     
413.                     if(i&(1<<j)){
     
414.                         av[vc++]=x[j];
     
415.                     }else{
     
416.                         au[uc++]=x[j];
     
417.                     }
     
418.                 }
     
419.                 if(verify(av,vc,au,uc,result))
     
420.                     return true;
     
421.             }
     
422.         }
     
423.     }
     
424.     for(u=0;u<10;u++){
     
425.         int h=x[u];
     
426.         uc=0;
     
427.         for(i=0;i<10;i++){
     
428.             if(i!=u){
     
429.                 au[uc++]=x[i];
     
430.             }
     
431.         }
     
432.         if(v9(au,result+h))
     
433.             return true;
     
434.         if(v9(au,result-h))
     
435.             return true;
     
436.         if(result.is_zero()&&h==0)return true;
     
437.         if(h!=0){
     
438.             if(v9(au,result*h))
     
439.                 return true;
     
440.             if(v9(au,result/h))
     
441.                 return true;
     
442.             if(!result.is_zero()){
     
443.                 if(v9(au,lnumber(h)/result))
     
444.                     return true;
     
445.             }
     
446.         }
     
447.     }
     
448.     return false;
     
449. }
     
450. 
     
451. bool v11(int x[],lnumber result)
     
452. {
     
453.     int u;
     
454.     int i,j;
     
455.     int N=11;
     
456.     int uc,vc;
     
457.     int au[11],av[11];
     
458.     for(u=(N+1)/2;u<=8;u++){
     
459.         int v=N-u;
     
460.         for(i=1;i<(1<<N)-1;i++){
     
461.             if(bc(i)==v){
     
462.                 uc=vc=0;
     
463.                 for(j=0;j<N;j++){
     
464.                     if(i&(1<<j)){
     
465.                         av[vc++]=x[j];
     
466.                     }else{
     
467.                         au[uc++]=x[j];
     
468.                     }
     
469.                 }
     
470.                 if(verify(av,vc,au,uc,result))
     
471.                     return true;
     
472.             }
     
473.         }
     
474.     }
     
475.     for(u=0;u<11;u++){
     
476.         int h=x[u];
     
477.         uc=0;
     
478.         for(i=0;i<11;i++){
     
479.             if(i!=u){
     
480.                 au[uc++]=x[i];
     
481.             }
     
482.         }
     
483.         if(v10(au,result+h))
     
484.             return true;
     
485.         if(v10(au,result-h))
     
486.             return true;
     
487.         if(result.is_zero()&&h==0)return true;
     
488.         if(h!=0){
     
489.             if(v10(au,result*h))
     
490.                 return true;
     
491.             if(v10(au,result/h))
     
492.                 return true;
     
493.             if(!result.is_zero()){
     
494.                 if(v10(au,lnumber(h)/result))
     
495.                     return true;
     
496.             }
     
497.         }
     
498.                 int u2;
     
499.                 for(u2=u+1;u2<11;u2++){
     
500.                         int hc=5,h2=x[u2];
     
501.                         number hh[5];
     
502.                         hh[0]=h+h2;hh[1]=abs(h-h2);hh[2]=h*h2;hh[3]=number(h,h2);hh[4]=number(h2,h);
     
503.                         for(int k=0;k<5;k++){
     
504.                                 uc=0;
     
505.                                 for(i=0;i<11;i++){
     
506.                                         if(i!=u&&i!=u2){
     
507.                                                 au[uc++]=x[i];
     
508.                                         }
     
509.                                 }
     
510.                                 if(v9(au,result+hh[k]))
     
511.                                         return true;
     
512.                                 if(v9(au,result-hh[k]))
     
513.                                         return true;
     
514.                                 if(result.is_zero()&&hh[k].is_zero())return true;
     
515.                                 if(!hh[k].is_zero()){
     
516.                                         if(v9(au,result*hh[k]))
     
517.                                                 return true;
     
518.                                         if(v9(au,result/hh[k]))
     
519.                                                 return true;
     
520.                                         if(!result.is_zero()){
     
521.                                                 if(v9(au,lnumber(hh[k])/result))
     
522.                                                         return true;
     
523.                                         }
     
524.                                 }
     
525.                         }
     
526.                 }
     
527.     }
     
528.     return false;
     
529. }
     
530. 
     
531. bool u9(int x[],const number& r, int size)
     
532. {
     
533.         int i,j;
     
534.         int y[9];
     
535.         for(i=0;i<(1<<9)-1;i++){
     
536.                 if(bc(i)>=size){
     
537.                         int c;
     
538.                         for(j=0,c=0;j<9;j++){
     
539.                                 if(i&(1<<j)){
     
540.                                         y[c++]=x[j];
     
541.                                 }
     
542.                         }
     
543.                         if(vs(y,c,r))
     
544.                                 return true;
     
545.                 }
     
546.         }
     
547.         return false;
     
548. }
     
549. 
     
550. bool u10(int x[],const number& r, int size)
     
551. {
     
552.         int i,j;
     
553.         int y[10];
     
554.         for(i=0;i<(1<<10)-1;i++){
     
555.                 if(bc(i)>=size){
     
556.                         int c;
     
557.                         for(j=0,c=0;j<10;j++){
     
558.                                 if(i&(1<<j)){
     
559.                                         y[c++]=x[j];
     
560.                                 }
     
561.                         }
     
562.                         if(c<9){
     
563.                                 if(vs(y,c,r))
     
564.                                         return true;
     
565.                         }else if(c==9){
     
566.                                 if(v9(y,r))
     
567.                                         return true;
     
568.                         }
     
569.                 }
     
570.         }
     
571.         return false;
     
572. }
     
573. 
     
574. bool u11(int x[], const number& r, int size)
     
575. {
     
576.         int i,j;
     
577.         int y[11];
     
578.         for(i=0;i<(1<<11)-1;i++){
     
579.                 if(bc(i)>=size){
     
580.                         int c;
     
581.                         for(j=0,c=0;j<11;j++){
     
582.                                 if(i&(1<<j)){
     
583.                                         y[c++]=x[j];
     
584.                                 }
     
585.                         }
     
586.                         if(c<9){
     
587.                                 if(vs(y,c,r))
     
588.                                         return true;
     
589.                         }else if(c==9){
     
590.                                 if(v9(y,r))
     
591.                                         return true;
     
592.                         }else if(c==10){
     
593.                                 if(v10(y,r))
     
594.                                         return true;
     
595.                         }
     
596.                 }
     
597.         }
     
598.         return false;
     
599. }
     
600. 
     
601. ///Now comes code for N=9
     
602. int _tmain(int argc, _TCHAR* argv[])
     
603. {
     
604.     int x;
     
605.     int i,j;
     
606.     int u[12]={1,2,3,4,5,6,7,8,9,10,11,12};
     
607.     if(v9(u,lnumber(38103))){
     
608.         fprintf(stderr,"Fail for test 9\n");
     
609.     }
     
610.         fprintf(stderr,"Finish test 9\n");
     
611.     if(v10(u,lnumber(231051))){
     
612.         fprintf(stderr,"Fail for test 10\n");
     
613.     }
     
614.         fprintf(stderr,"Finish test 10\n");
     
615. /*        if(u9(u,number(38103),5)){
     
616.                 fprintf(stderr,"Fail for subdata of 9\n");
     
617.         }
     
618. */        if(u10(u,number(231051),6)){
     
619.                 fprintf(stderr,"Fail for subdata of 10\n");
     
620.         }
     
621.         fprintf(stderr,"End of test 10\n");
     
622.         if(v11(u,lnumber(1765186))){
     
623.         fprintf(stderr,"Fail for test 11\n");
     
624.         }
     
625.         fprintf(stderr,"end for test 11\n");
     
626.         if(u11(u,number(1765186),7)){
     
627.                 fprintf(stderr,"Fail for subdata of 11\n");
     
628.         }
     
629.         fprintf(stderr,"End of test\n");
     
630.         return 0;
     
631. }
     

复制代码

无心人

我觉得有点慢
=====================
用二分是否好呢?
使用不同分划数量的两组整数
逐步递归产生结果？

无心人

比如11的
先考虑1个10个的分划
10个的再分划

因为有总目标存在
所以应该比原始题目快的多

mathe

我已经按你说的做了.这个已经比原始题目快很多了.原始题目如果采用+,-,*,/所有的操作符,最多只能计算到N=10(好像需要2天左右时间)

无心人

明白你如何做的了

mathe

昨天N=12的情况验证通过了。不过程序运行多长时间忘记了，估计在一到两周之间。