求助，21位花朵数解法

Question

如题，求解21位花朵数的解法，要求在3分钟之内计算完成
花朵数：N位整数，它等于各个位的数字的N次方之和，
例如有一个N位数字，a1a2a3a4.....aN = a1^N +a2^N+......aN^N要求使用java语言完成，哪个高手告诉小弟怎么解决啊~急~~~

Answer 1

21位的话...已经超过long型的最大长度了...貌似要用string了..
超麻烦的..

Answer 2

建议用BigInteger就可以了，算法应该不是很难了，自己先写一下吧

Answer 3

这是一个编程题目，楼上的说用BigInteger，那确实能存这么大的数，但是，计算时间上不可行，你能写一个出来，在三分钟之内计算完成的吗？谢谢了

Answer 4

import java.math.BigInteger;
import java.util.Arrays;public class Flower {
private static int num = 21;
private static BigInteger[] table = new BigInteger[10];
private static int[] nums;

public static void main(String[] args) {
long time = System.currentTimeMillis();
for (int i = 0; i < 10; i++)
table[i] = BigInteger.valueOf(i).pow(num);
nums = new int[num];
find(nums, 0, 0);
time = System.currentTimeMillis() - time;
System.out.println(time / 1000.0 + "s");
}

public static void find(int[] nums, int level, int num) {
nums[level] = num;
if (level == nums.length - 1) {
BigInteger big = sum(nums);
int[] temp = getArray(big);
if (check(nums, temp))
System.out.println(big);
return;
}
for (int i = num; i < 10; i++)
find(nums, level + 1, i);
}

public static boolean check(int[] a1, int[] a2) {
if (a1.length != a2.length)
return false;
Arrays.sort(Arrays.copyOf(a1, a1.length));
Arrays.sort(a2);
return Arrays.equals(a1, a2);
}

public static BigInteger sum(int[] nums) {
BigInteger sum = BigInteger.ZERO;
for (int i = 0; i < nums.length; i++)
sum = sum.add(table[nums[i]]);
return sum;
}

public static int[] getArray(BigInteger big) {
String s = String.valueOf(big);
char[] ch = s.toCharArray();
int[] res = new int[ch.length];
for (int i = 0; i < ch.length; i++)
res[i] = ch[i] - '0';
return res;
}
}

Answer 5

8^21*21=193690812773950291968是21位额，8^21*11就是21位了……
应该是(1e20/21)^(1/21)大概是7.75，也就是至少有一位8或99楼这个方法的确肯定不是最好的，目前我把递归改成回溯了，算是防止栈溢出吧……import java.math.BigInteger;
import java.util.Arrays;public class Narcissistic {
private static BigInteger[] table = new BigInteger[10]; public static void main(String[] args) {
long time = System.nanoTime();
find(31);
time = System.nanoTime() - time;
System.out.println(time / 1000000000.0 + "s");
} public static void find(int n) {
for (int i = 0; i < 10; i++)
table[i] = BigInteger.valueOf(i).pow(n);
int[] nums = new int[n];
int index = 0;
int num = 0;
while (true) {
if (index < nums.length && num < 10) {
nums[index] = num;
index++;
continue;
} else if (index >= nums.length) {
BigInteger big = sum(nums);
int[] temp = getArray(big);
if (check(nums, true, temp, false))
System.out.println(big);
} else if (index <= 0) {
break;
}
index--;
num = nums[index] + 1;
}
} public static boolean check(int[] a1, boolean copy1, int[] a2, boolean copy2) {
if (a1.length != a2.length)
return false;
if (copy1)
a1 = a1.clone();
if (copy2)
a2 = a2.clone();
Arrays.sort(a1);
Arrays.sort(a2);
return Arrays.equals(a1, a2);
} public static BigInteger sum(int[] nums) {
BigInteger sum = BigInteger.ZERO;
for (int i = 0; i < nums.length; i++)
sum = sum.add(table[nums[i]]);
return sum;
} public static int[] getArray(BigInteger big) {
String s = String.valueOf(big);
int length = s.length();
int[] res = new int[length];
for (int i = 0; i < length; i++)
res[i] = s.charAt(i) - '0';
return res;
}
}
其实效率还好啦，在现在使用的电脑上21位的话50秒左右，29位是675秒，最后测试的31位大概要1212秒，貌似现在已证明最大的是39位，反正再怎么也超不过60位……
而且真的要找高位水仙花数的话……跑久点我也觉得没什么吧

Answer 6

建议用BigInteger就可以了，算法应该不是很难了，自己先写一下吧

Answer 7

import java.math.BigInteger;
import java.util.Arrays;public class Narcissistic {
private static BigInteger[] table = new BigInteger[10]; public static void main(String[] args) {
long time = System.nanoTime();
find(31);
time = System.nanoTime() - time;
System.out.println(time / 1000000000.0 + "s");
} public static void find(int n) {
for (int i = 0; i < 10; i++)
table[i] = BigInteger.valueOf(i).pow(n);
int[] nums = new int[n];
int index = 0;
int num = 0;
BigInteger sum = BigInteger.ZERO;
BigInteger MIN = BigInteger.TEN.pow(n - 1);
BigInteger MAX = BigInteger.TEN.pow(n).subtract(BigInteger.ONE);
while (true) {
if (index < nums.length && num < 10) {
BigInteger temp = sum.add(table[num]);
if (temp.compareTo(MAX) < 0) {
nums[index] = num;
index++;
sum = temp;
continue;
}
} else if (index >= nums.length && sum.compareTo(MIN) > 0) {
int[] temp = getArray(sum);
if (check(nums, true, temp, false))
System.out.println(sum);
} else if (index <= 0) {
break;
}
index--;
num = nums[index];
sum = sum.subtract(table[num]);
num++;
}
} public static boolean check(int[] a1, boolean copy1, int[] a2, boolean copy2) {
if (a1.length != a2.length)
return false;
if (copy1)
a1 = a1.clone();
if (copy2)
a2 = a2.clone();
Arrays.sort(a1);
Arrays.sort(a2);
return Arrays.equals(a1, a2);
} public static int[] getArray(BigInteger big) {
String s = String.valueOf(big);
int length = s.length();
int[] res = new int[length];
for (int i = 0; i < length; i++)
res[i] = s.charAt(i) - '0';
return res;
}
}
改进……同样环境下现在21位35-36秒，31位695秒左右……

Answer 8

wo  ye bu zd a  

Answer 9

算法很值得学习。不过2种方法都漏掉很多。第二种漏掉跟多 
000--true--0--false
001--true--1--false
002--true--8--false
003--true--27--false
004--true--64--false
005--true--125--false
006--true--216--false
007--true--343--false
008--true--512--false
009--true--729--false
011--true--2--false
012--true--9--false
013--true--28--false
014--true--65--false
015--true--126--false
016--true--217--false
017--true--344--false
018--true--513--false
019--true--730--false
022--true--16--false
023--true--35--false
024--true--72--false
025--true--133--false
026--true--224--false
027--true--351--false
028--true--520--false
029--true--737--false
033--true--54--false
034--true--91--false

Answer 10

先修正我自己发现的问题(针对#43代码)
1)BigInteger MIN = n == 1 ? BigInteger.ZERO : BigInteger.TEN.pow(n - 1);
MIN赋值没考虑到n=1时0也是1位数，n=0时会遗漏0
2)if (temp.compareTo(MAX) <= 0) {
nums[index] = num;
index++;
sum = temp;
continue;
} else if (index <= 0) {
break;
}
判断应加上等号，n=0时会遗漏9；
最后应加上判断是否跳出循环判断，n=0时会数组越界异常(index=-1)
3) else if (index >= nums.length && sum.compareTo(MIN) >= 0) {
int[] temp = getArray(sum);
if (check(nums, true, temp, false))
System.out.println(sum);
}
判断应加上等号，n=0时会遗漏0/1

Answer 11

判断应加上等号，n=0时会遗漏9；
最后应加上判断是否跳出循环判断，n=0时会数组越界异常(index=-1)
3) 

Answer 12

水仙花数有什么数学解法啊？完美数至少还能和梅森数一一对应，水仙花数有啥特点我倒真不知道验证时参考这个资料的http://mathworld.wolfram.com/NarcissisticNumber.html

Answer 13

本身不需要遍历求解的，
这里肯定用到了几个算法，
我大概可以想到的是，储存9个数的21次方以内的所有次方，保存为21*9个值 共189个
然后按照21位的递归查找，用动态规划，遍历的过程形成的结果需要记录，因为能符合条件的结果并不多，中间存储不会太高，理论上是可以算出来的，只可惜不会java，也不想用长int，尝试用 分治 把21位分成3部分，一部分7位，用3个int组成一个数来求解。
一会儿写个c#的试试。就当复习算法了

Answer 14

用赫夫曼算法的编成吧，我不会JAVA，只会用C/C++
你看看赫夫曼算法吧，看完就能算了嘿嘿，看来你的数据结构学得不怎么样哈

Answer 15

貌似到现在为止只有我贴了代码，而且并不是简单的暴力遍历，就21位而言，#43的代码在修正后while循环一共执行了87814139次
这样的算法肯定不是最好的，但也不至于沦落到暴力遍历的程度

Answer 16

haojiumeiyouxiedaimal zhegewentihaishiwenwengaoshouhaol.

Answer 17

http://linux.chinaunix.net/bbs/forum-70-1.html  MaxWit技术讨论区

Answer 18

import java.math.BigInteger;
import java.util.Arrays;public class Narcissistic {
    private static BigInteger[] table = new BigInteger[10];    public static void main(String[] args) {
        long time = System.nanoTime();
        find(31);
        time = System.nanoTime() - time;
        System.out.println(time / 1000000000.0 + "s");
    }    public static void find(int n) {
        for (int i = 0; i < 10; i++)
            table[i] = BigInteger.valueOf(i).pow(n);
        int[] nums = new int[n];
        int index = 0;
        int num = 0;
        BigInteger sum = BigInteger.ZERO;
        BigInteger MIN = BigInteger.TEN.pow(n - 1);
        BigInteger MAX = BigInteger.TEN.pow(n).subtract(BigInteger.ONE);
        while (true) {
            if (index < nums.length && num < 10) {
                BigInteger temp = sum.add(table[num]);
                if (temp.compareTo(MAX) < 0) {
                    nums[index] = num;
                    index++;
                    sum = temp;
                    continue;
                }
            } else if (index >= nums.length && sum.compareTo(MIN) > 0) {
                int[] temp = getArray(sum);
                if (check(nums, true, temp, false))
                    System.out.println(sum);
            } else if (index <= 0) {
                break;
            }
            index--;
            num = nums[index];
            sum = sum.subtract(table[num]);
            num++;
        }
    }    public static boolean check(int[] a1, boolean copy1, int[] a2, boolean copy2) {
        if (a1.length != a2.length)
            return false;
        if (copy1)
            a1 = a1.clone();
        if (copy2)
            a2 = a2.clone();
        Arrays.sort(a1);
        Arrays.sort(a2);
        return Arrays.equals(a1, a2);
    }    public static int[] getArray(BigInteger big) {
        String s = String.valueOf(big);
        int length = s.length();
        int[] res = new int[length];
        for (int i = 0; i < length; i++)
            res[i] = s.charAt(i) - '0';
        return res;
    }
}