编程大题
花朵数
题目
一个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次方之和正好等于这个数本身。
如果满足条件的数字不只有一个，请从小到大输出所有符合条件的数字，每个数字占一行。因为这个数字很大，请注意解法时间上的可行性。要求程序在1分钟内运行完毕。
参考答案
代码语言：javascript复制import java.math.BigInteger;
public class Test1 {
public static void main(String[] args) {
long start = System.currentTimeMillis();
int[] a = new int[10];
BigInteger[] b = new BigInteger[10];
// 计算0~9 10个数的21次方并且存储在数组b中
b[0] = BigInteger.ZERO;
b[1] = BigInteger.ONE;
for (int i = 2; i <= 9; i ) {
b[i] = BigInteger.valueOf(i).pow(21);
}
// 调用函数
ss(b, a, 0, 21);
long end = System.currentTimeMillis();
double sec = (end - start) / 1000.0;
System.out.println(sec "秒");
}
// index现在进行到数组的第几个元素
// left这个元素出现的次数最多有多少次
// a数组的下标表示0~9这10个数字，a数组元素的值表示下标数字出现的次数
private static void ss(BigInteger[] b, int[] a, int index, int left) {
if (index == 9) {
// 一次深度优先走完
// 刚好21次也分配完了
a[9] = left;
if (a[9] < 10) {
// 9的21次方出现的次数不能超过10次，因为9的21次方是21位数
BigInteger ret = BigInteger.ZERO;
for (int i = 0; i < a.length; i ) {
// 一旦结果超过21位，立即跳出循环
if (ret.toString().length() > 21) {
ret = null;
break;
}
// 把每个数字出现的次数乘以它的21次方，然后累加起来
if (a[i] != 0) {
ret = ret.add(b[i].multiply(BigInteger.valueOf(a[i])));
}
}
if (ret != null && ret.toString().length() == 21) {
// 进一步验证每个数字出现的次数是否和a数组一致
String x = ret.toString();
// System.out.println(x);
int[] c = new int[10];
for (int i = 0; i < x.length(); i ) {
c[x.charAt(i) - '0'] ;
}
// 对比两个数组，一致说明找到答案
boolean isRight = true;
for (int i = 0; i < c.length; i ) {
if (a[i] != c[i]) {
isRight = false;
break;
}
}
if (isRight) {
System.out.println(x);
}
}
}
return;
}
// 为第index个a数组元素分配次数
for (int i = 0; i <= left; i ) {
a[index] = i;
ss(b, a, index 1, left - i);
}
}
}程序运行参考结果
代码语言：javascript复制128468643043731391252
449177399146038697307
