题目描述(简单难度)
将给定的数字的各个位相加得到新的数字,一直重复这个过程,直到这个数小于 ,将这个数输出。
解法一
开始有点不明所以,直接用递归或者循环按照题目的意思写不就行了吗,先用递归尝试了一下。
没想到直接通过了,上边的递归很简单可以直接写成迭代的形式。
解法二 数学上
看了下 Discuss
,原来要求的数叫做数字根,看下 的定义。
然后是它的用途。
我们把 1
到 30
的树根列出来。
可以发现数根 9
个为一组, 1 - 9
循环出现。我们需要做就是把原数映射到树根就可以,循环出现的话,想到的就是取余了。
结合上边的规律,对于给定的 n
有三种情况。
n
是 0
,数根就是 0
。
n
不是 9
的倍数,数根就是 n
对 9
取余,即 n mod 9
。
n
是 的倍数,数根就是 9
。
我们可以把两种情况统一起来,我们将给定的数字减 1
,相当于原数整体向左偏移了 1
,然后再将得到的数字对 9
取余,最后将得到的结果加 1
即可。
原数是 n
,树根就可以表示成 (n-1) mod 9 + 1
,可以结合下边的过程理解。
所以代码的话其实一句就够了。
当然上边是通过找规律得出的方法,我们需要证明一下。知乎的最高赞 讲的很清楚了,我再把推导和上边的公式一起说一下。
下边是作者的推导。
上边证明了对原数做一个 f
操作,也就是各个位上的数相加,然后不停的做 f
操作,最终的结果对 9
取余和原数 x
对 9
取余是相等的。
不考虑 0
这种特殊情况,不停的做 f
操作,最终得到的数就是 1 - 9
,对 取余的结果是 1 - 8
和 0
。结果是 0
的话对应数根就是 9
,其他情况的数根就是取余结果。
也就是我们之前讨论的。
同样的,我们可以通过 这个式子把上边的几种情况统一起来。
总
这道题的话如果用程序的话很好解决,就是不停的循环即可。解法二数学上的话就很神奇了,一般也不会往这方面想了。
添加好友一起进步~
如果觉得有帮助的话,可以点击 给一个 star 哦 ^^