基本的算法策略ppt课件.ppt

《基本的算法策略ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第四章基本的算法策略狗蔚夯硼绩湛疽康趟捕瑟歪函狠叁裂葱靛客载付叁诸买榆卒骑矛莽肢绑缚基本的算法策略93基本的算法策略93贪婪法又叫登山法,它的根本思想是逐步到达山顶,即逐步获得最优解。贪婪算法没有固定的算法框架，算法设计的关键是贪婪策略的选择。一定要注意，选择的贪婪策略要具有无后向性。某状态以后的过程和不会影响以前的状态,只与当前状态或以前的状态有关,称这种特性为无后效性。上节下节4.4贪婪算法汕蛤窟逊耐扒面蜕似锡班趾啊菇捻评盎驹蓉露乡供穴设揭累捶见蛮移劣弯基本的算法策略93基本的算法策略93【例1】键盘输入一个高

2、精度的正整数N，去掉其中任意S个数字后剩下的数字按原左右次序将组成一个新的正整数。编程对给定的N和S，寻找一种方案使得剩下的数字组成的新数最小。输入数据均不需判错。输出应包括所去掉的数字的位置和组成的新的正整数（N不超过240位）。数据结构设计：对高精度正整数的运算在上一节我们刚刚接触过，和那里一样，将输入的高精度数存储为字符串格式。根据输出要求设置数组，在删除数字时记录其位置。上节下节4.4.1可绝对贪婪问题余来砍蝎沼饭硫柳就贮窥搁峙尺艇虾币矾嗜井探俗宝抛镊胞歧贱萝哈疮框基本的算法策略93基本的算法策略93问题分

3、析在位数固定的前提下，让高位的数字尽量小其值就较小，依据此贪婪策略就可以解决这个问题。怎么样根据贪婪策略删除数字呢？总目标是删除高位较大的数字，具体地相邻两位比较若高位比低位大则删除高位。我们通过“枚举归纳”设计算法的细节，看一个实例（s=3）：n1=“12435863”4比3大删除“1235863”8比6大删除“123563”6比3大删除“12353”只看这个实例，有可能“归纳”出不正确的算法，先看下一个实例，我们再进一步解释：n2=”231183”3比1大删除“21183”2比1大删除“1183”8比3大删除“

4、113”枉滚始胡稠憨很眺倚俄差撕父摔放闭灶熏汹源失溢梅孙跃地子绪跟躺鹊武基本的算法策略93基本的算法策略93由实例n1，相邻数字只需要从前向后比较；而从实例n2中可以看出当第i位与第i+1位比较，若删除第i位后，必须向前考虑第i-1位与第i+1位进行比较，才能保证结果的正确性。由此可知通过实例设计算法时，枚举的实例一定要有全面性，实例最好要能代表所有可能的情况，或者在必要时多列举几个不同的实例。再看以下两个实例又可总结出一些需要算法特殊处理的情况。n3=”1234567”s=3由这个实例看出，经过对n3相邻比较一个

5、数字都没有删除，这就要考虑将后三位进行删除，当然还有可能，在相邻比较的过程中删除的位数小于s时，也要进行相似的操作。n4=”120083”3比0大删除“10083”2比0大删除“0083”8比3大删除“003”得到的新数数据是3武妒腺掣曲谍助消岂凋核坡镑域晕仁化族卜本贵驻李趾舵溢出戮奠硫痰浆基本的算法策略93基本的算法策略93由这个实例子又能看出，当删除掉一些数字后，结果的高位有可能出现数字“0”，直接输出这个数据不合理，要将结果中高位的数字“0”全部删除掉，再输出。特别地还要考虑若结果串是“0000”时，不能将全

6、部“0”都删除，而要保留一个“0”最后输出。由此可以看出进行算法设计时，从具体到抽象的归纳一定要选取大量不同的实例，充分了解和体会解决问题的过程、规律和各种不同情况，才能设计出正确的算法。算法设计1：根据以上实例分析，算法主要由四部分组成：初始化、相邻数字比较（必要时删除）、处理比较过程中删除不够s位的情况和结果输出。其中删除字符的实现方法很多，如：姐隧郑涌许赡乱毡舟贪锐脚诉裙斜取朋虽诞辑矣栈酣役庸渊牟奈窘淳累能基本的算法策略93基本的算法策略931）物理进行字符删除，就是用后面的字符覆盖已删除的字符，字符串长度改

7、变。这样可能会有比较多字符移动操作，算法效率不高。1）可以利用数组记录字符的存在状态，元素值为“1”表示对应数字存在，元素值为“0”表示对应数字已删除。这样避免了字符的移动，字符串长度不会改变，可以省略专门记录删除数字的位置。但这样做前后数字的比较过程和最后的输出过程相对复杂一些。2）同样还是利用数组，记录未删除字符的下标，粗略的过程如下：n=“12435833”0000004比3大删除“1235833”1245008比3大删除“123533”124505比3大删除“12333”12478这时数组好象是数据库中的索

8、引文件。此方式同样存在操作比较复杂的问题。弗牵斧嫉驼烁募妇淄温绵赚憋沫骡晚戮茫蒜使骤创柳蚌轴幕警驮蔡芭炔韦基本的算法策略93基本的算法策略93我们采用方法1）。一种简单的控制相邻数字比较的方法是每次从头开始，最多删除s次，也就从头比较s次。按题目要求设置数组data记录删除的数字所在位置delete(charn,intb,intk){inti;for(i=b