数学研发论坛

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

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

[复制链接]
 楼主| 发表于 2008-8-21 10:31:40 | 显示全部楼层
发现这道题目A060315也已经给到第10项了,和我结果相同。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-8-21 10:46:57 | 显示全部楼层
这个问题实际上我在02年4月份解决过:
http://www.mitbbs.cn/bbsann2/sci ... A/Re:%20yes....1413
现在将那个代码转贴过来

  1. #include <algorithm>
  2. #include <iostream>
  3. #include <vector>
  4. #include <time.h>
  5. #include <string>
  6. #include <set>
  7. #include <stdio.h>

  8. #ifdef _WIN32
  9. typedef __int64 longlong;
  10. #else
  11. typedef long long longlong;
  12. #endif
  13. using namespace std;

  14. #ifdef _DEBUG
  15. #include <assert.h>
  16. #define ASSERT(x) assert(x)
  17. #else
  18. #define ASSERT(x)
  19. #endif
  20. #define MAX_NUM 10

  21. #define SEARCH_VALUE 8

  22. //enlarge CACHE_LIMIT so that some expression will be saved in memory. This
  23. //will speed the program,
  24. //but then we could not print the correct expression by expression() function.
  25. //CACHE_LIMIT should be no more than 8. I found that the speed will drop when
  26. //CACHE_LIMIT is too large
  27. #define CACHE_LIMIT 0

  28. #if CACHE_LIMIT==0
  29. //#define DISPLAY_NEW_VISIT
  30. //We could not define macro DISPLAY_NEW_VISIT when CACHE_LIMIT is non-zero, since we could not dump out expression when only result of sub-tree is cached (and sub-tree not available)
  31. //define CACHE_LIMIT to 0 and define DISPLAY_NEW_VISIT could dump out all the first expression to reach any integer number
  32. #endif

  33. class number{
  34.     int up;
  35.     int down;
  36. public:
  37.     number(const number& n):up(n.up),down(n.down){}
  38.     number(int n=0):up(n),down(1){}
  39.     number& operator+=(const number& n);
  40.     number& operator-=(const number& n);
  41.     number& operator*=(const number& n);
  42.     number& operator/=(const number& n);
  43.     bool is_zero()const{return down!=0&&up==0;}
  44.     bool is_valid()const{return down!=0;}
  45.     bool is_one()const{return down!=0&&up==down;}
  46.     bool operator==(const number& n)const{return
  47.         is_valid()&&n.is_valid()&&n.down*up==n.up*down;}
  48.     bool operator<(const number& n)const;
  49.     bool operator>(const number& n)const{return n<*this;}
  50.     bool operator<=(const number& n)const{return !(*this>n);}
  51.     bool operator!=(const number& n)const{return !(n==*this);}
  52.     bool operator>=(const number& n)const{return !(*this<n);}
  53.     number operator+(const number& n)const{number m(*this);return m+=n;}
  54.     number operator-(const number& n)const{number m(*this);return m-=n;}
  55.     number operator*(const number& n)const{number m(*this);return m*=n;}
  56.     number operator/(const number& n)const{number m(*this);return m/=n;}
  57.     bool is_integer()const{return down!=0&&up%down==0;}
  58.     int get_integer()const{if(is_integer())return up/down;else return -1;}
  59.     number& operator=(int n){up=n;down=1;return *this;}
  60.     int get_up()const{return up;}
  61.     int get_down()const{return down;}
  62. };

  63. number& number::operator +=(const number& n)
  64. {
  65.     up=up*n.down+down*n.up;
  66.     down*=n.down;
  67.     return *this;
  68. }

  69. number& number::operator -=(const number& n)
  70. {
  71.     up=up*n.down-down*n.up;
  72.     if(up<0)up=-up;
  73.     down*=n.down;
  74.     return *this;
  75. }

  76. number& number::operator *=(const number& n)
  77. {
  78.     up*=n.up;
  79.     down*=n.down;
  80.     return *this;
  81. }

  82. number& number::operator /=(const number& n)
  83. {
  84.     down*=n.up;
  85.     up*=n.down;
  86.     return *this;
  87. }

  88. bool number::operator <(const number &n)const
  89. {
  90.     return up*n.down<n.up*down;
  91. }

  92. /*iterator to enumerate the partition of n different objects into m groups,where m is a varialbe so that the iterator will enumerate all m in range [2,n]
  93. * and sub-iterator split_iterator spliter is used to enumerator numbers of objects in each groups
  94. */
  95. class select_iterator{
  96.     int n;//total n element;
  97.     int m;//max group id; That's group 1<<8,2<<8,...,m<<8; m should be no less than 2.
  98.         //The select_iterator is used to split n elements into groups.
  99.     int select_array[MAX_NUM];///tells which group each number is located (It is select_array[x]>>8) and the order of the number inside the group (select_array[x]&255)
  100.     int sub_size[MAX_NUM]; ///sub_size[x] provides the number of elements of all groups whose group id no more than x
  101.     class split_iterator{///iterator to partition 'size' same objects into several groups (so only number of objects in each group is considered)
  102.         int split_array[MAX_NUM];///number of objects in each group
  103.         int last_index;///number of group - '1'
  104.     public:
  105.         split_iterator(int size)
  106.         {
  107.             ASSERT(size<=MAX_NUM);
  108.             if(size==1)
  109.             {
  110.                 last_index=0;
  111.                 split_array[0]=1;
  112.             }
  113.             else
  114.             {///Usually, we need partition data into at least two groups.
  115.                 last_index=1;
  116.                 split_array[0]=size-1;
  117.                 split_array[1]=1;
  118.             }
  119.         }
  120.         bool inc()///Move to the next partition
  121.         {
  122.             int i;
  123.             ASSERT(last_index<MAX_NUM);
  124.             for(i=last_index;i>=0;--i)
  125.             {
  126.                 if(split_array[i]>=2)
  127.                     break;
  128.             }
  129.             if(i==-1)
  130.             {
  131.                 int size=0;
  132.                 for(i=0;i<=last_index;++i)
  133.                     size+=split_array[i];
  134.                 if(size==1)
  135.                 {
  136.                     last_index=0;
  137.                     split_array[0]=1;
  138.                 }
  139.                 else
  140.                 {
  141.                     last_index=1;
  142.                     split_array[0]=size-1;
  143.                     split_array[1]=1;
  144.                 }
  145.                 return false;//end of search.
  146.             }
  147.             else
  148.             {
  149.                 int total;
  150.                 int last;
  151.                 last=--split_array[i];
  152.                 total=last_index-i+1;
  153.                 while(total>=last){
  154.                     split_array[++i]=last;
  155.                     total-=last;
  156.                 }
  157.                 if(total>0){
  158.                     split_array[++i]=total;
  159.                 }
  160.                 last_index=i;
  161.             }
  162.             return true;
  163.         }
  164.         friend class select_iterator;
  165.     }spliter;
  166.     void init_from_spliter();
  167. public:
  168.     select_iterator(int size);
  169.     bool inc();
  170.     int get_sub_group_count()const{return spliter.last_index+1;}
  171.     int get_sub_size(int group_id)const{return sub_size[group_id/256-1];}
  172.     int get_group_id(int num)const{return select_array[num];}
  173.     int get_main_id(int group_id)const{return group_id/256-1;}
  174.     int get_sub_id(int group_id)const{return group_id%256;}
  175.     int split_size(int i)const{return spliter.split_array[i];}
  176.     int size()const{return n;}
  177. #ifdef _DEBUG
  178.     void print()const;
  179. #endif
  180. };

  181. select_iterator::select_iterator(int size):spliter(size)
  182. {
  183.     init_from_spliter();
  184. }

  185. void select_iterator::init_from_spliter()
  186. {
  187.     int i,prev,sg,t;
  188.     n=0,m=0;
  189.     prev=-1;
  190.     for(i=0;i<=spliter.last_index;++i)
  191.     {
  192.         if(spliter.split_array[i]!=prev)
  193.         {
  194.             sub_size[m]=spliter.split_array[i];
  195.             m++;
  196.             sg=0;
  197.         }
  198.         else
  199.             sg++;
  200.         for(t=0;t<spliter.split_array[i];t++)
  201.         {
  202.             select_array[n++]=m*256+sg;
  203.         }
  204.         prev=spliter.split_array[i];
  205.     }
  206. }

  207. bool select_iterator::inc()
  208. {
  209.     int i;
  210.     int buf[MAX_NUM];
  211.     bool result;
  212.     do
  213.     {
  214.         result = next_permutation(select_array,select_array+n);///permutate all numbers until
  215.         if(!result)
  216.             break;
  217.         memset(buf,-1,sizeof(buf));
  218.         for(i=0;i<n;++i){//fill result into buf
  219.             int t=get_main_id(select_array[i]);
  220.             int q=get_sub_id(select_array[i]);
  221.             if(buf[t]<0)
  222.                 buf[t]=q;
  223.             else
  224.                 if(buf[t]>q)//invalid, all numbers in same subgroup should be ordered. Maybe we could optimize the code further
  225.                     break;
  226.         }
  227.         if(i==n)
  228.             break;
  229.     }while(true);
  230.     if(!result){///We need increase spliter when all permutation of data are searched
  231.         if(!spliter.inc())
  232.         {//set end.
  233.             init_from_spliter();
  234.             return false;
  235.         }
  236.         else
  237.         {
  238.             init_from_spliter();
  239.         }
  240.     }
  241.     return true;
  242. #if 0
  243.     for(i=n-1;i>0;--i)
  244.     {
  245.         if(select_array[i]>select_array[i-1])
  246.         {
  247.             if((select_array[i]/256)==(select_array[i-1]/256))
  248.             {//if in the same group.
  249.                 int j;
  250.                 // if(sub_size[select_array[i]/256-1]==1)
  251.                 // continue;
  252.                 for(j=i-2;j>=0;--j)
  253.                 {
  254.                     if(select_array[j]==select_array[i-1])
  255.                         break;
  256.                 }
  257.                 if(j>=0)//if found one.
  258.                     break;
  259.             }
  260.             else
  261.                 break;
  262.         }
  263.     }
  264.     if(i==0)//not found
  265.     {
  266.         if(!spliter.inc())
  267.         {//set end.
  268.             init_from_spliter();
  269.             return false;
  270.         }
  271.         else
  272.         {
  273.             init_from_spliter();
  274.         }
  275.     }
  276.     else
  277.     {
  278.         int tmp=select_array[i];
  279.         select_array[i]=select_array[i-1];
  280.         select_array[i-1]=tmp;
  281.         if(i<n-2)
  282.         {
  283.             sort(select_array+i+1,select_array+n);
  284.         }
  285.     }
  286.     return true;
  287. #endif
  288.     return result;
  289. }


  290. /*Expressions are represented by the tree iterator here.
  291. *There're two different kinds of trees according to the topmost level operator.
  292. *  the field get_prod is used to indicate whether the topmost level operators're mulitplication/division or add/sub.
  293. *  For example, expression 4*(-3)/(1+2*5) is an expression whose topmost level operators are {*,/}
  294. *   and it has three children, the first is 4, the second is (-3) and the third is expression 1+2*5
  295. *    and similarly the topmost level operators of 1+2*5 is {+}. It has two children, the first is 1 and the second 2*5, etc
  296. *  In each "tree_iterator" (a node of the tree), a spliter field is used to determine how much children nodes there're
  297. *    and how much operands there're in the (sub-)expression and how much topmost operators there're. And how those operands are partitioned to children.
  298. *  For example, if the expression is 4*(-3)/(1+2*5), there're totoal 5 operands {-3,1,2,4,5} and 2 topmost operators so that operands are partition into 3 group.
  299. *   The first child contains {4}, the second contans {-3}, the third contains {1,2,5}
  300. * Please pay attention that change ordering of children does not change the value as soon as we change the correspondent bits in pattern.
  301. * So the spliter will make sure that all groups are ordered according to number of elements to avoid those unnecessary recomputation
  302. * And the pattern will be increased by 2 instead of 1 when get_prod==0. It means that no '-' will be added to the first child.
  303. *    so that for operands set {a,b} with get_prod==0, we will only enumerate expression a+b and a-b. (b-a will not be enumerated)
  304. * And for the final result, as soon as we could reach the result -x<0, it means we could also reach x by exchange ordering of some operands.
  305. */
  306. class tree_iterator{
  307.     select_iterator spliter;
  308.     tree_iterator *next_sibling; ///pointer to the next sibling (the node whose has same parent node with this_node), NULL if it is the last child of the parent
  309.     tree_iterator *first_child;  ///pointer to the first child of the node, NULL if it is leaf. So we could use first_child->next_sibling to get the second child node
  310.     tree_iterator *current_child_iterator;///A temporary pointer used when visiting the tree. (Maybe we should not define it here)
  311.     int get_prod;   ///when get_prod!=0, all topmost operators are either * or /; otherwise all topmost operators are either + or -.
  312.     number valued;  ///field used to save the value of the expression.
  313.     int data[MAX_NUM]; ///field to save all operands used by all leaf nodes. so data[]={2,-3,1,2,5} for expression 2*(-3)/(1+2*5)
  314.     int pattern;      ///Used to determine whether an operator is * or / when get_prod!=0 and wheter an operator is + or - when get_prod==0.
  315.                         ///pattern will be treated as a bit vector. 1 for * or + and 0 for / or -.  refer to function set_values();
  316.     void build_tree();   ///Function to build the tree for an expression
  317.     void clear_child();  ///Function to remove all children(to clear the node)
  318.     void set_values();  ///set the value of the expression according to the value of children
  319.     int cached;
  320.     int finished_cached;
  321.     set<number> caches;
  322.     set<number>::iterator caches_it;
  323.     string prod_expression()const;  ///get the expression in string format when get_prod!=0
  324.     string sum_expression()const;   ///get the expression in string format when get_prod==0
  325.     bool no_cache_inc();   ///enumerate next expression
  326.     void no_cache_build_tree(); ///entry function to build the tree for first expression
  327. public:
  328.     bool inc();
  329.     tree_iterator(int n,int d[],int prod);
  330.     int size()const{return spliter.get_sub_group_count();}
  331.     ~tree_iterator(){clear_child();}
  332.     const number& get_value()const{return valued;}
  333.     string get_pattern()const;
  334.     bool debug_sum(){return true;}
  335.     bool debug_prod(){return false;}
  336.     string expression()const{if(get_prod)return prod_expression();else return
  337.         sum_expression();}
  338. };

  339. string tree_iterator::prod_expression()const
  340. {
  341.     if(first_child==NULL)
  342.     {
  343.         char buf[10];
  344.         sprintf(buf,"%d",valued.get_integer());
  345.         return string(buf);
  346.     }
  347.     else
  348.     {
  349.         int i;
  350.         string s;
  351.         bool first=true;
  352.         tree_iterator *child=first_child;
  353.         for(i=0;i<spliter.get_sub_group_count();++i)
  354.         {
  355.             if(pattern&(1<<i)){
  356.                 if(!first)
  357.                     s+='*';
  358.                 first=false;
  359.                 s+=child->sum_expression();
  360.             }
  361.             child=child->next_sibling;
  362.         }
  363.         child=first_child;
  364.         for(i=0;i<spliter.get_sub_group_count();++i)
  365.         {
  366.             if(!(pattern&(1<<i))){
  367.                 s+='/';
  368.                 s+=child->sum_expression();
  369.             }
  370.             child=child->next_sibling;
  371.         }
  372.         return s;
  373.     }
  374. }

  375. string tree_iterator::get_pattern()const
  376. {
  377.     if(first_child==NULL)
  378.     {
  379.         char buf[10];
  380.         sprintf(buf,"%d",valued.get_integer());
  381.         return string(buf);
  382.     }
  383.     else
  384.     {
  385.         int i;
  386.         string s;
  387.         tree_iterator *child=first_child;
  388.         s+='[';
  389.         for(i=0;i<spliter.get_sub_group_count();++i)
  390.         {
  391.             s+=child->get_pattern();
  392.             child=child->next_sibling;
  393.         }
  394.         s+=']';
  395.         return s;
  396.     }
  397. }

  398. string tree_iterator::sum_expression()const
  399. {
  400.     if(first_child==NULL)
  401.     {
  402.         char buf[10];
  403.         sprintf(buf,"%d",valued.get_integer());
  404.         return string(buf);
  405.     }
  406.     else
  407.     {
  408.         int i;
  409.         string s;
  410.         bool first=true;
  411.         tree_iterator *child=first_child;
  412.         s+='(';
  413.         for(i=0;i<spliter.get_sub_group_count();++i)
  414.         {
  415.             if(pattern&(1<<i)){
  416.                 if(!first)
  417.                     s+='+';
  418.                 first=false;
  419.                 s+=child->prod_expression();
  420.             }
  421.             child=child->next_sibling;
  422.         }
  423.         child=first_child;
  424.         for(i=0;i<spliter.get_sub_group_count();++i)
  425.         {
  426.             if(!(pattern&(1<<i))){
  427.                 s+='-';
  428.                 s+=child->prod_expression();
  429.             }
  430.             child=child->next_sibling;
  431.         }
  432.         s+=')';
  433.         return s;
  434.     }
  435. }

  436. bool tree_iterator::no_cache_inc()
  437. {
  438.     if(get_prod)
  439.         pattern++;
  440.     else
  441.         pattern+=2;
  442.     if(pattern<(1<<size()))
  443.     {
  444.         set_values();
  445.     }
  446.     else
  447.     {
  448.         while(current_child_iterator&&!current_child_iterator->inc())
  449.             current_child_iterator=current_child_iterator->next_sibling;
  450.         if(current_child_iterator)
  451.         {
  452.             current_child_iterator=first_child;
  453.             pattern=1;
  454.             set_values();
  455.         }
  456.         else
  457.         {
  458.             if(spliter.inc())
  459.             {
  460.                 no_cache_build_tree();
  461.             }
  462.             else
  463.             {
  464.                 no_cache_build_tree();
  465.                 return false;
  466.             }
  467.         }
  468.     }
  469.     return true;
  470. }

  471. bool tree_iterator::inc()
  472. {
  473.     if(finished_cached)
  474.     {
  475.         ++caches_it;
  476.         if(caches_it==caches.end())
  477.         {
  478.             caches_it=caches.begin();
  479.             valued=*caches_it;
  480.             return false;
  481.         }
  482.         valued=*caches_it;
  483.         return true;
  484.     }
  485.     else
  486.     {
  487.         return no_cache_inc();
  488.     }
  489. }

  490. void tree_iterator::clear_child()
  491. {
  492.     tree_iterator *child=first_child;
  493.     while(child!=NULL)
  494.     {
  495.         first_child=child->next_sibling;
  496.         delete child;
  497.         child=first_child;
  498.     }
  499.     first_child=NULL;
  500. }

  501. tree_iterator::tree_iterator(int n,int d[MAX_NUM],int prod):spliter(n)
  502. {
  503.     next_sibling=NULL;
  504.     first_child=NULL;
  505.     get_prod=prod;
  506.     cached=(n<=CACHE_LIMIT);
  507.     finished_cached=0;
  508.     current_child_iterator=NULL;
  509.     memcpy(data,d,sizeof(data));
  510.     build_tree();
  511. }

  512. void tree_iterator::set_values()
  513. {
  514.     int i;
  515.     if(get_prod)
  516.         valued=1;
  517.     else
  518.         valued=0;
  519.     tree_iterator *child=first_child;
  520.     for(i=0;i<spliter.get_sub_group_count();++i)
  521.     {
  522.         if(pattern&(1<<i))
  523.         {
  524.             if(get_prod)
  525.                 valued*=child->valued;
  526.             else
  527.                 valued+=child->valued;
  528.         }
  529.         else
  530.         {
  531.             if(get_prod)
  532.                 valued/=child->valued;
  533.             else
  534.                 valued-=child->valued;
  535.         }
  536.         child=child->next_sibling;
  537.     }
  538.     if(get_prod&&valued==number(0)||!valued.is_valid())
  539.     {
  540.         pattern=((1<<size())-1);
  541.     }
  542. }

  543. void tree_iterator::no_cache_build_tree()
  544. {
  545.     int i;
  546.     int catche[MAX_NUM];
  547.     int prev=-1;
  548.     int m=0,sg,j,t;
  549.     clear_child();
  550.     if(size()==1)
  551.     {
  552.         valued=data[0];
  553.         pattern=1;
  554.         return;
  555.     }
  556.     for(i=0;i<spliter.get_sub_group_count();++i)
  557.     {
  558.         if(spliter.split_size(i)!=prev)
  559.         {
  560.             m++;
  561.             sg=0;
  562.         }
  563.         else
  564.             sg++;
  565.         t=m*256+sg;
  566.         int k;
  567.         for(k=0,j=0;j<spliter.size();++j)
  568.         {
  569.             if(spliter.get_group_id(j)==t){
  570.                 catche[k++]=data[j];
  571.             }
  572.         }
  573.         tree_iterator *child=new tree_iterator(k,catche,!get_prod);
  574.         child->next_sibling=first_child;
  575.         first_child=child;
  576.         current_child_iterator=child;
  577.         prev=spliter.split_size(i);
  578.     }
  579.     pattern=1;
  580.     set_values();
  581. }

  582. void tree_iterator::build_tree()
  583. {
  584.     if(!cached){
  585.         no_cache_build_tree();
  586.     }else{
  587.         no_cache_build_tree();
  588.         do
  589.         {
  590.             if(valued.is_valid())
  591.                 caches.insert(valued);
  592.         }while(no_cache_inc());
  593.         finished_cached=1;
  594.         caches_it=caches.begin();
  595.         valued=*caches_it;
  596.     }
  597. }

  598. #define MAX_BUF_SIZE 10886400
  599. int main()
  600. {
  601.     vector<bool> visited(MAX_BUF_SIZE,false);
  602.     int a[10]={1,2,3,4,5,6,7,8,9,10};
  603.     longlong count=0;
  604.     int cur_scan=1;
  605.     time_t starttime=time(NULL);
  606.     {
  607.         tree_iterator it(SEARCH_VALUE,a,1);
  608.         do
  609.         {
  610.             if(it.get_value().is_integer()){
  611.                 int value=it.get_value().get_integer();
  612.                 if(value<0)value=-value;
  613. #ifdef DISPLAY_NEW_VISIT
  614.                 if(value<MAX_BUF_SIZE&&!visited[value]){
  615.                     cout<<value<<'='<<it.expression()<<endl;
  616.                 }
  617. #endif
  618.                 visited[value]=true;
  619.                 if(value==cur_scan)
  620.                 {
  621.                     while(cur_scan<MAX_BUF_SIZE&&visited[cur_scan])
  622.                         cur_scan++;
  623.                     cerr<<"Searching for "<<cur_scan<<" now"<<endl;
  624.                     cerr<<'\t'<<"Time cost "<<time(NULL)-starttime;
  625.                     cerr<<','<<"searched expressions:"<<count+1<<endl;
  626.                 }
  627.             }
  628.             count++;
  629.         }while(it.inc());
  630.     }
  631.     {
  632.         tree_iterator it(SEARCH_VALUE,a,0);
  633.         do
  634.         {
  635.             if(it.get_value().is_integer()){
  636.                 int value=it.get_value().get_integer();
  637.                 if(value<0)
  638.                     value=-value;
  639. #ifdef DISPLAY_NEW_VISIT
  640.                 if(value<MAX_BUF_SIZE&&!visited[value]){
  641.                     cerr<<value<<'='<<it.expression()<<endl;
  642.                 }
  643. #endif
  644.                 visited[value]=true;
  645.                 if(value==cur_scan)
  646.                 {
  647.                     while(cur_scan<MAX_BUF_SIZE&visited[cur_scan])
  648.                         cur_scan++;
  649.                     cerr<<"Searching for "<<cur_scan<<" now"<<endl;
  650.                     cerr<<'\t'<<"Time cost "<<time(NULL)-starttime;
  651.                     cerr<<','<<"searched expressions:"<<count<<endl;
  652.                 }
  653.             }
  654.             count++;
  655.         }while(it.inc());
  656.     }
  657.     cerr<<"Total expressions searched:"<<count<<endl;
  658.     cerr<<"Total time cost "<<time(NULL)-starttime<<endl;
  659.     cout<<"The first integer not reached is "<<cur_scan<<endl;
  660.     return 0;
  661. }
复制代码
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-8-21 12:45:38 | 显示全部楼层


怪不得啊
这么慢
用纯C描述不可以么?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-8-21 13:27:26 | 显示全部楼层
代码太复杂,用纯C写更加难一些
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-8-21 15:11:15 | 显示全部楼层


但是你代码似乎涉及很多动态变量啊
我的第二方案是模拟一个工作栈
你考虑下
我想我给出的已经实现代码至少说明
实现并不比C++复杂

10886400并不能计算出全部的11
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-8-21 15:41:23 | 显示全部楼层
那个缓冲区大小无所谓,只要打过最终要查找的数据就可以了。它只是用来记录是否某个整数已经有表达式可以表达,那个纯粹是给调试信息用的。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-8-21 15:45:42 | 显示全部楼层
我的实现主要是要避免产生等价的表达式,但是每个表达式都要从头开始计算。当然应该还可以做一些优化,但是从复杂度看,不会有本质的改善。而如果将宏CACHE_LIMIT定义成非零的值。那么那些操作数数目不超过CACHE_LIMIT的子表达式的结果会被缓存起来(结果重复的会被合并),从而表达式其他部分发生更新时这个部分不需要重复计算。这个方法可以用来提高一些计算速度。但是CACHE_LIMIT不能太大,不然内存消耗受不了。当然程序采用分数运算也降低了速度,但是保证了正确性
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-8-21 16:41:19 | 显示全部楼层
是否可以这么做
假设对每个数字
如果有1-n中的部分数字集合N1可四则计算出该数字
称为可N1表示

假设全部集合是N
是否能用部分结果逐步迭代
凑合成最终结果?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-8-21 20:09:20 | 显示全部楼层
明白基于栈的程序错误在哪里了
应该还要把表达式的位置信息压栈
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-9-11 09:49:51 | 显示全部楼层
关于这个问题无心人有进一步结果吗?
比如我们只查看所有计算中间结果都是整数的情况,最小无法达到的整数有哪些呢?
我们可以考虑设计一个算法,该算法只查看那些计算中间结果都是在某个较大范围的整数的情况,通过动态规划的方法计算出所有这些整数,那么我们所求的这个问题的解肯定在计算结果的补集中;这个可以作为第一步结果.
而第二步,我们需要对于补集中的数字x,验证是否的确没有表达式可以达到x
我们可以选择一个较大的素数p>x,然后计算所有表达式关于关于p的模,其中a/b通过a乘上b关于p的素论倒数来表示.我们知道,如果一个表达式最终结果为x,那么关于模p运算的最终结果也应该是p(如果可以运算). 我们可以通过动态规划的方法找出所有模p为x的表达式(应该不会太多),然后一一验证这些表达式结果是否为x.
上面方法唯一问题在于表达式计算过程中可能会出现a/0(mod p)形式的子表达式,而这些表达式中,分母可能只是p的倍数,而上面的运算方法对这个无效.所以我们需要记录所有那些出现了子表达式模p为0而且作为除数情况的表达式(其数目可能不会太少,需要一种比较有效的描述方式),然后我们首先需要验证这些子表达式是否是0,如果是0,我们不需要特殊考虑;不然,我们还需要继续穷举这些表达式.如果这样的表达式还很多,一种可行的方法是取另外一个素数q,再次对这些表达式进行筛选.
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

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

GMT+8, 2021-9-20 10:14 , Processed in 0.061504 second(s), 14 queries .

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

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