六種常用算法-文庫(kù)吧
2025-07-20 13:58 本頁(yè)面
【正文】 字面上理解，這種方法有些貪得無(wú)厭還是…？”答：“基本算法中的遞推法是我們最常使用的，貪心法是另一種有意思的算法。貪心法不僅僅是貪婪，而且是每一步都貪婪！下面舉例說(shuō)明。”什么是貪心法貪心法就是做一種目前最貪婪的行動(dòng)，一步步解決問(wèn)題。貪心法和遞推法有相似之外，也是從問(wèn)題的某一個(gè)初始解出發(fā)，向給定的目標(biāo)遞推，但不同的是每一步不是依據(jù)某一個(gè)固定的遞推式，而是做一個(gè)當(dāng)時(shí)看似最佳的貪心選擇，不斷地將問(wèn)題歸結(jié)為更小的相似的問(wèn)題。示例：刪數(shù)問(wèn)題鏈盤(pán)輸入一個(gè)高精度的數(shù)N，去掉任意S個(gè)數(shù)字后剩下的數(shù)字按原左右次序組成一個(gè)新的正整數(shù)，編程對(duì)于給定的N和S，尋找一種方案使得剩下的數(shù)字組成的新數(shù)最小。為了便于操作，將N做為字符串的形式輸入，可以使用盡可能逼近目標(biāo)的貪心算法來(lái)完成，刪數(shù)的過(guò)程中是一個(gè)一個(gè)進(jìn)行刪除的，為了保證最后得到的數(shù)最小，每一步總是要?jiǎng)h除使剩下的數(shù)最小的數(shù)字。之所以做出這樣貪心的選擇，是因?yàn)閯hS個(gè)數(shù)字的最優(yōu)解，包含了刪除一個(gè)數(shù)字的子問(wèn)題的最優(yōu)解。為了實(shí)現(xiàn)上述目的，我們可以進(jìn)行S次選擇，每次都選擇N中最大的數(shù)字，此數(shù)字選擇后將不再參與下次的選擇。具體實(shí)現(xiàn)請(qǐng)看源程序。語(yǔ)言、界面、源程序（1）語(yǔ)言程序中通過(guò)Virual 。（2）界面界面非常簡(jiǎn)單，建立一標(biāo)準(zhǔn)EXE工程，其caption設(shè)為“刪數(shù)問(wèn)題”。放入三個(gè)文本框和兩個(gè)按鈕，文本框起到輸入兩個(gè)數(shù)和輸出結(jié)果的作用，按鈕用來(lái)控制執(zhí)行，再放入三個(gè)標(biāo)簽起到說(shuō)明的作用。（3）源程序Private Sub CmdDelnum_Click()39。開(kāi)始刪數(shù)按鈕 Dim i As Integer Dim j As Integer Dim n As String 39。原數(shù) Dim s As Integer 39。刪數(shù)的個(gè)數(shù) Dim nlength As Integer 39。N的長(zhǎng)度 Dim a() As Integer 39。放位數(shù)數(shù)組 Dim k As Integer 39。記錄最大值位置 = n = s = Val() nlength = Len(n) ReDim a(nlength 1) 39。將各位的值放入數(shù)組 For i = 0 To nlength 1 a(i) = Mid(n, i + 1, 1) Next i 39。執(zhí)行貪心算法s步For j = 1 To s k = 0 For i = 1 To nlength j If a(k) a(i) Then k = i End If Next i d = a(k) For i = k To nlength 1 j a(i) = a(i + 1) Next i a(nlength j) = dNext j39。輸出結(jié)果For i = nlength 1 To nlength s Step 1 39。刪數(shù)過(guò)程 = + 刪除的第 + Str(nlength i) + 個(gè)數(shù) + Str(a(i)) + vbCr + vbLfNext i39。最后的數(shù)For i = 0 To nlength s 1 = + Str(a(i))Next iEnd Sub(上程序在VB60 Win2000下調(diào)試通過(guò))小結(jié)這就是有趣的貪心算法，說(shuō)是貪得無(wú)厭可以，說(shuō)是守住當(dāng)前的既得利益，以此為基礎(chǔ)，再穩(wěn)扎穩(wěn)打地進(jìn)行下一步也行！滴水不漏——列舉法破解難題問(wèn)：“列舉法是種什么樣子的算法呢？”答：“列舉法是比貪心法還要貪得多的算法，列舉法也是一種比較笨但卻很有效的算法，他想要的東東，一種情況他都不想落下，大有寧可錯(cuò)殺一千，不可放過(guò)一個(gè)的陣勢(shì)。下面舉例說(shuō)明。”什么是列舉法列舉是針對(duì)問(wèn)題所有的可能一一查看是不是符合條件，有些“寧肯錯(cuò)殺一千，不
高考資料相關(guān)推薦
鄂ICP備17016276號(hào)-1