深圳微信商城网站设计联系电话,哪些行业做网站多,wordpress 文章 打赏,假冒中国建设银行的网站问题描述
原题传送门#xff1a;1.五子棋对弈 - 蓝桥云课
在五子棋的对弈中#xff0c;友谊的小船说翻就翻#xff1f; 不#xff01;对小蓝和小桥来说#xff0c;五子棋不仅是棋盘上的较量#xff0c;更是心与心之间的沟通。这两位挚友秉承着友谊第…问题描述
原题传送门1.五子棋对弈 - 蓝桥云课
在五子棋的对弈中友谊的小船说翻就翻 不对小蓝和小桥来说五子棋不仅是棋盘上的较量更是心与心之间的沟通。这两位挚友秉承着友谊第一比赛第二的宗旨决定在一块 5×5 的棋盘上用黑白两色的棋子来决出胜负。但他们又都不忍心让对方失落于是决定用一场和棋平局作为彼此友谊的见证。
比赛遵循以下规则
棋盘规模比赛在一个 5×5 的方格棋盘上进行共有 25 个格子供下棋使用
棋子类型两种棋子黑棋与白棋代表双方。小蓝持白棋小桥持黑棋
先手规则白棋小蓝具有先手优势即在棋盘空白时率先落子下棋
轮流落子玩家们交替在棋盘上放置各自的棋子每次仅放置一枚
胜利条件率先在横线、竖线或斜线上形成连续的五个同色棋子的一方获胜
平局条件当所有 25 个棋盘格都被下满棋子而未决出胜负时游戏以平局告终
在这一设定下小蓝和小桥想知道有多少种不同的棋局情况既确保棋盘下满又保证比赛结果为平局。
答案提交
这是一道结果填空题你只需要算出结果后提交即可。本题的结果为一个整数在提交答案时只填写这个整数填写多余的内容将无法得分。
问题分析
说实话在赛场看到这样的题目说不慌张都是骗人的尤其是其还放在填空题中这对于我们这种水平偏中下的同学来说更是一个较为严峻的挑战。
本题在官方的难度分类中为中等题但是在小玉看来其难度就算在中等那也是中等中偏难的那种所以没有解题成功的同学并不需要慌张也不要气馁你能够在编程软件上敲下你的想法就已经超过了赛场上的很多人这是真的很多时候我们更应该做的是相信自己 (ง๑ •̀_•́)ง
言归正传万事开头难我们先来简单分析一下这个题目
这里的关键是统计所有可能的满盘棋局并确保没有出现五子连珠的情况。由于棋盘规模是 5×5共有 25! 种不同的落子顺序直接遍历是不可行的需要更高效的方法。
我们可以采用回溯 剪枝的方法进行搜索
回溯搜索逐步填充棋盘每次轮流落子白棋先手。剪枝在填充的过程中如果某个状态下已经形成五子连珠则立即剪枝不再继续。终止条件当棋盘填满时若没有五子连珠的情况则计数。
这个方法考虑了所有可能的棋局排列并检查是否有五子连珠的情况。但由于 25! 过于庞大直接使用排列组合的方法会导致计算量过大优化点在于
使用位运算或更紧凑的数据结构 以减少存储开销提前剪枝 在确定某个局面已经形成五子连珠时尽早结束
如果需要进一步优化可以考虑更复杂的数据结构如Zobrist哈希来避免重复计算。
上面是我一开始看到这个题目时脑子里所有冒出来的想法先不管对不对有想法就要坚持去实践万一实现了呢 [狗头先欠着]
下面是我开始解题时编写的python代码
当然这个代码是错误的因为只考虑到了逻辑上的可行性并没有考虑到实际运算的可行性有兴趣的同学可以将我错误示例与自己的相对比在错误中学习
def generate_permutations(elements):递归生成列表元素的全排列手工实现 permutations 生成器参数elements: list需要生成排列的元素列表Yieldslist: 一个排列组合# 基本情况空列表只有一种排列空列表if len(elements) 0:yield []else:# 遍历每个元素作为排列的第一个元素for i in range(len(elements)):# 排除当前元素后的剩余元素列表rest elements[:i] elements[i1:]# 递归生成剩余元素的所有排列for p in generate_permutations(rest):# 将当前元素与子排列组合yield [elements[i]] pdef check_five_in_a_row(board):检查五子棋棋盘是否存在五连珠情况参数board: list[list[int]]5x5的二维数组0表示空1/2表示玩家返回bool: 是否存在五连珠def check_line(x, y, dx, dy):检查从(x,y)出发沿(dx,dy)方向是否存在五连珠参数x, y: 起始坐标dx, dy: 方向步长取值应为0或±1返回bool: 是否五连color board[x][y]# 空位置直接返回否if color 0:return False# 检查连续五个位置for i in range(1, 5): # 只需要检查后续四个位置共五个nx, ny x i*dx, y i*dy# 确保不会越界根据调用方式其实不需要但保留更安全if nx 5 or ny 5 or nx 0 or ny 0:return Falseif board[nx][ny] ! color:return Falsereturn True# 检查所有可能的五连珠路线for i in range(5):# 横向检查每行的起始位置if check_line(i, 0, 0, 1):return True# 纵向检查每列的起始位置if check_line(0, i, 1, 0):return True# 对角线检查return check_line(0, 0, 1, 1) or check_line(0, 4, 1, -1)def count_draw_games():计算所有可能的平局棋局数量无五连珠的完整棋盘注意此实现因时间复杂度为O(25!)而无法实际运行仅作为逻辑演示返回int: 平局数量理论值# 生成所有棋盘位置坐标positions [(i, j) for i in range(5) for j in range(5)]draw_count 0# 遍历所有可能的落子顺序排列for perm in generate_permutations(positions):# 初始化空棋盘board [[0] * 5 for _ in range(5)]# 模拟落子过程for turn, (x, y) in enumerate(perm):# 交替玩家落子玩家1先手board[x][y] 1 if turn % 2 0 else 2# 每次落子后立即检查五连珠if check_five_in_a_row(board):break # 出现五连则终止当前棋局else:# 完整25步且无五连珠的情况计数draw_count 1return draw_count# 注意实际运行时本代码无法完成计算
print(count_draw_games())
好现在我们来真正地说一说本题的正确打开方式
首先如果你想要顺利的解出本题那么你需要了解一个至关重要的知识点将线性位置转换为二维坐标这个思路可以用于解决所有和本题相似的题目中
如果你不清楚这个知识点请你将下面得到两个式子记住如果你想了解这个式子是如何推导得到的欢迎访问我的个人网站在算法必备知识点模块数学篇可以找到相关的推导好吧现在网站没有了wuwuwuwu好消息是我找到了一个大佬写的解析希望可以为你解惑关于坐标压缩式子的解压缩式子-CSDN博客 x (position - 1) // line_size 1 # 行坐标y (position - 1) % line_size 1 # 列坐标
假设现在有一个坐标轴那么其中的position为坐标轴上的刻度也就是线性坐标Xline_size为你希望将其转换到二维坐标系下的坐标系长度二维平面XOY我们假设这个平面就像棋盘一样每一边都有其边长其中line_size就是这个边长此后我们便可以通过这个式子计算转换之后的每个点对应的二维坐标在本题中我们还应该注意到两条对角线索引计算的差异 主对角线xy范围2-10 副对角线x-y5转换负数为正数范围1-9
其次我们需要使用四个数组分别跟踪行、列、对角线的棋子差值白棋1黑棋-1由于棋盘上总共能放下 5x5 共25个棋子且 白棋先手轮流落子因此我们可以认为 初始白子13颗 初始黑子12颗
而防止有一方连成5子赢得比赛我们应该有对于二者棋子数量的 绝对值的限制4以确保同一颜色不会出现5连。
这点也可以成为我们后续简化代码的关键剪枝条件 白棋条件各方向统计值 4保证还能放白棋 黑棋条件各方向统计值 -4保证还能放黑棋
代码描述
当分析到这里对于知识点掌握比较扎实的同学应该可以猜到小玉要使用什么算法来解决本题了没错就是你想的那种就是——记忆化搜索启发式剪枝并行计算(劝退)
我们大概来介绍一下这几个小方向 记忆化搜索 缓存重复出现的棋盘状态 并行计算 将搜索树分解为多个子树并行处理 启发式剪枝 提前识别无效路径如双方都无法形成连线
其实这三个内容在上面的思路分析部分已经多多少少提到过了有没有课代表愿意画画重点呢要考的那么本题的具体代码如下让我们跟着思路一步一步实现 初始化棋盘尺寸和平局计数器 board_size 设置棋盘的大小为5。draw_count 用来记录平局的次数。 board_size 5 # 棋盘边长本题为正方形棋盘
draw_count 0 # 记录平局的次数 创建棋盘状态跟踪系统 使用四个数组来分别跟踪行、列、主对角线和副对角线上的棋子差值。白棋记为1黑棋记为-1。 row_count行差值统计数组长度为 board_size 1索引从1开始。 col_count列差值统计数组长度和索引同上。 main_diag_count主对角线差值统计数组长度为 2 * board_size 1索引对应于对角线上的位置。 anti_diag_count副对角线差值统计数组长度同上索引对应于副对角线上的位置。 # 统计数组分别记录行、列、主对角线、副对角线的棋子数
row_count [0] * (board_size 1)
col_count [0] * (board_size 1)
main_diag_count [0] * (2 * board_size 1)
anti_diag_count [0] * (2 * board_size 1) 定义递归函数 count_draw_games 参数 position 表示当前放置棋子的位置从1开始。 参数 white_pieces 和 black_pieces 分别表示剩余可以放置的白棋和黑棋的数量。 从线性坐标轴上看当 position 达到棋盘大小的平方加一时表示所有位置已填满此时增加 draw_count即达到和棋条件 将线性位置转换为二维坐标行 x 和列 y。 def count_draw_games(position, white_pieces, black_pieces):global draw_count# 终止条件所有位置已填满if position board_size * board_size 1:draw_count 1return# 将线性位置转换为二维坐标1-basedx (position - 1) // board_size 1 # 行坐标1-5y (position - 1) % board_size 1 # 列坐标1-5# 尝试放置白棋先手方需要多一个棋子if white_pieces 0:# 剪枝条件保证所有方向上白棋不超过4个if (row_count[x] board_size - 1 and # 行方向还能放白棋col_count[y] board_size - 1 and # 列方向还能放白棋main_diag_count[x y] board_size - 1 and # 主对角线方向anti_diag_count[x - y board_size] board_size - 1): # 副对角线方向# 更新所有跟踪数组row_count[x] 1col_count[y] 1main_diag_count[x y] 1anti_diag_count[x - y board_size] 1# 递归处理下一个位置count_draw_games(position 1, white_pieces - 1, black_pieces)# 回溯恢复状态row_count[x] - 1col_count[y] - 1main_diag_count[x y] - 1anti_diag_count[x - y board_size] - 1# 尝试放置黑棋if black_pieces 0:# 剪枝条件保证所有方向上黑棋不超过4个# 注意这里的比较方向是反的因为黑棋用负数表示if (row_count[x] 1 - board_size and # 行方向还能放黑棋col_count[y] 1 - board_size and # 列方向还能放黑棋main_diag_count[x y] 1 - board_size and # 主对角线方向anti_diag_count[x - y board_size] 1 - board_size):# 更新所有跟踪数组黑棋用减法row_count[x] - 1col_count[y] - 1main_diag_count[x y] - 1anti_diag_count[x - y board_size] - 1# 递归处理下一个位置count_draw_games(position 1, white_pieces, black_pieces - 1)# 回溯恢复状态row_count[x] 1col_count[y] 1main_diag_count[x y] 1anti_diag_count[x - y board_size] 1 以上便是本题的所有代码了以下是上述代码的总结 # 棋盘尺寸
board_size 5
# 平局计数器
draw_count 0
创新性的棋盘状态跟踪系统
使用四个数组分别跟踪行、列、对角线的棋子差值白棋1黑棋-1
这种设计使得我们可以在 O(1) 时间内判断是否允许落子# 行差值统计索引1-5
row_count [0] * (board_size 1)
# 列差值统计索引1-5
col_count [0] * (board_size 1)
# 主对角线左上到右下差值统计xy范围2-10
main_diag_count [0] * (2 * board_size 1)
# 副对角线右上到左下差值统计x-y5范围1-9
anti_diag_count [0] * (2 * board_size 1)def count_draw_games(position, white_pieces, black_pieces):global draw_count# 终止条件所有位置已填满if position board_size * board_size 1:draw_count 1return# 将线性位置转换为二维坐标1-basedx (position - 1) // board_size 1 # 行坐标1-5y (position - 1) % board_size 1 # 列坐标1-5# 尝试放置白棋先手方需要多一个棋子if white_pieces 0:# 剪枝条件保证所有方向上白棋不超过4个if (row_count[x] board_size - 1 and # 行方向还能放白棋col_count[y] board_size - 1 and # 列方向还能放白棋main_diag_count[x y] board_size - 1 and # 主对角线方向anti_diag_count[x - y board_size] board_size - 1): # 副对角线方向# 更新所有跟踪数组row_count[x] 1col_count[y] 1main_diag_count[x y] 1anti_diag_count[x - y board_size] 1# 递归处理下一个位置count_draw_games(position 1, white_pieces - 1, black_pieces)# 回溯恢复状态row_count[x] - 1col_count[y] - 1main_diag_count[x y] - 1anti_diag_count[x - y board_size] - 1# 尝试放置黑棋if black_pieces 0:# 剪枝条件保证所有方向上黑棋不超过4个# 注意这里的比较方向是反的因为黑棋用负数表示if (row_count[x] 1 - board_size and # 行方向还能放黑棋col_count[y] 1 - board_size and # 列方向还能放黑棋main_diag_count[x y] 1 - board_size and # 主对角线方向anti_diag_count[x - y board_size] 1 - board_size):# 更新所有跟踪数组黑棋用减法row_count[x] - 1col_count[y] - 1main_diag_count[x y] - 1anti_diag_count[x - y board_size] - 1# 递归处理下一个位置count_draw_games(position 1, white_pieces, black_pieces - 1)# 回溯恢复状态row_count[x] 1col_count[y] 1main_diag_count[x y] 1anti_diag_count[x - y board_size] 1# 初始化递归白棋13个黑棋12个
count_draw_games(1, (board_size * board_size 1) // 2, board_size * board_size // 2)print(draw_count)
结果提交
上述代码的运行结果 将上述代码提交到蓝桥杯官网 写在后面
本题的成功解决也告诉我们不应该随便忽略题设中的任何一个条件和字眼也就是审题是务必全面仔细实际赛场中如果你在未完全使用题设条件的前提下编写出了代码那其在实际测试时的样例通过率可能会非常感人
有小伙伴私信提到实际运行时间上的问题我想说的是实际赛场上的测试软件中对于python这个编程语言还是比较宽容的所以其实并不用太过于焦虑担心运行用时这块的问题。
且本题只是一个填空题并不需要多高超的解题方法在分析实际代码的时间复杂度允许的情况下我们完全可以选择舍弃一点时间来换取答案的准确性。
那么对于上述代码其实还可以在某些地方再次进行简化亲爱的小伙伴请问你看出来了吗欢迎在评论区交流哦~
