题目
正整数的数字根是通过对整数的数字求和来找到的。如果结果值为个位数,则该数字为数字根。如果结果值包含两个或多个数字,则对这些数字求和并重复该过程。只要有必要,就会继续这样做以获得一位数。
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
输入文件将包含一个正整数列表,每行一个。输入的末尾将由零的整数值表示。
Output
对于输入中的每个整数,在输出的单独行上输出其数字根。
Sample
Inputcopy | Outputcopy |
---|---|
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://www.toymoban.com/news/detail-816460.html
文章来源地址https://www.toymoban.com/news/detail-816460.html
到了这里,关于F - Digital Roots HUOJ的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!