数学研发网设为首页收藏本站
切换到窄版

 找回密码
 欢迎注册
数学研发论坛»论坛 › 【算法研发】 › 编程擂台 › 最小无法表达的正整数
1 ...101112131415161718下一页
返回列表 发新帖
楼主: mathe

[擂台] 最小无法表达的正整数

[复制链接]
无心人
发表于 2008-10-7 11:14:01 | 显示全部楼层
为什么啊？ 喜欢玩变态？
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

mathe
 楼主| 发表于 2008-10-9 07:42:34 | 显示全部楼层
1-11中任意多个数采用+,-,*,/不能达到1765186得到证明了. 不过要验证12个数看来很难,估计要花费很长时间.
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

无心人
发表于 2008-10-9 07:56:08 | 显示全部楼层
能给出验证程序么？
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

mathe
 楼主| 发表于 2008-10-9 08:01:37 | 显示全部楼层
代码挺慢,分两部分. 第一部分将所有1~n之间不超过8个数字通过+,-,*,/所能得到的结果全部计算出来并且保存在文件中,其中1~11所有结果产生需要10个多小时,总共数据15.6G. 而计算1~12所产生的结果运行了37个多小时,总共数据量54G
  2. #include "stdafx.h"
  3. #define N 8
  4. #include <set>
  5. using namespace std;
  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. };
  39. number& number::operator +=(const number& n)
  40. {
  41. up=up*n.down+down*n.up;
  42. down*=n.down;
  43. return *this;
  44. }
  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. }
  54. number& number::operator *=(const number& n)
  55. {
  56. up*=n.up;
  57. down*=n.down;
  58. return *this;
  59. }
  61. number& number::operator /=(const number& n)
  62. {
  63. down*=n.up;
  64. up*=n.down;
  65. return *this;
  66. }
  68. bool number::operator <(const number &n)const
  69. {
  70. return (long long)up*n.down<n.up*(long long)down;
  71. }
  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. }
  89. #define BUFF_LEN 4096
  90. number buff[BUFF_LEN];
  91. number buff2[BUFF_LEN];
  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. }
  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);
  155. if((mask&(mask+1))==0){
  156. output_r(size);
  157. }
  158. }
  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. }
  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. }
  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. }
  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
 楼主| 发表于 2008-10-9 08:03:58 | 显示全部楼层
第二部分代码是有了前面的结果,那么我们就可以将表达式拆分成两部分来求解,不过现在代码写的很简单,没有什么优化,即使N=11也运行了近一个晚上,这个代码应该可以改写的好看写,当然效率也可以改善一些.但是我觉得再怎么改,验证到N=12也已经是极限了.
  2. // checker.cpp : Defines the entry point for the console application.
  3. //
  5. #include "stdafx.h"
  6. #include <algorithm>
  7. using namespace std;
  8. #include <stdio.h>
  9. #include <stdlib.h>
  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. };
  43. number& number::operator +=(const number& n)
  44. {
  45. up=up*n.down+down*n.up;
  46. down*=n.down;
  47. return *this;
  48. }
  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. }
  58. number& number::operator *=(const number& n)
  59. {
  60. up*=n.up;
  61. down*=n.down;
  62. return *this;
  63. }
  65. number& number::operator /=(const number& n)
  66. {
  67. down*=n.up;
  68. up*=n.down;
  69. return *this;
  70. }
  72. bool number::operator <(const number &n)const
  73. {
  74. return (long long)up*n.down<n.up*(long long)down;
  75. }
  77. long long gcd(long long x,long long y)
  78. {
  79. if(x==0)return y;
  80. return gcd(y%x,x);
  81. }
  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. };
  131. lnumber& lnumber::operator +=(const lnumber& n)
  132. {
  133. up=up*n.down+down*n.up;
  134. down*=n.down;
  135. return *this;
  136. }
  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. }
  146. lnumber& lnumber::operator *=(const lnumber& n)
  147. {
  148. up*=n.up;
  149. down*=n.down;
  150. return *this;
  151. }
  153. lnumber& lnumber::operator /=(const lnumber& n)
  154. {
  155. down*=n.up;
  156. up*=n.down;
  157. return *this;
  158. }
  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. }
  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. }
  200. #define DATA_PATH "..\\..\\unr2\\unr2\\data\"
  201. #define FILT_PATH "..\\..\\unr2\\unr2\\idata\"
  202. #define T 38103
  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. }
  213. #define BUFF_LEN 4096
  214. #define MAX_BUFF_SIZE (40*1024*1024)
  215. number buff[BUFF_LEN];
  216. number buff2[MAX_BUFF_SIZE];
  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. }
  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);
  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);
  317. if(f1)fclose(f1);
  318. return false;
  319. }
  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. }
  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. }
  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. }
  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. }
  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. }
  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. }
  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. }
  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. }
  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. }
复制代码
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

无心人
发表于 2008-10-9 08:15:04 | 显示全部楼层
我觉得有点慢 ===================== 用二分是否好呢? 使用不同分划数量的两组整数 逐步递归产生结果？
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

无心人
发表于 2008-10-9 08:16:43 | 显示全部楼层
比如11的 先考虑1个10个的分划 10个的再分划 因为有总目标存在 所以应该比原始题目快的多
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

mathe
 楼主| 发表于 2008-10-9 09:18:36 | 显示全部楼层
我已经按你说的做了.这个已经比原始题目快很多了.原始题目如果采用+,-,*,/所有的操作符,最多只能计算到N=10(好像需要2天左右时间)
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

无心人
发表于 2008-10-9 09:30:55 | 显示全部楼层
明白你如何做的了
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

mathe
 楼主| 发表于 2008-11-5 11:54:00 | 显示全部楼层
昨天N=12的情况验证通过了。不过程序运行多长时间忘记了，估计在一到两周之间。
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

1 ...101112131415161718下一页
返回列表 发新帖
高级模式
B Color Image Link Quote Code Smilies
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2024-11-25 02:08 , Processed in 0.025096 second(s), 14 queries .

Powered by Discuz! X3.5

© 2001-2024 Discuz! Team.

快速回复 返回顶部 返回列表