找回密码
 欢迎注册
楼主: mathe

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

[复制链接]
发表于 2008-10-4 00:13:00 | 显示全部楼层
所谓不用考虑括号不过是针对程序处理而言
而我说的是针对推理证明
这一题如果不能证明1~n的数能够连续表示出1~(1+2)*3*...n的正整数
即时你能够做出11,还有12,13...
而且不考虑除的话结果肯定不对
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-10-4 08:08:41 | 显示全部楼层
原帖由 jiangbin00cn 于 2008-10-4 00:13 发表
所谓不用考虑括号不过是针对程序处理而言
而我说的是针对推理证明
这一题如果不能证明1~n的数能够连续表示出1~(1+2)*3*...n的正整数
即时你能够做出11,还有12,13...
而且不考虑除的话结果肯定不对

你应该先查看一下前面已经得出的一些结果。在做猜想时起码得检验一下是否成立
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-10-4 08:49:26 | 显示全部楼层
我来回答吧
1、没有括号是针对程序设计的
你仔细研究下我说的中序遍历下的表达式树序列
只要考虑从右边连续取数字压栈
碰到计算符号,弹出两个数字,计算后压栈
直到序列空,就会得到表达式值,当然也能得到带括号的原始表达式的
2、并不能表示1到n! * 3 / 2的所有连续数字
比如1-4,就不可以的
3、不考虑除法是因为除法有点复杂,这个问题一个数字有很多表示方法
不考虑除法会减少一些数字被成功解析的机会,但会大大增加速度
有除法参与的运算,需要考虑6种可能,没有除法仅考虑4种就可以了
而且加减乘运算,只需要运算,除法需要判定0做除数和是否除尽的
我们只是研究如果去掉除法,是否会对整体没有影响,我想可能在大数字下有影响

[ 本帖最后由 无心人 于 2008-10-4 08:50 编辑 ]
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-10-4 15:58:48 | 显示全部楼层
好像我这个最新的将中间结果保存到文件的程序比上一个版本(不保存到文件的)速度还要慢很多 实在没有想到,可能是文件访问太慢了.早知道原先版本就不应该停小来了.
不过这个程序现在已经完全产生了使用11个数中不超过8个数的所有可能结果(只保存结果值),所有数据才133M(看来都可以直接保存在内存中)
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-10-4 18:02:14 | 显示全部楼层


这么低啊????
我的可没这么低
11的我估计是现有硬盘空间无法承受的
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-10-4 21:14:45 | 显示全部楼层
是不是结果相等的表达式你重复保存了。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-10-5 09:26:27 | 显示全部楼层
是啊

可是结果相同的,使用的数字不一定相同啊
你觉得没有必要么?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-10-5 17:39:26 | 显示全部楼层
下面程序你可以运行一下看,Windows下面运行

  1. #include "stdafx.h"
  2. #define N 12
  3. #include <set>
  4. using namespace std;

  5. bool has_set(int x[],int size)
  6. {
  7.     int mask=0;
  8.     int i;
  9.     char fName[20];
  10.     for(i=0;i<size;i++){
  11.         mask|=1<<(x[i]-1);
  12.     }
  13.     sprintf(fName,"data\\%d",mask);
  14.     FILE *pFile=fopen(fName,"rb");
  15.     if(pFile==NULL)
  16.         return false;
  17.     fclose(pFile);
  18.     return true;
  19. }

  20. #define BUFF_LEN 4096
  21. int buff[BUFF_LEN];
  22. int buff2[BUFF_LEN];

  23. void output_r(int i)
  24. {
  25.     int s=(1<<i)-1;
  26.     char fName[20];
  27.     sprintf(fName,"data\\%d",s);
  28.     FILE *pFile=fopen(fName,"rb");
  29.     if(pFile==NULL){
  30.         fprintf(stderr,"Cannot read file %s\n",fName);
  31.         exit(-1);
  32.     }
  33.     int yu=fread(buff,sizeof(int),BUFF_LEN,pFile);
  34.     int x=1,start;
  35.     if(buff[0]==0)start=1;else start=0;
  36.     while(buff[start]==x){
  37.         x++;
  38.         start++;
  39.         if(start>=yu){
  40.             if(yu==BUFF_LEN){
  41.                 yu=fread(buff,sizeof(int),BUFF_LEN,pFile);
  42.                 start=0;
  43.                 if(yu==0)break;
  44.             }else break;
  45.         }
  46.     }
  47.     printf("r[%d]=%d\n",i,x);
  48.     fclose(pFile);
  49. }

  50. void save_set(const set<int>& result, int x[],int size)
  51. {
  52.     int mask=0;
  53.     int i;
  54.     char fName[20];
  55.     for(i=0;i<size;i++){
  56.         mask|=1<<(x[i]-1);
  57.     }
  58.     sprintf(fName,"data\\%d",mask);
  59.     FILE *pFile=fopen(fName,"wb");
  60.     if(pFile==NULL){
  61.         fprintf(stderr,"Cannot write file %s\n",fName);
  62.         exit(-1);
  63.     }
  64.     int j;
  65.     set<int>::const_iterator cit;
  66.     i=j=0;
  67.     for(cit=result.begin();cit!=result.end();++cit){
  68.         buff[j++]=*cit;
  69.         i++;
  70.         if(j==BUFF_LEN){
  71.             j=0;
  72.             fwrite(buff,sizeof(int),BUFF_LEN,pFile);
  73.         }
  74.     }
  75.     if(j>0){
  76.         fwrite(buff,sizeof(int),j,pFile);
  77.     }
  78.     fclose(pFile);

  79.     if((mask&(mask+1))==0){
  80.         output_r(size);
  81.     }
  82. }


  83. void add_result(set<int>& result, int y[],int yc,int z[],int zc)
  84. {
  85.     int mask=0;
  86.     int i,j;
  87.     char fName[20];
  88.     FILE *yFile,*zFile;
  89.     int yu,zu;
  90.     if(yc<=2){
  91.         if(yc==1){
  92.             yu=1;
  93.             buff[0]=y[0];
  94.         }else{
  95.             yu=3;
  96.             buff[0]=y[0]+y[1];
  97.             buff[1]=abs(y[0]-y[1]);
  98.             buff[2]=y[0]*y[1];
  99.         }
  100.         yFile=NULL;
  101.     }else{
  102.         mask=0;
  103.         for(i=0;i<yc;i++){
  104.             mask|=1<<(y[i]-1);
  105.         }
  106.         sprintf(fName,"data\\%d",mask);
  107.         yFile=fopen(fName,"rb");
  108.         if(yFile==NULL){
  109.             fprintf(stderr,"Cannot read file %s\n",fName);
  110.             exit(-1);
  111.         }
  112.         yu=fread(buff,sizeof(int),BUFF_LEN,yFile);
  113.     }
  114.     if(zc<=2){
  115.         if(zc==1){
  116.             zu=1;
  117.             buff2[0]=z[0];
  118.         }else{
  119.             zu=3;
  120.             buff2[0]=z[0]+z[1];
  121.             buff2[1]=abs(z[0]-z[1]);
  122.             buff2[2]=z[0]*z[1];
  123.         }
  124.         zFile=NULL;
  125.     }else{
  126.         mask=0;
  127.         for(i=0;i<zc;i++){
  128.             mask|=1<<(z[i]-1);
  129.         }
  130.         sprintf(fName,"data\\%d",mask);
  131.         zFile=fopen(fName,"rb");
  132.         if(zFile==NULL){
  133.             fprintf(stderr,"Cannot read file %s\n",fName);
  134.             exit(-1);
  135.         }
  136.         zu=fread(buff2,sizeof(int),BUFF_LEN,zFile);
  137.     }
  138.     if(zu<BUFF_LEN){
  139.         do{
  140.             for(i=0;i<zu;i++)for(j=0;j<yu;j++){
  141.                 result.insert(buff2[i]+buff[j]);
  142.                 result.insert(buff2[i]*buff[j]);
  143.                 result.insert(abs(buff2[i]-buff[j]));
  144.             }
  145.             if(yu<BUFF_LEN)break;
  146.             yu=fread(buff,sizeof(int),BUFF_LEN,yFile);
  147.         }while(1);
  148.     }else if(yu<BUFF_LEN){
  149.         do{
  150.             for(i=0;i<zu;i++)for(j=0;j<yu;j++){
  151.                 result.insert(buff2[i]+buff[j]);
  152.                 result.insert(buff2[i]*buff[j]);
  153.                 result.insert(abs(buff2[i]-buff[j]));
  154.             }
  155.             if(zu<BUFF_LEN)break;
  156.             zu=fread(buff2,sizeof(int),BUFF_LEN,zFile);
  157.         }while(1);
  158.     }else{
  159.         do{
  160.             do{
  161.                 for(i=0;i<zu;i++)for(j=0;j<yu;j++){
  162.                     result.insert(buff2[i]+buff[j]);
  163.                     result.insert(buff2[i]*buff[j]);
  164.                     result.insert(abs(buff2[i]-buff[j]));
  165.                 }
  166.                 if(yu<BUFF_LEN)break;
  167.                 yu=fread(buff,sizeof(int),BUFF_LEN,yFile);
  168.             }while(1);
  169.             if(zu<BUFF_LEN)break;
  170.             zu=fread(buff2,sizeof(int),BUFF_LEN,zFile);
  171.             if(zu==0)break;
  172.             fseek(yFile,0,SEEK_SET);
  173.             yu=fread(buff,sizeof(int),BUFF_LEN,yFile);
  174.         }while(1);
  175.     }
  176.     if(yFile)fclose(yFile);
  177.     if(zFile)fclose(zFile);
  178. }


  179. void gen_set(int x[],int size)
  180. {
  181.     int y[N],z[N];
  182.     int i,j,yc,zc;
  183.     if(size<=2)return;
  184.     if(has_set(x,size))return;
  185.     set<int> result;
  186.     for(i=1;i<(1<<size)-1;i+=2){
  187.         yc=zc=0;
  188.         for(j=0;j<size;j++){
  189.             if(i&(1<<j)){
  190.                 y[yc++]=x[j];
  191.             }else{
  192.                 z[zc++]=x[j];
  193.             }
  194.         }
  195.         gen_set(y,yc);
  196.         gen_set(z,zc);
  197.         add_result(result,y,yc,z,zc);
  198.     }
  199.     save_set(result,x,size);
  200. }


  201. int _tmain(int argc, _TCHAR* argv[])
  202. {
  203.     int x[]={1,2,3,4,5,6,7,8,9,10,11,12};
  204.     system("mkdir data");
  205.     gen_set(x,N);
  206.         return 0;
  207. }
复制代码
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-10-5 18:58:33 | 显示全部楼层
上面程序我在笔记本上用N=10运行了一下,花费时间还不算长,几分钟。但是N=11时间就受不了了。今天只有笔记本可以用,不能长时间运行程序。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-10-5 19:59:12 | 显示全部楼层


N=10你得到的输出和前面你原始的程序结果一致么?
另外,你估计下N=11可以改成持续运行的程序么?
或者说N=11需要不可中断的运行时间是多少?

假设在24小时内,甚至在72小时我想也可接受
如果是超过72小时,则可能不能保证停电后能继续
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

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

GMT+8, 2024-3-29 15:57 , Processed in 0.055165 second(s), 14 queries .

Powered by Discuz! X3.5

© 2001-2024 Discuz! Team.

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