数字根（digitalroot）
来源：LeetCode 258
Question：Given a non-negative integer num , repeatedly add all its digits until the result has only one digit.
For example:
Given num = 38 , the process is like: 3 + 8 = 11 , 1 + 1 = 2 . Since 2 has only one digit, return it.
Follow up:
赶小猪>森林王国 Could you do it without any loop/recursion in O(1) runtime?
分析：
数字根(digital root)是⾃然数的⼀种性质，即每个⾃然数都有⼀个数字根。数根是将⼀⾃然数的各个位数相加(即横向相加)，若加完后的值⼤于等于10的话，则继续将各位数进⾏横向相加直到其值⼩于10为⽌。例如54817的数根为7，因为5+4+8+1+7=25，25⼤于10则再加⼀次，2+5=7，7⼩于10，则7为54817的数字根。
上⾯问题即是求⼀个⾮负整数的数字根。很容易想到下⾯这种⽅法解决问题：
#include<stdio.h>
#include<asrt.h>
int addDigits(int num)
{
int temp=0;
分布函数右连续
葡萄籽的功效与作用while(num>=10)
{
temp+=(num%10);
num/=10;
}
temp+=num; //不要忽略最⾼位数
num=temp;
鸟的天堂课文
if(num>=10)
{
num=addDigits(num);//num仍⼤于10，则递归调⽤addDights函数
}
return num;
}
int main()
{
写名人的作文int num;
scanf("%d",&num);
asrt(num>=0); //⾮负整数断⾔
printf("%d\n",addDigits(num));
return0;
}
注意题⽬的延伸：要求我们不使⽤循环/递归复杂度O(1)形容老年人的词语
这⾥⽤到⼀个求数字根的公式：
上述公式的⽂字表述为：0的数字根为0，9的倍数的数字根为9，其他⾃然数的数字根为其除以9的余数。证明过程
上述公式可简单表述为：
所以对于延伸的问题我们可以写出解决⽅法如下：
#include<stdio.h>
#include<asrt.h>
int addDigits(int num)
{
儒道释
return1+(num-1)%9; //直接调⽤公式
}
int main()
{
int num;
scanf("%d",&num);
asrt(num>=0); //⾮负整数断⾔ printf("%d\n",addDigits(num)); return0;
}
