java - 字符的拆分和求和

Question

我必须编写一个函数，找到最小的数字，其数字之和为 N。我无法以比暴力更好的方式计算出它，但在将整数添加到数组，它的总和非常奇怪。

public int sumN(int N) {
        int total = 10;
        char[] n;
        ArrayList<Integer> nrs = new ArrayList<Integer>();
        int sum = 0;
        String x = "";
        if(N<=9)
            return N;
        else
        {
            while(true)
            {   
                x = Integer.toString(total);
                n = x.toCharArray();
                for(char c : n)
                {
                    nrs.add(Character.getNumericValue(c));
                }
                for(Integer i : nrs)
                {
                    sum = sum + i;
                }
                if(sum == N)
                {
                    return total;
                }
                total++;
            }
        }

Answer 1

您的标题和描述有点不一致，所以我可能误解了这个问题，但无论如何，工作都很有趣。

但我认为您要求一种算法来生成最小的数值，其以 10 为基数的数字加起来为 N。(问题可能更适合数学交换。)

一个假设:

N > 0

进行了一些观察:

1. 任何单个 10 进制数字的最大值为 9。
2. w位能得到的最大N为Math.pow(10,w) - 1 。 (例如，如果 w 是 2 位数字，则最大数字为 (10**2)-1 或 99。
3. 要与 N 相加的数字的最小位数 x 必须为 ceil(N/9)。 (例如，对于 N=20，该值必须至少有 3 位数字，因为 2 位数字之和的最大值为 18=9+9。)

因此，问题被简化为最小化最高有效数字，因为无论较小的数字如何，它都代表尽可能小的数字。

因此，为了最小化最高有效数字，应该最大化剩余的数字，即 (x-1) 9。

因此假设 x 被计算为最小位数:

x = ceil(N/9)               // e.g. N=82, x=10

那么最低有效数字是一系列 (x-1) 9:

y = pow(10,(x-1))-1         // 999999999

因此最小化最高有效数字变为

z = ((N - (9 * (x-1))) * pow(10,(x-1))   // 1000000000

然后结果是

r = (z + y)                // 1999999999

那么如何证明它是数字之和为N的最小可能数呢？

请注意，数字很快就会变大，因此如果您需要处理 N 的任何值，则需要使用 BigInteger它可以处理任意精度。

<小时/>

这里尝试证明:

假设存在 m其值小于r (上):

m < r

假设 m 的位数少于 r，根据定义满足条件。

但是如果

SUM(digits of m) == SUM(digits of r) == N

并且 r 对于 m 所具有的每个数字都有一个“9”(除了最高有效数字之外的所有 9)并且 r 有一个额外的数字，因此没有 m可以更少的数字并满足上述条件。

假设m位数相同且小于 r 。在这种情况下小于 r m 的最高有效数字必须小于 r 的最高有效数字。由于 r 的剩余数字(如果有)是 9，“m”不可能有剩余数字，这可能相当于一个数字来弥补最高有效数字的差异，因此 m位数不能相同且最高有效位小于 r .

如果m具有相同的位数，但最高有效位大于 r那么根据定义是一个更大的数字。

如果m位数多于 r那么根据定义是一个更大的数字。