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

哈佛程式設計基礎講座 CS50 附加資料：漸近符號、排序和搜尋演算法 第 3 週作業，第 1 部分。排序和搜尋。

比賽開始了！

玩的時間到了！大多數人都熟悉益智遊戲「Tag」。形式化地說，「Tag」是一個二維的4x4字段，這個字段中不是16個，而是15個方格，即有一個槽位是空的。每個方塊都有編號，並且可以在區域內水平或垂直移動（當然，如果有移動空間）。目標是將數字按從左到右、從上到下的順序排列，從 1 到 15。然後空白區域將位於右下角。任何一塊（或幾塊）的移動都是這個遊戲空間中的一個「步驟」。上圖所示的組合已經堆疊完畢，但請注意，可以將 12 或 15 塊瓷磚推入空位。規則規定，棋子不能對角移動或從遊戲板上移除。開始遊戲的配置其實很多（具體有多少你可以數一下），但為了簡單起見，我們將圖塊按照從大到小的順序排列，並在棋盤右下角留出一個空白區域。唯一的問題是，讓我們交換 1 和 2，這樣謎題就可以解決了。 現在轉到工作台的~/目錄，然後轉到/pset3/fifteen並開啟Fifth.c。它包含遊戲引擎的程式碼。任務是向遊戲添加程式碼。但首先，讓我們編譯我們的“引擎”（您可能已經知道如何做到這一點）。儘管遊戲尚未完成，您仍然可以啟動該應用程式。在比平常更大的終端視窗中運行它會更方便，可以透過點擊代碼選項卡之一旁邊的綠色加號 (+) 並選擇New Terminal來開啟該視窗。或者，您可以透過點擊控制台右上角的最大化圖示以全螢幕方式開啟終端機視窗。你會發現有些事情以某種方式起作用。但事實上，遊戲的大部分內容還沒寫完。這裡－準備好－就是你的出口！

學習

研究十五.c的 程式碼和註釋，然後回答以下問題：

1. 除了 4x4 棋盤外，我們的引擎還允許多大的場地大小？
2. 遊戲領域是什麼資料結構？
3. 在遊戲開始時呼叫什麼函數來迎接玩家？
4. 您需要實現哪些功能？
5. 注意：如果您希望自動檢查告訴您是否正確回答了問題，請在文件十五.c 旁邊找到文件十五.txt 並在其中寫下這些問題的答案。

執行

好吧，讓我們開始實現遊戲。請記住，我們正在一步步前進，不要試圖一次完成所有事情。相反，讓我們一次實現一個功能，並確保它們可以正常工作，然後再繼續。特別是，我們建議您按照以下順序實現遊戲函數：init（初始化）、draw（繪圖）、move（邁出一步）、won（獲勝）。設計決策（例如在數位圖塊之間插入多少空間）由您決定。比賽場地應該看起來像這樣： 15 14 13 12 11 10 9 8 7 6 5 4 3 1 2 _ 再次請注意，在起始位置，1 和 2 的位置相反（如果圖塊數量為奇數，這適用於經典的 4x4 場地）。若牌數為偶數且場地為 3x3，則無需交換兩張「最低」牌。 8 7 6 5 4 3 2 1 _ 要測試「Tag」的實現，您需要嘗試播放它們（不要忘記，您可以透過按組合鍵 crtl+c 在程式自然完成之前退出程式）。確保如果輸入的數字不正確，程式仍能正常運作。請記住，就像您自動化輸入 find 一樣，您也可以自動化遊戲的「演練」。事實上，在~cs50/pset3資料夾中有檔案3x3.txt和4x4.txt，其中包含在 3x3 和 4x4 場地獲勝的所有步驟序列。例如，要測試程序，請使用第一個文件，執行以下命令： ./fifteen 3 < ~cs50/pset3/3x3.txt 設定加速動畫所需的參數。一般來說，如果你願意，你可以隨時改變遊戲規則。享受包括顏色在內的“ANSI 轉義序列”的樂趣。看看我們的clear實作並查看http://isthe.com/chongo/tech/comp/ansi_escapes.html以學習新技巧。如果您願意，可以編寫自己的函數或更改我們編寫的函數的原型。唯一的限制是你不要改變main函數的邏輯，否則我們將無法對其應用一些自動測試來確認你的程式正常運作。特別是，當且僅當使用者解決了難題時，main 必須返回 0。所有錯誤選項都必須傳回非零值。如果出現任何錯誤，請寫信給我們。好吧，如果您想體驗 CS50 助手準備的應用程式的實現，請執行以下命令： ~cs50/pset3/fifteen 如果您有興趣查看更酷的實現（具有自動解謎功能），請查看該程式的「Hacker」版本： ~cs50/hacker3/fifteen 不要在遊戲視窗中輸入數字，而是輸入「GOD」一詞。太棒了，不是嗎？如果你想用 check50 正式檢查你的程式的正確性，請注意 check50 假設遊戲場的空白區域被 0 填滿；如果您選擇了不同的值，請將其替換為零以進行正確驗證。另外，check50 假定您按照 [行] [列] 的順序對板字段進行索引，而不是板 [列] [行]。 check50 2015.fall.pset3.fifteen fifteen.c

了解十五個遊戲功能的實現

• 初始化（初始化）
• 畫
• 移動（邁出一步）
• 贏得（獲勝）

在裡面

在此功能中，我們介紹了比賽場地。為此，我們使用二維整數數組。陣列維度為 MAX x MAX，其中 MAX 是常數，指示欄位的行或列中可容納的最大圖塊數。因此，我們需要定義變數int board[MAX][MAX] 但是，請記住，遊戲區域的大小是由使用者決定的。因此，我們需要定義一個變數來指示使用者必須輸入的板尺寸。這是int d。其中 d 為電路板尺寸，d <= MAX。但是，在 C 中，您無法變更陣列的大小，因此您必須滿足最大大小。在init中你需要將數值放在板上。 如果您還沒有使用過二維數組，請閱讀有關二維數組的更多資訊。簡而言之，它們有兩個索引，第一個表示行號，第二個表示列號。對於我們的問題，我們從最大數開始，並以 d = 3（“八”）的情況結束，其中有一個角和一個空角。如果我們還有“Tag”，那麼我們交換1和2。空出的空間該怎麼辦？我們的陣列由整數組成，因此必須用一些整數填滿空白。因此，您必須選擇一些整數來初始化空圖塊（或者，在實體遊戲的情況下，沒有圖塊）。循環可用於初始化遊戲板並用一組起始圖塊填充它。我們循環索引 i 和 j，其中board[i][j]是位於第 i 行和第 j 列的圖塊。我們按降序排列面板。如果圖塊數量（沒有空的）是奇數，則交換 1 和 2。

畫

此函數應列印運動場的當前狀態。請記住，我們可以使用一位或兩位數字的值，因此為了在數字 1-9 之後實現美觀的格式，函數應該列印一個空格 ( #s )。這可以使用%2d佔位符來完成。 printf (“%2d”, board[i][j]); 另外不要忘記空白單元格。選擇代表它的字元（在我們的範例中，這是一個下劃線）。當您點擊空白單元格時，繪製函數應該立即繪製該字元。所以我們的循環將是這樣的： 請記住，draw 函數將圖塊繪製到螢幕的順序應該反映它們在initfor каждой строки for каждого element строки print meaning и пробел print новую строку 函數中定義的陣列中的順序。

移動

一旦初始化了比賽場地並繪製了初始圖塊位置，您需要允許使用者編輯圖塊的位置，即進行移動。因此，在Fifteen.c中，程式取得使用者的輸出，建立遊戲板，然後呼叫 move 函數並告訴它他想要移動哪個圖塊。請注意：您將該函數專門應用於圖塊上的數字，而不是其在棋盤上的位置（在數組中）。所以你需要找到瓷磚的實際位置。此外，您應該只允許使用者在可能的情況下移動圖塊。 上圖中，我們只能移動2號、5號和8號的圖塊。如何確定這一點？按空瓷磚的價值。所以move函數的工作原理如下：

• 接受使用者想要移動的圖塊編號
• 尋找該圖塊在陣列中（在比賽場地上）的位置
• 記住空圖塊的位置
• 如果一個空圖塊與使用者想要移動的圖塊相鄰，則它們會在陣列中交換。

韓元

此函數在每個使用者步驟後檢查遊戲是否結束。如果圖塊順序正確（包括右下角空圖塊的位置），則傳回 true。在這種情況下，可以終止程序。如果磁磚仍然分散，則函數傳回 false 並將控制權傳遞給move函數。如何組織檢查？與初始化和繪製棋盤的情況一樣 - 使用兩個巢狀的 for 迴圈。例如，您可以設定一個條件，即數組中的每個後續數字都必須大於前一個數字。請注意空圖塊中寫入的值。或另一種方式 - 使用計數器來確保所有磁磚都就位，如果您可以處理它並編寫公式來獲得它。我們祝您實驗順利！

如何驗證您的代碼並獲得分數

注意力！如果您只需要檢查任務的正確性，那麼請使用 cs50check。如果您想在 edx 平台上取得成績，請依照以下步驟操作。請記住，此過程使用相同的 cs50check 來檢查任務。唯一的區別是它會記住結果併計算總分。

1. 登入CS50 IDE
2. 在CS50 IDE 的左上角（其檔案瀏覽器所在位置）附近（不在終端機視窗中），以滑鼠右鍵按一下 pset3 目錄，然後按一下「下載」。您應該會看到瀏覽器已下載pset3.tar.gz存檔。
3. 在單獨的視窗或標籤中，登入CS50 提交
4. 點擊螢幕左上角的“提交”圖標
5. 在左側的資料夾清單中，按一下Problem Set 3目錄，然後按一下 Upload New Submission 按鈕。這是在右邊。
6. 在出現的畫面上，按一下「新增檔案...」按鈕。將開啟一個用於從電腦中選擇檔案的視窗。
7. 導航到保存 pset3.tar.gz 的資料夾。它很可能位於您的下載資料夾中或瀏覽器預設放置檔案的位置。當您找到pset3.tar.gz時，按一下一次將其選中，然後按一下「開啟」。
8. 點擊開始上傳。您的檔案將上傳到CS50伺服器。
9. 在出現的畫面上，您應該會看到「未選擇檔案」視窗。如果將滑鼠遊標向左移動，您將看到下載檔案的清單。若要確認，請按一下每個選項。如果您不確定某些事情，可以透過重複相同的步驟來重新上傳檔案。在 2016 年底之前，您可以多次執行此操作。