数据结构与算法python版MOOC第五周

本系列博客基于“ (北京大学)数据结构与算法python版”慕课&＃xff0c;课程在中国大学慕课和bilibili上均可找到。

1. 内容

1. 递归三定律&＃xff1a;算法有一个基本结束条件&＃xff0c;算法会改变状态向基本结束条件演化&＃xff0c;算法需要调用自身
2. 递归的应用&＃xff1a;任意进制转换&＃xff0c;分形树&＃xff0c;谢尔宾斯基三角形&＃xff0c;汉诺塔&＃xff0c;探索迷宫
3. 海龟作图介绍

2. 课程代码

在GitHub中下载

3. OJ作业

所有代码均可在github中下载

3.1 进制转换

题目内容&＃xff1a;
   给定一个M进制的数&＃xff0c;请将其转换为N进制并输出

输入格式: 两行&＃xff0c;第一行为空格分隔的两个数字&＃xff0c;分别为10进制表示的M与N&＃xff1b;其中M, N均满足2 ≤ M、N ≤ 36。第二行为待转换的M进制数字&＃xff0c;其中每位超过9的部分从10至36分别用大写字母A-Z表示&＃xff1b;输入数据保证数据的每一位不超过M
输出格式&＃xff1a;一行字符串&＃xff0c;表示转换后的N进制数

输入样例&＃xff1a;
8 16
‭471‬
输出样例&＃xff1a;
‭139
方法&＃xff1a;先把输入转为十进制 再构建一个convert_ten_other函数进行递归

number &＃61; [str(i) for i in range(10)]
big_letter &＃61; [chr(i) for i in range(65, 91)]
num_string &＃61; number&＃43;big_letter # 存储输出数字的每个字符def func(in_number, m, n):# 将输入转为10进制in_sum &＃61; 0for i in range(len(in_number)):current_character &＃61; in_number[len(in_number)-i-1] # 当前要计算的位数的字符in_sum &＃61; in_sum&＃43;num_string.index(current_character)*pow(m, i)out_number &＃61; convert_ten_other(in_sum, n)return out_number# 十进制转其他进制的递归函数
def convert_ten_other(in_number, base):if in_number &＃61;&＃61; 0:return &＃39;&＃39;else:return convert_ten_other(in_number//base, base) &＃43; num_string[in_number % base]#
m, n &＃61; list(map(int, input().split()))
in_number &＃61; input()
print(func(in_number, m, n))


3.2 四柱汉诺塔

题目内容&＃xff1a;

   如课上所说&＃xff0c;汉诺塔问题源于印度一个古老传说。对于原始的汉诺塔游戏&＃xff0c;可供玩家操作的空间一共只有三根柱子&＃xff0c;导致按原传说的要求&＃xff0c;需要超过1.8*10^19步才能解开。
   透过新增柱子可以大幅度地减少需要的步数。此处要求在给出指定的盘数&＃xff0c;柱子数量为4&＃xff08;即限制为4根柱子&＃xff09;且不改变原有传说的其他规则的限制下&＃xff0c;找出完成迁移的最小步骤数。

输入格式: 一个非负整数M&＃xff0c;M代表盘数&＃xff0c;M<&＃61;1000。
输出格式&＃xff1a; 一个非负整数&＃xff0c;表示完成迁移的最小步骤数。

输入样例&＃xff1a;
3
输出样例&＃xff1a;
5

方法&＃xff1a;
   输入M代表盘数 输出为完成迁移的最小步骤数。四柱汉诺塔的步骤如下

1. 4柱汉诺塔算法把A柱上部分的n- r个碟子通过C柱和D柱移到B柱上【F( n- r )步】
2. 用3柱汉诺塔经典算法把A柱上剩余的r个碟子通过C柱移到D柱上【2^r-1步】
3. 用4柱汉诺塔算法把B柱上的n-r个碟子通过A柱和C柱移到D柱上【F(n-r)步】
4. 求出所有r情况下的步数&＃xff0c;取最小值
   可以发现每个n的最小步数是一个斐波那契数列&＃xff0c;所以得到最小步数公式为 F(n)&＃61;min(2*F(n-r)&＃43;2^r-1)&＃xff0c;&＃xff08;1≤r≤n&＃xff09;。
   代码

def calculate_min_step(m):min_step_list &＃61; [0]*(m&＃43;1) # 存储每种盘子数下的最小步数for n in range(1, m&＃43;1): # 在n个盘的情况下n_max &＃61; 1e10 # 先把n个盘的步数设为一个很大的数for r in range(1, n&＃43;1):n_sum &＃61; 2*min_step_list[n-r]&＃43;pow(2, r)-1 # 在r为某值时&＃xff0c;移动n个盘需要的步数if n_sum < n_max:n_max &＃61; n_summin_step_list[n] &＃61; n_max# print(min_step_list)# print(min_step_list[m])return min_step_list[m]m &＃61; int(input())
print(calculate_min_step(m))


3.3 ASCII谢尔宾斯基地毯

   谢尔宾斯基地毯是形如上图的正方形分形图案&＃xff0c;每个地毯可分为等大小的9份&＃xff0c;其中中央挖空&＃xff0c;其余均由更小的地毯组成。
   现给定地毯大小&＃xff08;行数&＃xff09;与组成地毯的字符元素&＃xff0c;请打印相应的地毯图形。
   注&＃xff1a;空腔以半角空格表示&＃xff1b;当给定字符元素长度不为1时空格数须与字符长度对应

输入格式: 输入为两行&＃xff0c;分别为地毯大小正整数N与组成元素字符串c。输入数据保证N为3的正整数幂
输出格式&＃xff1a;由N行长度为N*len©的字符串构成的谢尔宾斯基地毯

输入样例&＃xff1a;
9
[]

输出样例&＃xff1a;
[][][][][][][][][]
[] [][] [][] []
[][][][][][][][][]
[][][] [][][]
[] [] [] []
[][][] [][][]
[][][][][][][][][]
[] [][] [][] []
[][][][][][][][][]

方法&＃xff1a;空腔以半角空格表示&＃xff1b;当给定字符元素长度不为1时空格数须与字符长度对应。输入为两行分别为地毯大小正整数N与组成元素字符串c。输出为由N行长度为N * len(c&＃xff09;的字符串构成的谢尔宾斯基地毯
   先构造一个N*N的空格矩阵 空格的长度由字符串长度决定。递归赋值 当N//3&＃61;&＃61;0 直接赋值字符串 其余情况 找到四周八个正方形&＃xff0c;调用函数&＃xff0c;
   oj显示格式错误&＃xff0c;不知道什么原因

# 主函数
def carpet(N, char):char_len &＃61; len(char)global string_matrixblank &＃61; &＃39; &＃39;*char_len # 填充空格大小dstring_matrix &＃61; [[blank]*N for i in range(N)] # 初始化矩阵draw_square(N, char, 0, 0)# 打印地毯for i in range(N): # 行print_string &＃61; &＃39;&＃39;.join(item for item in string_matrix[i])print(print_string)print(&＃39;\n&＃39;)return# 画地毯递归函数
def draw_square(n, char, x, y): # 注意 n是当前正方形边长&＃xff0c;x是正方形左上顶点行号&＃xff0c;y是左上顶点列号if n//3 &＃61;&＃61; 0:string_matrix[x][y] &＃61; charreturnelse:point_list &＃61; compute_point(n, x, y)for item in point_list:draw_square(n//3, char, item[0], item[1])return# 计算周围正方形的坐标
def compute_point(n, x, y):point_list &＃61; [] # 按照顺时针方向 x是竖着 y是横着sl &＃61; n//3 # 小正方形边长point_list.append([x, y]) # 1point_list.append([x, y&＃43;sl]) # 2point_list.append([x, y&＃43;2*sl]) # 3point_list.append([x&＃43;sl, y&＃43;2*sl]) # 4point_list.append([x&＃43;2*sl, y&＃43;2*sl]) # 5point_list.append([x&＃43;2*sl, y&＃43;sl]) # 6point_list.append([x&＃43;2*sl, y]) # 7point_list.append([x&＃43;sl, y]) # 8return point_listn &＃61; int(input())
c &＃61; input()
carpet(n, c)