时间戳

首页 > 解决方案 > 字符的拆分和总和

java - 字符的拆分和总和

问题描述

我必须编写一个函数来找到其数字总和为 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++;
            }
        }

标签： javaalgorithmcharinteger

解决方案

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

但是我认为您要求一种算法来产生最小的值，其基数为 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那么根据定义是一个更大的数字。

推荐阅读