高精度计算-21阶花朵数

数据结构与算法
7.9k 词

题目

花朵数

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

如果满足条件的数字不只有一个，请从小到大输出所有符合条件的数字，每个数字占一行。因为这个数字很大，请注意解法时间上的可行性。要求程序在 1 分钟内运行完毕。

参考答案

128468643043731391252
449177399146038697307

思路

首先想到21位嘛，肯定不能暴力了，这个范围暴力效率太低了，而且的话涉及到高精度，比较费劲.

我们可以想一下：对于这个21位花朵数，它只需要每一位的21次方和为本身，那么可以进一步思考我们只需要对0-9每一种数进行计数，而忽略掉每一个数字在21位花朵数上的位置，实际上，就是放置9个隔板在21位数字上分成10组（0-9每一种数字为一种），每一组可以有0个或多个，然后枚举检查所有的组合方式是否为一个合法的21位花朵数。

也就是我们有0到9这10个不同的数字，要形成一个21位数字。问题的特殊之处在于，我们只关心数字的组合类型，而不是它们的排列顺序。也就是说，只要数字的分布相同，不论它们的顺序如何，我们都认为它们是同一种组合。

那么这个组合数该如何计算呢？

如果每一组至少都一定有一个数，那么就是C(20,9)，即在21个数字中的20个空隙插入九个隔板，但是这个题有一个特殊的就是这个数可以出现0次，这意味着某个数字可能不出现在最终的21位数字中。

但是仔细想想很简单，21个数字加上9个隔板一共就30个空，那么就30选9或者30选21填上9个空或21个空，那么剩下的一定就是21个数字或者是9个隔板了，那么就是C(30,9)/C(30,21)。

组合数计算

public static StringBuilder path = new StringBuilder();

public static void dfs(int i, int n, int k) {
    if (i == n) {
        if (k == 0) {
            int[] cnt = new int[10];
            int cur = 0;
            for (int j = 0; j < n; j++) {
                if (path.charAt(j) == '0') {
                    cnt[cur]++;
                } else {
                    cur++;
                }
            }
            check(cnt);
        }
        return;
    }
    if (k > 0) {
        path.append(1);
        dfs(i + 1, n, k - 1);
        path.deleteCharAt(path.length() - 1);
    }
    path.append(0);
    dfs(i + 1, n, k);
    path.deleteCharAt(path.length() - 1);
}

最后得到类似110101101010000001000001000000 这样的字符串，然后1相当于隔板，0相当于数字，然后我们可以使用一个数组进行计数，再通过这个数组求出这个21位数字，然后判断是否符合条件即可。

高精度计算

在判断这个21位数字是否符合条件的前，我们需要先实现高精度的计算，这里我们有两种方法来封装一个高精度的类，一种是用数组表示每一位，另一种则是万进制的表示。

数组表示

用一个数组来表示每一位数字（从低位开始），然后实现加法、乘法、幂运算等操作。

import java.util.*;

public class BigInt {
    public static void main(String[] args) {
        BigInt bigInt = new BigInt("99");
        BigInt bigInt1 = new BigInt("88");
        System.out.println(bigInt1.multiply(bigInt));  // 应该输出 8712
        System.out.println(bigInt.add(new BigInt("9999")));  // 应该输出 10098
        System.out.println(new BigInt("123456789").pow(2));  // 应该输出 15241578750190521
    }

    private final List<Integer> digits;

    public List<Integer> getDigits() {
        return digits;
    }

    public BigInt(String value) {
        digits = new ArrayList<>();
        int len = value.length();
        for (int i = len - 1; i >= 0; i--) {
            digits.add(value.charAt(i) - '0');
        }
    }

    public BigInt(List<Integer> digits) {
        this.digits = digits;
    }

    public BigInt add(BigInt num) {
        int len1 = this.length(), len2 = num.length();
        List<Integer> digits1 = new ArrayList<>(this.digits);
        List<Integer> digits2 = new ArrayList<>(num.getDigits());
        List<Integer> res = new ArrayList<>();
        int maxLen = Math.max(len1, len2);
        while (digits1.size() < maxLen) {
            digits1.add(0);
        }
        while (digits2.size() < maxLen) {
            digits2.add(0);
        }
        int carry = 0;
        for (int i = 0; i < maxLen; i++) {
            int digit1 = digits1.get(i);
            int digit2 = digits2.get(i);
            int sum = digit1 + digit2 + carry;
            res.add(sum % 10);
            carry = sum / 10;
        }
        if (carry != 0) {
            res.add(carry);
        }
        return new BigInt(res);
    }

    public BigInt multiply(BigInt num) {
        List<Integer> result = new ArrayList<>(Collections.nCopies(this.digits.size() + num.digits.size(), 0));
        for (int i = 0; i < this.digits.size(); i++) {
            int carry = 0;
            for (int j = 0; j < num.digits.size(); j++) {
                int product = this.digits.get(i) * num.digits.get(j) + result.get(i + j) + carry;
                result.set(i + j, product % 10);
                carry = product / 10;
            }
            if (carry > 0) {
                result.set(i + num.digits.size(), result.get(i + num.digits.size()) + carry);
            }
        }
        while (result.size() > 1 && result.get(result.size() - 1) == 0) {
            result.remove(result.size() - 1);
        }
        return new BigInt(result);
    }

    public BigInt pow(int n) {
        BigInt res = new BigInt("1");
        for (int i = 0; i < n; i++) {
            res = res.multiply(this);
        }
        return res;
    }

    public int length() {
        return this.digits.size();
    }

    private String arr2String(List<Integer> arr) {
        StringBuilder sb = new StringBuilder();
        for (int i = arr.size() - 1; i >= 0; i--) {
            sb.append(arr.get(i));
        }
        return sb.toString();
    }

    @Override
    public String toString() {
        return this.arr2String(this.digits);
    }
}

万进制表示

这里使用长度为6的数组进行万进制的表示，每一位表示四位数字，用来表示一个21位的数字，这样的话我们可以直接进行加法和乘法的操作。

class BigInt2 {
    int[] arr = new int[6];
    boolean overflow;

    public BigInt2(int n) {
        for (int i = 0; i < arr.length && n != 0; i++) {
            arr[i] = n % 10000;
            n /= 10000;
        }
    }

    public BigInt2(String s) {
        int len = s.length();
        for (int i = 0, j = len - 1; j >= 0; i++, j--) {
            arr[i / 4] += (int) ((s.charAt(j) - '0') * Math.pow(10, i % 4));
        }
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        boolean flag = true;
        for (int i = 5; i >= 0; i--) {
            if (arr[i] != 0 || !flag) {
                if (flag) {
                    sb.append(arr[i]);
                    flag = false;
                } else {
                    sb.append(String.format("%04d", arr[i]));
                }
            }
        }
        return flag ? "0" : sb.toString();
    }

    public boolean lessThan(BigInt2 b) {
        for (int i = 5; i >= 0; i--) {
            if (arr[i] != b.arr[i]) return arr[i] < b.arr[i];
        }
        return false;
    }

    public BigInt2 add(BigInt2 b) {
        BigInt2 result = new BigInt2(0);
        int carry = 0;
        for (int i = 0; i < 6; i++) {
            result.arr[i] = arr[i] + b.arr[i] + carry;
            carry = result.arr[i] / 10000;
            result.arr[i] %= 10000;
        }
        result.overflow = carry != 0;
        return result;
    }

    public BigInt2 multiply(int b) {
        BigInt2 result = new BigInt2(0);
        int carry = 0;
        for (int i = 0; i < 6; i++) {
            long product = (long) arr[i] * b + carry;
            result.arr[i] = (int) (product % 10000);
            carry = (int) (product / 10000);
        }
        result.overflow = carry != 0;
        return result;
    }

    public BigInt2 multiply(BigInt2 b) {
        BigInt2 result = new BigInt2(0);
        for (int i = 0; i < 6; i++) {
            if (arr[i] == 0) continue;
            BigInt2 temp = b.multiply(arr[i]);
            for (int j = 0; j < i; j++) {
                temp = temp.multiply(10000);
            }
            result = result.add(temp);
        }
        return result;
    }

    public BigInt2 pow(int n) {
        BigInt2 res = new BigInt2(1);
        for (int i = 0; i < n; i++) {
            res = res.multiply(this);
        }
        return res;
    }

    public static void main(String[] args) {
        BigInt2 a = new BigInt2("121");
        BigInt2 b = new BigInt2("121");
        BigInt2 c = a.multiply(b);
        System.out.println(c);
        System.out.println(a.add(b));
    }
}

检查是否符合条件

因为要计算每一位的21次幂，所有我们提前把0-9的每一个数的21次幂提前计算好放到数组里作为缓存，防止用的时候算一次而造成巨大的开销。

public static BigInteger[] cache;

public static void main(String[] args) {
    cache = new BigInteger[10];
    for (int i = 0; i < cache.length; i++) {
        cache[i] = pow21(i);
    }
}

public static BigInteger pow21(int i) {
    return new BigInteger(String.valueOf(i)).pow(21);
}

传入一个计数的数组然后进行累加求和，得到一个大数字。

这个数字要满足以下条件：

  • 长度等于21
  • 对这个大数再计数，然后逐一对比传入的计数数组，满足一一相等
public static void check(int[] cnt) {
    BigInteger sum = BigInteger.ZERO;
    for (int i = 0; i < cnt.length; i++) {
        sum = sum.add(cache[i].multiply(new BigInteger(String.valueOf(cnt[i]))));
    }
    String num = sum.toString();
    if (num.length() != 21) return;
    int[] checkCnt = new int[10];
    for (int i = 0; i < 21; i++) checkCnt[num.charAt(i) - '0']++;
    for (int i = 0; i < 10; i++) {
        if (cnt[i] != checkCnt[i]) {
            return;
        }
    }
    System.out.println(num);
}

AC代码

package 实践学期.第一节课高精度;

import java.math.BigInteger;

public class 二十一位水仙花数4 {

    public static BigInteger[] cache;

    public static StringBuilder path = new StringBuilder();

    public static void main(String[] args) {
        long start = System.currentTimeMillis();
        cache = new BigInteger[10];
        for (int i = 0; i < cache.length; i++) {
            cache[i] = pow21(i);
        }
        int[] cnt = new int[10];
        dfs(0, 30, 9);
        System.out.println(System.currentTimeMillis() - start);
    }

    public static BigInteger pow21(int i) {
        return new BigInteger(String.valueOf(i)).pow(21);
    }

    public static void check(int[] cnt) {
        BigInteger sum = BigInteger.ZERO;
        for (int i = 0; i < cnt.length; i++) {
            sum = sum.add(cache[i].multiply(new BigInteger(String.valueOf(cnt[i]))));
        }
        String num = sum.toString();
        if (num.length() != 21) return;
        int[] checkCnt = new int[10];
        for (int i = 0; i < 21; i++) checkCnt[num.charAt(i) - '0']++;
        for (int i = 0; i < 10; i++) {
            if (cnt[i] != checkCnt[i]) {
                return;
            }
        }
        System.out.println(num);
    }

    public static void dfs(int i, int n, int k) {
        if (i == n) {
            if (k == 0) {
                int[] cnt = new int[10];
                int cur = 0;
                for (int j = 0; j < n; j++) {
                    if (path.charAt(j) == '0') {
                        cnt[cur]++;
                    } else {
                        cur++;
                    }
                }
                check(cnt);
            }
            return;
        }
        if (k > 0) {
            path.append(1);
            dfs(i + 1, n, k - 1);
            path.deleteCharAt(path.length() - 1);
        }
        path.append(0);
        dfs(i + 1, n, k);
        path.deleteCharAt(path.length() - 1);
    }
}

这边直接用java自带的BigInteger，效率要比我写的高出不少，只用了14秒左右。

输出图片

至此，本题总结完毕。

留言