https://kagol.github.io/hanoi/

小猫分鱼问题描述

海滩上有一堆鱼，由N只小猫来分。第一只小猫把这堆鱼平均分为N份，多了i（i < N）个，它把多的i个扔入海中，拿走了一份；第二只小猫接着把剩下的鱼平均分成N份，又多了i个，同样把多的i个扔入海中，拿走了一份；第三只、第四只……第N只小猫仍是将最终剩下的鱼分成N份，扔掉多的i个，并拿走一份 。需要编写程序，输入小猫的数量N以及每次扔到海里的鱼的数量i，输出海滩上最少的鱼数，使得每只小猫都可吃到鱼。

解题思路

采用倒推法，从最后一只小猫往前推。假设最后一只小猫拿走的鱼数为last ，通过这个假设去计算上一只小猫分鱼前的鱼数，依次类推，直到推出最初的鱼数。在倒推过程中，要保证每一步计算出的鱼数都能满足后续小猫分鱼的条件，即计算过程中的鱼数能被(n - 1)整除（因为每只小猫分鱼时，是把鱼平均分成n份，拿走一份后剩下的鱼数应该能被n - 1整除） 。如果不满足整除条件，就增加last的值重新计算。

代码实现

#include <iostream>
using namespace std;

int main() {
    // last是最后一只小猫拿走的鱼数
    // n是猫数，m是扔掉的鱼数
    // result用来记录结果
    int n, m, last = 1, result = 1; 
    cin >> n >> m;
    for (int i = 0; i < n - 1;) { 
        // 如果i = 0，即只有一只小猫分鱼，固定result = 1
        // 计算最后一只小猫分之前的鱼数
        if (i == 0) { 
            result = last * n + m;
        }
        // 计算倒数第二只小猫分之前的鱼数
        // 设x是被分为n份后减去一份还丢m条的结果
        // 设y为x被分前的鱼数，通过公式推导得出y = x / (n - 1) * n + m
        // 对应代码中result = result / (n - 1) * n + m，且这个式子需要满足x / (n - 1)是整数
        if (result % (n - 1) != 0) { 
            // 如果中间有数不满足整除条件，则让last自增并重新开始循环
            i = 0;
            last++;
        }
        else {
            result = result / (n - 1) * n + m;
            i++;
        }
    }
    cout << result;
    return 0;
}

代码解释

1. 变量定义：
   • n 存储小猫的数量，m 存储每次扔掉的鱼的数量。
   • last 表示最后一只小猫拿走的鱼数，初始化为1 。
   • result 用来记录满足条件的最初鱼的数量，初始化为1 。
2. 循环计算：
   • for 循环用于从最后一只小猫开始往前倒推每只小猫分鱼前的鱼数。
   • 当 i == 0 时，先计算出最后一只小猫分鱼前的鱼数 result = last * n + m 。
   • 然后在每次循环中，判断当前计算出的 result 能否被 (n - 1) 整除。如果不能整除，说明当前 last 值不合适，将 i 重置为0 ，last 自增1 ，重新计算；如果能整除，就按照公式 result = result / (n - 1) * n + m 计算上一只小猫分鱼前的鱼数，并将 i 自增1 ，继续往前倒推。
3. 输出结果：循环结束后，result 即为满足条件的海滩上最少的鱼数，将其输出。

#include <iostream>
#include <vector>
using namespace std;
vector<long long> vec={99999,1,2,4};
//你正在爬楼梯，每次你可以爬 1 或 2 或 3 个台阶。问有多少种不同的方法可以爬到第 n 层？
int main() {
	int n;
	cin >> n;
	
	for (int i = 4; i <= n; ++i) {
		long long next = vec[i-1]+vec[i-2]+vec[i-3];
		vec.push_back(next);
	}
	
	cout << "第" << n << "项是：" << vec[n] << endl;
	
	return 0;
}

#include <iostream>
#include <vector>
using namespace std;
vector<long long> vec={0,1};
int main() {
	int n;
	cout << "请输入斐波那契数列的项数n: ";
	cin >> n;
	
	for (int i = 2; i <= n; ++i) {
		long long next = vec[i-1]+vec[i-2];
		vec.push_back(next);
	}
	
	cout << "第" << n << "项是：" << vec[n] << endl;
	
	return 0;
}

C++递推算法详细教程

一、递推算法概述

1. 定义

递推算法是一种通过已知的初始条件，利用特定的递推关系，逐步推导出后续结果的算法。它就像搭积木，从最开始的一块积木（初始条件）出发，按照一定的规则（递推关系），一块一块地搭出整个结构（最终结果）。

2. 分类

• 顺推法：从已知的初始条件出发，按照递推关系，逐步向前推导出后续的结果。例如，计算斐波那契数列，从最开始的两个数，依次往后计算出整个数列。
• 逆推法：从问题的结果出发，反向推导出初始条件。比如在一些路径规划的逆向问题中，从终点开始，倒推回到起点的路径。

3. 应用场景

• 数学计算：如计算阶乘、斐波那契数列等。
• 动态规划：很多动态规划问题的基础思路就是递推，通过不断地积累局部最优解来得到全局最优解。
• 实际生活场景：像银行存款利息的计算、任务调度等问题，都可以用递推算法来解决。

二、顺推法示例：斐波那契数列

1. 问题描述

斐波那契数列的特点是从第三项开始，每一项都等于前两项之和。其数列的前几项是：0, 1, 1, 2, 3, 5, 8, 13, 21, 34, …… 。我们的任务是使用C++编写程序，计算斐波那契数列的第n项。

2. 解题思路

• 初始条件：数列的前两项f(0) = 0，f(1) = 1。
• 递推关系：对于n > 1，f(n) = f(n - 1) + f(n - 2) 。

3. 代码实现

#include <iostream>
using namespace std;

// 计算斐波那契数列第n项
int fibonacci(int n) {
    if (n == 0) return 0;
    if (n == 1) return 1;
    int a = 0, b = 1, temp;
    for (int i = 2; i <= n; i++) {
        temp = b;
        b = a + b;
        a = temp;
    }
    return b;
}

int main() {
    int n;
    cout << "请输入要计算的斐波那契数列的项数n: ";
    cin >> n;
    int result = fibonacci(n);
    cout << "斐波那契数列第 " << n << " 项的值是: " << result << endl;
    return 0;
}

4. 代码解释

• 在fibonacci函数中，首先判断n是否为0或1，如果是则直接返回对应的初始值。
• 然后使用两个变量a和b分别表示数列的前两项，通过循环，按照递推关系不断更新a和b的值，最终得到第n项的值。

5. 复杂度分析

• 时间复杂度：由于我们只需要进行n - 1次循环计算，所以时间复杂度是$O(n)$ 。
• 空间复杂度：只使用了几个额外的变量，所以空间复杂度是$O(1)$ 。

三、逆推法示例：猴子吃桃问题

1. 问题描述

猴子第一天摘下若干个桃子，当即吃了一半，还不过瘾，又多吃了一个。第二天早上又将剩下的桃子吃掉一半，又多吃了一个。以后每天早上都吃了前一天剩下的一半零一个。到第10天早上想再吃时，见只剩下一个桃子了。求第一天共摘了多少个桃子。

2. 解题思路

• 初始条件：第10天早上剩下1个桃子。
• 递推关系：设第n天早上剩余桃子数为f(n)，那么第n - 1天早上剩余桃子数f(n - 1) = (f(n) + 1) * 2 ，我们从第10天的1个桃子开始，逆向推导出第一天的桃子数。

3. 代码实现

#include <iostream>
using namespace std;

// 计算第一天摘的桃子数
int monkeyPeach() {
    int peach = 1;  // 第10天早上剩下1个桃子
    for (int i = 9; i >= 1; i--) {
        peach = (peach + 1) * 2;
    }
    return peach;
}

int main() {
    int result = monkeyPeach();
    cout << "第一天共摘了 " << result << " 个桃子" << endl;
    return 0;
}

4. 代码解释

• 在monkeyPeach函数中，先初始化第10天早上的桃子数为1。
• 然后通过循环，按照逆推关系从第9天开始，依次计算出前一天的桃子数，直到得到第一天的桃子数。

5. 复杂度分析

• 时间复杂度：循环执行了9次，所以时间复杂度是$O(n)$，这里n = 9 。
• 空间复杂度：只使用了一个额外的变量peach，所以空间复杂度是$O(1)$ 。

四、递推算法编程题实战

1. 题目：上楼梯问题

• 问题描述：有一段楼梯共n级台阶，每次可以走1级或2级，问从第0级走到第n级台阶共有多少种走法？
• 解题思路
  • 初始条件：当n = 0时，走法有1种（站在原地不动也算一种走法）；当n = 1时，走法有1种；当n = 2时，走法有2种（一次走2级或者分两次每次走1级）。
  • 递推关系：设走到第n级台阶的走法数为f(n)，那么f(n) = f(n - 1) + f(n - 2) ，因为走到第n级台阶的前一步，要么是从第n - 1级走1级上来的，要么是从第n - 2级走2级上来的。
• 代码实现

#include <iostream>
using namespace std;

// 计算上楼梯的走法数
int climbStairs(int n) {
    if (n == 0) return 1;
    if (n == 1) return 1;
    if (n == 2) return 2;
    int a = 1, b = 2, temp;
    for (int i = 3; i <= n; i++) {
        temp = b;
        b = a + b;
        a = temp;
    }
    return b;
}

int main() {
    int n;
    cout << "请输入楼梯的级数n: ";
    cin >> n;
    int result = climbStairs(n);
    cout << "从第0级走到第 " << n << " 级台阶共有 " << result << " 种走法" << endl;
    return 0;
}

• 复杂度分析
  • 时间复杂度：循环执行n - 2次，所以时间复杂度是$O(n)$ 。
  • 空间复杂度：使用了几个额外变量，空间复杂度是$O(1)$ 。

2. 题目：铺瓷砖问题

• 问题描述：用1×2的瓷砖去覆盖2×n的地面，问有多少种不同的覆盖方法？
• 解题思路
  • 初始条件：当n = 1时，只有1种覆盖方法；当n = 2时，有2种覆盖方法（两块瓷砖竖着放或者横着放）。
  • 递推关系：设覆盖2×n地面的方法数为f(n)，那么f(n) = f(n - 1) + f(n - 2) 。因为对于2×n的地面，如果先铺一块1×2的瓷砖竖着放，那么剩下的是2×(n - 1)的地面；如果先铺两块1×2的瓷砖横着放，那么剩下的是2×(n - 2)的地面。
• 代码实现

#include <iostream>
using namespace std;

// 计算铺瓷砖的方法数
int tileCover(int n) {
    if (n == 1) return 1;
    if (n == 2) return 2;
    int a = 1, b = 2, temp;
    for (int i = 3; i <= n; i++) {
        temp = b;
        b = a + b;
        a = temp;
    }
    return b;
}

int main() {
    int n;
    cout << "请输入地面的长度n: ";
    cin >> n;
    int result = tileCover(n);
    cout << "覆盖2×" << n << "的地面共有 " << result << " 种方法" << endl;
    return 0;
}

• 复杂度分析
  • 时间复杂度：循环次数为n - 2，时间复杂度是$O(n)$ 。
  • 空间复杂度：使用常量级额外空间，空间复杂度是$O(1)$ 。

五、总结与鼓励

递推算法是一种非常实用的算法思想，它通过简单的初始条件和明确的递推关系，就能解决很多看似复杂的问题。在学习和练习递推算法的过程中，你会不断锻炼自己的逻辑思维能力和问题分析能力。每一次成功解决一个递推编程题，都是你编程技能提升的见证！继续保持热情，不断探索更多有趣的算法，你一定能在编程的世界里创造出属于自己的精彩！ 加油！

C++递推算法与编程题详解教程

一、递推算法入门

1.1 什么是递推算法？

递推是利用已知条件，通过特定规则推导出后续结果的方法。就像多米诺骨牌，每一张牌倒下都依赖前一张的推动。在编程中，递推通常使用循环结构实现，从初始值出发，逐步计算出所需结果。

递推与递归的区别：

• 递归：从问题出发，将大问题分解为小问题，通过函数调用自身实现（如斐波那契数列的递归解法）。
• 递推：从已知条件出发，直接计算后续值，无需函数调用（如斐波那契数列的递推解法）。

1.2 递推的核心思想

递推的关键在于找到递推关系式和初始条件。例如：

• 斐波那契数列：递推关系式为 f(n) = f(n-1) + f(n-2)，初始条件为 f(0)=0, f(1)=1。
• 阶乘：递推关系式为 f(n) = n * f(n-1)，初始条件为 f(0)=1。

二、递推算法的基本形式

2.1 线性递推

形式：每个值仅依赖前一个或几个值。 案例：斐波那契数列

#include <iostream>
using namespace std;

int main() {
    int n;
    cout << "请输入斐波那契数列的项数：";
    cin >> n;
    
    int a = 0, b = 1, c;
    cout << "斐波那契数列前" << n << "项：";
    for (int i = 0; i < n; i++) {
        if (i == 0) cout << a << " ";
        else if (i == 1) cout << b << " ";
        else {
            c = a + b;
            cout << c << " ";
            a = b;
            b = c;
        }
    }
    return 0;
}

2.2 二维递推

形式：每个值依赖于上方、左方或左上方的值。 案例：杨辉三角（帕斯卡三角形）

#include <iostream>
using namespace std;

const int MAXN = 10;

int main() {
    int n;
    cout << "请输入杨辉三角的行数：";
    cin >> n;
    
    int triangle[MAXN][MAXN] = {0};
    
    // 初始化边界
    for (int i = 0; i < n; i++) {
        triangle[i][0] = 1;
        triangle[i][i] = 1;
    }
    
    // 递推计算内部值
    for (int i = 2; i < n; i++) {
        for (int j = 1; j < i; j++) {
            triangle[i][j] = triangle[i-1][j-1] + triangle[i-1][j];
        }
    }
    
    // 输出杨辉三角
    cout << "杨辉三角：" << endl;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j <= i; j++) {
            cout << triangle[i][j] << " ";
        }
        cout << endl;
    }
    
    return 0;
}

三、经典递推问题解析

3.1 爬楼梯问题（斐波那契变种）

问题：每次可以爬1或2级台阶，问爬n级台阶有多少种方法？ 分析：

• 最后一步可能是从第n-1级或n-2级台阶爬上来的。
• 递推关系式：f(n) = f(n-1) + f(n-2)
• 初始条件：f(1)=1, f(2)=2

#include <iostream>
using namespace std;

int main() {
    int n;
    cout << "请输入台阶数：";
    cin >> n;
    
    if (n == 1) {
        cout << "方法数：1" << endl;
        return 0;
    }
    
    int a = 1, b = 2, c;
    for (int i = 3; i <= n; i++) {
        c = a + b;
        a = b;
        b = c;
    }
    
    cout << "方法数：" << b << endl;
    return 0;
}

3.2 汉诺塔问题

问题：将n个盘子从A柱移动到C柱，每次只能移动一个盘子，且大盘子不能放在小盘子上面。 分析：

• 移动n个盘子需要先移动n-1个盘子到B柱，再移动第n个盘子到C柱，最后移动n-1个盘子到C柱。
• 递推关系式：f(n) = 2*f(n-1) + 1
• 初始条件：f(1)=1

#include <iostream>
using namespace std;

int main() {
    int n;
    cout << "请输入盘子数：";
    cin >> n;
    
    long long moves = 1;  // 防止溢出
    for (int i = 2; i <= n; i++) {
        moves = moves * 2 + 1;
    }
    
    cout << "需要移动的次数：" << moves << endl;
    return 0;
}

3.3 兔子繁殖问题

问题：兔子出生后两个月开始繁殖，每月生一对小兔子。初始有一对兔子，问n个月后有多少对兔子？ 分析：

• 第n个月的兔子数 = 第n-1个月的兔子数 + 第n-2个月的兔子数（因为两个月前的兔子都会繁殖）。
• 递推关系式：f(n) = f(n-1) + f(n-2)
• 初始条件：f(1)=1, f(2)=1

#include <iostream>
using namespace std;

int main() {
    int n;
    cout << "请输入月数：";
    cin >> n;
    
    int a = 1, b = 1, c;
    for (int i = 3; i <= n; i++) {
        c = a + b;
        a = b;
        b = c;
    }
    
    cout << "第" << n << "个月的兔子对数：" << b << endl;
    return 0;
}

四、递推算法的应用技巧

4.1 状态转移方程的建立

• 分析问题：确定问题的状态（如斐波那契数列中的第n项）。
• 寻找递推关系：分析当前状态与之前状态的联系（如爬楼梯问题中的f(n)=f(n-1)+f(n-2)）。
• 确定初始条件：明确最基础的状态值（如斐波那契数列的f(0)=0, f(1)=1）。

4.2 空间优化技巧

对于一些递推问题，若当前状态只依赖前几个状态，可以使用滚动数组优化空间。 案例：斐波那契数列的空间优化

#include <iostream>
using namespace std;

int main() {
    int n;
    cout << "请输入项数：";
    cin >> n;
    
    if (n == 0) {
        cout << "结果：0" << endl;
        return 0;
    }
    
    int a = 0, b = 1;
    for (int i = 2; i <= n; i++) {
        int temp = b;
        b = a + b;
        a = temp;
    }
    
    cout << "结果：" << b << endl;
    return 0;
}

五、递推算法练习题

5.1 斐波那契数列变形

问题：计算斐波那契数列的第n项，但对结果取模1000000007（防止溢出）。 输入：一个整数n（1 ≤ n ≤ 1000000） 输出：斐波那契数列第n项对1000000007取模的结果。

5.2 杨辉三角变形

问题：计算杨辉三角第n行的所有元素之和。 输入：一个整数n（1 ≤ n ≤ 30） 输出：杨辉三角第n行的元素之和。

5.3 走方格问题

问题：在一个n×m的方格中，从左上角走到右下角，每次只能向右或向下走，有多少种不同的走法？ 输入：两个整数n和m（1 ≤ n, m ≤ 10） 输出：不同走法的数量。

六、总结与鼓励

递推算法是编程中最基础、最实用的算法之一，通过找到问题的递推关系式和初始条件，可以高效地解决许多问题。掌握递推算法不仅能提升编程能力，还能培养逻辑思维和问题分析能力。

记住：

• 遇到复杂问题时，先从简单情况入手，寻找规律。
• 多练习经典题目，积累解题经验。
• 遇到困难不要气馁，每一次尝试都是成长的机会！

现在，拿起键盘，开始挑战递推算法的练习题吧！💪