栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 软件开发 > 后端开发 > Java

【第22天】给定一个整数 n ,求它的各个数位之和 | 递归与循环

Java 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

【第22天】给定一个整数 n ,求它的各个数位之和 | 递归与循环

本文已收录于专栏
《Java入门一百例》

学习指引
  • 序、专栏前言
  • 一、【例题1】
    • 1、题目描述
    • 2、解题思路
    • 3、模板代码
      • 1、循环写法
      • 2、递归写法
    • 4、代码解析
  • 二、【例题2】
    • 1、题目描述
    • 2、解题思路
    • 3、模板代码
    • 4、代码解析
  • 三、推荐专栏
  • 四、课后习题

序、专栏前言

   本专栏开启,目的在于帮助大家更好的掌握学习Java,特别是一些Java学习者难以在网上找到系统地算法学习资料帮助自身入门算法,同时对于专栏内的内容有任何疑问都可在文章末尾添加我的微信给你进行一对一的讲解。
   但最最主要的还是需要独立思考,对于本专栏的所有内容,能够进行完全掌握,自己完完全全将代码写过一遍,对于算法入门肯定是没有问题的。
   算法的学习肯定不能缺少总结,这里我推荐大家可以到高校算法社区将学过的知识进行打卡,以此来进行巩固以及复习。
  学好算法的唯一途径那一定是题海战略,大量练习的堆积才能练就一身本领。专栏的任何题目我将会从【题目描述】【解题思路】【模板代码】【代码解析】等四板块进行讲解。

一、【例题1】 1、题目描述

  给定一个正整数 n ( 1 ≤ n ≤ 1000000 ) n(1 le n le1000000) n(1≤n≤1000000),求它的各个数位之和相加是多少?

2、解题思路

  对于该问题的核心在于,每次取下数字最末尾的一位,然后累加,直到数字为0。对于这个操作,我们可以发现,使用循环和递归都可以很好解决。

3、模板代码 1、循环写法
import java.util.*;
public class Main{
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n=sc.nextInt();
        System.out.println(sum(n));
    }
    static int sum(int x){
        int res=0;
        while (x!=0){
            res+=x%10;
            x/=10;
        }
        return res;
    }
}
2、递归写法
import java.util.*;
public class Main{
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n=sc.nextInt();
        System.out.println(sum(n));
    }
    static int sum(int x){
       if (x<10) return x;
       return x%10+sum(x/10);
    }
}
4、代码解析
  • ( 1 ) (1) (1)对于每个数x,我们每次需要对其剔除末尾数,然后再加上,直到x为0。所以我们可以使用循环,%取余运算能帮助我们获得最后一位数,/能剔除最后一位数。
  • ( 2 ) (2) (2)考虑递归写法。对于每层递归,我们只关心它此时最后一位数字的值,以及它剩下的数的数位之和,我们只需要把它递归丢下去即可。当然如果这个数小于10,就不能在递归下去了,我们直接返回它的值,这也就是我们的递归出口。题意很明显符合我们使用递归的两种要求:
  • ( 1 ) (1) (1)子问题考虑的事必须与原问题一致,且更为简单
  • ( 2 ) (2) (2)递归不能无限递归,必须需要有一个出口进行返回
二、【例题2】 1、题目描述

  给定一个非负整数 n ( 0 ≤ n ≤ 2 31 − 1 ) n(0 leq n leq 2^{31}-1) n(0≤n≤231−1),反复将各个位上的数字相加,直到结果为一位数。返回这个结果。

2、解题思路

  对于当前的数字x,获得它的所有数位之和,是一个很简单的操作,像上面两种方法都可以。但问题在于,得到的数之和并不是答案,而是要继续同样的操作。所以我们应当想到什么?递归!!! 子问题的处理操作和父问题一样,正是如此我们可以采用递归处理得到的新结果,当然递归出口题目明显提到了,当结果为1位数返回。

3、模板代码
import java.util.*;
public class Main{
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n=sc.nextInt();
        System.out.println(addDigits(n));
    }
    static int addDigits(int x){
       if (x<10) return x;
       int sum=0;
       while (x>0){
           sum+=x%10;
           x/=10;
       }
       return addDigits(sum);
    }
}
4、代码解析
  • ( 1 ) (1) (1)明显我们是将循环与递归结合起来解决了这道问题,当然两个循环或者两个递归都能解决,但这样写代码更简洁且可读性更强。
  • ( 2 ) (2) (2)这题还可以通过数学推导直接在 O ( 1 ) O(1) O(1)的时间复杂度内求得答案,具体的数学推导可以在课后习题内的题解中看。
class Solution {
   public int addDigits(int num) {
       return (num - 1) % 9 + 1;
   }
}

三、推荐专栏
《零基础学算法100天》
四、课后习题
序号题目链接难度评级
1 各位相加1
 学习有疑问?
转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/980649.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号