面试题

    技术2022-05-13  0

    问题:对于任意一个正整数 N,按以下操作把它转化为一个单一数字(大于 0 小于 10的数):

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

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

    ……

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

    如:2345

    2+3+4+5=14

    1+4=5 结果就为 5。

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

     

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

    个位数字:n0=N

    十位数字:n1=N/10

    百位数字:n2=N/100

    ……

    k 位数字:nk=N/10k

    把 N1=n0+n1+n2+...+nk 的结果再按上述操作,然后再按上述操作,直到得到一个单一数字为止。由此我们有以下算法:

    算法 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; // 返回结果 }


    最新回复(0)