2013
11-19

# C语言程序设计-Digital Roots[综合应用]

10065 选做题：Digital Roots

【问题描述】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.

【输入形式】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.

【输出形式】For each integer in the input, output its digital root on a separate line of the output.

【样例输入】24

39

0

【样例输出】6

3

【样例说明】样例如上。

【评分标准】本题共4个测试点，每个测试点0.25分，共1.0分。

#include <stdio.h>
int root(int);
int distribute(int);
int main()
{
int num;
while (scanf("%d",&num)&&num != 0)
{
// 	printf("%d\n",num);
printf("%d\n",root(num));
// 	int temp = distribute(num);
// printf("%d\n",temp);
}
return 0;
}

int root (int n)
{
if (n < 10)
{
return n;
}
else
{
//查分n
return root(distribute(n));
}
}

int distribute(int n)
{
int count = 0 ;
int tem = n;

while (tem != 0)
{
count += tem % 10;
tem = tem / 10;
}
return count;

}

1. 约瑟夫也用说这么长……很成熟的一个问题了，分治的方法解起来o(n)就可以了，有兴趣可以看看具体数学的第一章，关于约瑟夫问题推导出了一系列的结论，很漂亮

2. 问题3中，GetRightPosition()和GetLeftPosition()与STL中的upper_bound()和lower_boune()的代码实现一样吗？