一个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分钟内运行完毕。
#include<stdio.h>
#include <string.h>
#define N 100000//虚拟进制
#define BN 5//exp21的容量需求
int exp21[10][BN]={//0-9的21次方
{00000,00000,00000,00000,00000},
{00000,00000,00000,00000, 1},
{00000,00000,00000, 20,97152},
{00000,00000, 1, 4603,53203},
{00000,00000, 439,80465,11104},
{00000,00000,47683,71582, 3125},
{00000, 21,93695, 6403,77856},
{00000, 558,54586,40832,84007},
{00000, 9223,37203,68547,75808},
{00001, 9418,98913,15123,59209}
};
int cm[10];//0-9被选的次数
int nm[10];//21位数中0-9出现的次数
int sum[BN];//累加和
int pass[1000][10];//已经出现过的
int sum_pass;
int check()//检查sum是否合法
{
if (sum[0]>9&&cm[0]!=21) return 0;
return 1;
}
void Add(int *a,int *b)//大数加法：a+=b
{
int i,carry=0;
for (i=BN-1;i>=0;i--)
{
a[i]=a[i]+b[i]+carry;
carry = 0;
if (a[i]>=N)
{
a[i]-=N;
carry = 1;
}
}
}
void Sub(int *a,int *b)//大数减法：a-=b
{
int i,borrow=0;
for (i=BN-1;i>=0;i--)
{
a[i]=a[i]-b[i]+borrow;
borrow = 0;
if (a[i]<0)
{
a[i]+=N;
borrow = -1;
}
}
}
int IsRight()//判断是否是花朵数
{
int i,j;
memset(nm,0,sizeof(nm));
for (i=0;i<BN;i++)//统计sum中0-9的个数
{
j=sum[i];
while (j)
{
nm[j%10]++;
j/=10;
}
}
for (i=0;i<10;i++)
if (cm[i]!=nm[i])
return 0;
return 1;
}
void save()//将花朵数存储在pass数组中
{
int i;
pass[sum_pass][0]=sum[0];
for (i=1;i<BN;i++)
pass[sum_pass][i]=sum[i];
sum_pass++;
}
void sln(int n,int m)//用若干个m填充n个空
{
int i,j;
if (n==0)
return;
if (m==0)
{
cm[0]+=n;
if(IsRight())
save();
cm[0]-=n;
return;
}
for (i=n;i>=0;i--)//最多用n个，最少用0个
{
cm[m]+=i;
for (j=0;j<i;j++)Add(sum,exp21[m]);//sum加上i个exp21[m]
if (!check())//检查是否溢出
{
cm[m]-=i;
for (j=0;j<i;j++)Sub(sum,exp21[m]);//sum减去i个exp21[m]
continue;
}
if(n==1&&IsRight()) save();
sln(n-i,m-1);//用若干m-1填补剩余的n-i个空
cm[m]-=i;
for (j=0;j<i;j++)Sub(sum,exp21[m]);//sum减去i个exp21[m]
}
}
void print()//输出结果、有点偷懒。。。
{
printf("%d%05d%05d%05d%05d\n",pass[1][0],pass[1][1],pass[1][2],pass[1][3],pass[1][4]);
printf("%d%05d%05d%05d%05d\n",pass[0][0],pass[0][1],pass[0][2],pass[0][3],pass[0][4]);
}
void main()
{
sln(21,9);
print();
}
本文转自ZH奶酪博客园博客，原文链接：http://www.cnblogs.com/CheeseZH/archive/2012/04/06/2434560.html，如需转载请自行联系原作者
