哈佛 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 年底之前，您可以多次执行此操作。