貪心算法（二）——尋找最優(yōu)解1、（諸暨中學）存儲簡單幾何圖形（正方形、長方形和三角形）數(shù)據(jù)的方法描述如下：①使用特征數(shù)：1表示正方形，2表示長方形，3表示三角形；②正方形只用1個正整數(shù)數(shù)表示邊長、長方形用2個正整數(shù)分別表示它的長和寬、三角形用3個正整數(shù)表示其三邊的邊長；③數(shù)據(jù)的開頭一個正整數(shù)n（n不超過3000，數(shù)字之間用ASCII字符逗號分隔），表示接下來共有n個簡單幾何圖形的信息；所有原始數(shù)據(jù)都是合理的。如數(shù)據(jù)4，1，2，3，2，2，3，2，2，3，3，3，4，5，表示共有4個簡單幾何圖形。第一個為正方形，邊長為2；第二個為三角形，邊長分別為2，2，3；第三個為長方形，長和寬分別為2，3；第四個為三角形，三邊長分別為3，4，5根據(jù)上述存儲數(shù)據(jù)，小龍編寫了一個VB程序，功能如下：窗體加載時，自動讀取數(shù)據(jù)，依次存儲在數(shù)組元素a（1）、a（2）、a（3）……中。單擊“統(tǒng)計”按鈕Command1，程序對數(shù)據(jù)依次進行分析統(tǒng)計，并在列表框Listl中顯示每個簡單幾何圖形是什么形狀，其周長是多少，最后在列表框中所有簡單幾何圖形周長的最大值是多少。（1）數(shù)據(jù)“10，1，3，2，4，5，3，7，3，5，1，5，2，7，3，3，4，4，3，2，2，3，3，8，5，4，1，6，2，8，9”表示的簡單圖形中長方形共有個。（2）實現(xiàn)上述功能的VB程序如下，請在劃線處填入適合的代碼。Dima（1To3000）AsIntegerPrivateSubform_load（），讀取并將簡單幾何圖形的原始數(shù)據(jù)存儲在數(shù)組a中，代碼略EndSubPrivateSubCommand1_Click（）’讀取并存儲數(shù)據(jù)DimnAsLong，iAsLong，kAsLongDimmaxAsinteger，Lasinteger，pasinteger‘max表示最大周長，L表示正在處理的圖形的周長n=①max=0：②Fori=1TonIfa（k）=1ThenL=4*a（k+1）List1.Addltem"圖形”&Str（i）&"是正方形，周長為"&Str（L）IfL>maxthenmax=L:p=kk=k+2ElseIfa（k）=2Then③List1.Addltem”圖形”&Str（i）&”是長方形，周長為”&Str（L）IfL>maxthenmax=L:p=kk=k+3ElseL=a（k+1）+a（k+2）+a（k+3）Listl.Addltem”圖形”&Str（i）&”是三角形，周長為"&Str（L）IfL>maxthenmax=L:p=kk=k+4EndIfNextiList1.Addltem”所有簡單幾何圖形中，周長最大值為"&Str（max）EndSub2、（金華十校）波波同學一直夢想買彩票中500萬大獎，他收集了最近100期“雙色球”開獎信息，存儲于data.accdb文件中，并使用VB軟件編寫了“雙色球投注建議”程序，程序根據(jù)最近100期開獎信息，統(tǒng)計出現(xiàn)概率最低的6個紅色球號碼和1個藍色球號碼，給出投注建議。如果藍色球有多個概率最低的號碼，則輸出多個，紅色球不考慮并列概率最低情況。注：福彩“雙色球”玩法：在1-33個紅色球號碼中隨機生成6個號碼，在1-16個藍色球號碼中隨機生成1個號碼，共計6+1個號碼開獎。程序運行界面如下圖所示：（1）實現(xiàn)上述功能的VB程序如下，請完善劃線處的代碼。Dimred（1To600）AsInteger用于存儲100*6紅色球信息Dimblue（1To100）AsInteger用于存儲100*1藍色球信息PrivateSubForm_Load0本過程用于從數(shù)據(jù)庫data.accdb中讀取最近100期雙色球開獎信息將100*6個紅色球開獎信息依次存儲在數(shù)組red0中將100*1個藍色球開獎信息依次存儲在數(shù)組blue0中將最近100期開獎信息格式化后顯示在列表框List1中本過程代碼略EndSubPrivateSubCommand1_Click（）DimminAsIntegerDimsAsstringDimf（1To33）AsInteger--------以下開始處理藍色球部分--------Forb=1To100f（blue（b）=f（blue（b））+1Nextbmin=100Fori=1To16Iffi）<minThenmin=f(i）NextiFori=1To16Iff）=minThens=①f(i)=0NextiList2.Addltem"藍色球重點買入："+s--------以下開始處理紅色球部分--------Forr=1To600②Nextr③Fori=1To6Fori=1To6’查找概率最低的6個紅球數(shù)字k=1Forj=2To33Iff(j)<f（k）Thenk=jNextjs=s+Str（k）f(k)=100NextiList2.Addtem“紅色球重點買入：“+sEndSub在某次紅球部分處理時，若數(shù)組f中的，f（1）至f（33）的值依次為：結合加虛線框處代碼的算法，輸出的內(nèi)容是：紅色球重點買入：（按順序寫出6個紅球的號碼）3、（溫州一模）某地為各個村之間建灌溉管道，現(xiàn)需實現(xiàn)用最短的管道距離使得所有村莊可以連通。如圖所示，[V1，V2，V3，V4，V5]每個節(jié)點表示村莊，兩個節(jié)點之間的數(shù)值表示兩個村莊之間的邊距離。算法思路如下：①首先按邊距離升序排序；②找到邊距離最小值1，以及相應的兩個節(jié)點V1和V3；③以V1或V3作為起點，搜尋連接新節(jié)點且距離最小的邊，發(fā)現(xiàn)（V1，V4）邊最小為4；④以V1、V3、V4作為起點，搜尋連接新節(jié)點且距離最小的邊，發(fā)現(xiàn)（V4，V5）邊最小為2；⑤以V1、V3、V4、V5作為起點，搜尋連接新節(jié)點且距離最小的邊，發(fā)現(xiàn)（V2，V5）邊最小為3；因此可知，連通5個村莊的最短管道距離是1+4+2+3=10，效果如所示。現(xiàn)設計了如下VB程序，界面如圖所示，請回答下列問題：（1）V2到V5的邊距離若為6，則連通5個村莊的最短管道距離是。（2）請在劃線處填入合適的代碼。Constn=5’村莊數(shù)Constm=8’管道線路數(shù)DimpointAB（1To2*m）AsInteger’存儲連接的兩個村莊節(jié)點Dimlength（1Tom）AsInteger’存儲兩個村莊之間的距離Dimres（1To100）AsInteger’存儲管道規(guī)劃結果PrivateSubFormLoad（）’村莊節(jié)點數(shù)據(jù)存儲在pointAB數(shù)組，兩個村莊的距離數(shù)據(jù)存儲在length數(shù)組?！绲?7題圖c所示，（V1，V3）邊距離為1，則pointAB（1）=1，pointAB（2）=3，1ength（1）=1；（V1，V2）邊距離為6，則pointAB（3）=1，pointAB（4）=2，1ength（2）=6；其他依次類推，代碼略。EndSubFunctioncheck（xAsInteger）AsInteger’判斷x節(jié)點是否已在規(guī)劃中check=0Fori=1To100Ifx=res（i）Thencheck=1：ExitFunctionNextiEndFunctionPrivateSubCommand1_Click（）DimiAsInteger，jAsInteger，tmpAsInteger，totalAsInteger，sumAsIntegerFori=1Tom-1Forj=mToi+1Step-1If①Thentmp=pointAB（2*j-1）：pointAB（2*j-1）=pointAB（2*j-3）：pointAB（2*j-3）=tmptmp=pointAB（2*j）：pointAB（2*j）=pointAB（2*j-2）：pointAB（2*j-2）=tmptmp=length（j）：1ength（j）=length（j-1）：1ength（j-1）=tmpEndIfNextjNexti’開始規(guī)劃管道total=1res（1）=pointAB（1）：res（2）=pointAB（2）：sum=length（1）DoWhiletotal<②Fori=2TomIf③Thentotal=total+1res（2*total-1）=pointAB（2*i-1）：res（2*total）=pointAB（2*i）sum=sum+length（i）ExitForEndIfNextiLoop’輸出連通結果res以及管道總長度sum，代碼略。EndSub4、(2021衢州模擬15)某市要組織高中生參加競技比賽。現(xiàn)要求在報名的n名學生中挑選出m名身高大于等于175cm的學生，被挑選出的學生兩兩組隊，且隊內(nèi)兩名成員的體重之和不能超過175公斤。編寫VB程序，實現(xiàn)上述挑選、組隊功能。運行程序，在列表框List1中顯示m名身高大于等于175cm的學生信息，且根據(jù)體重數(shù)值降序排序。單擊“組隊”按鈕，在符合條件的情況下盡可能多的兩兩組隊，并將組隊結果顯示在列表框List2中。程序運行界面如第15題圖所示，實現(xiàn)上述功能的VB程序如下。請回答下列問題：（1）觀察代碼可知，該程序“組隊”按鈕的對象名為。（2）請在劃線處填入合適的代碼。（3）程序中加框處代碼有錯，請改正。Constn=20Dimid（1To20）AsInteger，h（1To20）AsInteger，w（1To20）AsInteger，mAsIntegerPrivateSubFormLoad（）’從數(shù)據(jù)庫中讀取n名學生的編號、身高和體重分別存儲在數(shù)組id、h和w中，代碼略。m=0’存儲身高≥175cm的學生總數(shù)Fori=1Tonk=iForj=i+1TonIfh（j）〉=175ThenIfw（j）〉w（k）Thenk=j‘（3）EndIfNextjIfk<>iThent=id（i）：id（i）=id（k）：id（k）=tt=h（i）：h（i）=h（k）：h（k）=tt=w（i）：w（i）=w（k）：w（k）=tEndIfIfh（i）<175Thenm=i-1ExitFor’結束挑選E1se①EndIfList1.AddItemstr（id（i））+""+Str（h（i））+""+Str（w（i））NextiEndSubPrivateSubCom_Click（）L=1：R=mDoWhileL<RIf②ThenList2.AddItemStr（id（L））+"號和"+Str（id（R））+"號組隊”L=L+1：R=R-1Else③EndIfLoopEndSub5、（2021年11月紹興診斷15）某景區(qū)渡口游客可乘船往返于河的兩岸，有m個人自河東去河西，n個人自河西返回河東?，F(xiàn)有一艘船，最大載重量為wt，最多可同時載兩人，船自河東出發(fā)，最后返回河東。所有人的體重不會超過wt，求把所有人載過河所需最少往返次數(shù)。編寫一個VB程序，實現(xiàn)上述功能。程序運行時，在列表框List1中顯示所有游客的體重和去向（W表示往西、E表示往東），如“132E”表示體重為132往東。單擊“統(tǒng)計”按鈕Command1，在標簽Labell中顯示最少往返次數(shù)。程序運行界面如圖所示。（1）VB語句Listl.Addltem""中Addltem是（單選，填字母：A.對象名/B.方法名/C.屬性名）。（2）實現(xiàn)上述功能的VB程序如下，請在劃線處填入合適代碼。（3）程序加框處的代碼有誤，請改正。Constm=6，n=8，wt=200Dimd（1Tom+n）AsString，a（1Tom+n）AsIntegerPrivateSubForm_Load（）’讀取m+n個人的體重及去向數(shù)據(jù)存入d數(shù)組，代碼略EndSubPrivateSubCommand1_Click）DimiAsInteger,pAsInteger,qAsInteger,sAsString，numAsInteger，numlAsInteger，num2AsInteger’以下代碼實現(xiàn)從d數(shù)組中提取每個人的體重數(shù)據(jù)，根據(jù)去向分段存入a數(shù)組p=1：q=①Fori=1Tom+ns=Mid（d（i），1，Len（d（i））-1）IfMid（d（i），②，1）="W"Thena（p）=Val（s）：p=p+1Elsea（q）=Val（s）：q=q+1EndIfNextinuml=GetNum（1，m）num2=GetNum（m+1，m+n）Ifnum1>num2Thennum=numlElsenum=num2Labell.Caption="過河需要最少往返次數(shù)："+Str（num）EndSubFunctionGetNum（headAsInteger，tailAsInteger）AsIntegerDimiAsInteger，jAsInteger，kAsInteger，cntAsInteger，tAsInteger’以下代碼實現(xiàn)對數(shù)組a降序排序i=headDoWhilei<tailk=i:i=tailForj=k+1TotailIfa（j-1）<a（j）Thent=a（j）：a（j）=a（j-1）：aj-1）=ti=jEndIfNextjLoopcnt=0：i=head:j=tailDoWhilei<=jIf③Thenj=j-1cnt=cnt+1:i=i+1LoopGetNum=cntEndFunction6、（超級全能生B卷）小明在某網(wǎng)絡商城選購商品，已知該商城商品打折方案是價格每滿90元將減40元，滿減次數(shù)不限。小明挑選n件商品并放入購物車，準備再從中選擇若干件商品購買。購買方案是：首選滿足優(yōu)惠幅度最大的商品組合（例如：總價275和總價181兩種組合將選擇總價為181組合），如果優(yōu)惠幅度相同，選擇其中總價最低組合，如果優(yōu)惠幅度和總價均相同，選擇最先符合要求的組合，程序運行界面如圖。小明依據(jù)上述描述設計如下VB程序，請在畫線處填入合適的代碼。Constn=12Dima（1Ton）AsInteger'a數(shù)組存儲所選購商品的價格Dimb（1Ton）AsInteger.'b數(shù)組標識對應商品是否購買，值為1表示購買，值為0表示不買PrivateSubForm_Load（）‘數(shù)據(jù)初始化，將所選購物車中商品價格存儲到數(shù)組a中，并在列表框List1中顯示商品編號及對應價格EndSubPrivateSubCommand1_Click（）DimiAsInteger，jAsIntegerDimcAsString，cmaxAsStringDimsAsInteger，smaxAsInteger，mmaxAsIntegerFori=1Tonb(i)=1Nextimmax=40：smax=0：i=1DoWhilei<=ns=0：c=""Forj=1Tons=s+a（j）*b（j）Ifb（j）<>0Thenc=c+Str（j）NextjIfs=0ThenExitDoIfsMod90<mmaxThenmmax=sMod90：smax=s:cmax=c①mmax=sMod90：smax=s:cmax=cEndIfi=1DoWhilei<=nAndb（i）=0i=i+1LoopIfi<=nThen②Forj=1Toi-1b（j）=1NextjEndIfLoopList2.AddItem"選購編號："+cmaxList2.Addltem“商品總價："+Str（smax）List2.Addltem"實際消費："+Str（③）EndSub7、（2021年9月七彩陽光16）班長為合唱比賽準備禮物，預算總金額有n元錢，預計購買p件禮物，每件禮物對應有商品編號、單價、數(shù)量和喜愛度。禮物不可分割，每人至多一份，班長希望每位獲得禮物的同學都盡可能喜愛獲得的禮物。按上述要求，編寫VB程序，功能如下：在文本框Text1中輸入預計禮物數(shù)，在文本框Text2中輸入總金額，單擊“計算”按鈕Command1，在列表框List1中顯示各類商品的編號、單價、數(shù)量、喜愛度，以及最佳購買方案、剩余金額和總喜愛度，若有多種最佳方案，則輸出第一個找到的方案信息，如第16題圖a所示。（1）請在劃線處填入合適的代碼。Constm=4有m種商品Dimsph（1Tom）AsString商品號Dimdj（1Tom）AsSingle單價Dimsl（1Tom）AsInteger數(shù)量Dimxa（1Tom）AsInteger喜愛度Dimhh（1Tom*10）AsInteger每件商品對應的貨號DimpAsInteger，nAsInteger，ncAsIntegerp個朋友，n元錢，共nc件商品DimzxaAsInteger總喜愛度為每件購買商品的喜愛度*購買數(shù)量的總和PrivateSubFormLoad）’各商品的商品號、單價、數(shù)量、喜愛度分別存入數(shù)組sph、dj、sl和xa并輸出，代碼略EndSubPrivateSubCommand1_Click（）Dimgoumai(1Tom*10)AsIntegerDimiAsDouble,jAsInteger,kAsInteger,tAsIntegerDimfsAsInteger,jeAsInteger,maxiasInteger,maxjeAsInteger,maxzxaAsIntegerp=Val(Text1.Text):n=Val(Text2.Text)：nc=0Fori=1TomForj=1Tosl(i)nc=nc+1：①NextjNextiFori=0To2^nc-1t=iForj=1ToncGoumai（j）=②t=t\2Nextjfs=0：je=0：zxa=0“初始化份數(shù)，金額，總喜愛度Forj=1Toncfs=fs+goumai（j）：je=je+dj（hh（j））*goumai（j）：zxa=zxa+xa（hh（j））*goumai（j）NextjIffs=pAnd③Thenmaxi=i：maxje=je:maxzxa=zxaNexti’輸出maxi對應的購買方案，代碼略Ifmaxje>0ThenListl.Addltem"剩余金額"&CStu（n-maxje）&”總喜愛度："&CSt（maxzxa）ElseListl.Adltem“錢太少”EndIfEndSub（2）根據(jù)題意，現(xiàn)有4種商品對應的信息如第16題圖b所示，若預算總金額為400元，預計購買10件禮物，則圖中購買方案中三種商品的購買數(shù)量分別為（填數(shù)字，中間用逗號分隔）。8、（2021年11月稽陽模擬16）物品搬運問題。有n×n個物品，按n行n列整齊的放在一塊場地上，每個物品的重量記錄在數(shù)組a中?，F(xiàn)在要把所有物品搬到一個位置，每次搬運所用的力氣=該物品重量×該次移動的直線距離。如n=6時，a（8）=6表示第2行第2列的物品重量為6。將位置8的物品搬到位置10，所用的力氣為a（8）×（10-8）=12。搬運分兩步進行：（1）把每一行的多個物品搬到該行同一個位置，原則是所用總力氣最少，若有多種方案所用力氣相同，以找到的第一個方案為準。（2）把多行匯集后的物品再次搬到一起，原則不變。根據(jù)上述算法編寫了VB程序，部分運行界面如第16題圖所示。運行程序時，在列表框Listl顯示物品矩陣，單擊“計算”按鈕，在文本框Textl輸出最終坐標和總花費力氣?；卮鹣铝袉栴}：（1）按第16題圖所示的數(shù)據(jù)，把第4行的所有物品搬到一起，使用最優(yōu)方案需要力氣。（2）請在劃線處填入合適的代碼，使程序完整。Constn=6Dima(1Ton*n)AsInteger，num(1Ton)AsIntegerPrivateSubCommand1Click（）DimiAsInteger，jAsInteger，min（1Ton）AsIntegerDimkAsInteger，fareAsSingle，sumAsSingle，ansAsSingleFori=1Ton'初始化各行搬運到一處的總力氣需9999min（i）=9999NextiFori=1Tonx=（i-1）*nForj=1Tonfare=0Fork=1TonIfk<>jThenfare=①EndIfNextkIfmin（i）>fareThenmin（i）=fare：num（i）=jEndIfNextjNextiFori=1Tonsum=0Forj=1Tonsum=dis（i，j）*min（i）+sumNextjIf②Thenans=sum:lasti=iNextians=Int（ans*10+0.5）/10Textl.Text="最終地點是"+Str（lasti）+"行"+Str（num（lasti））+”列，總力氣"+Str（ans）EndSubFunctiondis（xAsInteger，yAsInteger）AsSingled=Abs（x-y）^2+（num（x）-num（y））^2③EndFunctionPrivateSubForm_Load（）’生成數(shù)組a各元素，代碼略EndSub9、（金華十校16）學?；I辦社團節(jié)，每個社團先到A場地做“準備”，然后到B場地“風采展示匯報”。同一場地，同一時間只允許一個社團使用。每個社團使用A、B場地時間都有所不同。已知學校共n個社團，第i個社團使用A場地時長為a[i]分鐘，使用B場地時長為b[i]分鐘。為了更高效的組織這次活動，某同學編寫了如下VB程序計算此次活動的最小總時長和社團參會的順序算法思路；1.統(tǒng)計m[i]表示第i個社團中在A和B兩個場地中用時的較小值2.按m[i]值從小到大排序，然后按m[i]值的順序，逐個社團安排參會順序，策略如下：為了使得總時長最短，讓A場地用時最少的最先開始；B場地用時最少的最后開始。對