![[编程]求21位花朵数的java程序-国信蓝桥试题算法](https://img.doczj.com/img93/04fft6jncvlfevjekc7a-31.webp)
![[编程]求21位花朵数的java程序-国信蓝桥试题算法](https://img.doczj.com/img93/04fft6jncvlfevjekc7a-92.webp)
（编程题）花朵数
一个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分钟内运行完毕。
个人认为本题的思路：
1：关键是：去掉所含0-9数字个数雷同的21位数，以免反复运算，增长时候，
比如123456789012345678901与987654321098765432101与987654321012345678901中的所含数字的个数都是雷同的，所以其每一位的21次方的和都相等，将所得的21次方和从大到小进行排序，若对应的数与原数不相等，则都不成立，是以若不去掉反复的数，将会增长运算时候；
2：认为要将每一位数的21次方之和从大到小排序，所以运算从21个9这个最大数开端向下运算，又因为10个9的21次方之和跨越了21位数，所以从9个9，12个8开端一次往下运算即可，如许又可以节俭一项目组时候。
package dome;
import java.math.BigInteger;
import java.util.Hashtable;
public class Demo2
{
private static final int SIZE = 21;
private int[] countArray = new int[10]; // 个数列表
private int[] countSumArray = new int[10]; // 个数总数
private BigInteger[] sumArray = new BigInteger[10];// 值总数
private int offset = 0; // 浮标
/**
* 设置当前浮标对应的个数，个数的总数，值总数
*
* @param num
* 个数
*/
private void setValue(int num)
{
countArray[offset] = num;
if (offset == 0)
{
countSumArray[offset] = num;
sumArray[offset] = p(9 - offset).multiply(n(num));
} else
{
countSumArray[offset] = countSumArray[offset - 1] + num;
sumArray[offset] = sumArray[offset - 1].add(p(9 - offset).multiply(
n(num)));
}
}
/**
* 检验当前数据是否匹配
*
* @return
*/
private boolean checkPersentArray()
{
BigInteger minVal = sumArray[offset];// 当前已存在值
BigInteger maxVal = sumArray[offset].add(p(9 - offset).multiply(
n(SIZE - countSumArray[offset])));// 当前已存在值+可能存在的最大值// 最小值匹配
if (https://www.doczj.com/doc/9b4350960.html,pareTo(MAX) > 0)
{
return false;
}
// 最大值匹配
if (https://www.doczj.com/doc/9b4350960.html,pareTo(MIN) < 0)
{
return false;
}
String minStr = https://www.doczj.com/doc/9b4350960.html,pareTo(MIN) > 0 ? minVal.toString() : MIN
.toString();
String maxStr = https://www.doczj.com/doc/9b4350960.html,pareTo(MAX) < 0 ? maxVal.toString() : MAX
.toString();
// 找到最小值与最大值间首部相同的部分
int[] sameCountArray = new int[10];
for (int i = 0; i < SIZE; i++)
{
char c;
if ((c = minStr.charAt(i)) == maxStr.charAt(i))
{
sameCountArray[c - '0'] = sameCountArray[c - '0'] + 1;
} else
{
break;
}
}
// 判断如果相同部分有数据大于现在已记录的位数，返回false
for (int i = 0; i <= offset; i++)
{
if (countArray[i] < sameCountArray[9 - i])
{
return false;
}
}
// 如果当前值的总数为SIZE位，那么判断该值是不是需要查找的值if (countSumArray[offset] == SIZE)
{
String sumStr = sumArray[offset].toString();
BigInteger sum = ZERO;
for (int i = 0; i < sumStr.length(); i++)
{
sum = sum.add(p(sumStr.charAt(i) - '0'));
}
return https://www.doczj.com/doc/9b4350960.html,pareTo(sumArray[offset]) == 0;
}
return true;
}
/**
* 退出循环，打印
*
* @return
*/
private void success()
{
System.out.println(SIZE + "位的花朵数为:" + sumArray[offset]);
}
/**
* 将浮标指向下一位数
*
* @return
*/
private void next()
offset++;
setValue(SIZE - countSumArray[offset - 1]); }
/**
*
* 回退浮标，找到最近的浮标，并减一
*
* @return
*/
private boolean back()
{
// 回退浮标，找到最近的浮标，并减一
if (countArray[offset] == 0)
{
while (countArray[offset] == 0)
{
if (offset > 0)
{
offset--;
} else
{
return true;
}
}
}
if (offset > 0)
{
setValue(countArray[offset] - 1);
return false;
} else
{
return true;
}
}
/**
* 测试程序
*
* @param startValue
* 测试匹配数中包含9的个数* @param startTime
* 程序启动时间
private void test(int startValue, long startTime)
{
// 设置9的个数
offset = 0;
setValue(startValue);
while (true)
{
if (checkPersentArray())
{// 检查当前提交数据是否匹配
// 匹配且总数正好为SIZE的位数，那么就是求解的值
if (countSumArray[offset] == SIZE)
{
success();
}
// 总数不为SIZE，且当前值不在第10位（即不等于0）
if (offset != 9)
{
next();
continue;
}
// 总数不为SIZE，且当前值在第10位。
if (back())
{
break;
}
} else
{
if (back())
{
break;
}
}
}
System.out.println(Thread.currentThread() + " End,Spend time "
+ (System.currentTimeMillis() - startTime) / 1000 + "s"); }
/**
* 主函数
*/
public static void main(String[] args)
{
final long startTime = System.currentTimeMillis();
int s = MAX.divide(p(9)).intValue();
for (int i = 0; i <= s; i++)
{
// new Main().test(i, startTime);
// 启动十个线程同时运算
final int startValue = i;
new Thread(new Runnable()
{
public void run()
{
new Demo2().test(startValue, startTime);
}
}).start();
}
}
private static final BigInteger ZERO = new BigInteger("0");
private static final BigInteger MIN;
private static final BigInteger MAX;
/**
* 0-SIZE间的BigInteger
*/
private static final BigInteger n(int i)
{
return (BigInteger) ht.get("n_" + i);
}
/**
* 0-9的次方的BigInteger
*/
private static final BigInteger p(int i)
{
return (BigInteger) ht.get("p_" + i);
}
/**
* 用于缓存BigInteger数据，并初始化0-SIZE间的BigInteger和0-9的次方的BigInteger */
private static Hashtable
static
{
int s = SIZE < 10 ? 10 : SIZE;
for (int i = 0; i <= s; i++)
{
ht.put("n_" + i, new BigInteger(String.valueOf(i)));
}
for (int i = 0; i <= 10; i++)
{
ht.put("p_" + i, new BigInteger(String.valueOf(i)).pow(SIZE));
}
MIN = n(10).pow(SIZE - 1);
MAX = n(10).pow(SIZE).subtract(n(1));
}
}