计算机算法解决办法-Java教程-爱易网页

计算机算法解决办法

日期：2014-05-20　浏览次数：20649 次

计算机算法
一个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分钟内运行完毕。

------解决方案--------------------

Java code


import java.math.BigInteger;
import java.util.Arrays;

public class da2 {
    static BigInteger[] table = new BigInteger[10];
    static BigInteger sum = BigInteger.ZERO;
    static int times = 0;
    static BigInteger MAX = BigInteger.TEN.pow(21).subtract(BigInteger.ONE);
    static BigInteger MIN = BigInteger.TEN.pow(21 - 1);
    public static void main(String[] args) {
        long time = System.nanoTime();
        int n = 21;
        int[] nums = new int[n];
        for (int i = 0; i < 10; i++)
            table[i] = BigInteger.valueOf(i).pow(n);
        f(0,n,nums,0);
        time = System.nanoTime() - time;                              
        System.out.println("计算时间："+time / 1000000000.0 + "秒");
        System.out.println("循环次数:"+times+"次");
    }

    public static void f(int i,int n,int[] nums,int m)
    {
        if(i > n - 1)
        {
            times++;
            if(panduan(nums))
                System.out.println(sum);
        }
        else
        {
            for(int v = m;v < 10;v++)
            {
                nums[i] = v;
                sum = sum.add(table[v]);
                f(i+1,n,nums,v);
                sum = sum.subtract(table[v]);
            }
        }
    }
    public static boolean panduan(int[] nums)
    {
        if(sum.compareTo(MAX)>0||sum.compareTo(MIN)<0)
            return false;
        String s = String.valueOf(sum);
        int length = s.length();
        int[] a = new int[length];
        for (int i = 0; i < length; i++)
            a[i] = s.charAt(i) - '0';
        int[] b = nums.clone();
        Arrays.sort(a);
        Arrays.sort(b);
        return Arrays.equals(a, b);
    }
}