一面木板墻,每塊木板的寬度都是1,現(xiàn)在想在木板墻上沿著平行于地面的方向切割出一塊矩形區(qū)域。如果知道每塊木板的高度,如何切出的矩形面積最大?木板墻如圖所示:
圖中有7塊木板,每塊木板的高度分別為:2、4、4、3、5、1、1。嘗試后,我們發(fā)現(xiàn)最大的矩形就是波浪圖案部分所示。也就是切割了高度為4、4、3、5四塊木板,形成了一個(gè)高度為3,寬度為4的矩形,這個(gè)最大面積為12。
經(jīng)過(guò)嘗試,可以發(fā)現(xiàn):切下來(lái)的最大矩形,一定是以最大矩形所在的區(qū)域中最短的那塊木板為矩形的高度值。
這樣我們可以枚舉每一塊木板,每次都以當(dāng)前木板作為高度。就是把當(dāng)前木板當(dāng)成是切出來(lái)的矩形區(qū)域中最矮的木板,然后分別向左右延伸,切出此時(shí)的最大矩形區(qū)域。當(dāng)把所有的木板都嘗試過(guò)一遍后,我們?cè)谒械慕Y(jié)果中比較出最大值,這個(gè)最大值就是我們要求的最大矩形面積。如果木板的數(shù)量為n,那么這種算法的時(shí)間復(fù)雜度接近于0(n2)。但是,如果利用好棧這種數(shù)據(jù)結(jié)構(gòu),就能快速的定位左右延伸的最遠(yuǎn)位置,將算法的時(shí)間復(fù)雜的降低到 0(n)。
實(shí)現(xiàn)上述時(shí)間復(fù)雜度為0(n)的Python程序代碼如下,完成以下問(wèn)題。
(1)如果7塊木板從左往右依次的高度是2、1、4、5、1、3、3,切割出來(lái)的最大矩形面積是 。
(2)完成橫線處代碼。
【考點(diǎn)】程序設(shè)計(jì)實(shí)例.
【答案】見(jiàn)試題解答內(nèi)容
【解答】
【點(diǎn)評(píng)】
聲明:本試題解析著作權(quán)屬菁優(yōu)網(wǎng)所有,未經(jīng)書(shū)面同意,不得復(fù)制發(fā)布。
發(fā)布:2024/6/27 10:35:59組卷:2引用:1難度:0.9
相似題
-
1.公因數(shù)只有1的兩個(gè)非零自然數(shù),叫做互質(zhì)自然數(shù)。王老師編寫(xiě)了一個(gè)Python程序,程序的功能是隨機(jī)產(chǎn)生5個(gè)1到20之間的整數(shù),找出其中和最大的互質(zhì)數(shù)對(duì)。程序運(yùn)行界面如圖所示:
實(shí)現(xiàn)該功能的程序代碼如下:
請(qǐng)回答下列問(wèn)題:
(1)尋找互質(zhì)數(shù)對(duì)的算法屬于
(2)如產(chǎn)生的 5 個(gè)隨機(jī)數(shù)是[20,16,12,6,14],則程序輸出內(nèi)容是
(3)要實(shí)現(xiàn)程序的功能,請(qǐng)完善橫線處的代碼。發(fā)布:2024/12/20 18:0:1組卷:3引用:1難度:0.4 -
2.小紅用Python編寫(xiě)程序畫(huà)出了如圖形,在第三行下劃線處應(yīng)該填寫(xiě)( ?。?br />
發(fā)布:2024/12/18 11:0:1組卷:2引用:1難度:0.6 -
3.【加試題】小丫覺(jué)得回文字符串太優(yōu)美了(回文字符串是指順讀和倒讀都一樣的字符串,如“123321”),為此編寫(xiě)了VB 程序。程序運(yùn)行時(shí),單擊按鈕Command1 后,根據(jù)文本框Text1 中輸入的內(nèi)容判斷并輸出是不是回文串。實(shí)現(xiàn)上述功能的VB 代碼如下。
Private Sub Command1_Click( ?。?br />Dim s As String,f As Boolean,L As Integer
s=Text1.Text
j=Len(s)
i=1
Do while?、?/bdo>
i=i+1
j=j-1
Loop
If?、?/bdo>Then Print“是回文串“Else Print“不是回文串“
End Sub
在畫(huà)線處填入合適代碼,使程序能正常運(yùn)行。
①
②發(fā)布:2024/12/19 14:30:2組卷:0引用:1難度:0.4
把好題分享給你的好友吧~~