计算 Java 中从 1 到 n 的所有数字的数字和

2024年9月10日 | 阅读 9 分钟

在本节中，我们将讨论通过 Java 程序计算 1 到 n 所有数字的数位和的方法。

示例

输入： num = 7

输出

从 1 到 7 的数字中所有数字的数位和为

1 + 2 + 3 + 4 + 5 + 6 + 7 = 28

输入： num = 17

输出

从 1 到 17 的数字中所有数字的数位和为

1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 + 10 + 11 + 12 + 13 + 14 + 15 + 16 + 17

1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 + 1 + 0 + 1 + 1 + 1 + 2 + 1 + 3 + 1 + 4 + 1 + 5 + 1 + 6 + 1 + 7 = 81

解释

在上面的例子中，10 被拆分为 1 + 0，11 被拆分为 1 + 1，12 被拆分为 1 + 2，13 被拆分为 1 + 3，以此类推。

朴素方法

在此方法中，我们将每个数字拆分成其各位数字，然后计算其各位数字之和。观察以下程序。

文件名： ComputeSum.java

public class ComputeSum
{

public int findSum1ToN(int num1, int num2)
{
int res = 0; // initializing result
      
// For every number compute the sum of digits
// starting from 1 to n
for (int y = num1; y <= num2; y++)
{
res = res + findSumofDigits(y);
}

return res;
}
      
// The method is computing the sum of
// the digits in the given number num
public int findSumofDigits(int num)
{
    int s = 0;
    while (num != 0)
    {
        s = s + num % 10;
        num = num / 10;
    }
    
    return s;
}

// main method
public static void main(String argvs[])
{

// creating an object of the class ComputeSum
ComputeSum obj = new ComputeSum();
int n1 = 1;
int n2 = 17;
int result = obj.findSum1ToN(n1, n2);

// displaying the result
System.out.println("The sum of digits of numbers from " + n1 + " to " + n2 + " is: " + result);

n1 = 1;
n2 = 340;
result = obj.findSum1ToN(n1, n2);

// displaying the result
System.out.println("The sum of digits of numbers from " + n1 + " to " + n2 + " is: " + result);

n1 = 1;
n2 = 5;
result = obj.findSum1ToN(n1, n2);

// displaying the result
System.out.println("The sum of digits of numbers from " + n1 + " to " + n2 + " is: " + result);


}
}

输出

The sum of digits of numbers from 1 to 17 is: 81
The sum of digits of numbers from 1 to 340 is: 3367
The sum of digits of numbers from 1 to 5 is: 15

高效方法

更有效的方法有点棘手。需要一些观察才能找到技巧。让我们观察一些计算数字和的模式。

从 1 到 9，很容易计算和，因为我们可以使用前 n 个自然数的和的数学公式，即 (n x (n + 1) / 2)。请注意，单个数字不能拆分。

因此，

1 + 2 + 3 + … + 9 = (9 x (9 + 1)) / 2 = (9 x 10) / 2 = 90 / 2 = 45。

此数学公式的实现很容易，其时间复杂度为 O(1)。

现在，让我们尝试找到 99 以下数字的数位和。为了计算到 99，可以将此任务分解为如下所示的较小任务。

1 到 9 的数字的数位和 = 45

10 到 19 的数字的数位和

20 到 29 的数字的数位和

30 到 39 的数字的数位和

40 到 49 的数字的数位和

50 到 59 的数字的数位和

60 到 69 的数字的数位和

70 到 79 的数字的数位和

80 到 89 的数字的数位和

90 到 99 的数字的数位和

现在，为了计算 10 到 19 的数字的数位和，我们需要像下表所示那样拆分数字。

表 1

数字	第一位数字	第二位数字
10	1	0
11	1	1
12	1	2
13	1	3
14	1	4
15	1	5
16	1	6
17	1	7
18	1	8
19	1	9

第一位数字列中数字的总和为 10，第二位数字列中数字的总和为 (9 x (9 + 1)) / 2 = (9 x 10) / 2 = 90 / 2 = 45

因此，10 到 19 的数字的数位和为 10 + 45。

现在，我们将计算 20 到 29 的数字的数位和。与上表类似，我们创建了以下表。

表 2

数字	第一位数字	第二位数字
20	2	0
21	2	1
22	2	2
23	2	3
24	2	4
25	2	5
26	2	6
27	2	7
28	2	8
29	2	9

第一位数字列中数字的总和为 20，第二位数字列中数字的总和为 (9 x (9 + 1)) / 2 = (9 x 10) / 2 = 90 / 2 = 45

因此，20 到 29 的数字的数位和为 20 + 45。

请注意，包含第二位数字的列在两个表中是相同的。我们也看到了一个模式。

对于 10 到 19，我们得到 10 + 45

对于 20 到 29，我们得到 20 + 45

同样，对于 30 到 39，我们将得到 30 + 45。对于 40 到 49，我们得到 40 + 45。

现在，1 到 99 的数字的数位和将是

45 + 10 + 45 + 20 + 45 + 30 + 45 + 40 + 45 + … + 90 + 45

= 45 x 10 + 10 + 20 + 30 + 40 + … + 90

= 45 x 10 + 10 x (1 + 2 + 3 + 4 + … + 9) = 45 x 10 + 10 x ((9 x (9 + 1)) / 2)

= 45 x 10 + 10 x (45)

= (前 9 个自然数的和) x 10 + 45 x 10

因此，sumDig(99) = sumDig(9) x 10 + 45 x 10

其中 sumDig(n) 是一个计算 1 到 n 的数字的数位和的方法。类似地，

sumDig(999) = sumDig(99) x 10 + 45 x 100

总的来说，sumDig(10ⁿ - 1) = sumDig(10^{n - 1} - 1) x 10 + 45 x (10^{n - 1})

算法

基于上述公式，我们将编写一个算法来计算 1 到 328 的数字的数位和。

步骤 1：将数字 328 拆分为 1 到 299 和 300 到 328。

步骤 2：计算 1 到 299 的数字的数位和。从 1 到 299，我们看到 99 重复了三次：99、199 和 299。因此，1 到 99 的数字的数位和也会重复三次。因此，1 到 299 的数字的数位和为 = 3 x sum(99) + (1 + 2) x 100。

步骤 3：计算 300 到 328 的数字的数位和。和等于 3 x 29 + sumDig(28)。

同样，我们也可以处理其他数字。

算法

根据上述算法，编写了以下代码。

文件名： ComputeSum1.java

public class ComputeSum1
{

// Method to compute the sum of digits in
// the numbers from 1 to num.
public int sumOfDigitsFrom1ToN(int num)
{
// handling the base case: if num < 10 return the sum of
// the first num natural numbers
if (num < 10)
{
return (num * (num + 1) / 2);
}

// pow = the number of digits minus 1 in num
// For 3245, the value of pow is 2
int pow = (int)(Math.log10(num));

int arr[] = new int[pow + 1];
arr[0] = 0; arr[1] = 45;
for (int j = 2; j <= pow; j++)
{
arr[j] = arr[j - 1] * 10 + 45 * (int)(Math.ceil(Math.pow(10, j - 1)));
}

// computing 10 ^ pow 
int p = (int)(Math.ceil(Math.pow(10, pow)));

// Reason For the third and the fourth terms in
// the following line of code
return (msDigit * arr[pow] + (msDigit * (msDigit - 1) / 2) * p + 
msDigit * (1 + num % p) + sumOfDigitsFrom1ToN(num % p));
}

// main method
public static void main(String argvs[])
{
// creating an object of the class ComputeSum1
ComputeSum1 obj = new ComputeSum1();
int n1 = 17;
int result = obj.sumOfDigitsFrom1ToN(n1);

// displaying the result
System.out.println("The sum of digits of numbers from " + 1 + " to " + n1 + " is: " + result);

n1 = 328;
result = obj.sumOfDigitsFrom1ToN(n1);

// displaying the result
System.out.println("The sum of digits of numbers from " + 1 + " to " + n1 + " is: " + result);

n1 = 5;
result = obj.sumOfDigitsFrom1ToN(n1);

// displaying the result
System.out.println("The sum of digits of numbers from " + 1 + " to " + n1 + " is: " + result);

}
}

输出

The sum of digits of numbers from 1 to 17 is: 81
The sum of digits of numbers from 1 to 328 is: 3241
The sum of digits of numbers from 1 to 5 is: 15

时间复杂度：上述程序的时间复杂度为 O(pow²)。这是因为第一次递归调用需要 O(pow) 时间，第二次递归调用需要 O(pow - 1) 时间，第三次递归调用需要 O(pow - 2) 时间。将它们全部加起来，最终的渐近时间复杂度为 O(pow²)。

优化

上面的程序可以进一步优化以将时间复杂度降低到 O(pow)。

文件名： ComputeSum2.java

public class ComputeSum2
{

// Method to compute the sum of digits in
// the numbers from 1 to num.
public int sumOfDigitsFrom1ToN(int num)
{
        int pow = (int)(Math.log10(num));
        int arr[] = new int[num + 1];
        arr[0] = 0; arr[1] = 45;
        for (int j = 2; j <= pow; j++)
        {
            arr[j] = arr[j - 1] * 10 + 45 *
                (int)(Math.ceil(Math.pow(10, j - 1)));
        }
     
        return sumOfDigitsFrom1ToNUtility(num, arr);
    }
    
    public int sumOfDigitsFrom1ToNUtility(int num, int arr[])
    {
        if (num < 10)
        {
            return (num * (num + 1) / 2);
        }
       
        int pow = (int)(Math.log10(num));
        int p = (int)(Math.ceil(Math.pow(10, pow)));
        int msDigit = num / p;
        return (msDigit * arr[pow] + (msDigit * (msDigit - 1) / 2) * p +
            msDigit * (1 + num % p) + sumOfDigitsFrom1ToNUtility(num % p, arr));
    }

// main method
public static void main(String argvs[])
{
// creating an object of the class ComputeSum2
ComputeSum2 obj = new ComputeSum2();
int n1 = 17;
int result = obj.sumOfDigitsFrom1ToN(n1);

// displaying the result
System.out.println("The sum of digits of numbers from " + 1 + " to " + n1 + " is: " + result);

n1 = 328;
result = obj.sumOfDigitsFrom1ToN(n1);

// displaying the result
System.out.println("The sum of digits of numbers from " + 1 + " to " + n1 + " is: " + result);

n1 = 5;
result = obj.sumOfDigitsFrom1ToN(n1);

// displaying the result
System.out.println("The sum of digits of numbers from " + 1 + " to " + n1 + " is: " + result);

}
}

输出

The sum of digits of numbers from 1 to 17 is: 81
The sum of digits of numbers from 1 to 328 is: 3241
The sum of digits of numbers from 1 to 5 is: 15

下一个主题Java 中读取 PDF 文件

计算 Java 中从 1 到 n 的所有数字的数字和

朴素方法

高效方法

算法

算法

优化

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

Java Conversion

Java Misc

计算 Java 中从 1 到 n 的所有数字的数字和

朴素方法

高效方法

算法

算法

优化

相关帖子

How to Take Multiple String Input in Java Using Scanner

Java 中数组转字符串

Java 中的构造函数可以静态吗

Java 中的硬币排列问题

Java 中使用多线程进行单词计数

Java 中构造函数的特点

Java ClassLoader

Primitive Data Types in Java

Java 在线 IDE

Friends Pairing Problem in Java

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器