面试题

问题：对于任意一个正整数 N，按以下操作把它转化为一个单一数字（大于 0 小于 10的数）：

把 N 的各位上数字相加，若得到的结果不是一个单一数字，就把结果的各位上的数字相加，

若得到的结果还不是一个一位数，就还把结果的各位上的数字相加，

……

直到结果为一个单一数字为止。

如：2345

2＋3＋4＋5＝14

1＋4＝5 结果就为 5。

请写出一个方法，当传入任意一个正整数时，返回它按以上操作所得到的单一数字。

 

分析：如何算出各位上的数字是关键，对于任意一个正整数 N 我们让它对 10 取模，就可以得它的个位数字，由此我们不难想出如下解法：

个位数字：n₀=N

十位数字：n₁=N/10

百位数字：n₂=N/100

……

k 位数字：n_k=N/10^k

把 N₁=n₀+n₁+n₂+...+n_k 的结果再按上述操作，然后再按上述操作，直到得到一个单一数字为止。由此我们有以下算法：

算法 1：递归算法：

public static int getSingleNum1(int N) { int result = 0; // 保存返回结果 /* * 每次循环让N模10，即得到相对应位上的数字， 用result来保存这个模10结果， * 然后让N除10 直到N除10的结果等于0，停止循环 */ while (N > 0) { result += (N % 10); N /= 10;11 } /* * 若result小于10(即已经为单一数字)直接返回 * 若大于等于10则对其进行同样的操作（递归），直到返回的结果小于10 */ if (result < 10) { return result; } else { return getSingleNum1(result); } }

 

算法 2：对于一个递归算法我们可以对其进行消除递归：

public static int getSingleNum2(int N) { int result = N; // 保存返回结果 /* * 外层循环：每次把内层循环得到的结果赋值给N， 直到N的结果小于10为止 * 内层循环：每次循环让N模10，即得到相对应位上的数字， * 用result来保存这个模10结果，然后让N除10 直到N除10的结果等于0，停止循环 */ while ((N = result) >= 10) { result = 0; while (N > 0) { result += (N % 10); N /= 10; } } return result; // 返回结果 }