回归数
设k位数n的十进制形式为：bar{d_{1}d_{2}...d_{k}}。若n满足：
bar{d_{1}d_{2}...d_{k}}=\sum_{i=1}^{k}{d_{i}^k}
则称n为回归数。
比如，153就是一个回归数：153=1^{3}+5^{3}+3^{3}。
最大的回归数有39位，40位以上（含40位）就不存在回归数了。
请写一个代码求出所有回归数，看谁的用时最少。
[所有回归数是已知的，我只是想看看是否有很好的方法来求出这些数] :lol
似乎是我提出问题的子集吧？？ 我猜测最小时间是1分钟内 环比不动点麻烦得多。
但在1分钟内还是蛮有挑战性的。 1分钟内?太夸张了吧.我倒是很希望看到这样的算法. 我算17的环是10秒 我现在的算法求20位以下的回归数大概要9秒,求出所有的回归数要1个小时. 抱歉，我估计的确实有问题
10分钟都不可能算出来
程序存在问题
修改后再说 应该可以先进行下数学处理吧？
比如有那些数是不可能的。 发一下代码:#include <cstdlib>
#include <iostream>
#include <windows.h>
#include <cmath>
#include "gmp.h"
using namespace std;
const intL=40;
mpz_t Hash;
mpz_t dif;
mpz_t POW10;
char str;
void Init( ){
unsigned i, j;
for( i=0; i<10; ++i ){
for( j=0; j<L; ++j )
mpz_init( Hash );
}
mpz_set_ui( Hash, 0 );
mpz_init_set_ui( POW10, 1 );
for( i=1; i<10; ++i )
mpz_set_ui( Hash, 1 );
for( j=1; j<L; ++j ){
mpz_init( POW10 );
mpz_mul_ui( POW10, POW10, 10 );
}
for( i=0; i<10; ++i ){
for( j=1; j<L; ++j ){
mpz_mul_ui( Hash, Hash, i );
}
}
for( int k=0; k<L; ++k ){
for( i=0; i<10; ++i ){
for( j=0; j<10; ++j ){
mpz_init( dif );
mpz_sub( dif, Hash, Hash );
}
}
}
}
voidClean( ){
unsigned i, j;
for( i=0; i<10; ++i )
for( j=0; j<L; ++j ){
mpz_clear( Hash );
}
for( j=0; j<L; ++j )
mpz_clear( POW10 );
for( int k=0; k<L; ++k ){
for( i=0; i<10; ++i ){
for( j=0; j<10; ++j ){
mpz_clear( dif );
}
}
}
}
bool check( mpz_t &n, int *c ){
int i, d={0};
mpz_get_str( str, 10, n );
for( i=0; str!='\0'; ++i ){
d-'0']++;
if( d-'0']>c-'0'] ) return false;
}
return true;
}
void combination( unsigned n, unsigned m ){
int*c=new int, j, *num=new int;
intdig={0};
dig=m;
for( j=1; j<=m; ++j )c=j-1, num=c-j+1;
c=n;
mpz_t number;
mpz_init_set_ui( number, 0 );
R2:
if( mpz_cmp( number, POW10 )>0 && mpz_cmp( number, POW10 )<0 && check( number, dig ) ){
mpz_out_str( stdout, 10, number );
printf("\n");
}
if( m&1 )
if( c+1<c ){
--dig];
mpz_add( number, number, dif+1]] );
++c, ++num;
++dig];
goto R2;
}
else{
j=2;goto R4;
}
else
if( c>0 ){
--dig];
mpz_sub( number, number, dif]-1] );
--c, --num;
++dig];
goto R2;
}
else{
j=2;goto R5;
};
R4: if( c>=j ){
if( j<=m ){
--dig];
mpz_sub( number, number, dif]-j+1] );
}
if( j-1<=m ){
--dig];
mpz_sub( number, number, dif] );
}
c=c, num=c-j+1;c=j-2, num=c-(j-1)+1;
if( j<=m )
++dig];
if( j-1<=m )
++dig];
goto R2;
}
else
++j;
R5: if( c+1<c ){
if( j<=m ){
--dig];
mpz_sub( number, number, dif]+1-j+1] );
}
if( j-1<=m ){
--dig];
mpz_sub( number, number, dif]-j+2] );
}
c=c, num=c-(j-1)+1;c=c+1, num=c-j+1;
if( j<=m )
++dig];
if( j-1<=m )
++dig];
goto R2;
}
else{
++j;
if( j<=m ) goto R4;
}
delete []c;
delete []num;
mpz_clear( number );
}
int main(int argc, char *argv[])
{
int time=GetTickCount();
Init();
for( unsigned i=3; i<L; ++i ){
cout<<i<<" digits search start!\n";
combination( i+9, i );
}
Clean( );
cout<<"time : "<<GetTickCount()-time<<" ms\n";
cout<<"press any key to continue...\n";
cin.get();
return EXIT_SUCCESS;
}