C语言基础算法练习：整数拆分与青蛙跳台阶问题

本文介绍了两个基础的算法练习题，分别是输出一个整数的每一位和青蛙跳台阶问题。

1. 输出一个整数的每一位

输入：输入一个整数a(大小在int数据范围内) 输出：输出每一位并用空格隔开

求整数的每一位可以将整数转换为字符串，然后遍历字符串输出每一位数字。具体实现如下：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int main() {
    int n;
    printf("请输入一个整数：");
    scanf("%d", &n);
    
    // 将整数转换为字符串
    char str[12]; // 假设整数不超过 2^31-1，最多有 10 位数字，再加上符号位和结束符
    sprintf(str, "%d", n);
    
    // 遍历字符串输出每一位数字
    int len = strlen(str);
    for (int i = 0; i < len; i++) {
        printf("%c ", str[i]);
    }
    
    return 0;
}

2. 青蛙跳台阶问题

一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法？

青蛙跳台阶问题可以使用递归或动态规划来解决。

2.1 递归方法

递归的思路是，对于第 n 级台阶，青蛙可以跳上前一级台阶后再跳一级，也可以跳上前两级台阶后再跳两级，所以跳上第 n 级台阶的跳法数量等于跳上第 n-1 级和第 n-2 级台阶的跳法数量之和。具体实现如下：

#include <stdio.h>
#include <stdlib.h>

int jump(int n) {
    if (n <= 0) {
        return 0;
    }
    if (n == 1) {
        return 1;
    }
    if (n == 2) {
        return 2;
    }
    
    return jump(n - 1) + jump(n - 2);
}

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

2.2 动态规划方法

动态规划的思路是，用一个数组保存每一级台阶的跳法数量，初始时将数组前两个元素分别设置为1和2，然后从第三级台阶开始，每一级台阶的跳法数量等于前一级和前两级台阶跳法数量之和。具体实现如下：

#include <stdio.h>
#include <stdlib.h>

int jump(int n) {
    if (n <= 0) {
        return 0;
    }
    if (n == 1) {
        return 1;
    }
    if (n == 2) {
        return 2;
    }
    
    int dp[n];
    dp[0] = 1;
    dp[1] = 2;
    for (int i = 2; i < n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    
    return dp[n - 1];
}

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

本文提供的代码示例仅供参考，读者可以根据自己的需要进行修改和扩展。希望本文能够帮助读者更好地理解和掌握基础算法练习。