外观

2026-计算概论C-py7-练习 ​

题集链接 ​

OpenJudge/计算概论C(py)/2026-计算概论C-py7-练习

共 7 题。练习题的完整参考解析可直接查看。OJ 题集结束时间为北京时间 2027-01-31 00:00。

01：递归复习法 ​

题目描述 ​

据说，学渣复习期末考试，要用递归复习法，即当他复习知识点A的时候，他发现理解知识点A必须先理解知识点B和知识点C，于是他先去学习知识点B和知识点C，当他复习知识点B的时候，又发现理解知识点B必须先理解知识点D与知识点E，又得先去复习知识点D和知识点E。

现在学渣小明正在通过递归复习法复习知识点n。对任意知识点1 <= k <= n，他复习这个知识点本身需要k小时的时间。但是，小明对这些知识点非常不熟悉，以至于他对任意知识点k， 3 <= k <= n，都必须先复习知识点k - 1和k - 2才能复习知识点k；在复习知识点k - 1的时候，又得先复习知识点k - 2和k - 3才能复习知识点k - 1；以此类推……。注意，即使在复习知识点k - 1的时候他已经复习过了知识点k - 2，在复习知识点k之前他已经忘掉了知识点k - 2，因此他还是会再复习一遍知识点k - 2，并重复上述的递归过程完成新的一轮k - 2的复习后，才会复习知识点k。

现在请问他一共需要多少个小时才能完成知识点n的复习？

输入

第一行是一个整数m，代表数据组数，1 <= m <= 25
之后m行，每行是一组数据，即一个整数n，1 <= n <= 25

输出

对每组数据，输出小明复习知识点n所需要的时间

样例输入

9
1
2
3
5
7
9
15
20
25

样例输出

1
2
6
23
71
200
3786
42164
467833

提示

第一个输入n=1，需要复习一个小时。

第二个输入n=3，此时他需要先复习知识点1和知识点2，再复习知识点3，需要复习1+2+3=6个小时。

第三个输入n=5，此时他为了复习知识点5，必须先复习知识点3与知识点4。之前已知复习知识点3需要6个小时。复习知识点4前需要再复习知识点3与知识点2，加上复习知识点4本身的时间，共需要2+6+4=12个小时。因此，复习知识点5共需要6+12+5=23小时。

来源

何昊高洁

解题提示

本题知识点： 递归关系、记忆化。

总时间包含两个前置知识点的完整复习时间，再加当前知识点本身的 k 小时。边界是 T(1)=1、T(2)=2，递推为 T(k)=T(k−1)+T(k−2)+k。

易错点

题意中的重复复习必须重复计时；缓存的是子问题的数值，不是把重复发生的复习时间扣除。

题解 ​

思路 ​

总时间包含两个前置知识点的完整复习时间，再加当前知识点本身的 k 小时。边界是 T(1)=1、T(2)=2，递推为 T(k)=T(k−1)+T(k−2)+k。

知识点 ​

递归关系、记忆化第7章 常用的基本算法

代码（2026 秋整理） ​

python
from functools import lru_cache


@lru_cache(maxsize=None)
def review(n):
    if n <= 2:
        return n
    return review(n - 1) + review(n - 2) + n


m = int(input())
for _ in range(m):
    print(review(int(input())))

02：汉诺塔问题 ​

题目描述 ​

古代有一个梵塔，塔内有三个座A、B、C，A座上有n个盘子，盘子大小不等，大的在下，小的在上。三个座都可以用来放盘子。有一个和尚想把这n个盘子从A座移到C座，但每次只能允许移动一个盘子，并且在移动过程中，3个座上的盘子始终保持大盘在下，小盘在上。输入盘子数目n，要求输出移动的步骤。

输入

盘子数目n ( n < 8)

输出

移动方案

样例输入

3

样例输出

A->C
A->B
C->B
A->C
B->A
B->C 
A->C

解题提示

本题知识点： 递归、参数传递。

先把上面 n−1 个盘子移到辅助柱，再把最大盘移到目标柱，最后将辅助柱的盘子移到目标柱。递归参数应明确起点、辅助点和终点。

易错点

每次递归时柱子的角色都会变化；输出具体移动步骤，不是移动总次数。

题解 ​

思路 ​

先把上面 n−1 个盘子移到辅助柱，再把最大盘移到目标柱，最后将辅助柱的盘子移到目标柱。递归参数应明确起点、辅助点和终点。

知识点 ​

递归、参数传递第7章 常用的基本算法

代码（2026 秋整理） ​

python
def hanoi(n, source, helper, target):
    if n == 0:
        return
    hanoi(n - 1, source, target, helper)
    print(f"{source}->{target}")
    hanoi(n - 1, helper, source, target)


hanoi(int(input()), "A", "B", "C")

03：逃出迷宫 ​

题目描述 ​

"Boom!" 小锅一觉醒来发现自己落入了一个N*N(2 <= N <= 20)的迷宫之中，为了逃出这座迷宫，小锅需要从左上角(0, 0)处的入口跑到右下角(N-1, N-1)处的出口逃出迷宫。由于小锅每一步都想缩短和出口之间的距离，所以他只会向右和向下走。假设我们知道迷宫的地图（以0代表通路，以1代表障碍），请你编写一个程序，判断小锅能否从入口跑到出口？

例如，对于下图所示的迷宫：

小锅可以如下图红线所示从迷宫左上角的入口抵达迷宫右下角的出口：

输入

第一行为一个整数N，代表迷宫的大小
接下来N行为迷宫地图，迷宫地块之间以空格分隔
输入保证(0, 0)和(N - 1, N - 1)处可以通过

输出

一行字符串，如果能跑到出口则输出Yes，否则输出No

样例输入

5
0 0 1 1 0
0 0 0 0 0
0 1 1 1 0
0 1 1 1 0
0 1 1 1 0

样例输出

Yes

解题提示

本题知识点： 递归搜索、记忆化。

从当前位置尝试向右或向下；越界或遇障碍返回不可达，到达右下角返回可达。缓存位置的判断结果，避免反复探索相同区域。

易错点

只能向右和向下，不能按一般迷宫增加四个方向；输出为 Yes 或 No。

题解 ​

思路 ​

从当前位置尝试向右或向下；越界或遇障碍返回不可达，到达右下角返回可达。缓存位置的判断结果，避免反复探索相同区域。

知识点 ​

递归搜索、记忆化第7章 常用的基本算法

代码（2026 秋整理） ​

python
from functools import lru_cache

n = int(input())
maze = [list(map(int, input().split())) for _ in range(n)]


@lru_cache(maxsize=None)
def reachable(row, column):
    if row >= n or column >= n or maze[row][column] == 1:
        return False
    if row == n - 1 and column == n - 1:
        return True
    return reachable(row + 1, column) or reachable(row, column + 1)


print("Yes" if reachable(0, 0) else "No")

04：作业文件统计 ​

题目描述 ​

某同学本学期所有计算概论C作业都放在了一个名为“homework”的文件夹下面，这个文件夹下面存放着一系列.py文件和子文件夹，而子文件中又包含着一系列.py文件和子文件夹。‘homework’文件夹下子文件夹的深度不会超过5层，并且所有子文件夹不会重名，而且没有空文件夹，所有文件都有扩展名。请你统计一下这位同学本学期总共编写了多少个.py文件，并以相对路径的方式按一行一个文件名的形式把所有的.py文件的文件名输出。

输入

若干行，输完后输入空行表示所有输入结束。
每一行包含的信息有，当前文件夹的名字，该文件夹下包含的文件(不一定都是.py文件)和子文件夹，中间用空格分隔。

输出

若干行，除最后一行外，每一行为一个带有相对路径的.py文件的文件名，输出顺序按照读取顺序。
最后一行为一个整数，表示统计出的.py文件的个数。

样例输入

homework 01-intro 02-basicDataTypes 03-structure 
01-intro 01_circle.py 01_firstFile.py 
02-basicDataTypes 02_characterCipher.py other
other 02_dayDayUp.py readme.txt
03-structure 03_abnormality.py 03_calBMI.py

样例输出

homework\01-intro\01_circle.py
homework\01-intro\01_firstFile.py
homework\02-basicDataTypes\02_characterCipher.py
homework\02-basicDataTypes\other\02_dayDayUp.py
homework\03-structure\03_abnormality.py
homework\03-structure\03_calBMI.py
6

来源

lyqian

解题提示

本题知识点： 字典、递归路径构造。

读入各文件夹的条目，记录子文件夹的父目录。通过递归得到文件夹相对路径，再按文件在输入中的出现顺序输出 .py 文件并计数。

易错点

输入用空行结束，也兼容文件结束；路径用反斜杠，不读取本机真实文件。其他扩展名的文件不计数。

题解 ​

思路 ​

读入各文件夹的条目，记录子文件夹的父目录。通过递归得到文件夹相对路径，再按文件在输入中的出现顺序输出 .py 文件并计数。

知识点 ​

字典、递归路径构造第7章 常用的基本算法

代码（2026 秋整理） ​

python
import sys

parents = {}
files = []
for line in sys.stdin:
    if not line.strip():
        break
    folder, *children = line.split()
    for child in children:
        if "." not in child:
            parents[child] = folder
        elif child.endswith(".py"):
            files.append((folder, child))


def folder_path(folder):
    if folder == "homework":
        return folder
    return folder_path(parents[folder]) + "\\" + folder


for folder, filename in files:
    print(folder_path(folder) + "\\" + filename)
print(len(files))

05：求斐波那契数列第k项 ​

题目描述 ​

菲波那契数列是指这样的数列: 数列的第一个和第二个数都为1，接下来每个数都等于前面2个数之和。给出一个正整数k，要求菲波那契数列中第k个数是多少。

输入

输入一行，包含一个正整数k（1<=k<=46）。

输出

输出一行，包含一个正整数，表示菲波那契数列中第k个数。

样例输入

19

样例输出

4181

来源

Guo wei

解题提示

本题知识点： 递归、记忆化。

定义前两项均为 1，后续项为前两项之和。使用缓存保存各项，避免朴素递归大量重复计算。

易错点

题目下标从 1 开始；k 可达 46，未缓存的双分支递归可能超时。

题解 ​

思路 ​

定义前两项均为 1，后续项为前两项之和。使用缓存保存各项，避免朴素递归大量重复计算。

知识点 ​

递归、记忆化第7章 常用的基本算法

代码（2026 秋整理） ​

python
from functools import lru_cache


@lru_cache(maxsize=None)
def fibonacci(k):
    if k <= 2:
        return 1
    return fibonacci(k - 1) + fibonacci(k - 2)


print(fibonacci(int(input())))

06：很简单的整数划分问题 ​

题目描述 ​

将正整数n 表示成一系列正整数之和，n=n1+n2+…+nk, 其中n1>=n2>=…>=nk>=1 ，k>=1 。
正整数n 的这种表示称为正整数n 的划分。正整数n 的不同的划分个数称为正整数n 的划分数

输入

一个整数N(0 < N <= 30)。

输出

输出N的划分数。

样例输入

5

样例输出

7

提示

5, 4+1, 3+2, 3+1+1, 2+2+1, 2+1+1+1, 1+1+1+1+1

解题提示

本题知识点： 递归分类、记忆化。

定义状态为剩余和及允许的最大部分。按不使用最大部分、至少使用一个最大部分分类；使用后仍可继续使用该部分，从而允许重复数字。

易错点

同一组数字的不同顺序不应重复计数；剩余和为 0 表示找到一种划分，不能返回 0。

题解 ​

思路 ​

定义状态为剩余和及允许的最大部分。按不使用最大部分、至少使用一个最大部分分类；使用后仍可继续使用该部分，从而允许重复数字。

知识点 ​

递归分类、记忆化第7章 常用的基本算法

代码（2026 秋整理） ​

python
from functools import lru_cache


@lru_cache(maxsize=None)
def partitions(total, largest):
    if total == 0:
        return 1
    if largest == 0:
        return 0
    if largest > total:
        return partitions(total, total)
    return partitions(total, largest - 1) + partitions(total - largest, largest)


n = int(input())
print(partitions(n, n))

07：杨辉三角形(递归法) ​

题目描述 ​

杨辉三角形，又称帕斯卡三角形、贾宪三角形、海亚姆三角形、巴斯卡三角形，是二项式系数的一种写法，形似三角形，在中国首现于南宋杨辉的《详解九章算法》得名，其在书中说明是引自贾宪的《释锁算书》，故又名贾宪三角形。前6行写出如下：

1

1    1

1    2    1

1    3    3    1

1    4    6    4    1

1    5    10    10    5    1

杨辉三角形的规律如下：（截取与本题有关的部分）

  1. 杨辉三角形以正整数构成，数字左右对称，每行由1开始逐渐变大，然后变小，回到1。
  2. 其第n行（从0开始计数）有n+1个数字。
  3. 除每行最左侧与最右侧的数字以外，每个数字等于它的左上方与右上方两个数字之和（也就是说，第 n 行第 k 个数字等于第 n−1 行的第 k−1 个数字与第 k 个数字的和）。可用此性质写出整个杨辉三角形。

现在要求，给出n和m，输出杨辉三角形第n行第m个数字（行列都从0开始计数）。若给定的n和m超出杨辉三角形范围，输出0

要求：使用递归

输入

一行，两个非负整数n和m

输出

一行，一个整数，表示第n行m列的数字

样例输入

样例输入1：
0 0
样例输入2：
0 5
样例输入3：
4 2

样例输出

样例输出1：
1
样例输出2：
0
样例输出3：
6

提示

样例2解释：
由于第0行只有一个元素，5超出范围，所以返回0
样例3解释：
第四行为 1 4 6 4 1，第2个元素为6（从第0个开始计数）

使用递归，考虑清楚边界条件和递归关系式

解题提示

本题知识点： 递归、边界条件。

先判断列号是否超出本行范围，再处理两端为 1 的情况；内部元素等于上一行相邻两项之和。可缓存已算过的行列。

易错点

行和列都从 0 开始；必须先判越界，(0,5) 应输出 0，(0,0) 应输出 1。

题解 ​

思路 ​

先判断列号是否超出本行范围，再处理两端为 1 的情况；内部元素等于上一行相邻两项之和。可缓存已算过的行列。

知识点 ​

递归、边界条件第7章 常用的基本算法

代码（2026 秋整理） ​

python
import sys
from functools import lru_cache

n, m = map(int, input().split())
sys.setrecursionlimit(max(sys.getrecursionlimit(), 4 * n + 100))


@lru_cache(maxsize=None)
def pascal(row, column):
    if column < 0 or column > row:
        return 0
    if column == 0 or column == row:
        return 1
    return pascal(row - 1, column - 1) + pascal(row - 1, column)


print(pascal(n, m))

课程资料由授课教师、助教与同学共同积累。

PKU 计算概论 C · 历年资料归档