烟火尘霄

用户名：tzu190341102

访问量：63267

签　名：

等　　级
排　　名	95
经　　验	8670
参赛次数	1
文章发表	6
年　　龄	0
在职情况	学生
学　　校	泰州学院
专　　业

　　自我简介：

TA的其他文章

[编程入门]猴子吃桃的问题（C语言代码）
浏览：15374

[编程入门]筛选N以内的素数-题解（C语言代码）
浏览：2500

[递归]母牛的故事（C语言代码）
浏览：38469

你可能喜欢

台球碰撞（C++代码）

2004年秋浙江省计算机等级考试二级C 编程题(1) （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

C语言训练-8除不尽的数（C语言代码）暴力解法，答案只有一个，直接输出就好了

C语言程序设计教程（第三版）课后习题9.6 （C语言代码）

优质题解

[递归]母牛的故事（C语言代码）

　　作者: 烟火尘霄　　　　发表时间：2021-01-26 21:22:22 浏览：38469　|　评论：74　

原题链接：[递归]母牛的故事

解题思路:
审清题干，养成习惯。

有一头母牛，它每年年初生一头小母牛。每头小母牛从第四个年头开始，每年年初也生一头小母牛。是不是有点似曾相识？没错，这道题和斐波那契数列很相似，只不过递增的规律稍微变了一些。
一个输入，一个输出，多组测试用例，输入0结束，这是首先要明确的，所以要用到循环，并且输入0时结束循环。

我们先来分析一下这道题的规律吧。

这里简单地列一个表格：

年份	1	2	3	4	5	6	7	8	9
母牛数量	1	2	3	4	6	9	13	19	28

有没有看出一些端倪？没错，f_n=f_n-1+f_n-3(n>3)。记不记得斐波那契数列的公式？f_n=f_n-1+f_n-2(n>2)。说到这里，想必大家都会做了吧？

注意，这里题目明确要用递归的方法，所以大家尽量还是用递归来做，虽说用数组的方法也能提交。。。

既然是递归，那就离不开三点：找重复、找变化、找边界。

（1）找重复：就是递归时重复操作的部分，详见上面的公式；

（2）找变化：就是递归时参数的变化，上面的公式一起囊括了；

（3）找边界：就是递归脱出的条件，这里很明显是n<=3，因为此时上面的公式不适用了。

写成分段函数的形式就是：

n ,n<=3

f(n)= (没法打大括号，各位将就看)

f(n-1)+f(n-3) ,n>3

注意事项：

（1）注意测试用例是多组，要想办法循环输入并输出；

（2）注意程序运行结束的条件是输入0时结束；

（3）注意递归方法的脱出条件是n<=3；

参考代码:

# include<stdio.h>

int fun(int n)
{
	if(n<=3) return n;
	else return fun(n-1)+fun(n-3);
}
int main()
{
	int n;
	while(scanf("%d",&n) && n)
		printf("%d\n",fun(n));

	return 0;
}

如有裨益，吾之幸也。祝大家编程进步。

0.0分

1038 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

　　评论区

Kanays

按照参考代码打出来后显示超时了，有没有大佬告诉我应该怎么修改啊？

2022-10-15 21:14:45

牛小白

题解完整版：
#include<stdio.h>
int fun(int n)
{
    if(n<=3) return n;
    else return fun(n-1)+fun(n-3);
}
int main()
{
    int i;
    int ret;
   while(scanf("%d",&i)!=EOF)
   {
       if(0<i && i<55) 
       {
          ret=fun(i);
          printf("%d\n",ret);
        }
   }

   return 0;
}

2022-10-07 18:31:32

星

#define _CRT_SECURE_NO_WARNINGS
# include<stdio.h>
int f(int n) {
    if (n <= 4) {
    return n;
    }
    else {
        return f(n - 1) + f(n - 3);
    }
}


int main()
{   
    int n;
    scanf("%d", &n);
    printf("%d", f(n));
    return 0;
}
这个为什么会错啊

2022-09-27 16:15:55

徘浅墨飞

延时是因为最后输出内容有个空格

2022-06-02 20:36:54

玮

这种写法会显示超时，将判断条件n<=3改为n<=4就行了，如下
原：if(n<=3) return n;
改：if(n<=4) return n;
这样改会少一层嵌套。

2022-05-20 14:14:16

cheneyxu 2022-05-24 15:06:17 |

我也出了这个问题，怎么也看不出来哪里有问题可以优化，谢谢层主（笑哭）

苟富贵 2022-09-20 17:09:02 |

long i; if(x<4) return x;大哥为什么我一改就提醒alarm clock

牛小白 2022-10-07 18:05:13 |

将循环输入哪里判断条件改为 while(scanf("%d",&n) ！=EOF)

牛小白 2022-10-07 18:05:31 |

@19974674810 将循环输入哪里判断条件改为 while(scanf("%d",&n) ！=EOF)

很认真的人 2022-10-30 20:43:03 |

确实，把三改成四后就行了，感觉好离谱啊

玮 2022-11-11 19:51:21 |

@dotcpp0616402 递归是很占内存的，少一层会少很多

myq 2024-03-25 20:27:26 |

牛，

LRY

我有一个疑问为什么题解第一年都是一头母牛，第一年母牛自己加上生出来的母牛不是两头吗？为什么优质题解都是一头

2022-04-10 11:36:55

刘国立194 2022-06-30 15:42:04 |

因为她是小母牛哈哈

楠荀 2022-08-18 11:16:42 |

这题有点不太严谨，学到知识就好

坚 2022-08-31 14:43:54 |

因为牛是年初生的，她可能是年中被投进去的~

郁猪猪 2022-09-02 15:59:12 |

关于我刚买了一头牛第二题就生了一个小母牛那件事

星辰大海

可是题目要求先输入一组数据，在输出相应的，应该要用数组吧，不太明白

2022-04-09 07:57:55

Kaiiiiiix

#include<stdio.h>
#include<stdlib.h>
int fun(int n)
{
	if(n<=4)return n;
	
	else return fun(n-1) +fun(n-3);
}

int main(void)
{
	int y;
	while(scanf("%d",&y)==1)
	{
		if(y==0||y>=55)
		break;
		printf("%d\n",fun(y));
	 } 
	return 0;
}

2022-04-06 15:54:44