Java实现花朵数

一个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次方之和正好等于这个数本身。

如果满足条件的数字不只有一个，请从小到大输出所有符合条件的数字，每个数字占一行。因为这个数字很大，请注意解法时间上的可行性。

这些代码因为BigInteger要大约三分钟才会有结果

import java.math.BigInteger;

import java.util.ArrayList;

import java.util.Collections;

public class Main {

    public static ArrayList<BigInteger> set = new ArrayList<BigInteger>();

    public static BigInteger[] value = new BigInteger[10];

    public static int count = 0;

    public BigInteger getPow(BigInteger n) {

        BigInteger result = BigInteger.ONE;

        for(int i = 1;i <= 21;i++)

            result = result.multiply(n);

        return result;

    }

    public boolean check(int[] A) {

        BigInteger temp = BigInteger.ZERO;

        for(int i = 0;i < 10;i++) {

            BigInteger k = new BigInteger(""+A[i]);

            temp = temp.add(value[i].multiply(k));

        }

        String s = "" + temp;

        if(s.length() != 21)

            return false;

        int[] B = new int[10];

        for(int i = 0;i < 21;i++) {

            int k = s.charAt(i) - '0';

            B[k]++;

        }

        for(int i = 0;i < 10;i++)

            if(A[i] != B[i])

                return false;

        return true;

    }

    public void dfs(int step, int sum, int[] A) {

        if(step == 10) {

            if(sum == 21 && check(A)) {

                BigInteger temp = BigInteger.ZERO;

                for(int i = 0;i < 10;i++) {

                    BigInteger k = new BigInteger(""+A[i]);

                    temp = temp.add(value[i].multiply(k));

                }

                if(!set.contains(temp))

                    set.add(temp);

                count++;

            }

            return;

        } else {

            for(int i = 0;i <= 21 - sum;i++) {

                A[step] = i;

                dfs(step + 1, sum + i, A);

            }

        }

    }

    public static void main(String[] args) {

        Main test = new Main();

        for(int i = 0;i <= 9;i++) {

            BigInteger a = new BigInteger(""+i);

            value[i] = test.getPow(a);

        }

        int[] A = new int[10];

        test.dfs(0, 0, A);

        Collections.sort(set);

        for(int i = 0;i < set.size();i++)

            System.out.println(set.get(i));

    }

}

巴特西

Java实现花朵数

最新文章

热门文章