《算法经典问题》PPT课件.ppt

Click to edit Master title style,,Click to edit Master text styles,,Second level,,Third level,,Fourth level,,,,Click to edit Master title style,,Click to edit Master text styles,,Second level,,Third level,,Fourth level,,零基础学算法,第,8,章：算法经典问题,课程安排,8.1,,不定方程问题,,8.2,,推算问题,,8.3,,魔术方阵,,8.4,,智力趣题,,8.5,,趣味游戏,8.1,不定方程问题,,公鸡5文钱1只，母鸡3文钱1只，小鸡3只1文钱，要求用100文钱买100只鸡，求公鸡、母鸡和小鸡各应该买多少只？,,x+y+z=100,,5x+3y+z/3=100,,,设一个整数参数,k,，就有：,,,x=4k,,y=25 - 7k,,z=75 + 3k,8.1.1,百钱买百鸡,8.1,不定方程问题,8.1.2 存钱利息最大化,8.1,不定方程问题,8.1.3 求阶梯数,有一次，大科学家爱因斯坦给他的朋友出了这样一道数学题：在你面前有一条长长的阶梯。

如果你每步跨,2,阶，那么最后剩一阶如果你每步跨,3,阶，那么最后剩,2,阶如果你每步跨,5,阶，最后剩,4,阶，如果你每步跨,6,阶，最后剩,5,阶只有当你能够每步跨,7,阶时，才正好到头，一阶也不剩你想一想，这阶梯到底有多少阶？,8.2 推算问题,,一只猴子摘了一堆桃子，它每天吃了其中的一半然后再多吃了一个，直到第10天，它发现只有1个桃子了，问它第一天摘了多少个桃子？,,a,1,=(a,2,+1)×2;,,a,2,=(a,3,+1)×2;,,……,,a,9,=(a,10,+1)×2;,,a,10,=1;,,,8.,2.,1,,,猴,子吃桃,8.2 推算问题,这是一个典型的等比数列求和的问题第,1,格：,1,粒；,,第,2,格：,1×2=2,粒；,,第,3,格：,1×2×2=4,粒；,,第,4,格：,1×2×2×2=8,粒；,,,……,,将每一格的麦子粒数加起来：,,sum=1+2+4+8+……,,8.2.2 舍罕王的赏赐,8.3 魔术方阵,,8.,3,.,1,,简捷连续填数法,8.3 魔术方阵,,8.3.2 双向翻转法,8.3 魔术方阵,,8.3.3 井字调整法,8.4 智力趣题,,8.,4,.,1,,,汉诺塔,8.4 智力趣题,有一个背包最多可装重量,8,公斤的物品，假设要用该背包装如下水果，要求使背包中装的物品的价值最大，应该装下列哪些物品才能达到要求？,,各水果的重量和价值：,,苹果：,5,公斤，,40,元；,,梨：,2,公斤，,12,元；,,桃：,1,公斤，,7,元；,,葡萄：,1,公斤，,8,元；,,香蕉：,6,公斤，,48,元。

8.4.2 背包问题,8.4 智力趣题,国际象棋共有,8,行,8,列，共,64,个单元格，无论将马放于棋盘的哪个单元格，都可让马踏遍棋盘的每个单元格要求编写程序实现马踏棋盘的过程，输出马走过的次序马只能走日字，当马位于棋盘中间位置时，马可以向,8,个方向跳动，当马位于棋盘的边或角时，马可以跳动的方向将少于,8,个另外，当马所跳向的,8,个方向中的某一个或几个方向若已被马走过，也将跳至马下一步要走的位置8.4.3 马踏棋盘,8.4 智力趣题,八皇后问题是一个古老而著名的问题，是回溯算法的典型例题该问题是十九世纪著名的数学家高斯,1850,年提出：在国际象棋棋盘上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，求有多少种摆放方法8.4.4 八皇后问题,8.5 趣味游戏,有,n,堆石子，每堆有若干石子，数量不一定相同，两人（游戏者与计算机）轮流从任一堆中拿走任意数量的石子，最后把石子全部拿走者为胜利方所谓“必负局”，是指把剩余的每一堆的数目都转化成二进制的数，然后把它们相加，进行不进位的加法（也就是异或运算），即,0+0,＝,0,、,1+0,＝,1,、,0+1,＝,1,、,1+1,＝,0,（不进位），如果所得和是,0,（多个,0,），那么此种局势称为“必负局”。

8.5.1,取石子游戏,8.5 趣味游戏,生命游戏的规则很简单：假设平面上画许多方形网格，每个方格中放置一个生命细胞，生命细胞只有两种状态：“生”或“死”对其中一个网格有上、下、左、右、左上、左下、右上、右下共,8,个相邻网格，根据这些网络中的细胞数量决定当前网格细胞的存活，游戏规则如下：,,孤单死亡：若细胞的相邻网格中没有细胞存在，则该细胞在下一次状态中将死亡；,,拥挤死亡：若细胞的相邻网格中细胞数量在,4,个（含,4,个）以上，则该细胞在下一次状态中将死亡；,,复活：若细胞的相邻网格中细胞数量为,3,个，则将当前位置的细胞复活；,,稳定：若细胞的相邻网格中细胞数量为,2,个，则将当前位置的细胞保持原状8.5.2,,生命游戏,8.5 趣味游戏,洗扑克牌的原理其实与随机数排列是相同的，都是将一组数字打乱重新排列扑克牌共有,52,张，,4,种花色因此，在生成随机数时，除了生成数之外，还需要生成花色代号,8.5.3 洗扑克牌,8.5 趣味游戏,黑白棋，又叫翻转棋（,Reversi,）、苹果棋或奥赛罗棋（,Othello,）棋盘共有,8,行,8,列共,64,格开局时，棋盘正中央的,4,格先置放黑白相隔的,4,枚棋子，如图,8-32,所示。

通常黑子先行双方轮流落子只要落子和棋盘上任一枚己方的棋子在一条线上（横、直、斜线皆可）夹着对方棋子，就能将对方的这些棋子转变为我己方（翻面即可）如果在任一位置落子都不能夹住对手的任一颗棋，就要让对手下子棋当双方皆不能下子时，或者,64,个方格全部占满后，游戏就结束，子多的一方胜8.5.4 黑白棋,性格决定命运,,,专注成就人生,。