基本的算法策略.ppt

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

1、第四章基本的算法策略贪婪法又叫登山法,它的根本思想是逐步到达山顶,即逐步获得最优解。贪婪算法没有固定的算法框架，算法设计的关键是贪婪策略的选择。一定要注意，选择的贪婪策略要具有无后向性。某状态以后的过程和不会影响以前的状态,只与当前状态或以前的状态有关,称这种特性为无后效性。上节下节4.4贪婪算法【例1】键盘输入一个高精度的正整数N，去掉其中任意S个数字后剩下的数字按原左右次序将组成一个新的正整数。编程对给定的N和S，寻找一种方案使得剩下的数字组成的新数最小。输入数据均不需判错。输出应包括所去掉的数字的位置和组成的新的正整数（N不超过240位）。

2、数据结构设计：对高精度正整数的运算在上一节我们刚刚接触过，和那里一样，将输入的高精度数存储为字符串格式。根据输出要求设置数组，在删除数字时记录其位置。上节下节4.4.1可绝对贪婪问题问题分析在位数固定的前提下，让高位的数字尽量小其值就较小，依据此贪婪策略就可以解决这个问题。怎么样根据贪婪策略删除数字呢？总目标是删除高位较大的数字，具体地相邻两位比较若高位比低位大则删除高位。我们通过“枚举归纳”设计算法的细节，看一个实例（s=3）：n1=“12435863”4比3大删除“1235863”8比6大删除“123563”6比3大删除“12353”只看这个

3、实例，有可能“归纳”出不正确的算法，先看下一个实例，我们再进一步解释：n2=”231183”3比1大删除“21183”2比1大删除“1183”8比3大删除“113”由实例n1，相邻数字只需要从前向后比较；而从实例n2中可以看出当第i位与第i+1位比较，若删除第i位后，必须向前考虑第i-1位与第i+1位进行比较，才能保证结果的正确性。由此可知通过实例设计算法时，枚举的实例一定要有全面性，实例最好要能代表所有可能的情况，或者在必要时多列举几个不同的实例。再看以下两个实例又可总结出一些需要算法特殊处理的情况。n3=”1234567”s=3由这个实例看出

4、，经过对n3相邻比较一个数字都没有删除，这就要考虑将后三位进行删除，当然还有可能，在相邻比较的过程中删除的位数小于s时，也要进行相似的操作。n4=”120083”3比0大删除“10083”2比0大删除“0083”8比3大删除“003”得到的新数数据是3由这个实例子又能看出，当删除掉一些数字后，结果的高位有可能出现数字“0”，直接输出这个数据不合理，要将结果中高位的数字“0”全部删除掉，再输出。特别地还要考虑若结果串是“0000”时，不能将全部“0”都删除，而要保留一个“0”最后输出。由此可以看出进行算法设计时，从具体到抽象的归纳一定要选取大量不同

5、的实例，充分了解和体会解决问题的过程、规律和各种不同情况，才能设计出正确的算法。算法设计1：根据以上实例分析，算法主要由四部分组成：初始化、相邻数字比较（必要时删除）、处理比较过程中删除不够s位的情况和结果输出。其中删除字符的实现方法很多，如：1）物理进行字符删除，就是用后面的字符覆盖已删除的字符，字符串长度改变。这样可能会有比较多字符移动操作，算法效率不高。1）可以利用数组记录字符的存在状态，元素值为“1”表示对应数字存在，元素值为“0”表示对应数字已删除。这样避免了字符的移动，字符串长度不会改变，可以省略专门记录删除数字的位置。但这样做前后数

6、字的比较过程和最后的输出过程相对复杂一些。2）同样还是利用数组，记录未删除字符的下标，粗略的过程如下：n=“12435833”0000004比3大删除“1235833”1245008比3大删除“123533”124505比3大删除“12333”12478这时数组好象是数据库中的索引文件。此方式同样存在操作比较复杂的问题。我们采用方法1）。一种简单的控制相邻数字比较的方法是每次从头开始，最多删除s次，也就从头比较s次。按题目要求设置数组data记录删除的数字所在位置delete(charn,intb,intk){inti;for(i=b;i<=le

7、ngth(n)-k;i=i+1)n[i]=n[i+k];}Delete_digit（）{charn[100];ints,i,j,j1,c,data[100],len;input(n);input(s);len=length(n);if(s>len){print(“dataerror”);return;}j1=0;for(i=0;i<=s;i=i+1){for(j=1;j<=length(n);j=j+1)if(n[j]>n[j+1])//贪婪选择{delete(n,j,1);if(j>j1)data[i]=j+i;//记录删除数字位置else//

8、实例2向前删除的情况实例data[i]=data[i-1]-1;j1=j;break;}if(j>length(n))break;}fo