最小无法表达的正整数

mathe · 发表于 2008-8-21 10:31:40

发现这道题目A060315也已经给到第10项了，和我结果相同。

mathe · 发表于 2008-8-21 10:46:57

这个问题实际上我在02年4月份解决过: http://www.mitbbs.cn/bbsann2/sci ... A/Re:%20yes....1413 现在将那个代码转贴过来

#include <algorithm>
#include <iostream>
#include <vector>
#include <time.h>
#include <string>
#include <set>
#include <stdio.h>
#ifdef _WIN32
typedef __int64 longlong;
#else
typedef long long longlong;
#endif
using namespace std;
#ifdef _DEBUG
#include <assert.h>
#define ASSERT(x) assert(x)
#else
#define ASSERT(x)
#endif
#define MAX_NUM 10
#define SEARCH_VALUE 8
//enlarge CACHE_LIMIT so that some expression will be saved in memory. This
//will speed the program,
//but then we could not print the correct expression by expression() function.
//CACHE_LIMIT should be no more than 8. I found that the speed will drop when
//CACHE_LIMIT is too large
#define CACHE_LIMIT 0
#if CACHE_LIMIT==0
//#define DISPLAY_NEW_VISIT
//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)
//define CACHE_LIMIT to 0 and define DISPLAY_NEW_VISIT could dump out all the first expression to reach any integer number
#endif
class number{
int up;
int down;
public:
number(const number& n):up(n.up),down(n.down){}
number(int n=0):up(n),down(1){}
number& operator+=(const number& n);
number& operator-=(const number& n);
number& operator*=(const number& n);
number& operator/=(const number& n);
bool is_zero()const{return down!=0&&up==0;}
bool is_valid()const{return down!=0;}
bool is_one()const{return down!=0&&up==down;}
bool operator==(const number& n)const{return
is_valid()&&n.is_valid()&&n.down*up==n.up*down;}
bool operator<(const number& n)const;
bool operator>(const number& n)const{return n<*this;}
bool operator<=(const number& n)const{return !(*this>n);}
bool operator!=(const number& n)const{return !(n==*this);}
bool operator>=(const number& n)const{return !(*this<n);}
number operator+(const number& n)const{number m(*this);return m+=n;}
number operator-(const number& n)const{number m(*this);return m-=n;}
number operator*(const number& n)const{number m(*this);return m*=n;}
number operator/(const number& n)const{number m(*this);return m/=n;}
bool is_integer()const{return down!=0&&up%down==0;}
int get_integer()const{if(is_integer())return up/down;else return -1;}
number& operator=(int n){up=n;down=1;return *this;}
int get_up()const{return up;}
int get_down()const{return down;}
};
number& number::operator +=(const number& n)
{
up=up*n.down+down*n.up;
down*=n.down;
return *this;
}
number& number::operator -=(const number& n)
{
up=up*n.down-down*n.up;
if(up<0)up=-up;
down*=n.down;
return *this;
}
number& number::operator *=(const number& n)
{
up*=n.up;
down*=n.down;
return *this;
}
number& number::operator /=(const number& n)
{
down*=n.up;
up*=n.down;
return *this;
}
bool number::operator <(const number &n)const
{
return up*n.down<n.up*down;
}
/*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]
* and sub-iterator split_iterator spliter is used to enumerator numbers of objects in each groups
*/
class select_iterator{
int n;//total n element;
int m;//max group id; That's group 1<<8,2<<8,...,m<<8; m should be no less than 2.
//The select_iterator is used to split n elements into groups.
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)
int sub_size[MAX_NUM]; ///sub_size[x] provides the number of elements of all groups whose group id no more than x
class split_iterator{///iterator to partition 'size' same objects into several groups (so only number of objects in each group is considered)
int split_array[MAX_NUM];///number of objects in each group
int last_index;///number of group - '1'
public:
split_iterator(int size)
{
ASSERT(size<=MAX_NUM);
if(size==1)
{
last_index=0;
split_array[0]=1;
}
else
{///Usually, we need partition data into at least two groups.
last_index=1;
split_array[0]=size-1;
split_array[1]=1;
}
}
bool inc()///Move to the next partition
{
int i;
ASSERT(last_index<MAX_NUM);
for(i=last_index;i>=0;--i)
{
if(split_array[i]>=2)
break;
}
if(i==-1)
{
int size=0;
for(i=0;i<=last_index;++i)
size+=split_array[i];
if(size==1)
{
last_index=0;
split_array[0]=1;
}
else
{
last_index=1;
split_array[0]=size-1;
split_array[1]=1;
}
return false;//end of search.
}
else
{
int total;
int last;
last=--split_array[i];
total=last_index-i+1;
while(total>=last){
split_array[++i]=last;
total-=last;
}
if(total>0){
split_array[++i]=total;
}
last_index=i;
}
return true;
}
friend class select_iterator;
}spliter;
void init_from_spliter();
public:
select_iterator(int size);
bool inc();
int get_sub_group_count()const{return spliter.last_index+1;}
int get_sub_size(int group_id)const{return sub_size[group_id/256-1];}
int get_group_id(int num)const{return select_array[num];}
int get_main_id(int group_id)const{return group_id/256-1;}
int get_sub_id(int group_id)const{return group_id%256;}
int split_size(int i)const{return spliter.split_array[i];}
int size()const{return n;}
#ifdef _DEBUG
void print()const;
#endif
};
select_iterator::select_iterator(int size):spliter(size)
{
init_from_spliter();
}
void select_iterator::init_from_spliter()
{
int i,prev,sg,t;
n=0,m=0;
prev=-1;
for(i=0;i<=spliter.last_index;++i)
{
if(spliter.split_array[i]!=prev)
{
sub_size[m]=spliter.split_array[i];
m++;
sg=0;
}
else
sg++;
for(t=0;t<spliter.split_array[i];t++)
{
select_array[n++]=m*256+sg;
}
prev=spliter.split_array[i];
}
}
bool select_iterator::inc()
{
int i;
int buf[MAX_NUM];
bool result;
do
{
result = next_permutation(select_array,select_array+n);///permutate all numbers until
if(!result)
break;
memset(buf,-1,sizeof(buf));
for(i=0;i<n;++i){//fill result into buf
int t=get_main_id(select_array[i]);
int q=get_sub_id(select_array[i]);
if(buf[t]<0)
buf[t]=q;
else
if(buf[t]>q)//invalid, all numbers in same subgroup should be ordered. Maybe we could optimize the code further
break;
}
if(i==n)
break;
}while(true);
if(!result){///We need increase spliter when all permutation of data are searched
if(!spliter.inc())
{//set end.
init_from_spliter();
return false;
}
else
{
init_from_spliter();
}
}
return true;
#if 0
for(i=n-1;i>0;--i)
{
if(select_array[i]>select_array[i-1])
{
if((select_array[i]/256)==(select_array[i-1]/256))
{//if in the same group.
int j;
// if(sub_size[select_array[i]/256-1]==1)
// continue;
for(j=i-2;j>=0;--j)
{
if(select_array[j]==select_array[i-1])
break;
}
if(j>=0)//if found one.
break;
}
else
break;
}
}
if(i==0)//not found
{
if(!spliter.inc())
{//set end.
init_from_spliter();
return false;
}
else
{
init_from_spliter();
}
}
else
{
int tmp=select_array[i];
select_array[i]=select_array[i-1];
select_array[i-1]=tmp;
if(i<n-2)
{
sort(select_array+i+1,select_array+n);
}
}
return true;
#endif
return result;
}
/*Expressions are represented by the tree iterator here.
*There're two different kinds of trees according to the topmost level operator.
* the field get_prod is used to indicate whether the topmost level operators're mulitplication/division or add/sub.
* For example, expression 4*(-3)/(1+2*5) is an expression whose topmost level operators are {*,/}
* and it has three children, the first is 4, the second is (-3) and the third is expression 1+2*5
* 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
* In each "tree_iterator" (a node of the tree), a spliter field is used to determine how much children nodes there're
* 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.
* 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.
* The first child contains {4}, the second contans {-3}, the third contains {1,2,5}
* Please pay attention that change ordering of children does not change the value as soon as we change the correspondent bits in pattern.
* So the spliter will make sure that all groups are ordered according to number of elements to avoid those unnecessary recomputation
* 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.
* 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)
* 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.
*/
class tree_iterator{
select_iterator spliter;
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
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
tree_iterator *current_child_iterator;///A temporary pointer used when visiting the tree. (Maybe we should not define it here)
int get_prod; ///when get_prod!=0, all topmost operators are either * or /; otherwise all topmost operators are either + or -.
number valued; ///field used to save the value of the expression.
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)
int pattern; ///Used to determine whether an operator is * or / when get_prod!=0 and wheter an operator is + or - when get_prod==0.
///pattern will be treated as a bit vector. 1 for * or + and 0 for / or -. refer to function set_values();
void build_tree(); ///Function to build the tree for an expression
void clear_child(); ///Function to remove all children(to clear the node)
void set_values(); ///set the value of the expression according to the value of children
int cached;
int finished_cached;
set<number> caches;
set<number>::iterator caches_it;
string prod_expression()const; ///get the expression in string format when get_prod!=0
string sum_expression()const; ///get the expression in string format when get_prod==0
bool no_cache_inc(); ///enumerate next expression
void no_cache_build_tree(); ///entry function to build the tree for first expression
public:
bool inc();
tree_iterator(int n,int d[],int prod);
int size()const{return spliter.get_sub_group_count();}
~tree_iterator(){clear_child();}
const number& get_value()const{return valued;}
string get_pattern()const;
bool debug_sum(){return true;}
bool debug_prod(){return false;}
string expression()const{if(get_prod)return prod_expression();else return
sum_expression();}
};
string tree_iterator::prod_expression()const
{
if(first_child==NULL)
{
char buf[10];
sprintf(buf,"%d",valued.get_integer());
return string(buf);
}
else
{
int i;
string s;
bool first=true;
tree_iterator *child=first_child;
for(i=0;i<spliter.get_sub_group_count();++i)
{
if(pattern&(1<<i)){
if(!first)
s+='*';
first=false;
s+=child->sum_expression();
}
child=child->next_sibling;
}
child=first_child;
for(i=0;i<spliter.get_sub_group_count();++i)
{
if(!(pattern&(1<<i))){
s+='/';
s+=child->sum_expression();
}
child=child->next_sibling;
}
return s;
}
}
string tree_iterator::get_pattern()const
{
if(first_child==NULL)
{
char buf[10];
sprintf(buf,"%d",valued.get_integer());
return string(buf);
}
else
{
int i;
string s;
tree_iterator *child=first_child;
s+='[';
for(i=0;i<spliter.get_sub_group_count();++i)
{
s+=child->get_pattern();
child=child->next_sibling;
}
s+=']';
return s;
}
}
string tree_iterator::sum_expression()const
{
if(first_child==NULL)
{
char buf[10];
sprintf(buf,"%d",valued.get_integer());
return string(buf);
}
else
{
int i;
string s;
bool first=true;
tree_iterator *child=first_child;
s+='(';
for(i=0;i<spliter.get_sub_group_count();++i)
{
if(pattern&(1<<i)){
if(!first)
s+='+';
first=false;
s+=child->prod_expression();
}
child=child->next_sibling;
}
child=first_child;
for(i=0;i<spliter.get_sub_group_count();++i)
{
if(!(pattern&(1<<i))){
s+='-';
s+=child->prod_expression();
}
child=child->next_sibling;
}
s+=')';
return s;
}
}
bool tree_iterator::no_cache_inc()
{
if(get_prod)
pattern++;
else
pattern+=2;
if(pattern<(1<<size()))
{
set_values();
}
else
{
while(current_child_iterator&&!current_child_iterator->inc())
current_child_iterator=current_child_iterator->next_sibling;
if(current_child_iterator)
{
current_child_iterator=first_child;
pattern=1;
set_values();
}
else
{
if(spliter.inc())
{
no_cache_build_tree();
}
else
{
no_cache_build_tree();
return false;
}
}
}
return true;
}
bool tree_iterator::inc()
{
if(finished_cached)
{
++caches_it;
if(caches_it==caches.end())
{
caches_it=caches.begin();
valued=*caches_it;
return false;
}
valued=*caches_it;
return true;
}
else
{
return no_cache_inc();
}
}
void tree_iterator::clear_child()
{
tree_iterator *child=first_child;
while(child!=NULL)
{
first_child=child->next_sibling;
delete child;
child=first_child;
}
first_child=NULL;
}
tree_iterator::tree_iterator(int n,int d[MAX_NUM],int prod):spliter(n)
{
next_sibling=NULL;
first_child=NULL;
get_prod=prod;
cached=(n<=CACHE_LIMIT);
finished_cached=0;
current_child_iterator=NULL;
memcpy(data,d,sizeof(data));
build_tree();
}
void tree_iterator::set_values()
{
int i;
if(get_prod)
valued=1;
else
valued=0;
tree_iterator *child=first_child;
for(i=0;i<spliter.get_sub_group_count();++i)
{
if(pattern&(1<<i))
{
if(get_prod)
valued*=child->valued;
else
valued+=child->valued;
}
else
{
if(get_prod)
valued/=child->valued;
else
valued-=child->valued;
}
child=child->next_sibling;
}
if(get_prod&&valued==number(0)||!valued.is_valid())
{
pattern=((1<<size())-1);
}
}
void tree_iterator::no_cache_build_tree()
{
int i;
int catche[MAX_NUM];
int prev=-1;
int m=0,sg,j,t;
clear_child();
if(size()==1)
{
valued=data[0];
pattern=1;
return;
}
for(i=0;i<spliter.get_sub_group_count();++i)
{
if(spliter.split_size(i)!=prev)
{
m++;
sg=0;
}
else
sg++;
t=m*256+sg;
int k;
for(k=0,j=0;j<spliter.size();++j)
{
if(spliter.get_group_id(j)==t){
catche[k++]=data[j];
}
}
tree_iterator *child=new tree_iterator(k,catche,!get_prod);
child->next_sibling=first_child;
first_child=child;
current_child_iterator=child;
prev=spliter.split_size(i);
}
pattern=1;
set_values();
}
void tree_iterator::build_tree()
{
if(!cached){
no_cache_build_tree();
}else{
no_cache_build_tree();
do
{
if(valued.is_valid())
caches.insert(valued);
}while(no_cache_inc());
finished_cached=1;
caches_it=caches.begin();
valued=*caches_it;
}
}
#define MAX_BUF_SIZE 10886400
int main()
{
vector<bool> visited(MAX_BUF_SIZE,false);
int a[10]={1,2,3,4,5,6,7,8,9,10};
longlong count=0;
int cur_scan=1;
time_t starttime=time(NULL);
{
tree_iterator it(SEARCH_VALUE,a,1);
do
{
if(it.get_value().is_integer()){
int value=it.get_value().get_integer();
if(value<0)value=-value;
#ifdef DISPLAY_NEW_VISIT
if(value<MAX_BUF_SIZE&&!visited[value]){
cout<<value<<'='<<it.expression()<<endl;
}
#endif
visited[value]=true;
if(value==cur_scan)
{
while(cur_scan<MAX_BUF_SIZE&&visited[cur_scan])
cur_scan++;
cerr<<"Searching for "<<cur_scan<<" now"<<endl;
cerr<<'\t'<<"Time cost "<<time(NULL)-starttime;
cerr<<','<<"searched expressions:"<<count+1<<endl;
}
}
count++;
}while(it.inc());
}
{
tree_iterator it(SEARCH_VALUE,a,0);
do
{
if(it.get_value().is_integer()){
int value=it.get_value().get_integer();
if(value<0)
value=-value;
#ifdef DISPLAY_NEW_VISIT
if(value<MAX_BUF_SIZE&&!visited[value]){
cerr<<value<<'='<<it.expression()<<endl;
}
#endif
visited[value]=true;
if(value==cur_scan)
{
while(cur_scan<MAX_BUF_SIZE&visited[cur_scan])
cur_scan++;
cerr<<"Searching for "<<cur_scan<<" now"<<endl;
cerr<<'\t'<<"Time cost "<<time(NULL)-starttime;
cerr<<','<<"searched expressions:"<<count<<endl;
}
}
count++;
}while(it.inc());
}
cerr<<"Total expressions searched:"<<count<<endl;
cerr<<"Total time cost "<<time(NULL)-starttime<<endl;
cout<<"The first integer not reached is "<<cur_scan<<endl;
return 0;
}

复制代码

无心人 · 发表于 2008-8-21 12:45:38

怪不得啊这么慢用纯C描述不可以么？

mathe · 发表于 2008-8-21 13:27:26

代码太复杂，用纯C写更加难一些

无心人 · 发表于 2008-8-21 15:11:15

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

mathe · 发表于 2008-8-21 15:41:23

那个缓冲区大小无所谓，只要打过最终要查找的数据就可以了。它只是用来记录是否某个整数已经有表达式可以表达，那个纯粹是给调试信息用的。

mathe · 发表于 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

明白基于栈的程序错误在哪里了应该还要把表达式的位置信息压栈

mathe · 发表于 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,再次对这些表达式进行筛选.

账号		自动登录	找回密码
密码			欢迎注册

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