《水仙花数的研究与分析.pdf》由会员分享，可在线阅读，更多相关《水仙花数的研究与分析.pdf（7页珍藏版）》请在三一文库上搜索。
1、- 1 - 水仙花数的研究与分析水仙花数的研究与分析 水仙花苏的定义：水仙花苏的定义： 一个 N 位的十进制正整数，如果它的每个位上的数字的 N 次方的和等于这个数本身，则称其 为花朵数。 举例：举例： 当 N=3 时，153 就满足条件，因为 13 + 53 + 33 = 153，这样的数字也被称为水仙花数（其 中，“”表示乘方，53 表示 5 的 3 次方，也就是立方）。 当 N=4 时，1634 满足条件，因为 14 + 64 + 34 + 44 = 1634。 当 N=5 时，92727 满足条件。 实际上，对 N 的每个取值，可能有多个数字满足条件。 提出问题，设计程序：提出问题，设
2、计程序： 程序的任务是：求 N=21 时，所有满足条件的花朵数。注意：这个整数有 21 位，它的各个位 数字的 21 次方之和正好等于这个数本身。 如果满足条件的数字不只有一个，请从小到大输出所有符合条件的数字，每个数字占一行。因 为这个数字很大，请注意解法时间上的可行性。要求程序在 3 分钟内运行完毕。 算法分析：算法分析： 假设需要输出 n 位的水仙花数，首先，计算出 0-9 这十个数的 n 次方，并统计 0-9 中的每一个 数在水仙花数中最多出现的个数 MAX；然后，从 9 到 0 依次遍历其中的 9-0 中每一个数的位数从 MAX 到 0 进行遍历，遍历过程中，计算出它们 n 次方的和
3、，只有所得的数的位数小于等于 n 位时 才进入下一次递归遍历，否则继续当前的数字 num（0-9 中一个）个数的遍历。最后递归到 num=0 或 n 位被分完时，核查计算所得的数中 0-9 的个数，与分配的 0-9 中每个数的个数是否相 等，如果相等，则是水仙花数，否则不是水仙花数。在核查之前，检查所得的数的位数是否小于 n 位，如果小于 n 位，则结束所有遍历（因为遍历是从大到小的，只要出现小于 n 位的数，以后的数 就都是小于 n 位的） 程序设计：程序设计： #include #include /定义所需输出水仙花数的位数（此处位数可以调整） #define LENGTH_OF_NUMB
4、ER 21 /定义大数结构 typedef struct int numLENGTH_OF_NUMBER;/存放大数 int max_index;/标记大数的上面数组中的的最高位的下标 int max_num;/记录该大数在水仙花数中最多可出现多少次 BigInter; /用于标记所求数的位数是否小于所需位数 int flag; /计算并存储 0-9 的水仙花数的位数次方，并记录该数在水仙花数中最多可出现多少次 - 2 - void Init_BigInter(BigInter *numberflag); /寻找所需位数的所有水仙花数 void findnumber(int *num,BigI
5、nter *numberflag,int *sign,int No,int MAXNUM); /实现大数的加法 int Add_BigInter(int *num,BigInter number,int i); /判断所求数是否小于所需水仙花数的位数 int IsLetterNUMS(int *num); /判断所求数是否是水仙花数 int IsRight(int *num,int *sign); void main() int i,j; int numLENGTH_OF_NUMBER+1; int sign10=0;/记录 0-9 在所求数中的的个数，用于判断该数是否是水仙花数 BigInt
6、er numberflag10;/用于记录 0-9 的指定的次方，方便运算 time_t starttime=clock();/记录起始时间 Init_BigInter(numberflag); flag=1; printf(%d 位数中的水仙花数有：n,LENGTH_OF_NUMBER); for(i=numberflag9.max_num;i=0;i-) for(j=0;j=0;j-) printf(%d,numj); printf(n); else MAXINDEX = (MAXNUM=0;i-) for(j=0;jLENGTH_OF_NUMBER+1;j+) tempj = numj;
7、 signNo=i;/记录 No 在水仙花数中出现的次数 if(Add_BigInter(num,numberflagNo,i)/所求数的位数大于所需水仙花数的 位数，则不遍历 for(j=0;jLENGTH_OF_NUMBER+1;j+) numj = tempj; continue; findnumber(num,numberflag,sign,No-1,MAXNUM-i); for(j=0;jLENGTH_OF_NUMBER+1;j+) numj = tempj; signNo=0;/还原递归过程中被改变的值 /判断所求数是否小于所需水仙花数的位数 int IsLetterNUMS(in
8、t *num) if(numLENGTH_OF_NUMBER-1=0) return 1; else return 0; - 4 - /判断所求数是否是水仙花数 int IsRight(int *num,int *sign) int count10=0; int i; for(i=0;iLENGTH_OF_NUMBER;i+) countnumi+; for(i=0;i10;i+) if(counti!=signi) break; if(i=10) return 1; else return 0; /实现大数的加法 int Add_BigInter(int *num,BigInter numb
9、er,int i) int k; if(i!=0) k=0; while(k=number.max_index) numk += number.numk*i; k+; k=0; while(k=number.max_index|numk/10!=0) if(numk/10 = 0) k+; continue; numk+1 += numk/10; numk %= 10; k+; /判断是否大数超过了指定的位数 k=LENGTH_OF_NUMBER; while(kLENGTH_OF_NUMBER+1) if(numk!=0) - 5 - return 1; k+; return 0; /计算并
10、存储 0-9 的水仙花数的位数次方，并记录该数在水仙花数中最多可出现多少次 void Init_BigInter(BigInter *numberflag) int i,j,k; int max; int count=0; int numLENGTH_OF_NUMBER+1; /记录 0-9 的 LENGTH_OF_NUMBER(所需水仙花数的位数)次方 for(i=0;i=9;i+) numberflagi.num0=1; for(j=1;jLENGTH_OF_NUMBER+1;j+) numberflagi.numj=0; for(i=0;i=9;i+) numberflagi.max_i
11、ndex=0; if(i=0|i=1) numberflagi.num0=i; numberflagi.max_num = LENGTH_OF_NUMBER; else for(j=1;j=LENGTH_OF_NUMBER;j+) k=0; while(k=numberflagi.max_index) numberflagi.numk *= i; k+; k=0; while(k numberflagi.max_index) numberflagi.max_index = k; /while count = numberflagi.max_index; /for /else /for /记录
12、2-9 在所需水仙花数中最多可出现的次数 for(i=2;i=9;i+) max = numberflagi.max_index; count = max; for(j=0;jLENGTH_OF_NUMBER+1;j+) numj = 0; for(j=1;j=LENGTH_OF_NUMBER;j+) k=0; while(k=max) numk += numberflagi.numk; k+; k=0; while(kmax) max = k; count = max; if(max LENGTH_OF_NUMBER-1) break; /if /for numberflagi.max_num=j-1; /for - 7 - 信息提示：信息提示： 以上程序也可能存在不足，如果您有更好的方法，请联系我。 QQ：1016929994 姓名：魏南琛 身份：学生