求助，21位花朵数解法

bliteray 2010-08-19 09:08:14

加精

如题，求解21位花朵数的解法，要求在3分钟之内计算完成
花朵数：N位整数，它等于各个位的数字的N次方之和，
例如有一个N位数字，a1a2a3a4.....aN = a1^N +a2^N+......aN^N

要求使用java语言完成，哪个高手告诉小弟怎么解决啊~急~~~

...全文

5043 174 打赏收藏转发到动态举报

写回复

用AI写文章

174 条回复

切换为时间正序

请发表友善的回复…

发表回复

流智 2011-05-21

打赏
举报

import java.math.BigInteger;
import java.util.Hashtable;

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[offset])));// 当前已存在值+可能存在的最大值
// 最小值匹配
if (minVal.compareTo(MAX) > 0) {
return false;
}
// 最大值匹配
if (maxVal.compareTo(MIN) < 0) {
return false;
}
String minStr = minVal.compareTo(MIN) > 0 ? minVal.toString() : MIN.toString();
String maxStr = maxVal.compareTo(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 sum.compareTo(sumArray[offset]) == 0;
}
return true;
}

/**
* 退出循环，打印
*
* @return
*/
private void success() {
System.out.println("find a match number:" + 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 = SIZE > 9 ? 9 : SIZE;
for (int i = 0; i <= s; i++) {
// new Main().test(i, startTime);
// 启动十个线程同时运算
final int startValue = i;
new Thread(new Runnable() {

public void run() {
new Main().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<String, Object> ht = new Hashtable<String, Object>();

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));
}
}

shendear 2011-05-14

打赏
举报

这个是很久的帖子了。

xiongyuanming 2011-05-06

打赏
举报

求水仙花数的嘛
package test1;

import java.util.ArrayList;
import java.util.Calendar;
import java.util.GregorianCalendar;
import java.util.List;

public class ShuixianhuaNo {

/**
* @param args
*/
public static void main(String[] args) {
// boolean bool = ShuixianhuaNo.isNarcissusNumber(1634);
// if(bool) {
// System.out.println("是水仙数。");
// }else {
// System.out.println("不是水仙数。");
// }
boolean bool = false;
Calendar a = new GregorianCalendar();
long st = a.getTimeInMillis();
for (int i = 100; i < 100000; i++) {
bool = ShuixianhuaNo.isNarcissusNumber(i);
if (bool) {
System.out.println(i + " 是水仙数。");
}
}
a = new GregorianCalendar();
long et = a.getTimeInMillis();
System.out.println("*******************************");
System.out.println("耗时：：" + (et - st)+"ms");
}

/**
* 判断一个数是否是水仙花数（例如 153=1^3+5^3+3^3）水仙花数是指一个 n 位数 ( n≥3 )，它的每个位上的数字的 n
* 次幂之和等于它本身
*
* @param num
* int 相当于是要求num>=100
* @return
*/
public static boolean isNarcissusNumber(int num) {
boolean bool = false;
List<Integer> numList = new ArrayList<Integer>();
numList.clear();

int n = num;
int m = 0;

while (n > 0) {
m = 0;
m = n % 10;
numList.add(m);
n = n / 10;
}

if (numList != null && numList.size() > 0 && num == sum(numList)) {
bool = true;
}
return bool;
}

/**
* 求list元素的list.size()次方之和[list的长度必须大于0]
*
* @param list
* List<Integer>
* @return int
*/
public static int sum(List<Integer> list) {
int sum = 0;
int len = list.size();
for (Integer n : list) {
sum += power(n, len);
}
return sum;
}

/**
* 求得 n 的 nlen次方 [采用递归算法] 这里只能算nlen>=0的
*
* @param n
* Integer
* @param nlen
* Integer
* @return int
*/
public static int power(Integer n, int nlen) {
if (nlen > 0) {
return n * power(n, nlen - 1);
} else {
return 1;
}
}
}

cssb4216 2011-05-03

打赏
举报

有无算法？？

tylanbin 2011-05-02

打赏
举报

143楼真猛了……膜拜……

jy320751 2011-04-27

打赏
举报

正在找这题的解答呢`` 想爆脑子了还想不出,搜着搜着就到这来了,呵呵.
楼上方法不错啊.

opgnyqhy 2010-09-19

打赏
举报

好复杂啊，菜鸟路过

zhengbiao5 2010-09-19

打赏
举报

http://www.javaeye.com/topic/763764
分

chenbb110 2010-09-13

打赏
举报

学习中

绿色夹克衫 2010-09-04

打赏
举报



1 1

2 2

3 3

4 4

5 5

6 6

7 7

8 8

9 9

10 153

11 370

12 371

13 407

14 1634

15 8208

16 9474

17 54748

18 92727

19 93084

20 548834

21 1741725

22 4210818

23 9800817

24 9926315

25 24678050

26 24678051

27 88593477

28 146511208

29 472335975

30 534494836

31 912985153

32 4679307774

33 32164049650

34 32164049651

35 40028394225

36 42678290603

37 44708635679

38 49388550606

39 82693916578

40 94204591914

41 28116440335967

42 4338281769391370

43 4338281769391371

44 21897142587612075

45 35641594208964132

46 35875699062250035

47 1517841543307505039

48 3289582984443187032

49 4498128791164624869

50 4929273885928088826

51 63105425988599693916

52 128468643043731391252

53 449177399146038697307

54 21887696841122916288858

55 27879694893054074471405

56 27907865009977052567814

57 28361281321319229463398

58 35452590104031691935943

59 174088005938065293023722

60 188451485447897896036875

61 239313664430041569350093

62 1550475334214501539088894

63 1553242162893771850669378

64 3706907995955475988644380

65 3706907995955475988644381

66 4422095118095899619457938

67 121204998563613372405438066

68 121270696006801314328439376

69 128851796696487777842012787

70 174650464499531377631639254

71 177265453171792792366489765

72 14607640612971980372614873089

73 19008174136254279995012734740

74 19008174136254279995012734741

75 23866716435523975980390369295

76 1145037275765491025924292050346

77 1927890457142960697580636236639

78 2309092682616190307509695338915

79 17333509997782249308725103962772

80 186709961001538790100634132976990

81 186709961001538790100634132976991

82 1122763285329372541592822900204593

83 12639369517103790328947807201478392

84 12679937780272278566303885594196922

85 1219167219625434121569735803609966019

86 12815792078366059955099770545296129367

87 115132219018763992565095597973971522400

88 115132219018763992565095597973971522401