F - Digital Roots HUOJ

发布时间:2024年01月19日

题目

The digital root of a positive integer is found by summing the digits of the integer. If the resulting value is a single digit then that digit is the digital root. If the resulting value contains two or more digits, those digits are summed and the process is repeated. This is continued as long as necessary to obtain a single digit.
正整数的数字根是通过对整数的数字求和来找到的。如果结果值为个位数,则该数字为数字根。如果结果值包含两个或多个数字,则对这些数字求和并重复该过程。只要有必要,就会继续这样做以获得一位数。

For example, consider the positive integer 24. Adding the 2 and the 4 yields a value of 6. Since 6 is a single digit, 6 is the digital root of 24. Now consider the positive integer 39. Adding the 3 and the 9 yields 12. Since 12 is not a single digit, the process must be repeated. Adding the 1 and the 2 yeilds 3, a single digit and also the digital root of 39.
例如,考虑正整数 24。将 2 和 4 相加得到的值为 6。由于 6 是个位数,因此 6 是 24 的数字根。现在考虑正整数 39。将 3 和 9 相加得到 12。由于 12 不是个位数,因此必须重复该过程。将 1 和 2 相加,等于 3,一个位数,还有 39 的数字根。

Input

The input file will contain a list of positive integers, one per line. The end of the input will be indicated by an integer value of zero.
输入文件将包含一个正整数列表,每行一个。输入的末尾将由零的整数值表示。

Output

For each integer in the input, output its digital root on a separate line of the output.
对于输入中的每个整数,在输出的单独行上输出其数字根。

Sample

InputcopyOutputcopy
24
39
0
6
3

思路

如果单纯的按数字来算,由于数据范围未知,如果按数字来算,一次次的计算很复杂,并且容易造成时间超限,所以本题我们采用超过一个就变一次,这样可以降低时间复杂度,从而达到题目想要的目的。具体代码如下所示。

代码实现

#include <bits/stdc++.h>
using namespace std;
int main() {
	string s;//将数字看成字符串
	int i, t ;
	while (cin >> s, s != "0") {//多实例
		t = s[0] - '0';//将t设置成第一个数
		for (i = 1; i < s.size(); i++) {
			t += s[i] - '0';//从第二个数开始加
			while (t > 9) {
				t = t / 10 + t % 10;
			}//一旦超过了两位数,那么就算该数的数根,从而降低了时间复杂度
		}
		cout << t << endl;
	}
}

总结

本题为了降低时间复杂度,为了避免数字过大,设置了逐位相加的方法,帮我们实现了循环次数的减少同时帮助我们解决了问题。

尾声

本题帮我们熟悉了字符串代替数的方法,帮助我们有效的减少了时间复杂度,同时避免了数据过大从而溢出的问题,如果觉得笔者写的还不错的话,记得留下你的点赞收藏和关注哦~

文章来源:https://blog.csdn.net/2302_79862641/article/details/135700176
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。