習題1.1

1．研究一下al-Khorezmi（或者稱為al-Khwarizmi，譯名為阿爾·花剌子模），“算法”（algorithm）一詞起源于這個人的名字。研究過程中我們還會發現，“算法”一詞的起源和“代數”（algebra）一詞的起源是相同的。

2．如果告訴你，設立美國專利體系的基本目的是促進“有用的技術”，那么你認為算法在這個國家能夠申請到專利嗎？算法是否應該允許申請專利呢？

3．a．按照算法要求的精確性寫出你從學校到家里的駕駛指南。

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

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

6．a．用歐幾里得算法求gcd（31415, 14142）。

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

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

8．對于第一個數小于第二個數的一對數字，歐幾里得算法將會如何處理？該算法在處理這種輸入的過程中，上述情況最多會發生幾次？

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

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

10．a．在歐幾里得的書里，歐幾里得算法用的不是整數除法，而是減法。請用偽代碼描述這個版本的歐幾里得算法。

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

a．在參考資料中查閱擴展歐幾里得算法的描述（參見[KnuI]），然后任選一種語言實現它。

b．改寫上述程序以對丟番圖方程ax+by=c求解，系數a，b，c為任意整數。

12．帶鎖的門　在走廊上有n個帶鎖的門，從1到n依次編號。最初所有的門都是關著的。我們從門前經過n次，每一次都從1號門開始。在第i次經過時（i=1, 2, …, n）我們改變i的整數倍號鎖的狀態：如果門是關的，就打開它；如果門是打開的，就關上它。在最后一次經過后，哪些門是打開的，哪些門是關上的？有多少打開的門？