高中信息技术 中国版选修1 3.3穷举与问题解决(共12张PPT)

穷举与问题解决 算法与问题解决 也许有人要问，计算机运行速度发展那么快，为什么还需要刻意设计高效率的程序？原因很简单，人类的雄心与能力是一起增长的，技术进步再快也快不过人们对需求的增长。计算速度和存储容量上的革新仅仅提供了处理更复杂问题的有效工具，所以高效率的程序永远不会过时。或许，我们开发的软件会表现出很多不良现象，不要过多埋怨计算机或系统环境差，应考虑设计一种更快、更好的算法，这才是解决问题的实质。 穷举又称为枚举。穷举法的基本思想是：依据题目的已知条件，确定答案的大致范围，在此范围内对所有可能的情况逐一验证，直到全部情况验证完。若某种情况经验证符合题目的全部条件，则为本题的一个答案。若全部情况经验证后都不符合题目的全部条件，则本题无答案。 适合用穷举法求解的问题是：问题的可能答案是有限个，而且这些可能的答案必须是事先知道的。在程序设计中，穷举法主要通过循环语句来实现。 穷举算法的特点是算法简单，但是当需要穷举的数据量很大时，运行所花费的时间也就非常大，此时应该考虑优化算法。 韩信是我国秦末汉初的著名军事家，历史上有韩信用兵的种种传说。韩信统率过千军万马，他对手下士兵的数目了如指掌。他统计士兵数目有个独特的方法：他先令士兵排成5列纵队进行操练，结果余1人；接着，他命令士兵排成6列纵队进行操练，结果余5人；随后，又命令士兵排成7列纵队进行操练，结果余4人；最后，命令排成11列纵队，结果余10人。此时他便知道部队的实际人数了。后人把他这种统计士兵人数的方法称为“韩信点兵”，历史上还称之为“鬼谷算”或“隔墙算”。 一、韩信点兵 “韩信点兵”与“中国剩余定理” 18世纪中期欧洲数学家欧拉、拉格朗日等都曾 对一次同余式问题进行过研究。德国著名数学家高斯于1801年出版的《算术探究》一书中，记载有不定方程求解方法。“韩信点兵”的故事源于《孙子算经》，叙述的就是关于一次同余式问题的解法。1852年英国人伟烈亚力将《孙子算经》传入欧洲，人们才知道物不知数”的解法与数学家高斯的定理是一样的，但中国人的研究领先了一千多年。所以，人们将一次同余式问题的求解定理称为“中国剩余定理”或“孙子余数定理”。这个定理不但在我国古代数学史上是一个重要的定理，而且在近代数学和程序设计中也有很广泛的应用。 小资料