贪心算法 导学案-2021-2022学年高中信息技术浙教版选修1

《贪心算法》导学案 [考试要求] 1．贪心算法 (c) [学习目标] 1. 掌握贪心算法基本思想。 2. 使用贪心算法思想解决实际问题。 [自主学习] 1、 知识梳理 1．贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的是在某种意义上的 。 二、自我检测 1. 小王玩一个删数游戏，将一个正整数删去其中n位数字，要求在保证余下的数字不改变顺序的情况下尽可能小。例如，数字54632，删去2位数字后，能得到的最小的数字为432。小明的想法是每次删一位效字，使得每次删后产生的新数字是最小的，删n次后得到最终结果，所以将数字从左往右数，找到第一个降序数列，将数列的第一位数删去即可，如数字54632，第一个降序数列为5、4，删去5，得到4632，再次找到第一个降序数列6、3，删去数字6，得到432即为结果，运行效果如下，请完成填空。 （1）若数字为“178543”，要求删去4位，最终的数字为 。 （2）实现上述功能的VB程序如下，请在划线处填入合适代码。 ’函数Del（）通过删除的数s和待删除数的位置i进行删除 Function Del(s as Integer)as String If i = 1 then s = Mid(s, i+1,len(s)-1) ElseIf i = Len(s) then s = Mid(s, 1,len(s)-1) Else ① End If Del = s End Function Private Sub Command1_Click( ) Dim s As String ,n As Integer, i As Integer, h As Integer s = Text1.Text n = Val(Text2.Text) h = len(s) For i = 1 To ② If Mid(s, i , 1)>Mid(s, i+1 , 1) Then ③ n = n – 1 h = h – 1 i = 0 End if If n = 0