贪心算法 导学案-2021-2022学年高中信息技术浙教版选修1
高二信息技术导学案 VB模块 班级 姓名
《贪心算法》导学案
[考试要求]
1.贪心算法 (c)
[学习目标]
1. 掌握贪心算法基本思想。
2. 使用贪心算法思想解决实际问题。
[自主学习]
一、 知识梳理
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
高二信息技术导学案 VB模块 班级 姓名
h = h – 1
i = 0
End if
If n = 0 then Exit For
Next i
Label1.Caption = Str(s)
End Sub
[课堂练习]
1.最大整数问题:贪心算法中,有一类问题称为最大整数问题,问题的描述是:设有n个随机生成的正整数,将它们连接成一排,组成一最大的多位整数,其求解思想是:先把整数转换成字符串,然后在比较a+b和b-a,如果a十b>=a-b,就把a排在b的前面,反之则把a排在b的后面。例如:n=3时,3个整数13,12,343,连成的最大整数为34331213。
小王同学编写了一个VB程序,功能如下:
在列表框List1中随机生成n个1~1000之间的整数,单击“运行”按钮Command1后进行处理,最大整数结果输出在文本框Text1中,当n=4 时,程序运行界面如图所示。
VB程序如下,请回答下列问题:
(1)当n-3时,3个数:719,791,79,由这三个数组成的最大整数为 。
(2)请在划线处填入合适的代码。
Const n = 4
Dim a(l T0 10) As Integer
Private Sub Form Load()’函数CStr()和Str()功能类似,但输出字符时无前导空格
Randomize
For i = 1 To n
a(i) = ① ’ 生成1~1000间的随机整数
Listl.Addltem“a("+CStr(i)+“)=”+CStr(a(i))
Next i
End Sub
Function cmp(a As Integer, b As Inte-ger)As Boolean
If CStr(a) +CStr(b) < CStr(b) + CStr(a) Then
cmp = True
Else
cmp = False
End If
End Function
Private Sub Command1_Click()
Dim i As Integer, j As Integer, temp As Integer
Textl. Text =“”
For i = 1 To n - 1
For j = n To i + 1 Step -1
If ② Then
temp = a(j - 1)
a(j - 1)= a(j)
③
End If
Next j
Next i
For i = 1 To n
高二信息技术导学案 VB模块 班级 姓名
Textl. Text = Textl. Text + CStr(a(i)
Next i
End Sub
[课后练习]
1.物品装袋问题。现有n个物品(不超过20个),及一个能装体积不超过v的袋子,分别给出各物品的体积及价值,求装入袋子里的物品价值总和的最大值。请编写VB程序,实现如下功能:在文本框Textl中输入袋子的体积,单击“计算”按钮Commandl,在文本框Text2中输出装入袋子里的物品价值总和的最大值,运行效果如图所示。
算法设计:为了便装入袋子的价值总和最大,首先应该把单位价值(该物品的价值÷体积)最大的物品全部放入袋子(如果袋子当前剩余的容量不小于该物品的体积),然后再放单位价值第二的物品,如此往复。当袋子剩余的容量装不下一个完整的物品时,可以将这个物品的部分(若干个单位体积)装入袋子,直到袋子装满。
VB程序如下,请回答下列问题:
(1)根据题意与算法描述,现有4个物品,其对应的体积和价值如上表所示,若袋子的体积为30,则装入袋子里的物品最大价值为 (四舍五入保留1位小数)。
(2)请在划线处填入合适的代码。
Dim v(l T0 20) As Integer’每个物品体积
Dim w(l T0 20) As Integer’每个物品价值
Dim pw(l T0 20) As Double’依次存储每个物品的单位价值
Dim n As Integer’存储物品的总个数
Private Sub Form_Load()
’初始化操作,并将每个物品的体积和价值依次显示在列表框Listl中(代码略);
’将物品的个数存人变量n中;
’将每个物品的体积依次存人数组v(l)到v(n)中;
’将每个物品的价值依次存人数组w(l)到w(n)中;
End Sub
Sub Sort() ’根据每个物品的单位价值进行降序排序
For i =1 To n - 1
K= i
For j= j + 1 To n
If ① Then k = j
Next j
If k <> i Then
t=v(i):v(i)=v(k):v(k)=t
t=w(i):w(i)=w(k):w(k)=t
p=pw(i):pw(i)=pw(k):pw(k)=p
End If
Next i
End Sub