利用递归完成以下题目。有一农场主有一双绵羊，一年后成长为大绵羊，从第二年开始，每对大绵羊生一对小绵羊。假设绵羊一年繁衍一次，繁衍一次需要一年，不考虑绵羊的死亡，设计算法求第n年的绵羊总数
#include <stdio.h>
int get_sheep_count(int year) {
if (year <= 2) { // 第一年和第二年都只有 1 对
return 2;
} else {
// 前一年绵羊的总数
int last_year_sheep = get_sheep_count(year - 1);
// 再前一年绵羊的总数
int pre_last_year_sheep = get_sheep_count(year - 2);
// 当前年绵羊的总数等于前两年的绵羊总数之和
return last_year_sheep + pre_last_year_sheep;
}
}
int main() {
int n;
printf("请输入要查询的年份：\n");
scanf("%d", &n);
printf("第%d年共有%d只绵羊。\n", n, get_sheep_count(n));
return 0;
}
这是一个经典的递归问题，可以使用递归函数来求解。递归的基本思路是将一个大问题划分为若干个相似的小问题，并且这些小问题与大问题的求解方式是相同的。然后使用递归函数将这些小问题逐层调用，直到遇到边界条件，最后将所有结果合并起来得到最终结果。
根据题意，从第二年开始，每对大绵羊生一对小绵羊，因此在第n年共有F(n) = F(n-1) + F(n-2)只绵羊。其中F(n-1)表示一年前的绵羊总数，F(n-2)表示两年前的绵羊总数。
对于递归函数，我们可以定义一个名为get_sheep_count的函数，以当前年份n作为输入参数，返回第n年的绵羊总数。当n等于1或2时，我们直接返回1表示开始的一对绵羊；当n大于2时，我们递归调用get_sheep_count函数得到前两年的绵羊总数，并返回当前年份的绵羊总数。
下面是详细的代码实现：
def get_sheep_count(n):
if n == 1 or n == 2:
return 1
else:
return get_sheep_count(n-1) + get_sheep_count(n-2)
# 测试
n = 5
count = get_sheep_count(n)
print(f"第{n}年的绵羊总数为：{count}")
在上述代码中，我们测试了第5年的绵羊总数。输出结果为：
第5年的绵羊总数为：5
可以看到，第5年的绵羊总数为5，验证了上述递归函数的正确性。
由二叉树的前序遍历和中序遍历能确定唯一的一棵二叉树，用C语言或者C++实现由已知某二叉树的前序遍历序列和中序遍历序列，生成一棵用二叉链表表示的二叉树，并打印出后续遍历序列的算法。（算法要求有定义，且有主函数）
引用库函数
#include
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include
using namespace std;
结构体定义
typedef struct st
{
char data;
struct st *r,*l;
}tree;
char a[50],b[50];
建树方法
tree*create(char a[],char b[],char n)
{
int i;
tree *t;
if(n==0)
return NULL;
t=(tree*)malloc(sizeof(tree));
t->data=a[0]; //先建树根.
for(i=0;i<n;i++) //在中序串中找与当前前序串中第一个对应的数据
{
if(b[i]== a[0])
break;
}
/**********************
以题目中的
先 DBACEGF
中 ABCDEFG
则 i = 3
左子树的参数：a+1,b,i
右子树的参数：a+1+i,b+1+i,n-1-i
***********************/
t->l=create(a+1,b,i);
t->r=create(a+i+1,b+i+1,n-i-1);//右子树中有n-1-i个元素
return t;
}
遍历方法
tree*FirstandMiddlecreate(char a[],char b[],char n)//题目的变体，知道中序后序输出先序
{
int i;
tree *t;
if(n==0)
return NULL;
t=(tree*)malloc(sizeof(tree));
t->data=a[n-1]; //先建树根.
for(i=0;i<n;i++) //在中序串中找与当前前序串中第一个对应的数据
{
if(b[i]== a[n-1])
break;
}
/**********************
以题目中的
中 ABCDEFG
后 ACBFGED
***********************/
t->l=create(a,b,i);
t->r=create(a+i,b+i+1,n-i-1);//右子树中有n-1-i个元素
return t;
}
void PostOrder(tree*t)
{
if(t)
{
PostOrder(t->l);
PostOrder(t->r);
cout<<t->data;
}
}
void FirstOrder(tree*t)
{
if(t)
{
cout<<t->data;
PostOrder(t->l);
PostOrder(t->r);
}
}
/*************
层次遍历
************/
void levelOrder(tree*t)
{
queue<tree*>q;//辅助队列
q.push(t);
while(!q.empty())
{
t=q.front();
q.pop();
if(t)
{
cout<<t->data;
q.push(t->l);
q.push(t->r);
}
}
}
主函数测试
int main()
{
cin>>a>>b;
int n=strlen(a);
tree*t;
t=create(a,b,n);
PostOrder(t);
cout<<endl;
levelOrder(t);
cout<<endl;
return 0;
}