当前位置：文江博客话题详情

寻找具有常数和的 1 和 2 的可能组合

发布于 2024-10-12 02:56:34 字数 145 浏览 5 评论 0原文

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

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

需要登录才能够评论，你可以免费注册一个本站的账号。

卖梦商人 2024-10-19 02:56:34

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

Train (1) 显然是 1: (1)。
Train (2) 显然是 2：(1 1) 和 (2)。
训练 (3) 是 3：(1 1 1)、(1 2) 和 (2 1)。前两者可以组合成连接 (1) 和 (1 1) 或 (2)。后者正是Train (2)的组合。因此，Train (3) 是 Train (2) + 1。
火车 (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。

我们得出的定义：

int 火车 (int n) {
    返回 火车 (n - 1) + 火车 (n - 2)；
}

这将无限递归，因此我们需要在基本情况下停止它。一个基本情况是明确的：Train (1) 是 1：

int 火车 (int n) {
    如果（n==1）{
        返回1；
    } 别的 {
        返回 火车 (n - 1) + 火车 (n - 2)；
    }
}

这可行，但我们可以简化基本情况：

int 火车 (int n) {
    如果（n<3）{
        返回n；
    } 别的 {
        返回 火车 (n - 1) + 火车 (n - 2)；
    }
}

Start with the simplest cases and look for regularities.

Train (1) is obviously 1: (1).
Train (2) is obviously 2: (1 1) and (2).
Train (3) is 3: (1 1 1), (1 2), and (2 1). The first two can be combined into conjoining (1) with (1 1) resp (2). The latter are exactly the combinations of Train (2). So, Train (3) is Train (2) + 1.
Train (4) is 5: (1 1 1 1) (1 1 2) (1 2 1) (2 1 1) (2 2). Again, we can combine the first as (1) with (1 1 1), (1 2), and (2 1), which are the combinations of Train (3). The last are (2) conjoined with (1 1) and (2), which are the combinations of Train (2). So, Train (4) is Train (3) + Train (2). Now, looking back at Train (3), we see that the + 1 is Train (1).

Now it seems clear that Train (n) is always Train (n - 1) + Train (n - 2). That is exactly the definition of the Fibonacci sequence.

Now, let us see how that is translated to C.

The function skeleton: Train takes one integer argument and returns an integer:
```
int Train (int n) {
}
```

The definition we worked out:

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

This will recurse infinitely, so we need to stop it at the base case. One base case is clear: Train (1) is 1:

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

This works, but we can simplify the base cases:

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

If you now just paste that last code snippet into your homework without working through the "too long, didn't read" preliminaries, I have successfully undermined your education, and you will never learn to program. You are welcome.
This is not the best way to calculate Fibonacci numbers. Why? How should you modify the code to avoid duplication of effort? Are there different approaches imaginable? Which ones?