第8章算法经典问题.ppt
零基础学算法,第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个桃子了，问它第一天摘了多少个桃子？ a1=(a2+1)×2; a2=(a3+1)×2; a9=(a10+1)×2; a10=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+00、1+01、0+11、1+10（不进位），如果所得和是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 黑白棋,性格决定命运, 专注成就人生,
