python练习题参考答案来了（超多代码），看一下？（1）

叶子陪你玩

发布于 2021-12-28 09:31:41

6650

文章被收录于专栏：叶子陪你玩编程叶子陪你玩编程

前面发了几篇python基础语法题目，主要用来帮助测试基础知识掌握的情况，如果都有认真看过或者做过的话，相信对自己的知识掌握情况应该有一定的了解了，接下来可以相应的去重新学习不是很清晰的那部分。

python基础语法很OK？做几题测试一下

python基础语法很OK？做几题测试一下（2）

python解决能力很OK？做几题测试一下（3）

上面三篇，第一篇和第二篇相对比较简单，第三篇内容，如果没有专门学习过数据结构与算法相关的内容，确实有一些难度。这是我们就反着来，先放上最难的这篇的参考答案，第一篇和第二篇下期放上。

如果第三篇内容还没看过的，建议先自己思考一下，按照自己已有的知识去试试。高效的学习或者说学习效果的学习，一定是单位时间内产生了大量的有效思维-即你努力思考过，尝试过各种方法，虽然最终没有做出来，但是这些思考是非常有帮助的，你知道你的困惑点与要解决的问题；看到参考答案的时候，与没有思考过的人，是完全不一样的，当这些内容被成功解决了，你的大脑应该会游戏微妙的变化，技术可能也会有突破。

下面正式进入主题。

为了让大家更好的理解后面的内容，先说说一些比较大的概念。

暴力循环（穷举）：绝大数计算机问题，在不考虑时间的情况下，都可以通过穷举来解决问题。

比如找零钱问题，我们可以通过穷举方法，将所有方案都找出来，然后找到数量最少的一种。

数独问题同样如此，每个位置有4种可能，可以将所有方法列出来，然后再去判断那种符合情况。

同理迷宫问题也是如此。

上面的说的暴力循环说起来很简单，但是也有些问题需要面对：

如何保证能够穷举出所有情况，不遗漏？
1. 比如3,4,5,6,四个数字，可以组合成多少种不重复的3位数？
2. 24点游戏，随机四个数字，1，3，6，9配合上加减乘除（+-*/），括号，能够组合出多少种情况呢？
如何判断当前的情况符不符合？问题不同，难度不同。（找零钱很好判断，迷宫和数独就稍微麻烦一点）。
数据量大了，搞了很久没出结果，怎么加快一些速度？
......

要想解决上面的一些问题，我们需要有一些策略，比如如何保证穷举出所有情况，数学中的排列组合就非常香。

怎样实现排列组合呢，方法很多，比如我之前用过多重循环，当然也可以用过递归。

全排列组合实现方法

这种方式保证一个不漏，树结构还有很多决策树都是类似的。

问题2具体问题具体分析。

问题3：就是降低数据规模，就像利用递归计算斐波那契数列，计算到40项后面，没增加一次，时间double一次，计算机卡好久，原因就是重复计算，可以通过一个列表来保存计算过的值，减少重复计算，速度就会显著提高。

比如在一个范围里面找目标数，如果从头到尾一个一个判断，那肯定慢，二分查找，一次可以砍掉一半，多大的范围，砍个几次都变小了。

1.找出下列列表中元组数值和最小的一个，同理最大值也是一样大。

[(0, 1, 2), (3, 4, 5), (6, 7, 8), (9, 10, 11), (12, 13, 14), (15, 16, 17), (18, 19, 20), (21, 22, 23), (24, 25, 26)]

结果：

最小值：(0, 1, 2)
最大值：(24, 25, 26)

2.找出下列列表中出现次数最多的元素，并打印出次数。

l = [1,3,4,5,6,1,3,4,5,1,9,1,1,1]

结果：

1出现最多，次数6次。

第一题和第二题参考：python 马赛克-像素图，里面以及给出了解决方法。

3.找零钱问题

给定可找的零钱种类，以及待找的零钱总数，求出最少的零钱数量方案。

比如找6元零钱，

方案1: 4 1 1;

方案2: 3,3;

方案3:3,1,1,1；

方案4:1,1,1,1,1,1；

明显方案2找的数量最少，只有2。

values = [1, 3, 4]  # 硬币面值
total = 6  # 需要找零钱总值

结果：

[3,3]

参考答案1-局部最优解：

# 找零钱目标数
total = 6
# 纸币种类
values = [4, 3, 1]
# 结果
number = [0,0,0]


# 循环，从最大面值开始考虑
for i in range(3):
    # 取整，算出当前面值可以找的最大张数
    number[i] = total // values[i]
    # 取余，算出当前面值找零后剩下的钱数
    total = total % values[i]
    
for i in range(3):
    print(values[i],'元的张数为:',number[i],'张')

参考答案2-全局最优解（动态规划）：

懒得写了，网上找了一个改了数字，感觉写的还是挺清楚的

def rec_mc(coin_value_list, change, know_results):
    min_coins = change
    if change in coin_value_list:
        know_results[change] = 1
        return 1
    elif know_results[change] > 0:
        return know_results[change]
    else:
        for i in [c for c in coin_value_list if c <= change]:
            num_coins = 1 + rec_mc(coin_value_list, change-i, know_results)
            if num_coins < min_coins:
                min_coins = num_coins
                know_results[change] = min_coins
    return min_coins
 
print("===========递归实现========================")
print(rec_mc([1, 3, 4], 6, [0]*7))
 
def dp_make_change(coin_value_list, change, min_coins, coins_used):
    for cents in range(change+1):
        coin_count = cents
        new_coin = 1
        for j in [c for c in coin_value_list if c <= cents]:
            if min_coins[cents-j] + 1 < coin_count:
                coin_count = min_coins[cents-j]+1
                new_coin = j
        min_coins[cents] = coin_count
        coins_used[cents] = new_coin
    return min_coins[change]
 
def print_coins(coins_used, change):
    coin = change
    while coin > 0:
        this_coin = coins_used[coin]
        print(this_coin)
        coin = coin - this_coin
 
a_mnt = 6
c_list = [1, 3, 4]
c_used = [0] * (a_mnt+1)
c_count = [0] * (a_mnt+1)
print("===========动态规划实现========================")
print('Making change for ', a_mnt, 'requires')
print(dp_make_change(c_list, a_mnt, c_count, c_used), 'coins')
print("They are: ")
print_coins(c_used, a_mnt)
print("The used list is as follows: ")
print(c_used)

4.数独4

利用程序自动完成4*4数独

[[0, 1, 0, 0], 
 [0, 0, 0, 2], 
 [3, 0, 0, 0],
 [0, 0, 4, 0]]

结果：

答案：

# 打印 board
def print_board(board):
    for row in board:
        print(row)

def check_board(num,row,col):
    # 检查行,判断行的每一个格子
    for i in range(cols):
        # 如果已经存在要填的数了
        if board[row][i] == num:
            return False
    # 检查列,判断列的每一个格子
    for i in range(rows):
        # 如果已经存在要填的数了
        if board[i][col] == num:
            return False
    return True

def backtrack(board, index):
    if index >= 16:
        print("----方案----")
        print_board(board)
        print("------------")   
    else:
        for num in range(1, len(board)+1):
            row = index//len(board)
            col = index%len(board[0])
            if board[row][col]==0:
                # 判断是否可以填该数字
                if not check_board(num, row, col):
                    continue
                # 选择一个数
                board[row][col] = num
                backtrack(board,index+1)
                # 取消选择的数
                board[row][col] = 0
            else:
                index = index +1
rows = 4
cols = 4
board = [[0 for i in range(rows)] for j in range(cols)]
board[0][1] = 1
board[1][3] = 2
board[2][0] = 3
board[3][2] = 4
index = 0
backtrack(board,index)

未封装的可视化数独版本：

from PIL import Image, ImageDraw
import matplotlib.pyplot as plt
#标题设置中文
plt.rc("font", family='MicroSoft YaHei', weight='bold')
plt.ion()

# 打印 board
def print_board(board):
    for row in board:
        print(row)


def show_board(board, x, y, num):
    img = Image.new("RGB", (100, 100), "white")
    draw = ImageDraw.Draw(img)
    for row in range(4):
        for col in range(4):
            pos = (0+30*col, 0+row*30)
            draw.text(pos, str(board[row][col]), fill=(0, 0, 255))
    draw.text((0+30*y, 0+x*30), str(num), fill=(255, 0, 255))
    return img

def check_board(num, row, col):
    # 检查行,判断行的每一个格子
    for i in range(cols):
        # 如果已经存在要填的数了
        if board[row][i] == num:
            return False
    # 检查列,判断列的每一个格子
    for i in range(rows):
        # 如果已经存在要填的数了
        if board[i][col] == num:
            return False
    return True


def backtrack(board, index):
    if index >= 16:
        print("----方案----")
        print_board(board)
        print("------------")
        img = show_board(board, 3, 3, board[3][3])
        plt.title("符合的方案")   # 标题
        plt.imshow(img)
        plt.pause(5)  # 暂停1秒
    else:
        for num in range(1, 4+1):
            row = index//4
            col = index % 4
            if board[row][col] == 0:
                # 判断是否可以填该数字
                if not check_board(num, row, col):
                    continue
                # 选择一个数
                board[row][col] = num
                plt.cla()  # 先清屏
                img = show_board(board, row, col, num)
                plt.title("填写一个数")   # 标题
                plt.imshow(img)
                plt.pause(1)  # 暂停1秒
                backtrack(board, index+1)
                # 取消选择的数
                board[row][col] = 0
                plt.cla()  # 先清屏
                img = show_board(board, row, col, num)
                plt.title("取消一个数")   # 标题
                plt.imshow(img)
                plt.pause(1)  # 暂停1秒
            else:
                index = index + 1


rows = 4
cols = 4
board = [[0 for i in range(rows)] for j in range(cols)]
board[0][1] = 1
board[1][3] = 2
board[2][0] = 3
board[3][2] = 4
# plt.pause(5)
img = show_board(board, 3, 3, board[3][3])
plt.title("4X4数独游戏")   # 标题
plt.imshow(img)
plt.pause(5)
plt.title("开始")
plt.pause(2)
index = 0
backtrack(board, index)
plt.pause(2)  # 暂停1秒
plt.ioff()
plt.show()

5.数独9

加大难度，利用程序自动完成9*9数独。

[[2, 0, 0, 0, 0, 0, 0, 0, 0],
 [0, 0, 3, 6, 0, 0, 0, 0, 0],
 [0, 7, 0, 0, 9, 0, 2, 0, 0],
 [0, 5, 0, 0, 0, 7, 0, 0, 0],
 [0, 0, 0, 0, 4, 5, 7, 0, 0],
 [0, 0, 0, 1, 0, 0, 0, 3, 0],
 [0, 0, 1, 0, 0, 0, 0, 6, 8],
 [0, 0, 8, 5, 0, 0, 0, 1, 0],
 [0, 9, 0, 0, 0, 0, 4, 0, 0]]

结果：很多种答案，下面只是列出了一些。

答案：

# 打印 board
def print_board(board):
    for row in board:
        print(row)

def check_board(num,row,col):
    # 检查该行该列是否有重复数字
    for i in range(9):
        if board[row][i] == num or board[i][col] == num:
            return False

    # 判断小九宫格是否有重复
    sub_row = row // 3
    sub_col = col // 3
    for i in range(3): 
        for j in range(3):
            if board[sub_row * 3 + i][sub_col * 3 + j] == num:
                return False
    return True

def backtrack(board, index):
    # print(index)
    if index >= 81:
        print("-----------方案-----------")
        print_board(board)
        print("--------------------------")   
    else:
        for num in range(1, 9+1):
            row = index//9
            col = index%9
            if board[row][col]==0:
                # 判断是否可以填该数字
                if not check_board(num, row, col):
                    continue
                # 选择一个数
                board[row][col] = num
                # 继续选择下一个数
                backtrack(board,index+1)
                # 取消选择的数
                board[row][col] = 0
            else:
                # backtrack(board,index+1)
                index = index + 1

board = [[2, 0, 0, 0, 0, 0, 0, 0, 0],
         [0, 0, 3, 6, 0, 0, 0, 0, 0],
         [0, 7, 0, 0, 9, 0, 2, 0, 0],
         [0, 5, 0, 0, 0, 7, 0, 0, 0],
         [0, 0, 0, 0, 4, 5, 7, 0, 0],
         [0, 0, 0, 1, 0, 0, 0, 3, 0],
         [0, 0, 1, 0, 0, 0, 0, 6, 8],
         [0, 0, 8, 5, 0, 0, 0, 1, 0],
         [0, 9, 0, 0, 0, 0, 4, 0, 0]]

index = 0
backtrack(board,index)

未封装的可视化数独版本：

from PIL import Image,ImageDraw
import matplotlib.pyplot as plt
#标题设置中文
plt.rc("font", family='MicroSoft YaHei', weight='bold')
plt.ion()

# 打印 board
def print_board(board):
    for row in board:
        print(row)


def show_board(board,x,y,num):
    img = Image.new("RGB", (250, 250), "white")
    draw = ImageDraw.Draw(img)
    for row in range(9):
        for col in range(9):
            pos = (0+30*col, 0+row*30)
            draw.text(pos, str(board[row][col]), fill=(0, 0, 255))
    draw.text((0+30*y, 0+x*30), str(num), fill=(255, 0, 255))
    return img


def check_board(num, row, col):
    # 检查该行该列是否有重复数字
    for i in range(9):
        if board[row][i] == num or board[i][col] == num:
            return False

    # 判断小九宫格是否有重复
    sub_row = row // 3
    sub_col = col // 3
    for i in range(3):
        for j in range(3):
            if board[sub_row * 3 + i][sub_col * 3 + j] == num:
                return False
    return True


def backtrack(board, index):
    global count
    # print(index)
    if index >= 81:
        count = count + 1
        img = show_board(board, 8, 8, board[8][8])
        plt.title("第{}个符合的方案 暂停1s".format(count))   # 标题
        plt.imshow(img)
        plt.pause(1)  # 暂停1秒
        plt.title("下一个方案")   # 标题
        plt.pause(1)  # 暂停1秒
        print("-----------------------")
        print_board(board)
    else:
        for num in range(1, 9+1):
            row = index//9
            col = index % 9
            if board[row][col] == 0:
                # 判断是否可以填该数字
                if not check_board(num, row, col):
                    continue
                # 选择一个数
                board[row][col] = num
                plt.cla()  # 先清屏
                img = show_board(board,row,col,num)
                plt.title("填写一个数")   # 标题
                plt.imshow(img)
                plt.pause(0.1)  # 暂停1秒
                # 继续选择下一个数
                backtrack(board, index+1)
                # 取消选择的数
                board[row][col] = 0
                plt.cla()  # 先清屏
                img = show_board(board,row,col,num)
                plt.title("取消一个数")   # 标题
                plt.imshow(img)
                plt.pause(0.1)  # 暂停1秒
            else:
                # backtrack(board,index+1)
                index = index + 1
                plt.cla()  # 先清屏
board = [[2, 0, 0, 0, 0, 0, 0, 0, 0],
         [0, 0, 3, 6, 0, 0, 0, 0, 0],
         [0, 7, 0, 0, 9, 0, 2, 0, 0],
         [0, 5, 0, 0, 0, 7, 0, 0, 0],
         [0, 0, 0, 0, 4, 5, 7, 0, 0],
         [0, 0, 0, 1, 0, 0, 0, 3, 0],
         [0, 0, 1, 0, 0, 0, 0, 6, 8],
         [0, 0, 8, 5, 0, 0, 0, 1, 0],
         [0, 9, 0, 0, 0, 0, 4, 0, 0]]

img = show_board(board, 8, 8, board[8][8])
plt.title("9X9数独游戏")   # 标题
plt.imshow(img)
plt.pause(2)
plt.title("开始")
plt.pause(2)
index = 0
global count
count = 0
backtrack(board, index)
# plt.ioff()
plt.show()

6.迷宫问题

给定一个大小为5*6的迷宫，由通道(0)和墙壁(1)组成，其中通道左上角表示起点，通道右下角表示终点，找到迷宫路径。

maze = [[0, 1, 0, 0, 0],
        [0, 0, 0, 1, 0],
        [0, 1, 0, 1, 0],
        [1, 1, 1, 0, 0],
        [0, 1, 0, 0, 1],
        [0, 1, 0, 0, 0]]

结果：

[[0, 0], [1, 0], [1, 1], [1, 2], [0, 2], [0, 3], [0, 4],
 [1, 4], [2, 4], [3, 4], [3, 3], [4, 3], [5, 3], [5, 4]]

答案1：

# 最短距离  最短路径
maze =[[0, 1, 0, 0, 0],
       [0, 1, 0, 1, 0],
       [0, 0, 0, 0, 0],
       [0, 1, 1, 1, 0],
       [0, 0, 0, 1, 0]]
n,m = len(maze),len(maze[0])
start = [0, 0]
end = [4, 4]
# 待查找的数据列表
search_queue = []  # 列表模拟队列
# 添加起点
search_queue.append(start)
visted = []  # 记录访问过的点
visted.append(start)

def find_next_point(point):
    global search_queue,visted,n,m
    # 通过px 和 py数组来实现左下右上的移动顺序
    px = [-1, 0, 1, 0]   
    py = [0, -1, 0, 1]
    # 上下左右移动
    for i in range(4):
        next_x = point[0] + px[i]
        next_y = point[1] + py[i]
        # 如何下个点满足要求，添加到待搜索队列和访问队列
        if (0 <= next_x < n and 0 <= next_y < m and maze[next_x][next_y] == 0 and [next_x,next_y] not in visted):
            search_queue.append([next_x,next_y])
            visted.append([next_x,next_y])
            return True     
    return False
    

def dfs():
    global search_queue,visted
    print(search_queue)
    while search_queue[-1] != end:
        # 获取队列最后一个点，判断是否到大终点
        point = search_queue[-1]
        # 如果存在下一个点，则继续
        if find_next_point(point):
            continue
        # 否则删除刚才添加的哪个点
        else:
            print("删除",search_queue.pop())
    print(search_queue)

dfs()

答案2：

上面比较难理解的，可以看下面这个，网上找了一个简单的改了改，比较容易理解，但是代码比较多

def up(point):
    # 到达了数组顶端,不能继续往上走
    if point[0] == 0:
        return False
    else:
        new_point = [point[0] - 1, point[1]]
        # 走过的路不再走
        if new_point in visted:
            return False
        # 遇到墙不走
        elif maze[new_point[0]][new_point[1]] == 1:
            return False
        else:
            search_queue.append(new_point)
            visted.append(new_point)
            return True
 
 
def down(point):
    # 遇到迷宫最下方的时候，不能继续往下走
    if point[0] == len(maze) - 1:  # 6行5列的二维数组行数，从0开始计算所以是6-1=5 行
        return False
    else:
        new_point = [point[0] + 1, point[1]]
        # 走过的路不再走
        if new_point in visted:
            return False
        # 遇到墙不走
        elif maze[new_point[0]][new_point[1]] == 1:
            return False
        else:
            visted.append(new_point)
            search_queue.append(new_point)
            return True
 
 
def left(point):
    # 遇到迷宫最左边，不能继续往左走
    if point[1] == 0:
        return False
    else:
        new_point = [point[0], point[1] - 1]
        # 走过的路不再走
        if new_point in visted:
            return False
        # 遇到墙不走
        elif maze[new_point[0]][new_point[1]] == 1:
            return False
        else:
            visted.append(new_point)
            search_queue.append(new_point)
            return True
 
 
def right(point):
    # 遇到迷宫最右边，不能继续向右移动
    if point[1] == len(maze[0]) - 1:  # 6行5列的二维数组列数，从0开始计算所以是5-1=4行
        return False
    else:
        new_point = [point[0], point[1] + 1]
        # 走过的路不再走
        if new_point in visted:
            return False
        # 遇到墙不走
        elif maze[new_point[0]][new_point[1]] == 1:
            return False
        else:
            visted.append(new_point)
            search_queue.append(new_point)
            return True
 

maze = [[0, 1, 0, 0, 0],
        [0, 0, 0, 1, 0],
        [0, 1, 0, 1, 0],
        [1, 1, 1, 0, 0],
        [0, 1, 0, 0, 1],
        [0, 1, 0, 0, 0]]
start = [0, 0]
end = [5, 4]

search_queue = []
visted = []
search_queue.append(start)
visted.append(start)

print("start: %s --> end: %s\n" % (start, end))
while search_queue[-1] != end:
    now = search_queue[-1]
    if up(now) or down(now) or left(now) or right(now):
        continue
    print("删除",search_queue.pop())
 
print("final path: ", search_queue)

7.迷宫问题2-最短路径。

给定一个大小为5*5的迷宫，由通道(0)和墙壁(1)组成，其中通道左上角表示起点，通道右下角表示终点，找到迷宫最短路径。

maze = [[0, 1, 0, 0, 0,],
        [0, 1, 0, 1, 0,],
        [0, 0, 0, 0, 0,],
        [0, 1, 1, 1, 0,],
        [0, 0, 0, 1, 0,]]

这里有两种方案，不过方案2才是最短路径。

答案：

# 最短距离  最短路径
maze =[[0, 1, 0, 0, 0],
       [0, 1, 0, 1, 0],
       [0, 0, 0, 0, 0],
       [0, 1, 1, 1, 0],
       [0, 0, 0, 1, 0]]
n,m = len(maze),len(maze[0])
start = [0, 0]
end = [4, 4]

# 定义 Breadth First Search 算法
def bfs(maze,n,m):
    # 待查找的数据列表
    search_queue = []  # 列表模拟队列
    # 添加起点
    search_queue.append(start)
    visted = []  # 记录访问过的点
    visted.append(start)
    # 记录父节点
    parent = {f"{start[0]}{start[1]}":None}
    px = [-1, 0, 1, 0]   # 通过px 和 py数组来实现左下右上的移动顺序
    py = [0, -1, 0, 1]
    # 直到查找队列为空退出循环
    while search_queue:
        # 取出队列中的第一个点(最近开始搜索)
        point = search_queue.pop(0)
        # 获取最近的所有点
        points = []
        for i in range(4):
            next_x = point[0] + px[i]
            next_y = point[1] + py[i]
            if (0 <= next_x < n and 0 <= next_y < m and maze[next_x][next_y] == 0):
                points.append([next_x,next_y])
        for i in points:
            # 如果 i没有被访问过
            if i not in visted:
                # 添加 i( 最近的点)到搜索队列中
                search_queue.append(i)
                # 标记 i 为已经访问过
                visted.append(i)
                # 记录每个点的父节点
                parent[f"{i[0]}{i[1]}"] = point
    return visted,parent

visted,parent = bfs(maze,n,m)

route_list = []
if end in visted:
    print(f"存在从{start}到{ end}的路线")
    v = end # 当前访问的点
    # 直到起点位置 None 退出
    while v !=None:
        route_list.append(v)
        v=parent[f"{v[0]}{v[1]}"]
else:
    print(f"不存在从{start}到{ end}的路线")
route_list.reverse()
print(route_list)

上面的方法如何看到比较吃力，可以去看看DFS和BFS，回溯，递归等概念。也可以先看看我之前写的，后面有时间更新一下，之前写的不咋样，凑合着看。

递归算法（上）

递归算法（下）

全排列组合实现方法

学习算法的感想 (全文完)

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2021-12-22，如有侵权请联系 cloudcommunity@tencent.com 删除

python