C语言学习记录---函数4

汉诺塔问题（递归）

#include <stdio.h>

// 定义汉诺塔函数
void hanoi(int n, char A, char B, char C) {
  if (n == 1) {
    printf("将盘子从 %c 移动到 %c\n", A, C);
  } else {
    //将 n-1 个盘子从 A 移动到 B
    hanoi(n - 1, A, C, B);         

    //将第 n 个盘子从 A 移动到 C
    printf("将盘子从 %c 移动到 %c\n", A, C);       

    //将 B 上的 n-1 个盘子移动到 C
    hanoi(n - 1, B, A, C);         
  }
}

int main() {
  int n;
  printf("请输入盘子的数量：");
  scanf("%d", &n);

  // 调用汉诺塔函数
  hanoi(n, 'A', 'B', 'C');

  return 0;
}

如果一次只能移动一个

#include <stdio.h>

void hanoi(int n, char source, char aux, char dest) {
  if (n == 1) {
    printf("将盘子从 %c 移动到 %c\n", source, dest);
  } else {
    hanoi(n - 1, source, dest, aux);
    printf("将盘子从 %c 移动到 %c\n", source, dest);
    hanoi(n - 1, aux, source, dest);
  }
}

int main() {
  int n;
  printf("请输入盘子的数量：");
  scanf("%d", &n);

  hanoi(n, 'A', 'B', 'C');

  return 0;
}

青蛙跳台阶：（循环）

青蛙跳台阶问题是一个典型的动态规划问题。假设青蛙跳上 n 级台阶，这个问题可以拆解为两个子问题：跳到 n-1 级台阶和跳到 n-2 级台阶。

当青蛙在 n-1 级台阶上时，它只需再跳上 1 级台阶即可到达第 n 级台阶；
当青蛙在 n-2 级台阶上时，它只需再跳上 2 级台阶即可到达第 n 级台阶。

因此，青蛙跳上 n 级台阶的跳法数量是跳上 n-1 级台阶的跳法数量加上跳上 n-2 级台阶的跳法数量。

根据以上分析，我们可以得到递推式：
f(n) = f(n-1) + f(n-2)

初始情况：

• 当 n=1 时，青蛙只有一种跳法，即直接跳上第一级台阶。
• 当 n=2 时，青蛙有两种跳法，可以一次跳两级台阶，也可以分两次跳每次跳一级台阶。

#include <stdio.h>

int jumpSteps(int n){
  if (n <= 0) {
    return 0;
  } else if (n == 1) {
    return 1;
  } else if (n == 2) {
    return 2;
  }

  int a = 1;  // 第 n-2 级台阶的跳法数量
  int b = 2;  // 第 n-1 级台阶的跳法数量
  int result = 0;

  for (int i = 3; i <= n; i++) {
    result = a + b;
    a = b;
    b = result;
  }

  return result;
}

int main() {
  int num;
  printf("请输入台阶的级数：");
  scanf("%d", &num);

  int result = jumpSteps(num);
  printf("青蛙跳上 %d 级台阶的跳法数量为：%d\n", num, result);

  return 0;
}