软件大赛题目--第二个--求21位花骨朵数

winston

题目要求如下： （编程题）花朵数
一个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分钟内运行完毕。

【程序运行参考结果】
128468643043731391252
449177399146038697307

3. package com.bird.software;
5. import java.math.BigInteger;
6. import java.util.Arrays;
7. /**
8. * 如题，求解21位花朵数的解法，要求在3分钟之内计算完成花朵数： N位整数，它等于各个位的数字的N次方之和， *
9. * 例如有一个N位数字，a1a2a3a4.....aN = a1^N +a2^N+......aN^N
10. *  
11. * @author Bird
12. */  
13. public class FlowerNum {  
14.     private static int num = 21;  
15.     private static BigInteger[] table = new BigInteger[10];  
16.     private static int[] nums;  
17.     public static void main(String[] args) {  
18.         long time = System.currentTimeMillis();  
19.         for (int i = 0; i < 10; i++)  
20.             table[i] = BigInteger.valueOf(i).pow(num);  //分别获得0-9的21次方的值
21.         nums = new int[num];  
22.         find(nums, 0, 0);  
23.         time = System.currentTimeMillis() - time;  
24.         System.out.println(time / 1000.0 + "s");  
25.     }  
26.     /**
27.      * level表示第几位数，num表示第几位数的数字；
28.      */  
29.     public static void find(int[] nums, int level, int num) {  
30.         nums[level] = num;  
31.         if (level == nums.length - 1) {  
32.             BigInteger big = sum(nums);//当level为20时，表示nums数组下标为20即21位数字满后求和；  
33.             int[] temp = getArray(big);//将得到的21位数和转化为整形数组；并返回；  
34.             if (check(nums, temp))//测试是否是21位，并将数组复制给nums数组；  
35.                 System.out.println(big);//输出big数；  
36.             return;  
37.         }  
38.         for (int i = num; i < 10; i++)//递归；查找21位数字符合条件的数；  
39.             find(nums, level + 1, i);  
40.     }  
41.     /**
42.      * 检测长度，苦符合条件就复制a2到a1；
43.      * @param a1
44.      * @param a2
45.      * @return
46.      */  
47.     public static boolean check(int[] a1, int[] a2) {  
48.         if (a1.length != a2.length)  
49.             return false;  
50.         Arrays.sort(Arrays.copyOf(a1, a1.length));  
51.         Arrays.sort(a2);  
52.         return Arrays.equals(a1, a2);  
53.     }  
54.     /**
55.      * 得到nums数组的数做为table下标的数的和。并返回；
56.      * @param nums
57.      * @return
58.      */  
59.     public static BigInteger sum(int[] nums) {  
60.         BigInteger sum = BigInteger.ZERO;  
61.         for (int i = 0; i < nums.length; i++)  
62.             sum = sum.add(table[nums[i]]);  
63.         return sum;  
64.     }  
65.     /**
66.      * 将BigInteger转化为int[]类型数据；
67.      * @param big
68.      * @return
69.      */  
70.     public static int[] getArray(BigInteger big) {  
71.         String s = String.valueOf(big);  
72.         char[] ch = s.toCharArray();  
73.         int[] res = new int[ch.length];  
74.         for (int i = 0; i < ch.length; i++)  
75.             res[i] = ch[i] - '0';  //只有减去字符0才能转换成对应的int值
76.         return res;  
77.     }  
78. }  

复制代码

运行效果如下

44917739914603869730712846864304373139125231.205s

作者：a352193394 发表于2012-1-13 21:57:10 原文链接