資源簡介

第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)。

展開更多......

收起↑