C++ 编程作为一系列问题/第一章
汉诺塔是一个相当简单的谜题。它主要由三个杆和一组环组成。环有不同的尺寸，从最大到最小堆叠在第一个杆上。你的目标：将所有环移动到第二个或第三个塔。听起来很简单？规则：你只能移动给定塔上的最顶部的环，并且不能将更大的环放在较小的环上面。如果你已经知道如何获得解决方案，你可以跳过下一部分。
让我们从汉诺塔的简单版本开始，我们将以此为基础构建更大的版本。让我们从两个环的汉诺塔开始。我相信你应该能够轻松地将两个环移动到目标位置。我们将这些环分别称为 #1 和 #2。#1 堆叠在 #2 上，位于第一个杆上。我们希望将 #1 和 #2 都移动到第二个杆上；所以最终，我们必须将 #2 移动到第二个杆上。#2 是最底部的环，因此它不能放在任何其他东西的顶部；第二个杆必须是空的。因此，从这一点出发，我们制定出一个解决方案。我们将 #1 环移动到另一个杆上，然后将 #2 移动到目标杆上，然后将 #1 移动回目标杆上。
现在，让我们进入一个更大的示例。4 环汉诺塔怎么样？我们将尝试使用前面示例中的一些知识。首先，我们必须在解决方案的某个时刻将 #4 环移动到第二个杆上，为此，第二个杆必须是空的。为了使 #4 可移动，它的上面不能有任何东西，所以我们必须先将 #1、#2 和 #3 堆叠在另一个杆上。现在我们可以将 #4 移动到目标杆上，并在它的上面重新组装塔。
解决方案变得稍微复杂了。我们不能简单地拿起 #1、#2 和 #3。我们必须根据相同的规则移动它们。所以我们应用相同的模式，#3 必须移动到另一个杆上，而那个杆必须清空比 #3 数字小的环，也就是说没有 #2 或 #1。所以，另一个杆变成了我们的目标杆，只是我们移动的环更少。看到规律了吗？它被称为递归模式。所以，让我们定义一个基本规则：要使用c 作为备用杆，将n 个环从杆a 移动到杆b，首先我们将n-1 个环使用相同的规则移动到杆c，然后我们将环n 移动到杆b，然后我们将n-1 个环从杆c 移动回杆b。注意，当 n=0 时，我们应该什么也不做。现在，让我们将它变成一个程序。
打开你喜欢的文本编辑器，创建一个名为“hanoi.cpp”的新文件。此文件将包含我们的源代码。
首先，我们告诉自己存在一个递归模式。这个模式似乎使用了四个变量，n、a、b、c。我们应该给它们起一些更好的名字，比如depth、from、to 和alternate。所以，让我们创建一个函数。函数，就像数学中的函数一样，只是一组计算机要遵循的指令。它有一个名称，不像数学中所有函数都叫“f”或“x”，这毫无意义。我们将函数命名为“hanoi”。在你的文本程序中输入或粘贴以下内容
void hanoi(int depth, int from, int to, int alternate)
{
}
让我们花点时间分析一下。这行代码的第一部分是“void”。这意味着什么？实际上，这行代码的第一部分是返回类型。这是函数将返回的内容，即它的返回值，它的结果。类型仅仅意味着一种数据类型，例如一个数字、一个字母、一个字符串（一系列组成句子和内容的字母）甚至我们自己的数据类型（我们将在后面探讨）。void 类型表示无，也就是说，此函数没有结果，它会做其他一些事情，例如将结果输出给我们，而不是返回它。这行代码的第二部分是“hanoi”，正如你可能猜到的，它是函数的名称。
然后是一对括号，“(”和“)” ，在它们内部是一组参数。你可能也猜到这些参数是我们之前命名的：depth、from、to 和 alternate。它们用逗号隔开，这是合乎逻辑的。但是，你可能想知道int 部分是什么？请记住，我之前说过所有数据都有类型。int 是一种编译器认识的类型，它代表整数。因此，我们的四个变量是整数，因为它们代表负数或正数。depth 是一个数字，代表系统应该移动的环的数量。from、to 和 alternate 都是整数，用于指定我们正在使用哪个杆。事实上，这些也可以用字符串来完成，这样输出将更像“将环 #3 从塔 a 移动到塔 b”，而不是“将环 #3 从塔 1 移动到塔 2”。我们稍后可以这样做。
接下来的几行完全由一个左大括号“{”和一个右大括号“}”组成。这两个括号表示函数内部的内容，函数执行的操作。
现在，我们将开始创建函数。还记得我们的规则吗？它的一部分说，如果 n 或depth 为 0，我们应该什么也不做。所以，让我们先做到这一点。在括号之间新建一行，我们将添加一个if 语句。if 语句包含几个部分，主要遵循以下模式
if(something)
{ ..do something.. }
你可以注意到，“..do something..” 只有在“something” 为真时才会执行。在我们的例子中，“something” 是“depth 为 0”，而“do something” 是什么也不做，听起来很奇怪。因此，我们的代码是
if(depth == 0)
{
return;
}
我已经听到尖叫声了！你大喊“等等，这与模式不匹配！它应该在一行上，而不是三行！”。让我解释一下。你可以在代码中的任何地方添加空格和换行符，绝对任何地方，除了在一些愚蠢的地方，比如“if” 中的“i”和“f”之间，或者在“depth” 内部。但在大多数其他地方，它都是完全可以的。所以你可能会问，“为什么还要这样做？”。将代码分隔开有很多明显的优势。它使代码更易读。你会发现，随着你变得更有经验，你将花费超过三分之二的时间来阅读你在过去某个时间点编写的代码，而不是在那里和那时编写代码。你会花很多时间寻找代码中的错误或计算机错误。所以，你的代码易读变得至关重要。
话虽如此，我们应该讨论一下代码。首先，我们if 语句中的“something” 是“depth == 0”。你可能想知道为什么有两个等号而不是一个。这是因为只使用一个等号将改变 depth，“depth = 0” 会导致 depth 变为 0，而我们丢失了 depth 的旧值。两个等号表示比较，我们正在将 depth 与 0 比较，如果为真，我们将执行return 语句，否则我们将跳过括号中包含的所有内容。return 语句会导致函数立即返回，这意味着在该函数中没有更多操作要执行，因此在该函数中不会执行更多代码。这正是我们想要的：如果 depth 为 0，则不再执行任何操作，只需返回上一级。还要注意，return 语句在末尾有一个分号 (;)，而 if 语句没有。记住这一点非常重要：所有语句（除了使用括号的语句）都必须以分号结尾。
所以，进入下一部分。首先，我们将第 n 个环之上的所有环移动到备用杆上。所以，基本上，函数正在调用自身来执行此操作。添加以下代码
hanoi(depth-1, from, alternate, to);
你可以看到，我们正在再次调用 hanoi 函数。但是，我们现在交换了 alternate 和 to，以表示我们要将所有上面的环移动到备用杆上，而不是移动到我们要移动底部环的杆上。这很简单。
进入下一部分。我们必须将第 n 个环从from 移动到to。让我们决定如何执行此操作。我们不是在代码中实际执行此操作 - 这里没有 Pole 数据，我们也没有在杆之间移动 Ring 数据，我们只是发出命令，以便站在三个杆前面的读者可以自己执行操作。我们将在后面讨论更高级的形式。现在，添加以下代码
std::cout << "Move ring " << depth << " from pole " << from << " to pole " << to << "." << std::endl;
这是将输出我们的信息的代码。让我们分析一下。首先，它以“std::cout” 开头。“std::” 部分指定我们正在使用标准库中的某些东西。标准库包含许多有用的东西，并且每个 C++ 实现都包含它。“cout” 部分表示我们正在使用标准库中的cout，它代表“字符输出”。下一部分是“<<”。这被称为格式运算符。它将右边的内容发送到左边的内容。这个运算符几乎专门用于“std::cout”，尽管如果你真的想这样做，你也可以将其用于自己的目的。下一部分是“Move ring ”。这仅仅意味着我们将文本“Move ring ” 发送到 std::cout，而 std::cout 又会将它输出，以便我们看到。
然后你看到另一个“<<”，所以我们向 std::cout 发送更多内容，只是这次我们不是发送要精确复制的文本，而是发送深度，这意味着无论 depth 的值是多少，无论是 17、42 还是 15843，它都会输出该数字。下一部分是另一段文本。再次注意，开头有一个空格。这是因为当程序输出“depth”时，它不会在开头和结尾添加空格，因为那可能不是你想要的。因此，你必须手动添加空格。该行的其余部分很容易理解；我们只是输出更多信息。然而，最后一部分是 std::endl。标准库中的另一件东西。“endl”代表“end-line”，它使该行结束，并将所有先前的输出发送到屏幕。
让我们继续我们模式的下一部分。现在我们必须将所有环，现在应该在备用柱子上，移回目标柱子上。为此，我们使用与第一次使用类似的命令
hanoi(depth-1, alternate, to, from);
我们再次交换了东西。我们从备用柱子移到目标柱子（命名为“to”），并将从柱子用作新的备用柱子。感到困惑了吗？我希望没有。现在事情已经结束了，所有环应该都在正确的柱子上，所以这是我们函数的结尾。完整的函数如下所示
void hanoi(int depth, int from, int to, int alternate)
{
if(depth == 0)
{
return;
}
hanoi(depth-1, from, alternate, to);
std::cout << "Move ring " << depth << " from pole " << from << " to pole " << to << "." << std::endl;
hanoi(depth-1, alternate, to, from);
}
你可以记下我如何对事物进行空格，因为它可能不像你在文本编辑器中那样。你可以看到，对于每个“{”括号，我都会将内容缩进四个空格。同样，这是一种风格选择，但人们普遍认为四个空格可以使代码看起来整洁有序，同时仍然允许大量代码在屏幕上同时显示。
恐怖还没有结束！我们只有函数。我们还没有告诉计算机我们要用该函数做什么。我们还忘记了包含一些头文件，但我们稍后会详细介绍。现在，让我们添加以下代码
int main(int argc, char** argv)
{
hanoi(4, 1, 2, 3);
return 0;
}
我们创建了一个新函数，main，它返回一个整数。main 函数是特殊的，它指定程序的入口点。它接受两个参数。第一个我们可以很容易地弄清楚 - 它是另一个整数。第二个有点令人困惑。“char** 的东西是什么？”好吧，“char”代表字符。但两个星号以某种方式改变了这一点。我现在还不能完全解释它做了什么，这相当复杂。现在，只要确保它代表在命令行中传递给函数的参数即可。
让我们跳入函数体。它似乎执行了我们的 hanoi 函数，它提供了一个深度为 4 的深度，并且它希望你将环从塔 1 移动到塔 2，使用塔 3 作为备用。然后我们看到了return 语句再次出现，只是这次我们没有返回任何内容（就像我们在 hanoi 函数中所做的那样，该函数返回 void，这基本上是空的）。这次我们返回一个 0，它与 int 返回类型兼容。这就是我们 main 函数的结尾。看起来很简单，对吧？
我们只缺少最后一步才能使程序完整。还记得我们如何使用 std::cout 吗？好吧，编译器不会仅仅假设 std::cout 存在，你必须请求它。为此，你“包含头文件”。这是通过在文件的最开头添加以下内容来完成的
#include <iostream>
这会在编译时将 iostream 头文件复制并粘贴到你的文件中，而不是你手动执行此操作（这既容易出错又浪费时间，并且如果 iostream 头文件发生更改，你将不得不重复整个过程）。你必须记住这一点，std::cout 包含在 iostream 头文件中。如果你想使用 std::cout，你必须 #include iostream 头文件。
这是整个程序。请注意，编译器可能关心顺序，因此“main”应放在“hanoi()”函数定义之后。
#include <iostream>
void hanoi(int depth, int from, int to, int alternate)
{
if(depth == 0)
{
return;
}
hanoi(depth-1, from, alternate, to);
std::cout << "Move ring " << depth << " from pole " << from << " to pole " << to << "." << std::endl;
hanoi(depth-1, alternate, to, from);
}
int main(int argc, char** argv)
{
hanoi(4, 1, 2, 3);
return 0;
}
我们现在有一个完整的程序！你的第一个！恭喜！我认为是时候测试它了，你觉得呢？现在，打开一个控制台，进入 hanoi.cpp 所在的目录，并输入“g++ hanoi.cpp -o hanoi”。等待大约 2 秒，你就会得到你的程序。你可以通过执行“./hanoi”来执行它。太棒了，不是吗？它正在为你提供 4 环汉诺塔的命令。我认为你应该给自己拍拍手，并在准备好时进入下一部分。
扩展，一个人/女人还能想要什么？
[edit | edit source]所以，我们有一个汉诺塔程序。它告诉我们如何解决汉诺塔。大事。这不会给在 Google 给你面试的“开发主管”留下深刻印象。我们的程序需要变得更加复杂。以下是我们希望程序执行的一些事情
- 允许我们在启动程序时选择环的数量
- 向我们展示实际的汉诺塔，以及环的位置。
- 在计算机找到解决方案时，实时更新控制台上的图像
- 不要太快，因为我们想看到解决方案，而不是让它在一眨眼的功夫内从我们眼前闪过。