求水仙花数最速求解算法

问题描述：

求水仙花数最速求解算法
一个N位的十进制正整数,如果它的每个位上的数字的N次方的和等于这个数本身,则称其为花朵数.
例如：
当N=3时,153就满足条件,因为 1^3 + 5^3 + 3^3 = 153,这样的数字也被称为水仙花数（其中,“^”表示乘方,5^3表示5的3次方,也就是立方）.
当N=4时,1634满足条件,因为 1^4 + 6^4 + 3^4 + 4^4 = 1634.
当N=5时,92727满足条件.
实际上,对N的每个取值,可能有多个数字满足条件.
程序的任务是：求N=21时,所有满足条件的花朵数.注意：这个整数有21位,它的各个位数字的21次方之和正好等于这个数本身.
如果满足条件的数字不只有一个,请从小到大输出所有符合条件的数字,每个数字占一行.因为这个数字很大,请注意解法时间上的可行性.要求程序在3分钟内运行完毕.
普通算法绝对不可能3分钟内得结果,求快速算法

1个回答分类：数学 2014-11-04

问题解答：

我来补答

/*
128468643043731391252
449177399146038697307*/
#include
#include
#include
#include
/*
128468643043731391252
449177399146038697307*/
//我的程序只用了34秒
//乍一下很难,很容易往那个一位位枚举数字的方向去,但是这样的复杂度很高,尽管加上了一些判断还是于事无补
//我说一下思路吧,先把所有的数字的21次方求出来放在一个数组里保存,然后再去枚举每一个数字有几个,
//总共加起来是二十一位数字,这个枚举的操作次数相对刚才的那个是小多了,
//然后把这些数的21次方加起来,然后再去判断一下,是不是由这些数字组成就行了
const int BIT=100000000;
struct BigNum
{
int dig[6];
int len;
void Clr()
{
memset(dig,0,sizeof(dig));
len=1;
}
void Print()
{
int i;
printf("%d",dig[len-1]);
for(i=len-2;i>=0;i--)
printf("%08d",dig[i]);
puts("");
}
};
BigNum p[10],MAX,MIN;
BigNum sp[10][22];
int take[10]={0};
int LEN=21;
int GetLen(BigNum a)
{
int i;
for(i=5;i>0&&a.dig[i]==0;i--);
return i+1;
}
BigNum CarryUp(BigNum a)
{
int i;
for(i=0;ia.len)a.len=b.len;
for(i=0;i=0;i--)
{
b.dig[0]=b.dig[0]*10+a.dig[i];
}
for(i=15;i>=8;i--)
{
b.dig[1]=b.dig[1]*10+a.dig[i];
}
for(i=23;i>=16;i--)
{
b.dig[2]=b.dig[2]*10+a.dig[i];
}
return b;
}
bool ok(BigNum sum)
{
int aa[10]={0};
int i;
for(i=0;i

展开全文阅读