天天看點

《算法設計程式設計實驗:大學程式設計課程與競賽訓練教材》——1.1 機理分析法的實驗範例

根據客觀事物的特性,分析其内部的機理,弄清關系,在适當抽象的條件下,得到可以描述事物屬性的數學工具。

《算法設計程式設計實驗:大學程式設計課程與競賽訓練教材》——1.1 機理分析法的實驗範例

經過數學分析,如果能夠抽象出ad hoc類問題的内在規律,則可以采用機理分析法建立數學模型,然後根據模型的原理對應到算法,程式設計實作,通過執行算法得到問題解,如圖1.1-1所示。

機理分析法的核心是數學模組化,即使用适當的數學思想建立起模型;或者提取問題中的有效資訊,用簡明的方式表達其規律。需要注意的是:

1)選擇的模型必須盡量多地展現問題的本質特征。但這并不意味着模型越複雜越好,累贅的資訊會影響算法效率。

2)模型的建立不是一個一蹴而就的過程,而是要經過反複地檢驗和修改,在實踐中不斷完善。

3)數學模型通常有嚴格的格式,但程式編寫形式可不拘一格。

機理分析法是一個複雜的資料抽象過程。我們要善于透視問題的本質,尋找突破口,進而選擇适當的模型。模型的構造過程可以幫助我們認識問題,不同的模型從不同的角度反映問題,可以引發不同的思路,起到引導發散思維的作用。但認識問題的最終目的是解決問題,模型的固有性質雖可幫我們建立算法,其優劣也可通過時空複雜度等名額來分析和衡量,但最終還是以程式的運作結果為标準。是以模型不是一成不變的,同樣要通過各種技術不斷優化。模型的産生雖然是人腦思維的産物,但它仍然是客觀事物在人腦中的反映。是以要培養良好的模組化能力,還必須依靠在平時的學習中積累豐富的知識和經驗。

下面舉兩個實驗範例。

【1.1.1 factstone benchmark】

【問題描述】

amtel已經宣布,到2010年,它将發行128位計算機晶片;到2020年,它将發行256位計算機;等等,amtel堅持每持續十年将其字大小翻一番的戰略。(amtel于2000年發行了64位計算機,在1990年發行了32位計算機,在1980年發行了16位計算機,在1970年發行了8位計算機,并首先在1960年發行了4位計算機。)

amtel将使用新的标準檢查等級(factstone)來宣傳其新晶片大大提高的能力。factstone等級被定義為這樣的最大整數n,使得n!可以表示為一個計算機字中的無符号整數(比如1960年的4位計算機可表示3!=6,而不能表示4!=24)。

給出一個年份1960≤y≤2160,amtel最近釋出的晶片的factstone等級是什麼?

輸入:

給出若幹測試用例。每個測試用例一行,給出年份y。在最後一個測試用例後,給出包含0的一行。

輸出:

對于每個測試用例,輸出一行,給出factstone等級。

《算法設計程式設計實驗:大學程式設計課程與競賽訓練教材》——1.1 機理分析法的實驗範例

試題來源:waterloo local 2005.09.24

線上測試位址:poj 2661,uva 10916

試題解析

對于給定的年份,先求出當年amtel處理器的字大小,然後計算出最大的n的值,使得n!成為一個符合字的大小的無符号整數。

在1960年,字的大小是4位,以後每十年字的大小翻一番,這就意味着,y年字的位數為k=22+y-196010。能放在k位中最大的無符号整數是2k-1。如果n!為不大于2k-1的最大正整數,則n為y年晶片的factstone等級。計算方法有兩種:

方法1:直接求不大于2k-1的最大正整數n!,這種方法極容易溢出且速度慢。

方法2:采用對數計算,即根據log2n!=log2n+log2(n-1)+…+log21≤log2(2k-1)計算y年字的位數k,累加log2i(i從1出發,每次加1),直到數字超過k為止。此時,i-1即為factstone等級。

程式清單

【1.1.2 bridge】

n個人要在晚上過橋,在任何時候最多兩人一組過橋,每組要有一隻手電筒。在這n個人中隻有一隻手電筒可以用,是以要安排以某種往返的方式來返還手電筒,使得更多的人可以過橋。

每個人的過橋速度不同,每組的速度由速度較慢的成員所決定。請确定一個政策,讓n個人用最少的時間過橋。

輸入的第一行給出n,接下來的n行給出每個人的過橋時間,不會超過1000人,且沒有人的過橋時間超過100秒。

輸出的第一行給出所有n個人過橋的總的秒數,接下來的若幹行給出實作政策。每行包含一個或兩個整數,表示組成一組過橋的一個人或兩個人(每個人用其在輸入中給出的過橋所用的時間來辨別。雖然許多人的過橋時間相同,但即使有混淆,對結果也沒有影響)。這裡要注意的是過橋也有方向性,因為要返還手電筒讓更多的人通過。如果用時最少的政策有多個,則任意一個都可以。

《算法設計程式設計實驗:大學程式設計課程與競賽訓練教材》——1.1 機理分析法的實驗範例

試題來源:waterloo local 2000.09.30

線上測試位址:poj 2573,zoj 1877,uva 10037

稍動腦筋,便可以得出一個簡單的邏輯:要使得n個人用最少的時間過橋,慢的成員必須借助快的成員傳遞手電筒。

由于一次過橋最多兩人且手電筒需要往返傳遞,是以以兩個成員過橋為一個分析機關,計算過橋時間。我們按過橋時間遞增的順序将n個成員排序。設目前序列中,

a是最快的人,b是次快的人,a和b是序列首部的兩個元素。

a是最慢的人,b是次慢的人,a和b是序列尾部的兩個元素。

有兩種過橋方案:

方案1:用最快的成員a傳遞手電筒幫助最慢的a和b過橋。

如果帶一個最慢的成員,則所用的時間是a+a(a表示最快和最慢的兩個成員到對岸所需的時間,而a是最快的成員傳回所需的時間)。顯然帶兩個最慢的成員所用的時間是2*a+a+b。

方案2:用最快的成員a和次快的成員b傳遞手電筒幫助最慢的a和b過橋。

步驟1:a和b到對岸,所用時間為b。

步驟2:a傳回,将手電筒給最慢的a和b,所用時間為a。

步驟3:a和b到對岸,所用時間為a;到對岸後,他們将手電筒交給b。

步驟4:b需要傳回原來的岸邊,因為要交還手電筒,所需時間為b。

是以,需要的總時間為2*b+a+a。

顯然,最慢的a和b要用最少的時間過橋,隻能借助a或者a和b傳遞手電筒過橋,其他方法都會增加過橋時間。哪一種過橋方案更有效?比較一下就行了:

如果(2a+a+b<2b+a+a),則采用第1種方案,即用最快的成員a傳遞手電筒;否則采用第2種方案,即用最快的成員a和次快的成員b傳遞手電筒(2a+a+b<2b+a+a等價于b+a<2*b)。

我們每次幫助最慢的兩個成員過橋(n-=2),累計每個最佳過橋方案的時間。最後産生兩種可能情況:

1)對岸剩下2個隊員(n==2),全部過橋,即累計時間為b。

2)對岸剩下3個隊員(n==3),用最快的成員傳遞手電筒,幫助最慢的成員過橋,然後與次慢的成員一起過橋,即累計時間為a+a+b。

繼續閱讀