算法設(shè)計與分析蠻力法(編輯修改稿)
2025-02-04 15:47 本頁面
【文章內(nèi)容簡介】 2， 120， 121， 122， 130， 200， 201， 202， 211， 212， 220， 221， 300， 301， 310。 不難驗證只有 100， 101兩個數(shù)符合要求。 例 3 獄吏問題 某國王對囚犯進行大赦，讓一獄吏 n次通過一排鎖著的 n間牢房，每通過一次，按所定規(guī)則轉(zhuǎn)動 n間牢房中的某些門鎖 , 每轉(zhuǎn)動一次 , 原來鎖著的被打開 , 原來打開的被鎖上；通過 n次后，門鎖開著的，牢房中的犯人放出，否則犯人不得獲釋。 轉(zhuǎn)動門鎖的規(guī)則是這樣的，第一次通過牢房，要轉(zhuǎn)動每一把門鎖，即把全部鎖打開；第二次通過牢房時，從第二間開始轉(zhuǎn)動，每隔一間轉(zhuǎn)動一次；第 k次通過牢房，從第 k間開始轉(zhuǎn)動，每隔 k1 間轉(zhuǎn)動一次；問通過 n次后，哪些牢房的鎖仍然是打開的？ 算法分析與設(shè)計 15 算法設(shè)計 1： 1） 一維數(shù)組 a[n]記錄 n個鎖的狀態(tài) 1:被鎖上 0:被打開 2） 對 i號鎖的一次開關(guān)鎖可以轉(zhuǎn)化為算術(shù)運算： a[i]=1a[i]。 3） 第一次轉(zhuǎn)動的是 1， 2， 3， …… ， n號牢房； 第二次轉(zhuǎn)動的是 2， 4， 6， …… 號牢房； 第 i次轉(zhuǎn)動的是 i， 2i， 3i， 4i， …… 號牢 房 ， 是起點為 i， 公差為 i的等差數(shù)列 。 4）不做其它的優(yōu)化，用蠻力法通過循環(huán)模擬獄吏的開關(guān)鎖過程，最后當(dāng)?shù)?i號牢房對應(yīng)的數(shù)組元素 a[i]為 0時，該牢房的囚犯得到大赦。 算法分析與設(shè)計 16 算法 1如下： input(n)。//輸入 n a=new int(n+1)。 for (i=1。 i=n。i++) a[i]=1。 for (i=1。 i=n。i++) for (j=i。 j=n。j=j+i) a[i]=1a[i]。 for (i=1。 i=n。i++) if (a[i]=＝ 0) print(i,”is free.”)。 算法分析：以一次開關(guān)鎖計算 ， 算法的時間復(fù)雜度 為 n(1+1/2+1/3+…… +1/n)=O(nlogn)。 問題分析： 轉(zhuǎn)動門鎖的規(guī)則可以有另一種理解，第一次轉(zhuǎn)動的 是編號為 1的倍數(shù)的牢房；第二次轉(zhuǎn)動的是編號為 2的倍數(shù)的牢 房；第三次轉(zhuǎn)動的是編號為 3的倍數(shù)的牢房； …… 則 獄吏問題是 一個關(guān)于因子個數(shù)的 問題。令 d(n)為自然數(shù) n的因子個數(shù)，這里 不計重復(fù)的因子，如 4的因子為 1， 2， 4共三個因子，而非 1， 2， 2， 4。則 d(n)有的為奇數(shù)，有的為偶數(shù)，見下表 : 表 1 編號與因數(shù)個數(shù)的關(guān)系 n 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 … d(n) 1 2 2 3 2 4 2 4 3 4 2 6 2 4 4 5 … 算法分析與設(shè)計 18 數(shù)學(xué)模型 1： 上表中的 d(n)有的為奇數(shù)，有的 為偶數(shù)， 由于 牢房
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1