3

1行にn個のアイテムがあります。連続する2つのアイテムを選択できないという制限付きで、アイテムを選択できる方法の数を見つける必要があります。

漸化式でやってみましたが、なかなか届きませんでした。問題を解決するのを手伝ってください。

4

5 に答える 5

7

ネットで検索したところ、上記の問題の解決策が見つかりました。

N個のアイテムがあるとします。Nが偶数の場合、2つが連続しないようにほぼN / 2のアイテムを選択でき、Nが奇数の場合、ほぼ（N + 1）/2のアイテムを選択できます。Kを選択可能な最大アイテムとします。

1〜Kアイテムを選択できます。

  • 1つのアイテムを選択するために、任意のアイテムを選択できます。

  • 2つのアイテムを選択するために、N-2アイテムを順番に保持します。以下の円は、シーケンス内のアイテムを表しています。そして、最初のアイテムの左から最後のアイテムの右まで、合計N-1個のスペースがあります。スペースは「_」アンダースコアで表されます。いずれかのスペースを2つ選択し、それらをアイテムに置き換えると、N個のアイテムがあり、2つのスペースが連続していないため、選択した2つのアイテムは連続しません。

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

  • p個のアイテムを選択するために、Np個のアイテムを順番に保持します。これによりN-p+1個のスペースが作成されます。これらのN-p+1スペースから任意のpスペースを選択できます。

したがって、可能な方法の合計は、最初の
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））。最初のアイテムを選択した場合（最初の位置に連続しているため、2番目のアイテムは選択できません）、組み合わせの数は、残りの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

これを行うには、長さ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は、選択される左端のアイテムです。

明らかに、アイテムを選択する方法は1つしかなく、右端のアイテムが選択される左端のアイテムになります。n = 5の場合、ピッキングは次のように表すことができます。00001

同様に、2番目に右のアイテムの場合、左端のアイテムになるようにアイテムを選択する方法は1つだけです00010。

3番目に正しいアイテムの場合、そのアイテムのみを選択する1つの方法があり、次に2番目に選択される可能性のある各アイテムを選択する方法の数を追加する必要があります（これが2番目のループの目的です） ）。そのため、そのアイテムには：00100とが含まれ00101ます。

4番目に正しい項目：01000、、。0101001001

5番目に右のアイテム（左側の最初のアイテム）10000：、、、、、。10100101011001010001

したがって、n=5の配列は次の値になります。{5,3,2,1,1}

そして、合計は次のようになります：5 + 3 + 2 + 1 + 1 = 12

于 2012-05-21T08:43:05.677 に答える
0

その簡単な解決策。

2つが連続しないように、最初の100個の自然数から3個の数を選択する必要があるとします。

最初の98個の自然数を検討し、3つの自然数（a、b、c）をランダムに選択し98C3ます。

、、、、、を知って います（a0 < a、bb、cは異なるため）。c < 99|a-b||b-c||a-c| >= 1

しましょうA=a+0; B=b+1; C=c+2;

したがって、 A、B、およびCのいずれか2つの差が1より大きいことがわかります（つまり、 A、B、およびCを連続した数にすることはできません）。

そして0 < A、、、。B_ A、B、Cは、必要な質問のすべての条件を満たす。C<101

したがって、解決策は98 C 3です。

一般化→ Nからp個のアイテムを選択し、2つが連続しないようにします。(N-p-1) C p

于 2012-08-23T12:04:55.023 に答える
0

Ans）（n + 1-r）C r

n個のアイテムがあるとします。また、2つのオブジェクトが連続して選択されないように、r個のアイテムを選択または選択します。私たちは代表するつもりです'0'のオブジェクト。これで、00000000 ....... 0000 {最大n項}のシーケンスができました。これで、「i」番目の位置からアイテムを選択するたびに、i = {1、......、n}、それを1と表現しましょう。したがって、位置2から1つのアイテムを選択すると、新しいシーケンスは01000000 ....000{最大n項}になります。ここで、r個の要素を選択する必要がある場合、設計しているバイナリシーケンスにr1があります。しかし、興味深い点は、2つの連続する1の間に、任意の数の0が存在する可能性があることです。したがって、n -r（r 1もあります！）のゼロを一緒に配置すると、合計n-r + 1のギャップ（各ゼロの左右）が存在します。次に、r1sを所定の位置に配置する必要があります。n-r+1の位置からr1sの位置を選択できます。これは（n + 1-r）Crで行うことができます。ご理解いただければ幸いです。

于 2020-11-23T10:00:29.827 に答える