習(xí)題1.1

1．研究一下al-Khorezmi（或者稱為al-Khwarizmi，譯名為阿爾·花剌子模），“算法”（algorithm）一詞起源于這個(gè)人的名字。研究過(guò)程中我們還會(huì)發(fā)現(xiàn)，“算法”一詞的起源和“代數(shù)”（algebra）一詞的起源是相同的。

2．如果告訴你，設(shè)立美國(guó)專(zhuān)利體系的基本目的是促進(jìn)“有用的技術(shù)”，那么你認(rèn)為算法在這個(gè)國(guó)家能夠申請(qǐng)到專(zhuān)利嗎？算法是否應(yīng)該允許申請(qǐng)專(zhuān)利呢？

3．a(chǎn)．按照算法要求的精確性寫(xiě)出你從學(xué)校到家里的駕駛指南。

b．按照算法要求的精確性寫(xiě)出你最喜歡的菜的烹飪方法。

4．設(shè)計(jì)一個(gè)計(jì)算5．設(shè)計(jì)一個(gè)算法，在已經(jīng)排序的兩個(gè)列表中，找出所有相同的元素。例如，列表2, 5,5, 5和2, 2, 3, 5, 5, 7，應(yīng)該輸出2, 5, 5。如果給定的兩個(gè)列表的長(zhǎng)度分別為m和n，你設(shè)計(jì)的算法的最大比較次數(shù)是多少？

6．a(chǎn)．用歐幾里得算法求gcd（31415, 14142）。

b．用歐幾里得算法求gcd（31415, 14142），速度是檢查min{m, n}和gcd（m, n）間連續(xù)整數(shù)的算法的多少倍？請(qǐng)估算一下。

7．證明等式gcd（m, n）=gcd（n, m mod n）對(duì)每一對(duì)正整數(shù)（m, n）都成立。

8．對(duì)于第一個(gè)數(shù)小于第二個(gè)數(shù)的一對(duì)數(shù)字，歐幾里得算法將會(huì)如何處理？該算法在處理這種輸入的過(guò)程中，上述情況最多會(huì)發(fā)生幾次？

9．a(chǎn)．對(duì)于所有m≥1，n≤10的輸入，歐幾里得算法最少要做幾次除法？

b．對(duì)于所有m≥1，n≤10的輸入，歐幾里得算法最多要做幾次除法？

10．a(chǎn)．在歐幾里得的書(shū)里，歐幾里得算法用的不是整數(shù)除法，而是減法。請(qǐng)用偽代碼描述這個(gè)版本的歐幾里得算法。

11．?dāng)U展歐幾里得算法　不僅能夠求出兩個(gè)正整數(shù)m和n的最大公約數(shù)d，還能求出兩個(gè)整數(shù)x和y（不一定為正），使得mx+ny=d。

a．在參考資料中查閱擴(kuò)展歐幾里得算法的描述（參見(jiàn)[KnuI]），然后任選一種語(yǔ)言實(shí)現(xiàn)它。

b．改寫(xiě)上述程序以對(duì)丟番圖方程ax+by=c求解，系數(shù)a，b，c為任意整數(shù)。

12．帶鎖的門(mén)　在走廊上有n個(gè)帶鎖的門(mén)，從1到n依次編號(hào)。最初所有的門(mén)都是關(guān)著的。我們從門(mén)前經(jīng)過(guò)n次，每一次都從1號(hào)門(mén)開(kāi)始。在第i次經(jīng)過(guò)時(shí)（i=1, 2, …, n）我們改變i的整數(shù)倍號(hào)鎖的狀態(tài)：如果門(mén)是關(guān)的，就打開(kāi)它；如果門(mén)是打開(kāi)的，就關(guān)上它。在最后一次經(jīng)過(guò)后，哪些門(mén)是打開(kāi)的，哪些門(mén)是關(guān)上的？有多少打開(kāi)的門(mén)？