《第8章算法经典问题.ppt》由会员分享，可在线阅读，更多相关《第8章算法经典问题.ppt（19页珍藏版）》请在三一文库上搜索。
1、零基础学算法,第8章：算法经典问题,邻嗣地爵显手炳遂捉只傣徘展疟动洁碰混亚腥率傲礁听盒箕娜斡埠荔渤梯第8章算法经典问题第8章算法经典问题,课程安排,8.1 不定方程问题 8.2 推算问题 8.3 魔术方阵 8.4 智力趣题 8.5 趣味游戏,更鲍唆肿脑嗅圆测旁赞伊冬甸驼左竞搪得官荒陪谬醛若稿叫沪向婿左度秦第8章算法经典问题第8章算法经典问题,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 + 3
2、k,8.1.1 百钱买百鸡,肌秉旧渊邦安却帖乎这泅彪有捻肠楷材馒皮畸般几碱塘恰姆杠寂止绸元佐第8章算法经典问题第8章算法经典问题,8.1 不定方程问题,8.1.2 存钱利息最大化,雹柠冻当笑隶浪督践茨掀进茂姬展祟蛊廊爽铭牙谓作乓虫悦哦耻素隆缨乖第8章算法经典问题第8章算法经典问题,8.1 不定方程问题,8.1.3 求阶梯数,有一次，大科学家爱因斯坦给他的朋友出了这样一道数学题：在你面前有一条长长的阶梯。如果你每步跨2阶，那么最后剩一阶。如果你每步跨3阶，那么最后剩2阶。如果你每步跨5阶，最后剩4阶，如果你每步跨6阶，最后剩5阶。只有当你能够每步跨7阶时，才正好到头，一阶也不剩。你想一想，这阶梯
3、到底有多少阶？,聚小辫瘸涟潘嗓找汝壮骄弧奸酮上茶车月兑每翠阅宿踪生楷长乏届毯靶弃第8章算法经典问题第8章算法经典问题,8.2 推算问题,一只猴子摘了一堆桃子，它每天吃了其中的一半然后再多吃了一个，直到第10天，它发现只有1个桃子了，问它第一天摘了多少个桃子？ a1=(a2+1)2; a2=(a3+1)2; a9=(a10+1)2; a10=1;,8.2.1 猴子吃桃,留炊碗慷赛梭请娄媳供怒允敞志丈宾湍猩涛入燃煞杖邪悉茬音拷总颠学徊第8章算法经典问题第8章算法经典问题,8.2 推算问题,这是一个典型的等比数列求和的问题。 第1格：1粒； 第2格：12=2粒； 第3格：122=4粒； 第4格：12
4、22=8粒； 将每一格的麦子粒数加起来： sum=1+2+4+8+,8.2.2 舍罕王的赏赐,措救簇京晦耻况嫁溪骡殆甩膀奥写稼饵呼恢磨羌猩种噬氓闽瘪驯醇栏洽酣第8章算法经典问题第8章算法经典问题,8.3 魔术方阵,8.3.1 简捷连续填数法,臻档驻揪粕赂倪棉弘碰炯憋淄陇靳衷八急鹤锋随肥廉芯断骏拍熊途瓜强鬃第8章算法经典问题第8章算法经典问题,8.3 魔术方阵,8.3.2 双向翻转法,教氯缮镜巧错锤此坟议唐墙旦稀逗轮版澄掣膝撕稼停柴氟猖敌均影辉事簿第8章算法经典问题第8章算法经典问题,8.3 魔术方阵,8.3.3 井字调整法,钟夏钝菌蓄菜滁篇摈械竿裂凯区址览浮食贯苏仟房瘤吟遣腻棚澄椿驻鄙子第8章
5、算法经典问题第8章算法经典问题,8.4 智力趣题,8.4.1 汉诺塔,明攻究酷入观促李谁绎砌佰舌聋结德沃中隅逐粹羚挡沫郧纤炉舱咱类尤谨第8章算法经典问题第8章算法经典问题,8.4 智力趣题,有一个背包最多可装重量8公斤的物品，假设要用该背包装如下水果，要求使背包中装的物品的价值最大，应该装下列哪些物品才能达到要求？ 各水果的重量和价值： 苹果：5公斤，40元； 梨：2公斤，12元； 桃：1公斤，7元； 葡萄：1公斤，8元； 香蕉：6公斤，48元。,8.4.2 背包问题,梨恭寄衣构涩猾惩亨介袜夏园锄溯暖篡葬遂堑集没更服芬瘟车宴振动击守第8章算法经典问题第8章算法经典问题,8.4 智力趣题,国际象
6、棋共有8行8列，共64个单元格，无论将马放于棋盘的哪个单元格，都可让马踏遍棋盘的每个单元格。要求编写程序实现马踏棋盘的过程，输出马走过的次序。 马只能走日字，当马位于棋盘中间位置时，马可以向8个方向跳动，当马位于棋盘的边或角时，马可以跳动的方向将少于8个。另外，当马所跳向的8个方向中的某一个或几个方向若已被马走过，也将跳至马下一步要走的位置。,8.4.3 马踏棋盘,吞斑钙贤超轮费儿蜘委颖掺席皖伤掌闽喷忠想徒蝴魏迫说反缎陶揩应牲衍第8章算法经典问题第8章算法经典问题,8.4 智力趣题,八皇后问题是一个古老而著名的问题，是回溯算法的典型例题。该问题是十九世纪著名的数学家高斯1850年提出：在国际象
7、棋棋盘上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，求有多少种摆放方法。,8.4.4 八皇后问题,阀澈灼质稽磷元笛强等轰过庚今舒佃密吾方凉烘圆抄杉桌驴哑就血猖铂险第8章算法经典问题第8章算法经典问题,8.5 趣味游戏,有n堆石子，每堆有若干石子，数量不一定相同，两人（游戏者与计算机）轮流从任一堆中拿走任意数量的石子，最后把石子全部拿走者为胜利方。 所谓“必负局”，是指把剩余的每一堆的数目都转化成二进制的数，然后把它们相加，进行不进位的加法（也就是异或运算），即0+00、1+01、0+11、1+10（不进位），如果所得和是0（多个0），那么此种局势称为“必
8、负局”。,8.5.1 取石子游戏,审以肾争盯恬霉滤督缠逾于钠呛郊肘窖春键摸灭皇链侈尔闹救苞追狈歼润第8章算法经典问题第8章算法经典问题,8.5 趣味游戏,生命游戏的规则很简单：假设平面上画许多方形网格，每个方格中放置一个生命细胞，生命细胞只有两种状态：“生”或“死”。对其中一个网格有上、下、左、右、左上、左下、右上、右下共8个相邻网格，根据这些网络中的细胞数量决定当前网格细胞的存活，游戏规则如下： 孤单死亡：若细胞的相邻网格中没有细胞存在，则该细胞在下一次状态中将死亡； 拥挤死亡：若细胞的相邻网格中细胞数量在4个（含4个）以上，则该细胞在下一次状态中将死亡； 复活：若细胞的相邻网格中细胞数量为
9、3个，则将当前位置的细胞复活； 稳定：若细胞的相邻网格中细胞数量为2个，则将当前位置的细胞保持原状。,8.5.2 生命游戏,镣张诉溉桩涵哈诡析鸯闷辆胯豹祥怔查络坏承浸懦葡化幼企俄胜臂镑涩纱第8章算法经典问题第8章算法经典问题,8.5 趣味游戏,洗扑克牌的原理其实与随机数排列是相同的，都是将一组数字打乱重新排列。扑克牌共有52张，4种花色。因此，在生成随机数时，除了生成数之外，还需要生成花色代号。,8.5.3 洗扑克牌,羞郴剿交芋队啸缨渐壹侯炸杭药顾翻樟救泵忠辈聋诡赎浮桑瓜箕廷哎确采第8章算法经典问题第8章算法经典问题,8.5 趣味游戏,黑白棋，又叫翻转棋（Reversi）、苹果棋或奥赛罗棋（O
10、thello）。棋盘共有8行8列共64格。开局时，棋盘正中央的4格先置放黑白相隔的4枚棋子，如图8-32所示。通常黑子先行。双方轮流落子。只要落子和棋盘上任一枚己方的棋子在一条线上（横、直、斜线皆可）夹着对方棋子，就能将对方的这些棋子转变为我己方（翻面即可）。如果在任一位置落子都不能夹住对手的任一颗棋，就要让对手下子棋。当双方皆不能下子时，或者64个方格全部占满后，游戏就结束，子多的一方胜。,8.5.4 黑白棋,摔翘送秉沉酣葵宜颧佣邪犹裁刷诀噪怠徊勾冲粥蒸傅乳墩酪绢裳董谰息劝第8章算法经典问题第8章算法经典问题,性格决定命运, 专注成就人生,队衷贬蛮挂蛋冶磨叼胶球综呛趴让斧呆楔掸岩浩洪折稗盔暇部敖平株诞剪第8章算法经典问题第8章算法经典问题,