16.元旦放假,小明幫助外公在果園搬果子。果園里有n堆(n<=100)重量不一的果子,需要將它們合并成一堆。已知合并兩堆果子所消耗的體力等于兩堆果子的重量之和。為了節(jié)省體力,每次合并,小明會(huì)把其中重量最小的兩堆果子合并一起,n堆果子經(jīng)過(guò)若干次合并之后只剩一堆為止。比如,n=4時(shí),表示共有4堆果子,重量分別是2、4、5、9,先合并重量為2和4的果子堆,新堆重量是6,耗費(fèi)體力為6;接著將重量5和6的果子堆合并,新堆重量是11,耗費(fèi)體力為11;最后將重量9和11的果子堆合并,新堆重量是20,耗費(fèi)體力為20。因此總消耗體力是6+11+20=37,這樣合并是最少耗費(fèi)體力的方法。請(qǐng)?jiān)O(shè)計(jì)程序,計(jì)算合并這n堆果子最少消耗的體力值。
(1)有5堆果子重量分別是:17,15,16,16,19,則小明將5堆果子搬成1堆至少需要消耗體力值為
。
(2)請(qǐng)?jiān)冖佗冖厶幪钌虾线m代碼,實(shí)現(xiàn)程序功能。
Dim n As Integer
Dim a(1 To 100)As Integer'a數(shù)組存儲(chǔ)各堆果子重量
Dim b(o To 100)As Integer'b(0)存放a數(shù)組中最小值的下標(biāo),若a(i)是數(shù)組中最大數(shù),則 b(i)的值為-1
Dim flag(1 To 100)As Boolean
Private Sub Form_Load ____
初始化果子的數(shù)量n和每堆果子的重量a(i),并依此顯示在列表框list1中,代碼略
初始化b數(shù)組的值均為-1,flag 數(shù)組的值均為False,代碼略
End Sub
Private Sub Command1_Click _____
Dim i As Integer,k As Integer
Dim p As Integer,q As Integer,w As Integer
p=0
Do While True'生成b數(shù)組,標(biāo)記升序后a(i)的下一個(gè)元素在a數(shù)組中的位置為b(i)
For i=1 To n
If Not flag(i)Then k=i:Exit For
Next i
If i=n+1 Then Exit Do
i=1
Do While i<=n
If Not flag(i) And a(k)>a(i)Then k=i
i=i+1
Loop
b(p)=k
flag(k)=True
①
Loop
w=0
p=b(0):q=b(p)
Do While b(p)<>-1
a(p)=a(p)+a(q)
w=②
If b(q)<>-1 Then b(0)=b(q)Else Exit Do
Call sort(p)
p=b(0):q=b(p)
Loop
Text1.Text=Str(w)
End Sub
Sub sort(p As Integer)'將a(p)插入到合適位置
Dim pl As Integer,ql As Integer
pl=b(0)
If a(p)<=a(pl)Then
b(0)=p:b(p)=pl
Else
Do While a(p)>a(p1)And b(p1)<>-1
ql=pl:pl=b(pl)
Loop
If b(p1)=-1 And a(p)>a(p1)Then
b(pl)=p:b(p)=-1
Else
b(p)=pl:③
End If
End If
End Sub