個人做的課后練習

書籍：算法設計與分析基礎(第三版）

習題2.2

二. a.正確 b.正確 c.錯誤 d.錯誤

三. a.n的20次方 b.n c.n的平方 log2（n） d.3的n次方 e. log2（n）

四. log(n) < n < n*log(n) < n的平方 < n的三次方 < 2的n次方 < n!

九. a.線性對數 b.線性

十. a.n b.1 c.n d.log（n）

十一. 因為我們不知道到底假幣是比真幣輕了還是重了。所以我們在此，把所有的硬幣平均分成了三組。然后，我們再分別討論可能出現的各種情況。假設總的硬幣數目是n。 1. n = 3*k 剛好是三的整數倍，我們可以把硬幣分成3堆，每一堆k個。然后我們只需稱兩次，就可以確定到底有假幣到底是輕了還是重要。（分三堆，主要是為了構造成兩個正確的樣本和一個不正確的樣本，從而確定不正確樣本到底是輕了還是重了） 2. n = 3*k + 1或2 我們可以把硬幣分成4堆，前三堆的每堆有k個，最后一堆只有1或2個。然后按照1.中的方法進行操作。如果發現兩次的稱量都是相等的話。我們就可以確認有問題的硬幣在最后一堆那里，然后我們只需要從沒有問題的前三堆硬幣那里，取出與第四堆等價的硬幣，然后再稱量一次，就可以確認假幣到底是輕了還是重了。

十二. 墻上的門 假設我們一開始所處的位置為0，而向左取正，向右取負。 1.假設我們只往一個方向走，顯然，如果門在另一個方向我們就永遠無法遇到門。 2.所以我們可以要不停的往返走，這樣我們才能遇到門。 如果我們采取的策略是： 0 1 -1 2 -2 3 -3 4 -4 … 我們可以列出移動步數的數列： 0 1 2 3 4 5 6 7 8 … 移動步數的和為：S（n）=(2n-1)*n；S（-n）=(2n+1)*n 所以這些都是 O（n*n）的算法。

如果我們嘗試采取走多一點再折返： 0 1 -2 3 -4 5 -6 7 -8 9 -10… 我們可以寫出移動的步數的數列： 0 1 3 5 7 9 11 13 15 17 19… 移動步數的和為：S（n）=n*n 所以一樣也是O（n*n）的算法。

如果我們選擇一下類似的策略： 0 k -k*k k*k*k -k*k*k*k … 最終我們得出的求和公式大概就為：S（n）=n*n/k 因為，n的值可以取無限大，所以算法依然是屬于O（n*n）類型的。

顯然我們要跳出乘法的思維限制。 如果我們選擇每逢 2的n次方 往反方向行走。 0 2 -4 8 -16 32 -64 128… 我們可以得到移動步數的數列： 0 2 6 12 24 48 96 192… 移動步數的和為：S（n）=3*n-4 所以，滿足O（n）

再進一步思考一下，假設我們每逢 k的n次方 就往反方向行走。 我們得到移動步數和的式子為：S（n）=((2+k)n-n-2k)/(k-1)

但是，我們還有沒有更加穩當的策略呢？ 我個人想了想，我覺得還是有的，如果我們選擇 每逢n！ 就往反方向走。至于求和公式，暫時以我的能力我算不出來。但是我感覺當n趨向無窮的時候，這種方法的效率顯然要比以上的幾種做法都要高。