有基础班_day05课上题目

zxcvbnm

2025-07-05 16:17:22

发布于：上海

19阅读

0回复

0点赞

题目
【递归】斐波那契数列
最大公约数
最小公倍数
进制转换1
进制转换2
进制转换3
前 n 项和
汉诺塔2

【递归】斐波那契数列

题目大意

给定一个正整数 $n$ （ $1 \leq n \leq 30$ ），请用递归方法求出斐波那契数列的第 $n$ 项。
斐波那契数列定义如下：

$F(1) = 1,\quad F(2) = 1,\quad F(n) = F(n-1) + F(n-2)\quad (n \geq 3)$

解题思路

根据定义，我们可以用最朴素的递归方法实现。
对于输入的 $n$ ：

如果 $n = 1$ 或 $n = 2$ ，直接返回 $1$ ；
否则返回 $f(n - 1) + f(n - 2)$ 。

虽然这个方法在效率上不是最优（时间复杂度是指数级的 $O(2^n)$ ），但题目明确要求使用递归，并且 $n \leq 30$ ，可以接受。

时间复杂度分析

时间复杂度： $O(2^n)$ ，因为会有大量重复递归调用；
空间复杂度： $O(n)$ ，递归深度最多为 $n$ 。

代码实现（C++）

#include <iostream>
using namespace std;

// 最简单的递归定义
int fib(int n) {
    if (n == 1 || n == 2) return 1;
    return fib(n - 1) + fib(n - 2);
}

int main() {
    int n;
    cin >> n;
    cout << fib(n) << endl;
    return 0;
}

最大公约数

题目大意

给定两个正整数 $a$ 和 $b$ ，要求输出它们的最大公约数（Greatest Common Divisor, GCD），即同时整除 $a$ 和 $b$ 的最大正整数。

题意分析

最大公约数是整数运算中非常基础的概念。可以使用辗转相除法（欧几里得算法）来高效计算：

$\gcd(a, b) = \gcd(b, a \bmod b)$
当 $b = 0$ 时，结果为 $a$

例如：

$\gcd(16, 6) \to \gcd(6, 4) \to \gcd(4, 2) \to \gcd(2, 0) = 2$

解题思路

使用递归实现欧几里得算法，时间复杂度为 $O(\log \min(a, b))$ ，即使 $a, b$ 最大为 $10^5$ ，效率也非常高。

时间复杂度分析

时间复杂度： $O(\log \min(a, b))$
空间复杂度：
- 递归实现： $O(\log \min(a, b))$ （递归栈）

C++ 代码实现

#include <iostream>
using namespace std;

// 欧几里得算法求最大公约数
int gcd(int a, int b) {
    if (b == 0) return a;
    return gcd(b, a % b);
}

int main() {
    int a, b;
    cin >> a >> b;
    cout << gcd(a, b) << endl;
    return 0;
}

最小公倍数

题目大意

给定两个正整数 $a$ 和 $b$ ，求它们的最小公倍数 $LCM(a, b)$ ，即能同时被 $a$ 和 $b$ 整除的最小正整数。

题意分析

最小公倍数与最大公约数的关系如下：

$\mathrm{LCM}(a, b) = \frac{a \times b}{\gcd(a, b)}$

其中 $\gcd(a, b)$ 表示 $a$ 和 $b$ 的最大公约数。

举个例子：

$\gcd(3, 4) = 1$ ， $\mathrm{LCM}(3, 4) = \frac{3 \times 4}{1} = 12$
$\gcd(2, 6) = 2$ ， $\mathrm{LCM}(2, 6) = \frac{2 \times 6}{2} = 6$

解题思路

使用欧几里得算法计算 $\gcd(a, b)$ ；
使用公式 $\mathrm{LCM}(a, b) = \dfrac{a \cdot b}{\gcd(a, b)}$ 计算最小公倍数；
注意防止乘法时超出整数范围（不过本题数据保证结果在 int 范围内）。

时间复杂度分析

计算 $\gcd$ ： $O(\log \min(a, b))$
总体复杂度： $O(\log \min(a, b))$

C++ 代码实现

#include <iostream>
using namespace std;

// 欧几里得算法求最大公约数
int gcd(int a, int b) {
    if (b == 0) return a;
    return gcd(b, a % b);
}

// 最小公倍数
int lcm(int a, int b) {
    return a / gcd(a, b) * b; // 先除再乘防止溢出
}

int main() {
    int a, b;
    cin >> a >> b;
    cout << lcm(a, b) << endl;
    return 0;
}

最小公倍数

题目大意

输入两个正整数 $a$ 和 $b$ ，求它们的最小公倍数（LCM）。

题意分析

最小公倍数和最大公约数之间有如下关系：

$\mathrm{LCM}(a, b) = \frac{a \times b}{\gcd(a, b)}$

解题思路

使用欧几里得算法计算 $\gcd(a, b)$ ；
再使用公式 $\mathrm{LCM} = \dfrac{a \cdot b}{\gcd(a, b)}$ ；
为防止整数溢出，使用 long long 存储结果。

时间复杂度分析

计算最大公约数： $O(\log \min(a, b))$
计算最小公倍数： $O(1)$

总时间复杂度： $O(\log \min(a, b))$

C++ 代码实现

#include <iostream>
using namespace std;

// 欧几里得算法计算最大公约数
long long gcd(long long a, long long b) {
    return b == 0 ? a : gcd(b, a % b);
}

// 最小公倍数
long long lcm(long long a, long long b) {
    return a / gcd(a, b) * b; // 先除再乘，避免中间结果溢出
}

int main() {
    long long a, b;
    cin >> a >> b;
    cout << lcm(a, b) << endl;
    return 0;
}

进制转换1

题目大意

将输入的一个十进制正整数 $n$ 转换为对应的二进制数，并输出结果。要求必须使用递归完成。

题意分析

例如十进制数 $6$ ，它的二进制形式为 $110$ 。
本质上是将 $n$ 不断除以 $2$ ，从而构造出它的二进制表达。
输出顺序是从高位到低位，因此递归非常适合这个问题。

解题思路

我们考虑将十进制数 $n$ 转换为二进制数的过程：

对 $n$ 进行整数除以 $2$ 得到下一层递归；
每次输出当前位的余数： $n % 2$ ；
递归的结束条件是： $n == 0$ 时终止（但实际要从 $n > 0$ 才开始输出）。

为了防止前导 0 输出，我们在主程序中单独处理 $n=0$ 的情况。

时间复杂度解析

每次递归都会将 $n$ 除以 $2$ ，最多递归 $\log_2 n$ 层；
时间复杂度为 $O(\log n)$ ，空间复杂度也是 $O(\log n)$ ，非常高效。

代码演示

#include <iostream>
using namespace std;

// 递归函数：输出n的二进制表示
void printBinary(int n) {
    if(n == 0) return;         // 基础情况，递归终止
    printBinary(n / 2);        // 先递归处理高位
    cout << n % 2;             // 再输出当前位（低位）
}

int main() {
    int n;
    cin >> n;
    if(n == 0) cout << 0;      // 特判n = 0 的情况
    else printBinary(n);
    return 0;
}

进制转换2

题目大意

输入两个整数 $X$ 和 $M$ ，将十进制整数 $X$ 转换为 $M$ 进制的数，并输出对应结果。要求必须使用递归实现。

题意分析

需要将 $X$ 从十进制转换成 $M$ 进制（其中 $2 \leq M \leq 16$ ）；
若 $M$ 为 $16$ ，则要处理 $10\sim15$ 对应的字符 A~F；
输出顺序是从高位到低位，天然适合递归。

解题思路

递归函数思路如下：

若 $X == 0$ ，终止递归；
否则先递归处理 $X / M$ ；
然后输出当前位： $X % M$ ，若大于等于 $10$ ，输出 A~F。

另外在 main() 中要特殊处理 $X = 0$ 的情况（输出 0）。

时间复杂度解析

每次递归将 $X$ 除以 $M$ ，最多递归 $\log_M X$ 次；
因此时间和空间复杂度均为 $O(\log X)$ 。

代码演示

#include <iostream>
using namespace std;

// 递归函数：将十进制数x转换为m进制
void convert(int x, int m) {
    if(x == 0) return; // 递归终止条件
    convert(x / m, m); // 先处理高位
    int r = x % m;     // 当前位
    if(r < 10) cout << r;
    else cout << char('A' + (r - 10)); // 10~15 映射到 A~F
}

int main() {
    int x, m;
    cin >> x >> m;
    if(x == 0) cout << 0; // 特判x=0
    else convert(x, m);
    return 0;
}

进制转换3

题目大意

给定一个 N进制的数 $X$ （字符串形式） 和一个整数 $N$ ，将其转换为十进制数并输出。要求使用递归算法。

题意分析

输入中 $X$ 是一个 字符串，可能包含数字 0~9 和字母 A~F 或 a~f（表示 10~15）；
进制 $N$ 范围在 $2 \sim 16$ ；
要将字符串 $X$ 解释为 $N$ 进制，转化成十进制整数；
用递归实现：自然可以从左到右依次处理每一位。

解题思路

我们可以定义一个递归函数如下：

定义：convert(s, len, base) 表示将前 len 位的字符串 s 视为 base 进制数，转换为十进制。
递归表达式：
- 若长度为 1：直接返回该位的十进制值；
- 否则，答案为：convert(s, len-1, base) * base + 当前位的十进制值。

时间复杂度

每一位递归一次，共有 $\text{len}(X)$ 位；
时间复杂度为 $O(\text{len}(X))$ ，最多约为 $O(7)$ ，很快。

代码演示

#include <iostream>
#include <string>
using namespace std;

// 将字符 ch 转成它的十进制值
int toDigit(char ch) {
    if(ch >= '0' && ch <= '9') return ch - '0';
    if(ch >= 'A' && ch <= 'F') return ch - 'A' + 10;
    if(ch >= 'a' && ch <= 'f') return ch - 'a' + 10;
    return -1; // 非法字符
}

// 递归函数：将前len位的s视为base进制，转为十进制
int convert(string s, int len, int base) {
    if(len == 1) return toDigit(s[0]);
    return convert(s, len - 1, base) * base + toDigit(s[len - 1]);
}

int main() {
    string s;
    int base;
    cin >> s >> base;
    cout << convert(s, s.length(), base) << endl;
    return 0;
}

前 n 项和

题目大意

输入一个正整数 $n$ ，使用递归的方式求出 $1 + 2 + 3 + \cdots + n$ 的结果。

题意分析

题目要求使用递归方法求和；
不能使用循环或数学公式 $n(n+1)/2$ 。

解题思路

使用递归公式定义：

定义 f(n) 为前 $n$ 项和；
递推关系：
- $f(n) = f(n - 1) + n$
- 边界： $f(1) = 1$

时间复杂度分析

每次递归调用 $n-1$ 次，时间复杂度为 $O(n)$ ；
空间复杂度（递归栈）也是 $O(n)$ ，对于 $n \leq 100$ 完全可以接受。

代码演示

#include <iostream>
using namespace std;

// 递归函数：返回1+2+...+n的和
int sum(int n) {
    if (n == 1) return 1;       // 递归终止条件
    return sum(n - 1) + n;      // 递归表达式
}

int main() {
    int n;
    cin >> n;
    cout << sum(n) << endl;
    return 0;
}

汉诺塔2

题目大意

有 $n$ 种大小不同的圆盘，每种大小各有两个相同的圆盘（共 $2n$ 个），初始都在柱子 A 上。按照 汉诺塔规则（一次只能移动一个圆盘、且大盘不能放在小盘上），将所有盘子移动到柱子 C 上，输出最少移动次数。

注意：同一尺寸的两个圆盘是不可区分的。

题意分析

和普通汉诺塔不同的是：每种尺寸有 两个不可区分的圆盘。
目标是移动这 $2n$ 个圆盘到柱 C，最少需要多少步？

解题思路

观察样例和递归特性，我们可以发现：

普通汉诺塔的递归步骤（n 个不同盘）：移动 $n$ 个盘子的最少步数为 $2^n - 1$ 。

本题特殊之处：每个盘有两个一模一样的拷贝，但规则仍然要求不能把大盘放在小盘上。

构造递推公式：

设 $f(n)$ 表示将 $n$ 种盘移动到目标柱的最小步数，则：

首先把 $n-1$ 对盘移到辅助柱子，需要 $f(n-1)$ 步；
然后将当前第 $n$ 对盘子从起始柱移到目标柱，共 2 步；
然后再将辅助柱上的 $n-1$ 对盘子移到目标柱，再需要 $f(n-1)$ 步。

于是可以得出递推式：

$f(n) = 2 \times f(n-1) + 2$

边界条件： $f(1) = 2$

时间复杂度分析

这是一个递归式，时间复杂度为 $O(n)$ ，不会爆栈或超时， $n \leq 15$ 时可以安全运行。

代码演示

#include <iostream>
using namespace std;

// 递归函数：求解 n 种圆盘最少移动次数
long long f(int n) {
    if (n == 1) return 2;                 // 基础情况：1 对盘需要 2 次
    return 2 * f(n - 1) + 2;              // 递推公式
}

int main() {
    int n;
    cin >> n;
    cout << f(n) << endl;                // 输出最少移动次数
    return 0;
}

有帮助，赞一个

去预览

0/2000

全部评论 1

比比和虎🐯


`#include <iostream>
using namespace std;

// 递归函数：求解 n 种圆盘最少移动次数
long long f(int n) {
    if (n == 1) return 2;                 // 基础情况：1 对盘需要 2 次
    return 2 * f(n - 1) + 2;              // 递推公式
}

int main() {
    int n;
    cin >> n;
    cout << f(n) << endl;                // 输出最少移动次数
    return 0;
}`

2025-07-06 来自上海

【递归】斐波那契数列

题目大意

解题思路

时间复杂度分析

代码实现（C++）

最大公约数

题目大意

题意分析

解题思路

时间复杂度分析

C++ 代码实现

最小公倍数

题目大意

题意分析

解题思路

时间复杂度分析

C++ 代码实现

最小公倍数

题目大意

题意分析

解题思路

时间复杂度分析

C++ 代码实现

进制转换1

题目大意

题意分析

解题思路

时间复杂度解析

代码演示

进制转换2

题目大意

题意分析

解题思路

时间复杂度解析

代码演示

进制转换3

题目大意

题意分析

解题思路

时间复杂度

代码演示

前 n 项和

题目大意

题意分析

解题思路

时间复杂度分析

代码演示

汉诺塔2

题目大意

题意分析

解题思路

构造递推公式：

时间复杂度分析

代码演示

全部评论 1

热门讨论