《算法经典问题》ppt课件

《《算法经典问题》ppt课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、零基础学算法第8章：算法经典问题课程安排8.1不定方程问题8.2推算问题8.3魔术方阵8.4智力趣题8.5趣味游戏8.1不定方程问题公鸡5文钱1只，母鸡3文钱1只，小鸡3只1文钱，要求用100文钱买100只鸡，求公鸡、母鸡和小鸡各应该买多少只？x+y+z=1005x+3y+z/3=100设一个整数参数k，就有：x=4ky=25-7kz=75+3k8.1.1百钱买百鸡8.1不定方程问题8.1.2存钱利息最大化8.1不定方程问题8.1.3求阶梯数有一次，大科学家爱因斯坦给他的朋友出了这样一道数学题：在你面前有一条长长的阶梯。如果你每步跨2阶，那么最后剩一阶。如果你每步跨3阶，那么最后剩

2、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+……

3、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个单元格，无论将马放于棋盘的哪个单元格，都可让马踏遍棋盘的每个单元格。要求编写程序实现马踏棋盘的过程，输出马

4、走过的次序。马只能走日字，当马位于棋盘中间位置时，马可以向8个方向跳动，当马位于棋盘的边或角时，马可以跳动的方向将少于8个。另外，当马所跳向的8个方向中的某一个或几个方向若已被马走过，也将跳至马下一步要走的位置。8.4.3马踏棋盘8.4智力趣题八皇后问题是一个古老而著名的问题，是回溯算法的典型例题。该问题是十九世纪著名的数学家高斯1850年提出：在国际象棋棋盘上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，求有多少种摆放方法。8.4.4八皇后问题8.5趣味游戏有n堆石子，每堆有若干石子，数量不一定相同，两人（游戏者与计算机）轮流从任一堆中拿走任

5、意数量的石子，最后把石子全部拿走者为胜利方。所谓“必负局”，是指把剩余的每一堆的数目都转化成二进制的数，然后把它们相加，进行不进位的加法（也就是异或运算），即0+0＝0、1+0＝1、0+1＝1、1+1＝0（不进位），如果所得和是0（多个0），那么此种局势称为“必负局”。8.5.1取石子游戏8.5趣味游戏生命游戏的规则很简单：假设平面上画许多方形网格，每个方格中放置一个生命细胞，生命细胞只有两种状态：“生”或“死”。对其中一个网格有上、下、左、右、左上、左下、右上、右下共8个相邻网格，根据这些网络中的细胞数量决定当前网格细胞的存活，游戏规则如下：孤单死亡：若细胞的相邻网格中没有细胞存

6、在，则该细胞在下一次状态中将死亡；拥挤死亡：若细胞的相邻网格中细胞数量在4个（含4个）以上，则该细胞在下一次状态中将死亡；复活：若细胞的相邻网格中细胞数量为3个，则将当前位置的细胞复活；稳定：若细胞的相邻网格中细胞数量为2个，则将当前位置的细胞保持原状。8.5.2生命游戏8.5趣味游戏洗扑克牌的原理其实与随机数排列是相同的，都是将一组数字打乱重新排列。扑克牌共有52张，4种花色。因此，在生成随机数时，除了生成数之外，还需要生成花色代号。8.5.3洗扑克牌8.5趣味游戏黑白棋，又叫翻转棋（Reversi）、苹果棋或奥赛罗棋（Othello）。棋盘共有8行8列共64格。开局时，棋盘正中

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