哈佛 CS50：第 3 週作業（第 7 講和第 8 講），第 1 部分

哈佛 CS50 程式設計基礎課程講座 附加資料：漸近符號、排序和搜尋演算法 第二部分。C語言中的“標籤”

準備

在做題之前，先觀看第7-8講，閱讀並深入研究「第三週的補充資料」。他們致力於搜尋演算法（線性和二進制）、排序（有很多！）以及調試器的工作（使用調試器調試程序的能力是一項極其重要的技能！）。如果講座和理論一切順利，您可以輕鬆回答測驗問題：

• 為什麼二分查找需要排序數組？
• 為什麼冒泡排序估計是O(n2)？
• 為什麼插入排序估計是Ω(n)？
• 選擇排序如何運作？用三句話（或更少）描述。
• 合併排序可以運行多久的上限（最壞情況）是多少？
• GDB 偵錯器可讓您偵錯程式。如果你更具體地闡述，它到底能讓你做什麼？

目標

• 了解如何處理包含多個文件的項目
• 學會閱讀別人的原始碼
• 了解各種演算法和遞歸函數

大多數這些目標實際上不可能進行正式評估。因此，從形式化驗證問題的角度來看，沒有什麼會讓你覺得困難的。不過，我們提醒您：只有不斷練習才能學會程式設計！因此，我們鼓勵您不僅要解決任務，還要花費額外的時間和精力來實現本週討論的所有演算法。向前！

開始

回想一下，對於第一週和第二週的練習題，您從頭開始編寫程式並使用mkdir指令建立了自己的pset1和pset2目錄。對於第三週的練習作業，您需要下載我們編寫的發行版（或我們所謂的「發行版」）並向其中新增您自己的程式碼行。首先，閱讀我們的程式碼並嘗試理解它。本週最重要的技能是學習如何閱讀別人的程式碼。因此，登入 cs50.io 並 在終端機視窗中執行命令以確保工作區版本是最新的。如果您不小心關閉了終端視窗並且找不到它，請轉到“檢視”功能表並確保選中“控制台”選項（如果沒有選中，請選中）。點選 (+)，在終端視窗框架上的綠色圓圈內，選擇New Terminal。 之後，執行命令 並確保您位於工作區目錄中（這是您的目錄）。之後，執行指令： 將問題書的 ZIP 檔案下載到您的工作空間（wget 是 Linux 下載指令）。如果一切正常，您將在行中看到以下短語： 確保您確實透過執行命令 下載了pset3.zip ： 然後運行 以解壓縮該檔案。如果現在再次執行ls指令，您也會看到pset3目錄。透過執行命令轉到它 ，然後再次請求查看該目錄的內容： 您將看到該目錄中有兩個子目錄： 已經很有趣了！ update50cd ~/workspacewget http://cdn.cs50.net/2015/fall/psets/3/pset3/pset3.zip'pset3.zip' savedlsunzip pset3.zipcd pset3lsfifteen find

搜尋

現在讓我們深入研究這些子目錄之一。為此，我們將運行命令： cd ~/workspace/pset3/find 如果您在螢幕上顯示此資料夾的內容（您可能已經記得如何執行此操作），您應該看到以下內容： 哇，有 helpers.c helpers.h Makefile find.c generate.c 很多文件。不過別擔心，我們現在就來對付他們。檔案generate.c包含一個程式的程式碼，該程式使用「偽隨機數產生器」（由drand48函數產生）來產生大量隨機（實際上是偽隨機，電腦無法處理純隨機性！）數字，並一次將它們放在一行中。編譯程式： make generate 現在透過執行命令來運行它： ./generate 程式將給您以下訊息： Usage: generate n [s] 這意味著程式需要一個或兩個命令列參數。使用第一個， n, 是必填項；這個數字表示要創建多少個偽隨機數。參數s 是可選的，如方括號所示。數字s 可以稱為偽隨機數產生器的「種子」。透過「種子」我們指的是影響其輸出的偽隨機數產生器的輸入資料。例如，如果您使用drand48，首先透過呼叫srand48（另一個函數，其目的是「播種」drand48），參數為1，然後然後呼叫drand48 三次，drand48 可能會傳回2728，然後是29785，然後是54710。如果您使用drand48 而不是前一個，首先使用參數（例如2）呼叫srand48，然後再次使用drand48 三次，drand48 可能會返回返回59797，然後是10425，然後是37569。但是，如果您透過再次呼叫srand48（參數為1）來重新看到drand48，則接下來三次呼叫drand48 的結果將再次獲得2728，然後是29785，然後是54710！你看，一切的發生都是有原因的。再次運行程序，這次假設n=10，如下所示；您將看到包含 10 個偽隨機數的清單。 ./generate 10 讓我們使用相同的 n 值第三次運行該程式；您應該會看到另一個包含 10 個數字的清單。現在嘗試使用兩個參數來執行該程式。讓我們取 s=0 如下所示。 ./generate 10 0 現在再次運行相同的命令： ./generate 10 0 您甚至無法爭論：您再次看到了相同的十位數字的「隨機」序列。如果您不更改偽隨機數產生器種子，就會發生這種情況。現在讓我們來看看generate.c程式本身（還記得怎麼做嗎？）。該文件開頭的註釋解釋了該程式的一般功能。但我們似乎忘記了對程式碼本身進行評論。仔細閱讀程式碼，不斷地閱讀，直到理解每一行的含義。然後為我們註解掉這段程式碼，用描述對應一行或多行程式碼的目的或功能的片語取代每個 TODO。（注意：unsigned int 是「無符號」int，這表示它不能為負數）。要獲取有關 rand 或 srand 的更多信息 ，請 運行man drand48 ： 提醒一下，make命令會自動編譯程式碼，因此您不必透過手動插入一堆開關來執行 clang 命令。但事實上，make只是簡化了我們的輸入，但實際上，它的背後隱藏著與我們需要的參數相同的clang。然而，隨著程式變得越來越大，make 無法再從上下文中找出如何編譯程式碼。在這種情況下，您必須告訴 make 如何編譯程序，特別是當它們涉及使用不同的原始檔（例如 .c）時。為了解決這個問題，我們將使用設定檔（Makefile）來告訴 make 到底要做什麼。make 指令怎麼知道我們該如何編譯生成？事實上，團隊使用了我們已經編寫的設定檔。該檔案稱為Makefile ，與generate.c位於同一目錄中。Makefile 是指定如何從generate.c 建立檔案generate 的規則清單。在該檔案中，您將特別發現相關行： 第一行告訴 make 應透過呼叫第二行的命令來建立名為「generate」的「目標」。此外，第一行告訴make，generate依賴generate.c，這表示如果檔案已更改，make只會在後續運行中重建generate。這是一個不錯的節省時間的技巧，對吧？事實上，如果您沒有更改generate.c ，請再次執行以下命令。 您將收到通知，generate 已更新至目前版本。 注意：第二行開頭的縮排不是空格序列，而是製表符。不幸的是，make 要求命令前面有製表符，所以要小心不要將它們更改為空格，否則你會遇到奇怪的錯誤！-Werror標誌告訴clang命令man srand48make generategenerate: generate.c clang -ggdb3 -O0 -std=c11 -Wall -Werror -o generate generate.cmake generate將警告（不好的）視為錯誤（甚至更糟），因此您將被迫（以良好的、有教育意義的方式！）糾正它們。現在讓我們看看find.c檔。請注意，程式需要一個命令列參數：“igloo”，它必須在值的“乾草堆”中找到。之後，檢查程式碼並透過執行以下命令編譯程式。 make find make 基本上給了我們以下資訊： clang -ggdb3 -O0 -std=c11 -Wall -Werror -o find find.c helpers.c -lcs50 -lm 注意！您剛剛編譯了一個由一個但兩個檔案組成的應用程式：helpers.c和find.c。是怎麼知道這件事的？要了解這一點，請再次打開 Makefile 以查看其中到底發生了什麼。相關行如下。 find: find.c helpers.c helpers.h clang -ggdb3 -O0 -std=c11 -Wall -Werror -o find find.c helpers.c -lcs50 -lm 我們所說的依賴（冒號後面）的意思是，對find.c、helpers.c或helpers.h的任何更改都將強制 make 在下次出於這些目的調用時重建 find 。現在，透過執行以下操作來執行程式： ./find 13 此後，系統會要求您提供一定的堆疊（即整數），並一次給它們餵食一根吸管。一旦厭倦了輸入數字，請按組合鍵Ctrl-D。此組合將向程式發送一個文件結束（EOF）字元。此符號將強制 CS50 函式庫中的GetInt函數傳回常數INT_MAX，而這反過來在find.c中將強制 find 停止鍵入「stack」。該程式現在將在您提供的大海撈針中尋找針，並最終告訴您是否找到了它。簡而言之，程式在數組中搜尋某些值。至少她應該要找到，但問題是她還找不到什麼！但你來救援了！稍後我們將討論您角色的重要性。事實上，提供乾草堆的過程可以自動化，至少可以透過將generate 的輸出「合併」到find 作為輸入。例如，下面的命令傳遞 1000 個偽隨機數進行查找，然後在這些值中搜尋 42。請注意 ./generate 1000 | ./find 42 ，當generate 傳遞原始資料進行查找時，您不會看到產生數字，但會看到 find 正在運行。或者，您可以使用以下命令將generate的輸出「重定向」到一個檔案：該檔案 ./generate 1000 > numbers.txt 的內容可以使用以下命令重定向到find的輸入： ./find 42 < numbers.txt 讓我們再看一下Makefile中的程式碼，並注意以下行： all: find generate 這意味著您可以透過執行以下命令來建立生成和查找： make all 此外，該行下面的命令與其上面的命令等效，因為 make 預設情況下建立 Makefile 中的第一個條目。 make 如果您能將所有這些練習任務歸結為一個命令就好了！可惜！最後，請注意 Makefile 中的最後幾行： clean: rm -f *.o a.out core find generate 此條目允許您刪除所有以 .o 結尾或稱為 core 的文件（我們稍後會解釋這一點！），並且還可以簡單地運行查找或生成程序通過執行以下行： 如果您想進行 make clean 實驗，那麼需要注意以下幾點：不要將*.c加入 Makefile 的最後一行！（為什麼？）所有以 # 符號開頭的行都只是註解。

任務 1：搜尋

是時候做一些有趣的事情了！請注意，find.c呼叫search ，這是在helpers.h中宣告的函數。不幸的是，我們忘記在helpers.c中完全實作這個函數！（需要注意的是，我們可以將helpers.h和helpers.c的內容放入一個find.c中。但有時最好將程式分成幾個檔案。特別是如果某些函數（或更確切地說是實用函數）可能有用對於其他程式。例如CS50庫函數。看一下helpers.c，你會發現無論給定值是否在values中，search總是返回false。重寫search，使其使用線性搜索，返回true ，如果值在值中，如果值不在值中則傳回false。如果n 不是正數，請注意立即傳回false。當您準備好檢查有效性時，請嘗試呼叫以下命令：由於列印的數字之一 ./generate 1000 50 | ./find 127 當50 播種時，generate 是127，您的程式碼應該找到針！作為對比，請嘗試以下命令：由於128 不在 50 被播種時由generate 產生的數字集中，因此您的程式碼不必找到「 ./generate 1000 50 | ./find 128 針」 。透過使用一些種子運行生成、分析輸出並尋找大海撈針來運行其他測試。注意find.c中main的寫法是如果找到「針」則find回傳0，否則回傳1。你可以檢查main在執行其他一些程式後執行時傳回的所謂「輸出碼」指令 echo $? 。例如，如果您的搜尋實作是正確的，如果您運行， ./generate 1000 50 | ./find 127 echo $? 您將看到 0，而 127 是使用種子 50 產生的 1000 個數字之一，因此您編寫的搜尋應該會傳回 true。在這種情況下，main（我們寫的）應該會回傳0（即退出）。如果您給出以下輸入 ./generate 1000 50 | ./find 128 echo $? ，您將看到1，因為128 不屬於生成種子為50 時輸出的1000 個數字。在這種情況下，search（由您編寫）將返回false，而main（由我們編寫）將返回false ) 將返回 1 （然後完成工作）。你明白其中的邏輯嗎？當一切準備好使用 check50 檢查時，請執行以下命令： check50 2015.fall.pset3.find helpers.c 順便說一下，在自己測試程式碼之前，您不應該習慣使用 check50 來測試程式碼。畢竟，check50 並不真正存在，因此使用您自己的輸入樣本運行程式碼，將實際輸出與預期輸出進行比較，是您此時可以養成的最佳習慣。這是真的，別上癮！如果您有興趣使用 cs50 助手的 find 實現，請執行以下命令： ~cs50/pset3/find

排序

線性搜尋並不是真正令人印象深刻的東西，但是從第一堂課開始（在第七堂課中我們再次重複了這個技巧！）你會記得你可以更快地大海撈針。但首先我們需要先對乾草堆進行排序。請注意，find.c呼叫sort ，這是在helpers.h中宣告的函數。不幸的是，我們「忘記」在helpers.c中完全實現這個功能！查看 helpers.c，您會發現 sort 立即返回，即使 find 的 main 函數實際上將實際數組傳遞給它。現在記住數組聲明語法。您不僅可以指定該陣列的元素類型，還可以在方括號中指定其大小。這就是我們在find.c中對 haystack 所做的事情： int haystack [MAX]; 但是在遍歷數組時，您只需指定它的名稱。當我們透過 haystack 在find.c中進行排序時，我們的做法完全相同：（ sort (haystack, size); 猜猜為什麼我們單獨傳遞該數組的大小？）當我們聲明一個採用一維數組作為參數的函數時，我們不需要指定數組的大小。同樣，當我們在 helpers.h（和 helpers.c）中聲明 sort 時，我們也沒有這樣做： void sort (int values [] int n); 實現 sort 以便該函數實際上對數字數組從小到大進行排序。它需要的運行時間等於 O(n ² )，其中 n 是數組的大小。正如我們在第三週所了解的那樣，您可能想要實現冒泡排序、選擇排序或插入排序。然而，值得注意的是：沒有「正確」的方法來實作這些演算法。有大量的變體。事實上，只要您的實作收斂於 O(n2 ⁾ ，您就可以隨時改進它們（如果您認為合適） 。但是，將實驗留給函數體，並且為了簡化測試，不要更改我們的排序聲明。它應該如下所示： void sort (int values [] int n); 由於函數傳回一個 void 值，因此它不應該傳回排序數組。相反，它必須「破壞性地」對其「運行」的實際數組進行排序，移動其元素。第四周我們將討論數組是透過引用而不是值傳遞的。也就是說，sort 不會接收陣列的副本，而是接收原始陣列本身。雖然您無法變更我們的排序聲明，但您始終可以在 helpers.c 中定義自己的函數，然後可以從 sort 呼叫該函數。自己決定如何最好地測試排序實作。不要忘記 printf 和 GDB 會幫助你！並且不要忘記，您可以透過明確指定生成的種子值來一遍又一遍地創建相同的偽隨機數序列。

二分查找，提示

關於find函數 ，您首先需要了解的是我們已經編寫了程式碼（分發）。我們只是填補現有程式碼中的一些空白。find.c程式要求輸入數字（即填充「堆疊」），然後根據使用者的請求，使用 helpers.c 中定義的排序和搜尋函數在其中搜尋「針」。所以，find已經寫好了，我們要寫helpers。所以這就是我們需要做的：

1. 實施搜尋。如果在堆疊中找到該值，則函數應傳回 true；如果不存在，則傳回 false。
2. 實作 sort，一個對值數組進行排序的函數。

最初，搜尋是線性實現的。但你可以做得更好。線性搜尋演算法的運行時間為O(n)。你的任務是寫一個二分搜尋演算法。其執行時間為O(log n)。然而，它的問題是它需要排序的資料作為輸入，否則它將無法運作。你還記得被撕破的書的例子，你可能知道為什麼會這樣。如果您對元素進行了二分查找，並且沒有剩下任何元素（也就是說，這個「堆疊」中根本沒有「針」），則需要該函數傳回 false。二分搜尋可以迭代或遞歸地實現（David Malan 在第八講中談到了遞歸）。