3

一行中有 n 个项目。我们必须在不能选择两个连续项目的限制下找到可以选择项目的方式的数量。

我试图用递归关系来做，但无法达到任何。请帮我解决问题。

4

5 回答 5

7

在网上搜索后，我得到了上述问题的解决方案。

假设有 N 个项目。如果 N 是偶数，我们可以选择几乎 N/2 个项目，使得没有两个是连续的，如果 N 是奇数，我们可以选择几乎 (N+1)/2 个项目。设 K 是可以选择的最大项目数。

我们可以选择 1 到 K 个项目。

  • 为了选择一个项目，我们可以选择任何项目。

  • 为了选择两个项目，我们将 N-2 个项目保持在一个序列中。下面的圆圈代表序列中的项目。从第一项的左侧到最后一项的右侧，我们总共有 N-1 个空格。空格由“_”下划线表示。如果我们选择任意空格中的两个，并将它们替换为 item，那么我们将有 N 个 item，并且选择的两个 item 不会是连续的，因为没有两个空格是连续的。

                  _ o _ o _ o _ o _ o _ o _ o _ o _ o _ o _

  • 为了选择 p 个项目，我们将在序列中保留 Np 个项目，这将产生 N-p+1 个空间。我们可以从这些 N-p+1 个空间中选择任何 p 个空间。

因此，所有可能的方式将变为
N C 1 + N-1 C 2 + N-2 C 3 + ... + N-K+1 C K这是前 N 个斐波那契数的总和 (1,1,2,3, 5，...）。
前 N 个斐波那契数的总和也是 F(n+2) - 1

于 2012-05-21T18:14:21.327 回答
1

似乎很难理解您解释为什么它是斐波那契数列的方式。我有一种更简单的解释方式，如下所示。假设我们将 n 个项目的组合数表示为 T(n)。如果我们不选择第一项，则组合数与剩余 n-1 项的组合数相同，即 T(n-1)。如果我们选择第一个项目（我们不能选择第二个项目，因为它与第一个位置连续），那么组合的数量与剩余 n-2 个项目的组合数量相同，即 T(n-2)。因此得出以下结论。

T(n) = T(n-1) + T(n-2).
T(1) = 2 (1. selected and 2. not selected)
T(2) = 3 (1. both not selected, 2. only first selected, 3. only second selected)

这是一个斐波那契数列，可以以 O(n) 时间复杂度计算。

于 2013-05-20T16:30:04.767 回答
0

它是一个简单的解决方案。

假设您需要从前 100 个自然数中选择 3 个数字，这样没有两个数字是连续的。

考虑前 98 个自然数，并随机选择 3 个自然数（a、b、c）98C3。

我们知道0 < a, b,c < 99 和|a-b|, |b-c|, |a-c| >= 1（因为a , b , c是不同的 ）。

让A=a+0; B=b+1; C=c+2;

所以我们现在知道A、B和C中任意两个之间的差大于 1（即A、B和C不能是连续数字）。

和0 < A, B, C<101. A、B和C满足所需问题的所有条件。

所以解决方案是98 C 3。

泛化→从N中选择p个项目，使得没有两个是连续的。(N-p-1) C p

于 2012-08-23T12:04:55.023 回答
0

我认为您可以通过构建一个长度为 n 的数组来做到这一点，数组上的每个位置表示如果该位置是第一个被选择的位置，则可以选择项目的方式数。（从左到右选择。）

伪代码（未经测试）：

int[] list = new int[n];
int total = 0;

for(int position = n-1; position >= 0; position--)
{
    list[position] = 1;
    for(int subPos = position + 2; subPos < n; subPos++)
    {
        list[position] += list[subPos];
    }
    total += list[position];
}

解释：

完成运行时的值list[i]表示从行中挑选项目的方式数，其中项目 i 是最左边被挑选的项目。

显然，只有一种挑选物品的方法，最右边的物品是最左边的物品。如果 n = 5，则在这种情况下可以像这样表示采摘：00001

同样，对于第二个最右边的项目，只有一种方法可以选择最左边的项目：00010.

对于第三个最正确的项目，有一种选择方法，您只选择该项目，然后您必须添加选择每个可能第二次选择的项目的方式的数量（这是第二个循环的目的）。因此该项目将具有：00100和00101。

最右边的第四项：01000, 01010, 01001.

最右边的第一项（左边的第一项）：10000, 10100, 10101, 10010, 10001.

所以 n=5 的数组最终会得到这些值：{5,3,2,1,1}

那么总数将是：5 + 3 + 2 + 1 + 1 = 12

于 2012-05-21T08:43:05.677 回答
0

答案) (n+1-r)C r

假设我们有 n 个项目。我们要选择或选择 r 个项目，确保没有连续选择两个对象。我们要代表带有“0”的对象。所以现在我们有一个序列 00000000.......0000 {upto n terms} 现在，当我们从第 i 个位置 i={1,......,n} 中选择一个项目时，让我们将其表示为 1。因此，如果我们从位置 2 中选择一项，则新序列变为 01000000....000 {最多 n 个项}。现在，如果我们必须选择 r 个元素，我们正在设计的二进制序列中将有 r 1 个。但有趣的是，在两个连续的 1 之间，可以有任何自然数的 0。因此，如果我们将 n -r（r 1 也将在那里！）个零放在一起，那么总共有 n-r+1 个间隙（每个零的左侧和右侧）。然后我们必须将 r 1 s 放置到位。我们可以从 n-r+1 个位置中选择 r 1 s 的位置。这可以在 (n+1-r)C r 中完成。希望你能理解。

于 2020-11-23T10:00:29.827 回答