21位花朵数 C语言(执行时间小于16s)

it2022-05-20  48

一个N位的十进制正整数,如果它的每个位上的数字的N次方的和等于这个数本身,则称其为花朵数。

例如:

N=3时,153就满足条件,因为 1^3 + 5^3 + 3^3 = 153,这样的数字也被称为水仙花数(其中,“^”表示乘方,5^3表示53次方,也就是立方)。

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("%ddddd\n",pass[1][0],pass[1][1],pass[1][2],pass[1][3],pass[1][4]); printf("%ddddd\n",pass[0][0],pass[0][1],pass[0][2],pass[0][3],pass[0][4]);}void main(){ sln(21,9); print();}

 

转载于:https://www.cnblogs.com/CheeseZH/archive/2012/04/06/2434560.html


最新回复(0)