技術(shù)參考貪心策略ppt課件(編輯修改稿)
2025-06-08 08:29 本頁面
【文章內(nèi)容簡介】 過程分開，著重探討求 max的問題。 下面我們以求 max為例來討論此題用貪心策略求解的合理性。 討論：假設(shè)經(jīng)（Ｎ－ 3）次變換后得到３個數(shù)：a,b,max＇（ max＇ ≥ａ ≥ｂ），其中 max＇是（Ｎ－２）個數(shù)經(jīng)（Ｎ－３）次ｆ變換后所得的最大值，此時有兩種求值方式，設(shè)其所求值分別為， ，則有： ＝（ａ ｂ＋１） max＇＋１， ＝（ａ max＇＋１） ｂ+１ 所以 － ＝ max＇－ｂ ≥０若經(jīng)（Ｎ－２）次變換后所得的３個數(shù)為：ｍ，ａ，ｂ（ｍ ≥ａ ≥ｂ）且ｍ不為（Ｎ－２）次變換后的最大值，即ｍ＜ max＇則此時所求得的最大值為： ＝（ａ ｂ +１） ｍ +１ 此時 － ＝（１ +ａｂ）（ max＇－ｍ）＞０ 所以此時不為最優(yōu)解。 所以若使第ｋ（１ ≤ ｋ ≤ Ｎ－１）次變換后所得值最大，必使（ｋ－１）次變換后所得值最大（符合貪心策略的特點 2），在進行第ｋ次變換時，只需取在進行（ｋ－１）次變換后所得數(shù)列中的兩最小數(shù)ｐ，ｑ施加ｆ操作：ｐ ← ｐ ｑ +1，ｑ←∞ 即可（符合貪心策略特點 1），因此此題可用貪心策略求解。討論完畢 在求ｍｉｎ時，我們只需在每次變換的數(shù)列中找到兩個最大數(shù)ｐ，ｑ施加作用ｆ：ｐ ← ｐ ｑ +１，ｑ← ∞即可．原理同上。 這是一道兩次運用貪心策略解決的一道問題，它要求選手有較高的數(shù)學(xué)推理能力。 ［例３］最優(yōu)乘車問題 試題描述 Ｈ城是一個旅游勝地，每年都有成千上萬的人前來觀光．為方便游客，巴士公司在各個旅游景點及賓館、飯店等地都設(shè)置了巴士站，并開通了一些單向巴士線路。每條單向巴士線路從某個巴士站出發(fā)，依次途徑若干個巴士站，最終到達(dá)終點巴士站。 阿昌最近到Ｈ城旅游，住在ＣＵＰ飯店。他很想去Ｓ公園游玩。聽人說，從ＣＵＰ飯店到Ｓ公園可能有也可能沒有直通巴士。如果沒有，就要換乘不同線路的單向巴士，還有可能無法乘巴士到達(dá)。 現(xiàn)在用整數(shù)１，２， ...，ｎ給Ｈ城的所有巴士站編號，約定ＣＵＰ飯店的巴士站編號為１，Ｓ公園巴士站的編號為Ｎ。 寫一個程序，幫助阿昌尋找一個最優(yōu)乘車方案，使他在從ＣＵＰ飯店到Ｓ公園的過程中換車的次數(shù)最少。 試題背景 出自ＮＯＩ９７ 試題分析 此題看上去很像一道搜索問題。在搜索問題中，我們所求的使經(jīng)過車站數(shù)最少的方案，而本題所求解的使換車次數(shù)最少的方案。這兩種情況的解是否完全相同呢？我們來看一個實例： 圖 5 如圖 5所示：共有５個車站（分別為ａ、
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1