【C语言】C语言⻘蛙跳台阶问题--递归问题

简介: 【C语言】C语言⻘蛙跳台阶问题--递归问题

一、青蛙跳台阶问题

青蛙跳台阶问题是一个经典的递归问题,可以使用递归方法来解决。

问题描述:有n级台阶,青蛙每次可以跳1级台阶或者2级台阶,问青蛙跳上n级台阶有多少种不同的跳法。

解决方法:

当n=1时,只有一种跳法。

当n=2时,有两种跳法:跳一次2级台阶或者跳两次1级台阶。

当n>2时,青蛙的第一次跳有两种选择:跳一级台阶或者跳两级台阶。


如果青蛙第一次跳一级台阶,那么跳上剩下的n-1级台阶的跳法数目为f(n-1)

如果青蛙第一次跳两级台阶,那么跳上剩下的n-2级台阶的跳法数目为f(n-2)

所以,跳上n级台阶的总跳法数目为f(n) = f(n-1) + f(n-2)

下面是使用递归方法实现的C代码:

#include <stdio.h>

// 递归函数
int jump(int n) 
{
    if (n == 1) 
    {
        return 1;
    } 
    else if (n == 2) 
    {
        return 2;
    } 
    else 
    {
        return jump(n-1) + jump(n-2);
    }
}

int main() {
    int n;
    printf("请输入台阶数:");
    scanf("%d", &n);
    int result = jump(n);
    printf("跳上%d级台阶的跳法数目为:%d\n", n, result);
    return 0;
}

二、求解第n个斐波那契数

斐波那契数列是一个以递归方式定义的数列,其中每个数字是前两个数字的和。斐波那契数列的前几个数字是0、1、1、2、3、5、8、13等等。

以下是使用递归方式求解第n个斐波那契数的C语言代码:

#include <stdio.h>
int fibonacshu(int n) 
{
    if (n <= 1) 
    {
        return n;
    }
    return fibonacshu(n - 1) + fibonacshu(n - 2);
}

int main() 
{
    int n;
    printf("请输入要求解的斐波那契数的位置:");
    scanf("%d", &n);
    printf("第%d个斐波那契数为:%d\n", n, fibonacshu(n));
    return 0;
}

这段代码中,fibonacshu函数用于递归地求解第n个斐波那契数。当n小于等于1时,直接返回n。否则,递归地计算第n-1个斐波那契数和第n-2个斐波那契数的和。

main函数用于输入要求解的斐波那契数的位置,并调用fibonacshu函数进行计算,最后输出结果。

三、判断一个字符串是否是回文字符串

回文字符串是指正着读和倒着读都一样的字符串。

要判断一个字符串是否是回文字符串,可以使用递归的方式进行判断。下面是一个递归函数来判断字符串是否是回文字符串:

分析:

在C语言中,字符串是一个字符数组,每个字符都有一个对应的索引。字符串的索引是从0开始的,也就是第一个字符的索引为0,第二个字符的索引为1,依此类推。

例如,对于一个字符串 “level”,它包含5个字符,每个字符的索引如下:

字符:     l     e     v     e     l
索引:     0     1     2     3     4

在C语言中,我们可以使用索引来访问字符串中的单个字符,例如 str[0] 表示字符串的第一个字符,str[1] 表示字符串的第二个字符,以此类推。

需要注意的是,字符串的最后一个字符的索引是字符串长度减1,因为索引是从0开始计数的。如果一个字符串的长度为n,那么最后一个字符的索引就是n-1。

#include <stdio.h>

int Palindrome_string(char str[], int start, int end)
{
    if (start >= end)
    {
        return 1;
    }
    else if (str[start] != str[end])
    {
        return 0;
    }
    else
    {
        return Palindrome_string(str, start + 1, end - 1);
    }
}

int main() 
{
    char str[] = "level";
    int len = strlen(str);

    int result = Palindrome_string(str, 0, len - 1);

    if (result == 1)
    {
        printf("该字符串是回文字符串\n");
    }
    else
    {
        printf("该字符串不是回文字符串\n");
    }

    return 0;
}

在此递归函数中,我们首先检查字符串的起始索引是否大于等于结束索引。如果是,说明已经检查完了字符串的所有字符,且每个字符都相等,所以返回1,表示是回文字符串。

如果起始索引和结束索引对应的字符不相等,说明字符串不是回文字符串,返回0。

如果起始索引和结束索引对应的字符相等,我们将起始索引加1,结束索引减1,然后再次调用递归函数,继续检查剩余的字符。


相关文章
|
9天前
|
算法 程序员 编译器
C语言初阶③(函数)知识点+编程作业(递归模拟strlen,pow)
C语言初阶③(函数)知识点+编程作业(递归模拟strlen,pow)
17 0
|
1天前
|
C语言
万字详解:C语言三子棋进阶 + N子棋递归动态判断输赢(二)
我们可以通过创建并定义符号常量NUMBER,来作为判断是否胜利的标准。如三子棋中,令NUMBER为3,则这八个方向中有任意一个方向达成3子连珠,则连珠的这个棋子所代表的玩家获胜。
11 1
|
1天前
|
算法 C语言 C++
万字详解:C语言三子棋进阶 + N子棋递归动态判断输赢(一)
三子棋游戏设计的核心是对二维数组的把握和运用。
12 1
|
1天前
|
机器学习/深度学习 编译器 C语言
C语言(6)----函数的递归思想
C语言(6)----函数的递归思想
8 0
|
1天前
|
C语言
青蛙跳台阶问题的递归实现(C语言)
青蛙跳台阶问题的递归实现(C语言)
|
1天前
|
C语言
汉诺塔————经典递归问题(C语言实现)
汉诺塔————经典递归问题(C语言实现)
|
1天前
|
C语言
C语言递归练习
C语言递归练习
|
5天前
|
机器学习/深度学习 算法 编译器
【C语言】函数 ---- 函数的嵌套调用和链式访问、函数的声明和定义、变量的声明和定义、函数递归与迭代、递归时的栈溢出问题
【C语言】函数 ---- 函数的嵌套调用和链式访问、函数的声明和定义、变量的声明和定义、函数递归与迭代、递归时的栈溢出问题
24 0
|
8天前
|
C语言
【C语言】青蛙跳台阶 —— 详解
【C语言】青蛙跳台阶 —— 详解
|
8天前
|
算法 编译器 C语言
【C语言】函数和递归
【C语言】函数和递归