最小无法表达的正整数

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

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

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

浏览过的版块