资源简介

第11节　贪心算法
模拟演练
1.摘苹果游戏。游戏中的苹果树结了n个苹果,每个苹果有一个地面高度和摘它所需要的力气,要摘到苹果,必须具备高度和力气两个条件,每摘一个苹果都要用掉一定的力气。小林的可用力气是个有限值s,小林手伸直后能摘的最大高度为b,她可以借助的梯子的高度为a。游戏中苹果的高度和所需力气分别存储在数组 h和数组c中。程序运行界面如图所示。运行程序后,输入梯子高度a、手伸直高度b、可用力气s的值, 单击“计算”按钮(Command1),在文本框Text4中输出小林最多能摘得的苹果数ans。
(1)如图所示,树上的苹果总数为15。若将可用力气修改为90,则小林最多能摘得苹果的总数是　　　。?
/
(2)相应程序如下,在划线处填入适当的语句和代码,把程序补充完整。
Dim c(1 To 100) As Integer, h(1 To 100) As Integer, d(1 To 100) As Integer
Dim n As Integer
Private Sub Form_Load()
’从数据库中读取n个苹果的摘取所需力气和高度存放在数组c和h中,并显示在List1中,代码略
End Sub
Private Sub Command1_Click()
Dim a As Integer, b As Integer, s As Integer, i As Integer, j As Integer, m As Integer
a = Val(Text1.Text)’梯子高度
b = Val(Text2.Text)’手伸直高度
s = Val(Text3.Text)’可用力气
m = 0
For i = 1 To n’将所有能够摘得的苹果所需力气存储到数组d中
　If　①　Then?
m = m + 1
d(m) = c(i)
　End If
Next
For i = 1 To m - 1
　k = i
　For j = i + 1 To m
If　②　Then k = j?
　Next
　If k <> i Then
t = d(k): d(k) = d(i): d(i) = t
　End If
Next
ans = 0’用剩余的力气去摘最多的苹果
For i = 1 To m
　If s >= d(i) Then
　③　?
ans = ans + 1
　End If
Next
Text4.Text = Str(ans)
End Sub
答案　(1) 6 　(2)①a+b>=h(i)　② d(j)解析　从数据库中导入数组c和h,当梯子高度与手伸直的高度可以够到某个苹果时,就把所用的力气c(i)转存到的d(m)中,对数组d进行升序选择排序,先摘手可够到、耗费力气小的苹果,再摘耗费力气大的,这样摘到的苹果最多。
2.物品装袋问题。现有n个物品(不超过20个),及一个容量不超过v的袋子,分别给出各物品的体积及价值,求装入袋子里的物品价值总和的最大值。请编写VB程序,实现如下功能:在文本框Text1中输入袋子的体积,单击“计算”按钮Command1,在文本框Text2中输出装入袋子里的物品价值总和的最大值,运行效果如图所示。
/
算法设计:为了使装入袋子的价值总和最大,首先应该把单位价值(该物品的价值+体积)最大的物品全部放入袋子(如果袋子当前剩余的容量不小于该物品的体积),然后放单位价值第二的物品,如此重复。当袋子剩余的容量装不下一个完整的物品时,可以将这个物品的部分(若干个单位体积)装入袋子,直到袋子装满。
实现上述功能的VB程序如下,请回答下列问题:
(1)根据题意,现有4个物品,其对应的体积和价值如表所示,若袋子的体积为30,则装入袋子的最大价值为　　　(四舍五入保留1位小数)。?
物品编号
体积
价值
1
26
19
2
7
14
3
22
11
4
10
22
(2)请在划线处填入合适的代码。
Dim v(1 To 20) As Integer ’依次存储每个物品的体积
Dim w(1 To 20) As Integer ’依次存储每个物品的价值
Dim pw(1 To 20) As Double ’依次存储每个物品的单位价值
Dim n As Integer’存储物品的总个数
Private Sub Form_Load()
’初始化操作,并将每个物品的体积和价值依次显示在列表框List1中(代码略)
’将物品的个数存入变量n中,将每个物品的体积和价值分别依次存入数组v(1)到v(n)中、w(1)到w(n)中
End Sub
Sub Sort (　) ’根据每个物品的单位价值进行降序排序
For i = 1 To n -1
　k=i
　For j = i + 1 To n
If pw(k) < pw(j) Then　①　?
　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
Private Sub　Command1_Click()
Dim i As Integer, k As Integer, t As Integer
Dim p As Double, bw As Integer, tot As Double
bw = Val(Text1.Text)
For i = 1 To n
　pw(i) = w(i) / v(i)
Next i
　②　?
For i = 1 To n
　If bw >= v(i) Then
tot = tot + w(i)
bw = bw -v(i)
　Else
　③　?
Exit For
　End If
Next i
Text2.Text = Str(tot)
End Sub
答案　(1)45.5　(2)① k=j　② Call Sort 或者 Call Sort()　③ tot=tot+bw*pw(i)
解析　先以每个物品的单位价值为关键字进行降序排序。本题中用了一个自定义过程来实现排序,用了冒泡排序。接着在装袋的过程中,先拿单位价值高的,再依次拿单位价值低的,直到袋子装满(剩余可装体积bw=0)。变量tot存储的是总价值。
3.删数问题。输入一个数字串s,删去其中k个数字(k<数字串中数字的个数),使剩余数字在保持相对位置不变的情况下构成一个值最小的整数。例如,s=“19990608”,k=4,处理结果:608。
删数的算法如下:
(1)如果k>0,则从前往后检测相邻字符,否则,转(3);
(2)①若所有相邻字符都已非降序,则将串尾k个字符删去,k值置0,转(1);②若相邻两数存在逆序(即前一个数>后一个数),则将前一个数删除,k值变化,然后回到(1);
(3)去掉串首的0,输出结果。
按照上述算法思路,编写了VB程序,功能如下:在文本框Text1中输入数字串,在文本框Text2中输入删除的个数,单击“处理”按钮Command1,在文本框Text3中显示最小的整数。
程序运行界面如下图所示。
/
(1)如果输入的数字串为“20160125”,删除个数为4,则结果是　　　。?
(2)实现上述功能的VB程序如下,请在划线处填入合适代码。
delete函数说明:(delete st,x,y)为自定义函数,功能为在字符串st中删除x位置开始的y长度的子串。
Private Sub Command1_Click ()
Dim s As String,k As Integer
Dim i As Integer,j As Integer, n As Integer
s = Text1.Text
k = Val(Text2.Text)
n = Len(s)
Do While k>0
　i=1
　Do While i　i=i+1
　Loop
　If i=n Then
　②　?
n=n-k
k = 0
　Else
s = delete(s, i, 1)
n=n-1
　③　?
　End If
Loop
i= 1
Do While n>1 And Mid(s,1,1)= “0”
　s = delete(s,1 ,1)
　i = i+1
　n = n-1
Loop
Text3.Text = s
End Sub
Function delete(st As String,x As Integer,y As Integer) As String
delete=Mid(st,1,x-1)+Mid(st,x+y)
’Mid函数第3个参数省略,则截去从开始位置向右到字符串结尾的所有字符
End Function
答案　(1)12　(2)①Mid(s,i,1)<=Mid(s,i+1,1)　②s= delete(s,n
-k+1 ,k)　③k=k-l
解析　程序的功能是给出一串数字和要删除的个数,使得删除后得到的数字最小。题目已经将程序的思想给出,即从高位开始,判断相邻两位是否前一位大于后一位,若是,则将前一位删除,若不是,则保持不变,如果每位数字已经满足升序排列而仍旧需要删除数字,则直接从低位开始删除直至不需再删为止。
4.小明在玩一个数字游戏,给定一个n位正整数(n<=20),根据设定的保留位数,删除k个数字,剩下的数字按原次序组成一个最大的新数。例如原数36351328,删除5个数,最大数为658。算法如下:先确定最高位的数字,在第1位至最后2位数字前的363513中找到最大的数6,从而确定最高位是6,再确定次高位的数字,从6后面的数开始到最后1位数字前的35132中找到最大数5,确定次高位是5,依次找下去得到最大新数。他设计了一个VB程序来进行验证,在文本框Text1中输入一个n位正整数,在文本框Text2中输入删除位数k,点击“确定”按钮,在文本框Text3中输出保留的最大新数。程序运行界面如图所示。
/
(1)如果输入的原数是3638132,删除3位数字,则输出的新数是　　　。?
(2)实现上述功能的VB代码如下,请在划线处填入合适代码。
Private Sub Command1_Click()
Dim a(1 To 20) As String
Dim ys As String, xs As String ’s记录最大的新数
Dim k As Integer, h As Integer, n As Integer
Dim i As Integer, j As Integer
Dim F As Boolean
xs =“”
ys = Text1.Text
n = Len(ys)
k = Val( Text2.Text)
F = True
If ys =“”Or n > 20 Or k = 0 Or k > n Then
　Label4.Caption = “输入的原数或保留位数不符,请重输!”
　F = False
End If
For i = 1 To n
　　①　?
　If a(i) < “0” Or a(i) > “9” Then
Label4.Caption =“输入的原数不是数字,请重输!”
Text1.Text = “”
F = False
　End If
Next i
If F = True Then
　h = 1
　For i = 1 To n-k
For j = h To　②　?
　If a(j) > a(h) Then h = j
Next j
　③　?
h = h + 1
　Next i
　Text3.Text = xs
End If
End Sub
答案　(1)8132　(2)①a(i)=Mid(ys,i,1)　②k+i　③xs=xs+a(h)
解析　(1)因为字符串总共7位数,删除3位,还剩4位数。前5位数字中最大的数是8,后面只剩下3位,所以答案是8132。
(2)①后面要判断a(i)是不是数字,所以要取出字符来判断,所以答案是a(i)=Mid(ys,i,1)。②因为每次都要在当前位置和最后还剩几位之间查找最大的数,所以答案是k+i。③把每次找到的最大的数保留在结果xs中,所以答案是xs=xs+a(h)。

展开更多......

收起↑