c - 寻找 1 和 2 的可能组合，总和为常量

Question

这是一个用 C 语言完成的任务。你能告诉我如何处理吗？

火车的长度为 n 米。它由 1 米或 2 米长的独立隔间组成。对于给定长度的火车，这些车厢有多少种不同的组合？编写一个函数 Train (n) 来计算它。

Answer 1

从最简单的案例开始，寻找规律。

1. Train(1)显然是1:(1)。
2. Train (2) 显然是 2: (1 1) and (2).
3. 火车 (3) 是 3:(1 1 1)、(1 2) 和 (2 1)。前两个可以组合成连接 (1) 与 (1 1) resp (2)。后者正是 Train (2) 的组合。所以，Train (3) 是 Train (2) + 1。
4. 火车 (4) 是 5:(1 1 1 1) (1 1 2) (1 2 1) (2 1 1) (2 2)。同样，我们可以将第一个组合为 (1) 与 (1 1 1)、(1 2) 和 (2 1)，它们是 Train (3) 的组合。最后是 (2) 与 (1 1) 和 (2) 的结合，它们是 Train (2) 的组合。所以，Train (4) 是 Train (3) + Train (2)。现在，回顾 Train (3)，我们看到 + 1 是 Train (1)。

现在似乎很清楚 Train (n) 总是 Train (n - 1) + Train (n - 2)。这正是斐波那契数列的定义。

现在，让我们看看它是如何翻译成 C 语言的。

1. 函数骨架:Train 接受一个整数参数并返回一个整数:

   int Train (int n) {
   }
   

2. 我们制定的定义:

   int Train (int n) {
       return Train (n - 1) + Train (n - 2);
   }
   

3. 这将无限递归，所以我们需要在基本情况下停止它。一个基本情况很清楚:Train (1) 是 1:

   int Train (int n) {
       if (n == 1) {
           return 1;
       } else {
           return Train (n - 1) + Train (n - 2);
       }
   }
   

4. 这还不够。想象一下 Train (2) 的作用:它将计算 Train (1) + Train (0)。 Train(1)没问题，但是Train(0)会计算Train(-1) + Train(-2)，这又是无限递归。因此，我们需要另一个基本情况:Train (2) 是 2。

   int Train (int n) {
       if (n == 1) {
           return 1;
       } else if (n == 2) {
           return 2;
       } else {
           return Train (n - 1) + Train (n - 2);
       }
   }
   

5. 这可行，但我们可以简化基本情况:

   int Train (int n) {
       if (n < 3) {
           return n;
       } else {
           return Train (n - 1) + Train (n - 2);
       }
   }
   

6. 如果您现在只是将最后一个代码片段粘贴到您的家庭作业中，而没有完成“太长，没读过”的预备知识，那么我已经成功地破坏了您的教育，您将永远学不会编程。不客气。

7. 这不是计算斐波那契数列的最佳方法。为什么？您应该如何修改代码以避免重复工作？有没有可以想象的不同方法？哪些？