PTA递归练习

作者：~小明学编程 

文章专栏：C语言基础知识

目之所及皆为回忆，心之所向皆为过往

目录

第一题：捡豆子(递归版)

函数原型

裁判程序

测试数据

我的答案

提交截图

 第二题：母牛生小牛-递归

函数接口定义：

裁判测试程序样例：

输入样例：

输出样例：

第三题：递归 递推

输入格式:

输出格式:

输入样例:

输出样例:

 第四题：递归法求最大公约数

递归法：

程序输入：

程序输出：

函数接口定义：

主程序样例：

输入样例：

输出样例：

第五题：整数转换为字符串

输入格式:

输出格式:

输入样例:

输出样例:

---

第一题：捡豆子(递归版)

题目：

有 n 颗豆子，每次捡 1 ~ 4 颗豆子，一共有多少种捡法？

函数原型

double Pick(int n);

说明：参数 n 是豆子的数量。若 n ＞ 0，则函数值是捡豆子的方法总数，否则函数值为 0。

裁判程序

#include <stdio.h>

double Pick(int n);

int main()
{
    int n;
    scanf("%d", &n);
    printf("%g\n", Pick(n));
    return 0;
}

/* 你提交的代码将被嵌在这里 */

测试数据

输入样例	输出样例
-5	0
0	0
1	1
2	2
3	4
4	8
5	15
35	5.35022e+009

要求：不得使用循环语句。

我的答案

double Pick(int n)
{
    if (n < 0)
        return 0;

    else if (n >= 0 && n < 3)
        return n;

    else if (n == 3)
        return 4;

    else if (n == 4)
        return 8;

    else
        return Pick(n - 1) + Pick(n - 2) + Pick(n - 3) + Pick(n - 4);

    
}

提交截图

 第二题：母牛生小牛-递归

题目：

有一头母牛，它每年年初生一头小母牛。每头小母牛从第四个年头开始，每年年初也生一头小母牛。请编程实现在第n年的时候，共有多少头母牛？递归实现（母牛第一年不生）。

函数接口定义：

int Cow(int n);

该函数返回第n天牛的总数量，递归实现。

裁判测试程序样例：

#include <stdio.h>
int Cow(int n);
int main()
{
    int day;
    scanf("%d", &day);
    printf("%d\n", Cow(day));
    return 0;
}

/* 请在这里填写答案 */

输入样例：

5

输出样例：

6

代码长度限制

16 KB 

时间限制

400 ms   

内存限制

64 MB

我的答案

int Cow(int n)
{
    if (n<=0)
        return 0;
    else if (n < 4&&n>0)
        return n;

    else
        return Cow(n-1) + Cow(n - 3);
}

提交截图

第三题：递归 递推

题目：

大一新生LinYX 最近学了一个新的算法—递归，他发现这个算法可以解决一些高中的数列问题，如果已知f1以及公式fn=a*fn-1+b，求fn很方便。聪明的你也应该已经学会了递归，那就来表现一下吧。

输入格式:

输入包含若干行数据，每行都有4个整数，n，f1,a，b。

输出格式:

输出fn 。每组测试数据显示在不同行。

输入样例:

在这里给出一组输入。例如：

1 4 1 1
1 6 2 3
2 2 1 1

输出样例:

在这里给出相应的输出。例如：

4
6
3

代码长度限制

16 KB

时间限制

400 ms

内存限制

64 MB

我的答案：

#include<stdio.h>
int Lin(int a,int b,int n,int f1)
{
    if(n==1)
        return f1;
    else
        return a*Lin(a,b,n-1,f1)+b;
}
int main()
{
    int n,f1,a,b;
    while(scanf("%d %d %d %d",&n,&f1,&a,&b)!=EOF)
    {
    printf("%d\n",Lin(a,b,n,f1));
        
    }
    
    return 0;
}

提交截图

 第四题：递归法求最大公约数

题目：

两个正整数的最大公约数（Greatest Common Divisor,GCD）是能够整除这两个整数的最大整数。请实现程序，用递归方法计算两个数的最大公约数。

递归法：

当a > b时，a 和 b的最大公约数相当于 a - b 和 b 的最大公约数；

当b > a时，a 和 b的最大公约数相当于 b - a 和 a 的最大公约数；

当a = b时，a 和 b的最大公约数就是 a （或b）；

程序输入：

由用户输入两个正整数

程序输出：

两个正整数的最大公约数。

如果输入的数不是正整数，则程序输出：

Input number should be positive!

函数接口定义：

int Gcd(int a, int b);

其中，a和b是用户输入的两个正整数。

函数返回a和b的最大公约数。

如果a或b小于等于0，则函数返回-1。

主程序样例：

这里给出主函数及对Gcd函数的调用样例：

#include <stdio.h>
int Gcd(int a, int b);
int main()
{
    int a, b, c;
    scanf("%d %d", &a, &b);
    c = Gcd(a,b);
    if (c != -1)
    {
        printf("%d\n", c);
    }
    else
    {
        printf("Input number should be positive!\n");
    }
    return 0;
}

/* 请在这里完成 Gcd 函数*/

输入样例：

在这里给出一组输入。例如：

15 20

输出样例：

在这里给出相应的输出。例如：

5

代码长度限制

16 KB

时间限制

400 ms

内存限制

64 MB

我的答案：
 

#include <stdio.h>
int Gcd(int a, int b);
int main()
{
    int a, b, c;
    scanf("%d %d", &a, &b);
    c = Gcd(a,b);
    if (c != -1)
    {
        printf("%d\n", c);
    }
    else
    {
        printf("Input number should be positive!\n");
    }
    return 0;
}

/* 请在这里完成 Gcd 函数*/

int Gcd(int a,int b)
{
    if(a<=0||b<=0)
        return -1;
    else if(a==b)
        return a;
    else
    {
        if(a>b)
            return Gcd(a-b,b);
        else
            return Gcd(b-a,a);
    }

}

提交截图：

第五题：整数转换为字符串

题目：

将一个整数n转换成字符串。例如；输入483，应得到字符串"483"。其中，要求用一个递归函数实现把一个正整数转换为字符串。

输入格式:

首先输入测试组数T，然后输入T组测试数据。每组测试数据输入一个整数n（-2^31≤n≤2^31-1）。

输出格式:

对于每组测试，输出转换后的字符串。

输入样例:

1
1234

输出样例:

1234

代码长度限制

16 KB

时间限制

400 ms

内存限制

64 MB

我的答案：
 

#include<stdio.h>
void reverse(int n)
{
    if(n<10)
        printf("%d",n);
    else
    {
         reverse(n/10);
         printf("%d",n%10);
    }
}
int main()
{
    int T=0;
    int arr[100]={0};
    scanf("%d",&T);
    for(int i=0;i<T;i++)
    {
        scanf("%d",&arr[i]);
    }
    for(int i=0;i<T;i++)
    {
        reverse(arr[i]);
        printf("\n");
    }
    return 0;
}

提交截图：