贺州学院ivy


私信TA

用户名:Livy

访问量:21330

签 名:

好好学习,天天向上,汝何秀?

等  级
排  名 131
经  验 7394
参赛次数 5
文章发表 25
年  龄 0
在职情况 学生
学  校 贺州学院
专  业 软件工程

  自我简介:

假猪套天下第一

解题思路:

注意事项:

参考代码:

 /*

这一题我们可以这样子来想递归的,题意是输入N,样例是4,只有1元和2元来分4元

所以,就是把4拆分成多个1和2的组合

所以就是4要么-1,4要么-2


样例如下所示:

4=1+1+1+1
4=2+1+1
4=1+2+1
4=1+1+2
4=2+2

样例是加法,其实也是减法,4减1,或者4减2


递归的结束条件就是当x==0的时候

所以,我用递归的思路是先减1,然后就是减2

然后在减1或者减2之后,进入新的递归函数里,判断减去之后的x是否等于0,等于0那就

说明这是一个合适的拆分种类,于是sum++,结束当前递归,返回之前的上一步


就拿4来说

a层:digui(4);x= 4,进入这个函数,两个if不合适条件,来到digui(x-1),也就是递归(3),进入digui(3);


b层:digui(3);x = 3,进入这个函数,两个if不合适条件,来到digui(x-1),也就是递归(2),进入digui(2);


c层: digui(2)  ; x = 2,进入这个函数,两个if不合适条件,来到digui(x-1),也就是递归(1),进入digui(1);


d层:digui(1);x = 1,进入这个函数,两个if不合适条件,来到digui(x-1),也就是递归(0),进入digui(0);


e层:digui(0);x = 0.进入这个函数,满足了第一个if的条件x==0,然后sum++,结束e层,返回上一层d层。        (从a层看到e层你就可以发现是 4=(a层)1+(b层)1+(c层)1+(d层)1也就是样例的第一个4=1+1+1+1。)


d层:digui(1);x = 1,进入这个函数,digui(x-1)已经运行过了,接下来是下一句代码

digui(x-2);也就是digui(-1),进入e层。


e层:digui(-1);x=-1,进入这个函数,第一个if的x==0不符合,来到下一个if,x<0,x=-1,-1<0,拆分钱不会拆到自己还要给钱的吧?也就是不可能为负数的,然后return,结束e层,返回d层;


d层:digui(1);x = 1,进入这个函数,digui(x-1)和digui(x-2)都已经运行过了,接下来是下一句代码return. 说明d层已经减1和减2都尝试过了,然后结束d层,返回上一层c层,进入c层


............................然后急救按照这样子的思路一直往下走,返回上一层,进入下一层,(太多了,懒得写了......写不动写不动.......)




所以这个递归先判断是否等于0或者小于0,满足0就sum++,结束当前层,返回上一层

然后每一次是先-1,然后在-2,-1进入下一层

*/


#include<iostream>

using namespace std;

int sum = 0;       //记录多少种的数目

void digui(int x){

    if (x == 0){sum++;return;}

    if (x < 0)return;

    digui(x - 1);

    digui(x - 2);

    return;

}

int main(){

    int x;

    cin >> x;

    digui(x);

    cout << sum;

    return 0;

}


 

0.0分

11 人评分

  评论区

学习了!
2020-12-11 20:52:17
  • «
  • 1
  • »