求C语言用递归写一道题，最好有注释

chongming

一看到这种就头晕，半天不知道怎么写

侃遍天下无二人

斐波那契数列， f(1) = 1, f(2) = 1, f(3) = f(2) + f(1)，...
递归写法自己上网查，不想用递归也完全可以迭代的

---------
才发现要输出40个月的，你确定要用递归吗，别忘了递归的复杂度接近 2^n

cattie

[C++] 纯文本查看 复制代码

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int born[21]; //第n年有多少兔子出生
    memset(born,0,sizeof(born)); //初始化
    for(int i=1;i<21; i++)
    {
        if(i<3) born[i] = 0;//前两月没有兔子出生
        else if (i<6) born[i] = 2; //3 4 5月每月出生一对兔子
        else 
        {
            for(int j = 1; j<=i-3; j++)
                born[i] += born[j];// 三个月前出生的所有兔子已经成熟，每月出生三个月前成熟所有兔子数量的兔子
            born[i] += 2; //再加上之前的一对兔子
        }
        //cout<<born[i]<<endl; //Debug用
    }
    for(int i = 1; i <= 20; i++)
    {
        static int sum = 2;
        sum += born[i];
        cout<<sum<<endl;
    }
}

时间复杂度O(n^2)，嗯还好，也就是打表的水平。
不知道思路对不对，我算法很渣的。

tflyr

#include <stdio.h>

// 定义递归函数，计算第n个月兔子的总数
long long int rabbit(int month) {
    // 基准情况：前两个月兔子的总数为1对
    if (month == 1 || month == 2) {
        return 1;
    }
    // 递归情况：第n个月兔子的总数等于前两个月兔子总数之和
    return rabbit(month - 1) + rabbit(month - 2);
}

int main() {
    int numMonths = 40;

    for (int i = 1; i <= numMonths; i++) {
        long long int rabbitPairs = rabbit(i);
        printf("第%d个月的兔子总数为：%lld\n", i, rabbitPairs);
    }

    return 0;
}


以上代码由AI生成

SineL

代码：
/*
每一对兔子在出生的第三个月就能（成熟）生育一对兔子，即第i个月每出生的一对兔子，在第i+2个月就相应生育一对新兔子。
那么,第k个月出生的兔子数目=第k个月时的成熟兔子总数=第k-2个月时的兔子总数数(k>=3)。
当月兔子总数=前一个月兔子总数+当月出生兔子总数。。
设第n个月的兔子总数为f(n)，递推关系：f(n)=f(n-1)+f(n-2)，n>=3
*/

#include<stdio.h>

//递归方法
int rabbit(int month){
    if(month<3){
        return 2;
    }
    return rabbit(month-1)+rabbit(month-2);//当月兔子总数=上月兔子总数+当月出生兔子总数
}

int main(){
    int months=0;
    scanf("%d",&months);
    for(int i=1;i<=months;i++){
        printf("第%d个月兔子总数=%d\n",i,rabbit(i));
    }
    return 0;
}

zhuxiangyu1024

算法尽量靠搜素引擎很多人会讲解的很细，来论坛提问会很影响你的学习效率。

侃遍天下无二人

cattie 发表于 2023-7-27 22:19
本帖最后由 cattie 于 2023-7-27 22:28 编辑
[mw_shl_code=cpp,true]#include
using namespace std;

迭代的复杂度应该是O(n)才对。f[0]=1, f[1]=1，n≥2时，f[n] = f[n-1] + f[n-2]，这就完了

cattie

侃遍天下无二人 发表于 2023-7-28 09:20
迭代的复杂度应该是O(n)才对。f[0]=1, f[1]=1，n≥2时，f[n] = f[n-1] + f[n-2]，这就完了

嗯，迭代快一点，我这是直接用时间换空间了

Do_zh

第三个数是前两个数之和。

侃遍天下无二人

cattie 发表于 2023-7-28 09:21
嗯，递归快一点，我这是直接用时间换空间了

递归的复杂度才是接近O(n^2)的，而且更费栈空间，迭代只有O(n)