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