高中信息技术 全国青少年奥林匹克联赛教案 贪心法

1、情报学奥林匹克中的基本算法(贪婪法)在求最优解问题的过程中，根据某个贪婪标准，从问题的初始状态开始，直接求每一步的最优解，通过多次贪婪选择，最终得到整个问题的最优解，这一解决方法就是贪婪算法。从贪婪算法的定义可以看出，贪婪法不是整体考虑问题，其选择是某种意义上的局部最优解，问题本身的特性决定该问题使用贪婪算法得到最优解。让我们看看下面的例子贪婪法的应用例1均分卡(NOIP2002tg )问题描述有n张卡，号码分别是1、2、n。 每个堆栈有多张，但卡片总数一定是n的倍数。 可以在任何一座山上取多张卡片移动。 关于移卡规则，在编号1的堆栈中取得的卡可以移动到编号2的堆栈中，在编号n的堆栈中取得的卡

2、可以移动到编号N-1的堆栈中，在其他堆栈中取得的卡可以移动到相邻的左侧或右侧的堆栈中。 现在，寻求寻找以最少的移动次数使每1堆的卡数同样多的移动方法。 例如，n=4、4堆的卡片数分别为 9 8 17 6移动三次就能达到目的从中取4张卡，从 (9 8 13 10) -中取3张卡，从(9 11 10 10)-中取1张卡，放置在(10 10 10 10 )。输入 :用键盘输入文件名。文件格式： N(N堆卡，1=N=100 )A1 A2 An (N堆卡，每个堆卡的初始数量，l=Ai=10000 )输出：输出到画面。 格式是所有堆相等时的最小移动次数。输入输出样本在：49 8 17 6屏幕显示： 3算法

3、解析：将ai作为第I张堆卡的张数(0=i=n )，将v等分后的每个堆卡的张数，将s作为最小移动次数。我们使用贪婪法，从左到右顺序移动卡片。 第I个堆栈(0v，ai-v张卡从第I个堆栈移动到第I 1个堆栈。(2)若a，若v，贪欲选择联苯胺英国语： 卡移位步数计数:=a，I，a，I，v 将第I张牌数设为v结束； 我爱你写入(s )；结束。用贪婪算法解决问题，需要解决两个问题一个是问题是否适合用贪婪法解。 让我们看看寻找货币的例子。 货币系统有3种货币价值，面额分别为一角、五分和一分，求最小货币数时，可以用贪婪法求解。如果将这3种货币价值变更为一角1分、5分、1分，则不能用贪婪法求解。 用贪婪法解是

4、方便的，但其适用范围小，判断一个问题是否适合用贪婪法解，目前没有共同的方法，在信息学竞赛中，需要根据个人的经验判断什么时候应该使用贪婪算法。二是使用贪婪算法，确定如何选择贪婪标准，从而得到问题的最佳解。 在选择贪婪标准时，必须验证和使用选择的贪婪标准，以免被表面上看起来正确的贪婪标准所迷惑。例2 (NOIP1998tg )设置n个正整数，将它们串联为一列，构成一个最大的多比特整数。 例如，在：n=3的情况下，三个整数13、312、343，连续的最大整数为：另外，在：n=4的情况下，4个整数7、13、4、246连接的最大整数为输入： nn个数输出：连接的多位数算法分析：这个问题容易考虑使用贪婪法，考试时很多学生将整数按从大到小的顺序连接起来，测试题的目的例子也符合，但最后的测试结果并不全部正确。 根据这种贪婪的标准，反例可以容易地找到： 12，121应该配置12121而不是12112，从包含彼此的时候到大的时候不一定是12，123不一定是12112 这个问题不能用贪婪法吗？其实这个问题可以用贪婪法解决，但是刚才的贪婪标准是错误的。 正确的贪婪标准是先整数化成字符串，然后将a b和b a进行比较，如果是a bb a，则将a排在b之前，相反，将a排在b之后。原始程式：华尔街字符串，字符串，字符串。t :字符串； I，j，k，n 3