習題1.1
習題1.1
1．研究一下al-Khorezmi（或者稱為al-Khwarizmi，譯名為阿爾·花剌子模），“算法”（algorithm）一詞起源于這個人的名字。研究過程中我們還會發(fā)現(xiàn)，“算法”一詞的起源和“代數(shù)”（algebra）一詞的起源是相同的。
2．如果告訴你，設(shè)立美國專利體系的基本目的是促進“有用的技術(shù)”，那么你認為算法在這個國家能夠申請到專利嗎？算法是否應該允許申請專利呢？
3．a(chǎn)．按照算法要求的精確性寫出你從學校到家里的駕駛指南。
b．按照算法要求的精確性寫出你最喜歡的菜的烹飪方法。
4．設(shè)計一個計算5．設(shè)計一個算法，在已經(jīng)排序的兩個列表中，找出所有相同的元素。例如，列表2, 5,5, 5和2, 2, 3, 5, 5, 7，應該輸出2, 5, 5。如果給定的兩個列表的長度分別為m和n，你設(shè)計的算法的最大比較次數(shù)是多少？
6．a(chǎn)．用歐幾里得算法求gcd（31415, 14142）。
b．用歐幾里得算法求gcd（31415, 14142），速度是檢查min{m, n}和gcd（m, n）間連續(xù)整數(shù)的算法的多少倍？請估算一下。
7．證明等式gcd（m, n）=gcd（n, m mod n）對每一對正整數(shù)（m, n）都成立。
8．對于第一個數(shù)小于第二個數(shù)的一對數(shù)字，歐幾里得算法將會如何處理？該算法在處理這種輸入的過程中，上述情況最多會發(fā)生幾次？
9．a(chǎn)．對于所有m≥1，n≤10的輸入，歐幾里得算法最少要做幾次除法？
b．對于所有m≥1，n≤10的輸入，歐幾里得算法最多要做幾次除法？
10．a(chǎn)．在歐幾里得的書里，歐幾里得算法用的不是整數(shù)除法，而是減法。請用偽代碼描述這個版本的歐幾里得算法。
11．擴展歐幾里得算法 不僅能夠求出兩個正整數(shù)m和n的最大公約數(shù)d，還能求出兩個整數(shù)x和y（不一定為正），使得mx+ny=d。
a．在參考資料中查閱擴展歐幾里得算法的描述（參見[KnuI]），然后任選一種語言實現(xiàn)它。
b．改寫上述程序以對丟番圖方程ax+by=c求解，系數(shù)a，b，c為任意整數(shù)。
12．帶鎖的門 在走廊上有n個帶鎖的門，從1到n依次編號。最初所有的門都是關(guān)著的。我們從門前經(jīng)過n次，每一次都從1號門開始。在第i次經(jīng)過時（i=1, 2, …, n）我們改變i的整數(shù)倍號鎖的狀態(tài)：如果門是關(guān)的，就打開它；如果門是打開的，就關(guān)上它。在最后一次經(jīng)過后，哪些門是打開的，哪些門是關(guān)上的？有多少打開的門？