算法是编程的核心,是计算机解决问题的方法流程,简单说来,算法就是解决问题的步骤。如果用我们熟知的事物来类比,算法就像是菜谱,按照正确的顺序遵从这些步骤做菜,做出的菜会很美味。同样的道理,计算机按照算法描述的流程来执行程序,会得出美妙的计算结果。
学习Python编程不仅仅是学习Python编程语言本身,计算机算法也同样的重要。计算机语言和技术日新月异,但万变不离其宗的永远是算法。算法就是编程的内功、精髓。因此,要想学好编程,掌握算法知识必不可少。
易嘉编程趣味算法系列将基于Python3为各位同学讲解日常工作、生活和学习中常用的算法。一起来看一个实际的问题场景,到底怎样巧妙地利用算法解决场景中的问题呢?
Part.1
问题场景:
小明的爷爷喜欢读报纸,更喜欢钻研报纸上的数独题,一天,小明爷爷对报纸上一个标题为世界上最难的数独题发起挑战。
这个数独题是芬兰数学家因卡拉花费3个月时间设计出来的,号称世界上迄今难度最大的数独游戏,而且只有一个答案。因此卡拉说只有思考能力最快、头脑最聪明的人才能破解这个游戏。
小明的爷爷做了好长时间时间没做出来,于是就找到了小明,希望小明能帮忙解出答案。
这个数独如下:
现在该如何通过Python编程快速准确地解决这个问题呢?
首先,分析问题,明确问题会用到的知识,并设计解决问题的步骤;
其次,找出解决步骤对应的算法,编写程序代码来实现这个算法;
最后,运行程序代码,即可得出结果。
Part.2
分析思路:
解答这个数独题,那么我们最应该做的是先了解数独的游戏规则。
这题正好是一个以9宫数独题,在9阶方阵中,包含了81个小格(九列九行),其中又再分成九个小正方形(称为宫),每宫有九小格。数独(sudoku)是一种在宫格里面填数的小游戏,标准数独的规则一般都只有三点:
- 每行内的数字为1-9且不重复;
- 每列内的数字为1-9且不重复;
- 每宫内的数字为1-9且不重复。
所以,做这个数独题的时候就需要我们填入的数字符合数独的游戏规则。
做数独题,最常用的方法就是尝试法,一个数一个数的去尝试,如果填入的数字不符合数独规则就换一个数去试,如果所有的数都不符合时,就需要回退到上一步,将上一步的数字换掉,重新进行新一轮的尝试。
这就好像是在走迷宫一样,没有地图,没有引导,面对每一个岔路口都只能以尝试探索的方式深入,进而找到出口,在这个尝试探索的过程中,一旦发现线路不对,就需要返回岔路口,一旦发现当前岔路口都不能走,则需要返回上一岔路口,重新选择路线去尝试。
实际上这个解题思路就是我们计算机算法中的回溯算法.
算法:回溯算法(Backtracking algorithm)
回溯算法,又称试探法,选优搜索法。回溯算法的核心思想刚才已经阐述了。能够应用回溯算法解决的问题大都具备以下特点:
- 问题的答案有多个元素,且它至少有一个解;
- 问题需要满足一些约束条件(如:数独规则约束);
- 寻找答案的方式在每一步相同。
回溯算法是在尝试过程中,逐步构建最终的答案。
Part.3
Python代码实现 :
程序运行结果:
答案填在原题中就是:
回溯算法实质上一种深度优先的算法,许多复杂的,规模较大的问题都可以使用回溯法,有“通用解题方法”的美称。
正如上例,在回溯算法面前,号称世界上最难的数独题也不过如此,轻轻松松就能得到解决。怎么样?是不是感觉算法真的很强大?
易嘉编程后续将会和大家分享更多的Python算法趣味例子,一起进步。
想了解更多Python算法的朋友可以关注我们易嘉编程微信公众号:yjbc88888888。
声明:我要去上班所有作品(图文、音视频)均由用户自行上传分享,仅供网友学习交流,版权归原作者音符跳动666所有,原文出处。若您的权利被侵害,请联系删除。
本文标题:(python趣味代码)(python趣味编程100例)
本文链接:https://www.51qsb.cn/article/m9fvn.html