编写程序一个三位正整数等于它的各位数字的立方和
玛丽莲梦兔
869次浏览
2021年02月01日 07:19
最佳经验
本文由作者推荐
黑客电影-网络推广经验
编写程序
:
一个三位正整数等于它的各位数字的立方和
经楼下朋友 提醒，
我这个算法求出的正好是
21
位水仙花数。
于是我对其进行了稍微的修 订，
使得其支持任意位数的水仙花数求值，
效果还不错，
理论上的水仙花最大数为34
位
(
我算了
下，至少到
39
位还有解
)< br>，我的求解花了半分多钟，而
21
位数的求解只化了
2
秒多。
[
原题
]
一个
21
位的整数
,
它的各个位数的
21
次方的和加起来等于它本身
.
要求
:
程序在三分钟内完成
,Java
语言实现
.
写道
一个
21
位的整数
,
它的各个位数的
21
次方的和加起来等于它本身
.
要求
:
程序在三分钟内完
成
,Java
语言实现
.
[
解决思路
]
这个我最初 的思路也是想找出其中是否有数学规律，无奈大学数学就混过来的，只能
穷举解决了。
虽然是穷举，但是不同的实现，效果也不一样，如果要从
1 00000000
穷
举到
999999999999999999999
，我 想肯定麻烦大了。
这里我主要是换个思路，穷举这个数中 的每个位置上的数字的总数。从一开始，我们
假设共有该数中存在
9
个
9，我们将这个数的信息存到几个特定的数组中去：
Java
代码
private int[] countArray = new int[10]; //
个数列表
private int[] countSumArray = new int[10]; //
个数总数
private BigInteger[] sumArray = new BigInteger[10];//
值总数
private int offset = 0;//
浮标
countArray
记录依 次从
9
到
0
每个数的个数，
countSumArray
是
countArray
中的各个数
与
其
之
前
所有
数
的
个
数
的
总
和
(
即countSumArray[n]=countSumArray[n-1]+countNum)
，
sumArray
是当前数的总值
(
即
sumArray[n] =sumArray[n-1]+num)
。
offset
是浮标，即当前判定
的数的位置
我们对该个数进行 判断，
9
个
9
后面还有
12
位数，那么
9
个
9
最小就是
9
个
9
的平方
+12
个0
的平方，最大是
9
个
9
的平方
+12
个8
的平方。我们从以下三个方面来判断：
1.
最小值不大于
999999999999999999999
2.
最大值不小于
100000000
3.
最
大
值
与
最
小
值
从
首
部
是
否
相
同
的
部
分
，
如
7 77700000
与
777799999999999999999
，存在
7 777
相同的部分，如果该相同的部分中有某个数的个数大
于
offset
中 相同的值的个数，那么该值也判定为失败
还有一个很重要的判断就 是，
如果
countSumArray
中对应的
offset
中的值 为
21
，
那么即
所有的位数都有值，
那么直接判定如果该值
=
其各个位置上的数的
21
次方之和，
如果不等返
回失败，反之，这 个数就是要求的数。
总体判断如上所述，如果失败我 们即查询下一个数
next()
，
countSumArray[offset]=2 1
，
那么就是查到头了，就返回查找
back()
。
用到了几个技巧，就是将
BigInteger
的运算结果直接存储到
has htable
中去，可以节约
大量运算时间。
题中给予了
4
分钟的时 间，
以为很需要一段时间，
就设置了多线程，后来发
现，不使用多线程也只要花费2
秒种，多线程的意义也就不复存在了。
应楼下朋友要求，
贴图描述解题思路，
很少画图，
更没用
Dia
画 过图，
有粗制滥造之嫌，
请勿怪了。
。
。
[
代码实现
]
Java
代码
import eger;
import ble;
public class Main {
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[offse
t])));//
当前已存在值
+
可能存在的最大值
//
最小值匹配
if (eTo(MAX) > 0) {
return false;
}
//
最大值匹配
if (eTo(MIN) < 0) {
return false;
}
String minStr = eTo(MIN) > 0 ? ng() : ng();
String maxStr = eTo(MAX) < 0 ? ng() : ng();
//
找到最小值与最大值间首部相同的部分
int[] sameCountArray = new int[10];
for (int i = 0; i < SIZE; i++) {
char c;
if ((c = (i)) == (i)) {
sameCountArray[c - '0'] = sameCountArray[c - '0'] + 1;