哈佛 CS50：第 2 週作業（第 5 講和第 6 講）

CS50 講座在這裡：https://cdn.javarush.com/images/article/155cea79-acfd-4968-9361-ad585e939b82/original.pngcs50.html。本資料包含 3 項任務、有關它們的理論資訊和行動指南。

目標

• 深入了解函數與函式庫 • 熟悉密碼學，實作一些簡單的密碼

附加材料

https://reference.cs50.net/ - 訓練期間使用的函式庫函數的解釋。用英語。 http://computer.howstuffworks.com/c.htm第 11 – 14 及 39 頁

準備

登入 cs50.io update50 以確保您的工作區版本是最新的。如果您不小心關閉了終端窗口，請轉到“視圖”功能表並確保“控制台”項目旁邊有一個複選標記（如果沒有，請選中它）。 點選 (+)，在終端視窗框架上的綠色圓圈內，選擇New Terminal。 建立工作目錄： 請注意mkdir和~/workspace/pset2mkdir ~/workspace/pset2 之間有一個空格。回顧一下，~表示根目錄，~/workspace是根目錄中名為工作空間的資料夾，~/workspace/pset2是~/workspace中名為pset2的目錄。現在運行： 更改到新目錄。命令列看起來像這樣： 如果有任何問題，請重複這些步驟。您也可以呼叫命令 來按時間順序查看最後幾條命令。您也可以將遊標放在命令列上，然後按鍵盤上的向上箭頭，按從最後輸入到第一個輸入的順序查看所有命令。使用向下按鈕可以返回。順便說一句，您可以捲動已輸入的命令，然後按 Enter 鍵再次執行它們，而不是每次都輸入相同的命令。您可能已經注意到，大衛在他的講座中正是這樣做的。第二週的任務應保存在pset2中。 cd ~/workspace/pset2username:~/workspace/pset2 $history

任務 0. 初始化

讓我們仔細看看這些線條。在initials.c檔案中，編寫一個程序，請求使用者的姓名（使用GetString函數我們以字串形式取得姓名），然後以大寫形式顯示名字（或多個名字）和姓氏的首字母，不帶空格，句點或其他字符，僅帶有換行符 ( \n )。我們假設使用者僅輸入字母（小寫或大寫，或兩者）以及單字之間的一個空格。考慮一下約瑟夫·戈登-萊維特、柯南·奧布萊恩或大衛·J·馬蘭等人不會使用該程式。 要檢查程式是否正確運行，請呼叫check50： 您想玩CS50工作人員編寫的程式的執行情況嗎？輸入以下行： username:~/workspace/pset2 $ ./initials Zamyla Chan ZC username:~/workspace/pset2 $ ./initials robert thomas bowden RTBcheck50 2015.fall.pset2.initials initials.c~cs50/pset2/initials

密碼學

密碼學，加密和破解訊息的科學……事實上，加密訊息自古以來就存在，並被軍隊用來傳遞秘密訊息。好吧，現在您在 Facebook 和其他網路上的密碼都以加密形式儲存。

任務1.凱撒萬歲！

理論資訊

我們將研究最簡單的密碼之一 - 凱撒密碼，以羅馬皇帝的名字命名。在此密碼中，文字中的每個字母都被另一個字母替換，該字母是字母表中固定數量的較低字母。這個固定數量的字母稱為密鑰。因此，密鑰 1 將拉丁字母 C 轉換為字母 D，將 Z 透過循環轉換為 A。如果密鑰是 3，則字母 C 將轉換為 F，Z 將轉換為 C。例如：我們使用 凱撒密碼鍵5在貓這個字上。 c -> h a -> f t -> y Caesar (cat, 5) = hfy 金鑰 = 7，單字 = 電腦 c->j o->v m->t p->w u->b t->a e->l r->y Caesar(computer,7) = jvtwbaly 凱撒密碼很簡單，但是，唉，不可靠（這些是相互關聯的東西！）：對於英文字母表來說，只有25 個加密選項，即使沒有電腦也很容易完成所有選項。然而，凱撒密碼經常被用作其他密碼的一個步驟，例如維吉尼亞密碼（下一段將詳細介紹）。讓我們對凱撒密碼進行「數學化」。讓我們用字母 p 來表示明文，pi 是文字 p 中位置編號為 i 的字母。我們將金鑰字母稱為 k，將 c 稱為密文，將 ci 稱為密文中位於 i 位置的字母。然後您可以使用以下公式計算密碼的每個字母： ci = (pi + k) % 26 習慣這種形式化，它允許您對演算法進行編程並準確而簡潔地表達密碼的含義。如果密鑰 k = 13 並且原始文字 p 是“一定要喝掉你的阿華田！”，這就是我們得到的密碼： 請注意 Or fher gb qevax lbhe Binygvar! ，O（密文中的第一個字母）從字母B（密文中的第一個字母）移動了13 個位置。原文的第一個字母）。同樣，字母 r（加密中的第二個字母）從 e（原始中的第二個字母）移動了 13 個字母。加密中的第三個字母 f 從 s（原始中的第三個）移動了 13 個字母，這裡我們從 z 到 a 轉了一圈。密鑰為 13 的凱撒密碼具有特殊名稱ROT13。它是對稱的：應用兩次，我們就回到原文了。當然，還有ROT26，這個通常是超級安全的，但前提是你沒有明確表達你的想法=）。

健康）狀況

在檔案caesar.c中寫一個使用凱撒密碼加密文字的程式。提供一個命令列參數作為程式的輸入：一個非負整數。為了簡單起見，我們稱之為 k。如果使用者在不使用命令列參數或使用多個參數的情況下執行程序，則應用程式應發出警告並傳回值 1（這通常是表示錯誤的方式）：在所有其他情況下，程式會提示使用者 return 1; 輸入文字加密，然後顯示以密鑰 k 加密的文字（即沿循環向右移動 k 個位置）。如果文字包含英文字母以外的字符，程式不會更改它們。列印密文後，應用程式退出，main返回 0： return 0; 如果main沒有明確返回 0，它會自動返回它（int 實際上是 main 的返回類型，但稍後會詳細介紹）。根據約定（程式設計中良好形式的規則），如果您明確傳回 1 來指示錯誤，那麼您也應該傳回 0 作為指向程式成功完成的指標。雖然英文字母表中只有 26 個字母，但 k 可以大於 26。本質上，鍵 k = 27 將給出與 k = 1 相同的結果，但您需要允許使用者輸入任何非負數，而不是超過2^31 – 26（它必須適合int）。程式還必須考慮到小寫字母按小寫加密，大寫字母按大寫加密。我們從哪裡開始？由於應用程式必須直接在參數字串中接受 k 的值，因此我們的主函數頭如下所示： int main(int argc, string argv[]) 從第 6 章中，您知道argv是一個字串數組。該陣列可以被認為是健身房中的一排儲物櫃。它們中的每一個都隱藏著一些意義。在我們的例子中，每個單元格內都有一個參數，例如 string 要打開第一個儲物櫃，我們使用 argv[0]，第二個 - argv[1]，依此類推。如果我們有 n 個鎖，那麼我們需要在 argv[n - 1] 處停止，因為 argv[n] 不再存在（或存在，但屬於別人，我們最好不要碰它）。所以你可以像這樣存取 k 參數： string k = argv[1]; 我們相信那裡確實有東西！回想一下，argc 是一個 int 變量，等於 argv 中的行數。這意味著最好在嘗試打開單元格之前檢查 argc 的值，因為可能會發現它不存在。理想情況下argc = 2。為什麼會這樣呢？argv[0]裡面通常是程式的名稱。也就是說，argc 總是至少為 1。但是我們的程式需要使用者提供一個命令列參數 k，因此，argc = 2。自然，如果使用者在命令列輸入多個參數，argc 也會成長且可以大於2如果使用者在字串中輸入整數，這並不意味著輸入的值將自動儲存為int。更準確地說，它不會。它將是一個字串，即使它看起來完全像一個 int！所以我們需要自己將string轉換為int。幸運的是，有一個名為 atoi 的函數就是為此目的而設計的。它的語法是： int k = atoi(argv[1]); 請注意，k 是 int 類型，因此您可以用它進行算術運算。使用此函數，您不必擔心使用者輸入的是整數還是 foo：在這種情況下，atoi 將返回 0。atoi 函數在 stdlib.h 庫中聲明，因此請務必 #將其包含在程式的開頭。程式碼將在沒有這個的情況下編譯，因為我們已經將此函數包含在cs50.h庫中。但是，最好信任本機庫。所以你把 k 儲存為 int 。現在讓我們請求文字輸入。如果您完成了第一週的作業，您已經熟悉了名為 GetString 的 CS50 函式庫函數。她會幫助我們。收到 k 和初始文字後，讓我們開始加密。回顧一下，您可以迭代字串的所有字元並使用以下循環列印它們： for (int i = 0, n = strlen(p); i < n; i++) { printf("%c", p[i]); } 換句話說，就像argv是一個字串陣列一樣，string也是一個字元陣列。因此，我們可以使用方括號來存取各個字串元素，就像在 argv 中取得各個字串一樣。當然，列印每個字元並不需要加密。或者，從技術上講，當 k = 0 時。但我們必須幫助凱撒加密他的文字！凱撒萬歲！要使用 strlen，您需要包含另一個庫。由於我們正在自動化一些驗證測試，因此程式的行為應該與此完全相同： username:~/workspace/pset2 $ ./caesar 13 Be sure to drink your Ovaltine! Or fher gb qevax lbhe Binygvar! 除了atoi之外，您還可以在ctype.h和stdlib.h庫中找到其他很酷的函數。為此，請點擊連結並在那裡進行一些搜尋。例如，isdigit 顯然是一些有趣的東西 =)。從 Z 到 A（或從 z 到 a）時，不要忘記模運算子%用C語言編寫。還要研究一下表格，它不僅顯示字母的ASCII字元。要使用check50檢查程式是否正常運作，請執行以下操作： check50 2015.fall.pset2.caesar caesar.c 如果您有興趣使用 CS50 工作人員編寫的程式碼，請執行指令： ~cs50/pset2/caesar 順便說一句，uggc://jjj.lbhghor.pbz/jngpu ?i=bUt5FWLEUN0。

任務分析

1. 拿到鑰匙
2. 取得文字
3. 加密
4. 顯示加密訊息

1. 我們形成 main 函數，以便使用者在命令列輸入金鑰並檢查金鑰的正確性。 int main(int argc, string argv[]) argc： • int • 在命令列中輸入的參數數量 • 如果argc = 2 則一切正常。如果沒有，請列印指令並關閉程式。• 如果argc = 2，我們檢查鍵是否為整數。• Argv 是一個字串數組，是一個包含輸入參數的列表。數組是一個資料結構，在不同單元格中包含相同類型的不同資料。 例如，使用者輸入字串“blastoff Team Rocket”，然後： 使用 atoi() 函數，我們將結果數字轉換為整數。如果不可能，函數將傳回 0. 2. 提示使用者輸入文字。很簡單：用戶輸入的所有內容都是字串。3、加密。演算法很簡單，但是如何向電腦解釋哪些字母是一個接一個出現的呢？是時候記住 ASCII 表了！ 然而，字串中可能不僅僅只有字母……在繼續更改字串之前，想像一下您只需要更改一個字元。我們想要更改初始文字中的字母，而不是符號或數字。我們該做什麼？首先我們要檢查這個字元是否在字母表中。這可以使用isalpha()函數來完成。如果字元在字母表中，則此函數傳回 true，否則傳回 false。兩個更有用的函數 - isupper()和islower()如果字母是大寫或小寫，則分別傳回 true。因此： Isalpha(‘Z’) -> true Isalpha(‘;’) -> false Isupper(‘Z’) ->true Isupper(‘z’) -> false Islower(‘Z’) -> false Islower(‘z’)->true 如果 isalpha 傳回 true，我們需要使用 key 來變更這個字元。我們以CS50助手Zamili的程式為例來考慮與分析。 您可能想知道為什麼「A」明明是一個字母卻是一個整數。事實證明，符號和整數是可以互換的。將字母 A 放在單引號中，您可以獲得其 int 形式的 ASCII 代碼。請注意：您需要單引號；如果沒有單引號，編譯器將尋找名為 A 的變量，而不是符號。然後， 我們將鍵值新增到字母的 ASCII 程式碼中，並將它們儲存在整數變數中。即使結果是 int，printf 語句也會使用 %c 字元佔位符。因此程式列印與整數結果相關的字元。在第二種情況下，我們使用 %d 佔位符顯示數字。您可以將此程式碼輸入到 cs50 IDE 中並使用它。讓我們檢查一下 asciimath 對於不同的鍵是如何運作的。讓我們取值25，我們將看到下圖： 現在讓密鑰為26： 我們得到[，而不是字母A。它只是Z之後的下一個ASCII字元。所以簡單地添加密鑰不會工作。當我們用完字母時，我們需要使用密碼公式回到字母表的開頭。請記住，我們在上面已經寫過： /* * asciimath.c * by Zamyla Chan * * Calculates the addition of a char and an integer, * and displays both the resultant character and its * ASCII value. * * Usage: ./asciimath key [char] * */ #include #include #include int main(int argc, string argv[]) { if (argc != 2) { printf("print the key next time \n"); return 1; } // key is the second command line argument int key = atoi(argv[1]); //преобразование строки в int int letter = 'A'; printf("\nCalculating '%c' + %d...\n", letter, key); int result = (letter + key); printf("The ASCII value of %c is %d.\n\n", result, result); return 0; } int result = (letter + key);ci = (pi + k) % 26 其中ci是密文中的第i個字母，pi是明文中的第i個字母，k是密鑰，%26是除以26的餘數（或稱「模26」）。我們將此公式應用到字母 Y 上。取 k = 2。計算 ('Y' + 2) %26 字母 'Y' 的 ASCII 碼 = 89。然後 ('Y' + 2) %26 = (89 + 2 )% 26 = 91%26 = 13 但這不是我們需要的字母A的ASCII值，它是65。現在讓我們按順序給字母表中的每個字母一個從0到25的值。在本例中，Y = 24。(24+2)%26 = 0 字母 A 就有這樣的索引。因此，公式指的是字母的字母索引，而不是它們的 ASCII 值。要列印加密字符，您需要它的 ASCII 值。並弄清楚如何在 ASCII 值和字母表中的數字之間切換。一旦我們弄清楚了一個字元的公式，我們就需要將其應用於從鍵盤輸入的字串中的每個字母。但前提是這些是字母！請記住，大寫字母和小寫字母需要不同的意義。這就是 isupper 和 islower 函數派上用場的地方。您可能有兩個公式，一個用於大寫字母，另一個用於小寫字母，函數將幫助您選擇應用哪一個。如何將公式應用於字串中的每個字元？請記住，字串只是一個字元數組。strlen函數（字串長度） 將幫助您確定循環中的迭代次數。

任務 2. Parlez-vous Français？

理論

維吉尼亞密碼比凱撒密碼更安全：它使用單字作為密鑰，並且很難單獨使用頻率分析或暴力破解。密鑰的每個字母都會產生一個數字，因此我們得到了幾個用於移動字母的密鑰。 範例： p = Meet me in the park at eleven am В качестве ключевого слова возьмем k = bacon Длина messages p = 25 В то время How длина k = 5 Поэтому его нужно повторять 5 раз. 如果訊息中的字母數量不能被密鑰整除，則我們在密鑰的最後一次應用中僅使用其中的一部分：為了 找到偏移量的值，我們使用培根密鑰的每個字母的位置在字母表中（從a到z）。我們像真正的程式設計師一樣從頭開始計算。原始文本中的每個字母都會移動給定的數字，就像凱撒密碼一樣，如有必要，在 Z 之後返回字母表的開頭。所以M會移動1個位置，第一個e根本不會移動，第二個e會移動2個位置。下面您可以看到原始訊息、書面金鑰及其應用程式結果。 當然，維吉尼亞密碼更強，但如果你知道密鑰的長度，它很容易被破解。如何識別呢？如果原始文字夠長，某些單字在其中出現多次，那麼您會看到一些重複：您 也可以使用暴力破解，但有很多選項： 26^n – 1 其中 n 是未知密鑰的長度。但通常這是很多。確實，這對計算機來說不是問題。現在是密碼的數學：設 p 是一些文本，k 是關鍵字，kj 是密鑰的第 j 個字母，pi 是原始文本中的字母編號 i，ci 是加密中的字母編號 i 。然後： ci = (pi + kj) % 26

鍛鍊

條件 寫一個程式 vigenere.c，使用 Vigenere 密碼對訊息進行加密。我們提供一個命令列參數給程式輸入：關鍵字 k，由英文字母組成。如果應用程式啟動時帶有多個參數或帶有不包含在字母表中的參數，則有必要顯示錯誤訊息並終止程式。也就是說，main 將返回 1 - 在這種情況下，我們的自動測試將了解這裡一切正常，並且會考慮此條件。如果一切順利，程式應該繼續請求一個文字字串 p，我們用上面獲得的密鑰 k 對其進行加密，列印結果並完成程序，返回值 0。 說明 有必要確保在密鑰中k 字元A 和a指定為0，B 和b 指定為1，...，Z 和z 指定為25。程式必須僅將維吉尼亞密碼套用於文字p 的字母。其餘字元（數字、標點符號、空格）必須原樣輸出。如果演算法要將第 j 個字元k應用於不在字母表中的第 i 個字元p ，則將第 j 個關鍵字元應用於文字中的下一個字母字元；你不能就離開它並轉向 k 中的另一個角色。最後，程式必須保留p中每個字母的大小寫。

不知道從哪裡開始？

以下是 CS50 課程助理 Zamilya 的一些建議

幸運的是，該程式與凱撒密碼非常相似，只是密鑰是字串而不是整數。如果您成功實施了羅馬統治者的名字密碼，那麼這可能是第二個任務的良好開端。您可能已經意識到以一個字母作為密鑰的維吉尼亞密碼與凱撒密碼相同。Vigenère 演算法使用與 Caesar 相同的步驟：

1. 拿到鑰匙
   • codeword 是第二個命令列參數 argv[1]
   • 必須在字母表中： isalpha 函數
2. 取得文字
3. 加密
4. 列印密文

因此，讓我們檢查第二個命令列參數 argv[1] 以查看它是否屬於字母字元。我們使用已經熟悉的isalpha來做到這一點。如果密鑰正確，我們會收到用戶發送的字串並開始加密。維吉尼亞密碼公式與凱撒密碼公式類似。如何將字母轉換為對應的密碼偏移量？嘗試使用 ASCII 表比較這些值。 最有可能的是，您將能夠使用表中的序列找到字母及其字母索引之間的模式。您是否知道如何從一個字母中減去另一個字母以獲得所需的結果？大寫字母和小寫字母的偏移量是相同的，因此您必須定義兩個類似的公式來確定小寫字母的偏移量並分別確定大寫字母的偏移量。另請記住，文字循環應忽略非英語字元。並且不要忘記保留字母大小寫。如果你看一下密碼公式： ci = (pi + kj) % 26 你會看到兩個索引變量，i和j。一個儲存來源文字中的位置，另一個儲存鍵中的位置。如果文字比鍵長，則鍵上的索引將從鍵的末端回到開頭。怎麼做？使用模除運算！運算的結果是兩個數相除的餘數。這種操作在程式設計上的實際好處簡直是巨大的！想像一下，一大群人需要分成三個小組。一種方法是要求他們支付第一、第二、第三次的費用。 即，第一人屬於第一組，第二人屬於第二組，第三人屬於第三組，第四人又屬於第一組，以此類推。您可以使用模除來執行相同的操作。讓我們從頭開始對相同的三組進行編號。操作方法如下： 如果您採用索引並將其除以最大值的模，則所得結果將永遠不會大於或等於該值。試試這個原理，將關鍵字回到開頭！只是您需要關鍵字的索引而不是按群組排序，這樣您就可以在不超過密鑰長度的情況下偏移正確的字母。由於我們正在自動對您的程式碼進行一些測試，因此程式的行為應如下所示： jharvard@appliance (~/Dropbox/pset2): ./vigenere bacon Meet me at the park at eleven am Negh zf av huf pcfx bt gzrwep oz 除了手動計算密文之外，您還能如何測試程式？我們很友善：為此我們編寫了程式devigenere。它需要一個且僅一個命令列參數（關鍵字），其工作是將密文輸入並傳回明文。運行它： ~cs50/pset2/devigenere k 其中 k 是關鍵字。如果您想使用 check50 檢查程序的正確性，請執行： check50 2014.fall.pset2.vigenere vigenere.c 如果您想評估我們的 vigenere 實現，請輸入： ~cs50/pset2/vigenere

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

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

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