日期:2014-05-20  浏览次数:20754 次

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

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

------解决方案--------------------
Java code
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;
    }
}

------解决方案--------------------
Java code
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;
    }
}