0

私の要件は、コードが 0 と 1 の 2 桁のみの組み合わせの数を見つけることです。X 桁のサイズは 1 .. 1000 から変化する可能性があるため、2 つの 1 がすぐに連続することはできませんが、0 は可能です

私たちが持っている4桁の入力について言う

1010 1000 0000 0101 0001 0010 0100 1001

このような 0 と 1 の組み合わせを生成するアルゴリズムがどれかわかりません。

4

3 に答える 3

7

答えはフィボナッチ数列で与えられます。

f(n) = f(n-1) + f(n-2)

最初のいくつかの結果は次のとおりです。

length     number of combinations
1          2   (0, 1)
2          3   (00, 01, 10)
3          5   (000, 001, 010, 100, 101)
4          8   (0000, 0001, 0010, 0100, 0101, 1000, 1001, 1010)

「0」または「10」で始まる文字列を別々に考えると、フィボナッチ数列との関係がある理由がわかります。

  number of sequences of n digits
= number of sequences starting with 0, followed by n-1 more digits
+ number of sequences starting with 10, followed by n-2 more digits

「11」で始まるシーケンスは許可されていません。

フィボナッチ数は、適切な手法を使用すれば非常に迅速に計算できますが、増加するにつれて答えが非常に急速に大きくなることに注意する必要がありますmaxlen。正確な答えが必要な場合は、任意の大きな整数を処理できるライブラリを使用する必要があります。

于 2012-04-27T06:02:20.567 に答える
1

1 つのアイデアは、and という単語を使用して完全な文字列を作成することです10( 0andを使用します1が、最後にのみ)。

build(sofar, maxlen):
  if len(sofar) > maxlen: return
  if len(sofar) == maxlen: found(sofar); return
  if len(sofar) == maxlen - 1: build(sofar + "1", maxlen)
  build(sofar + "10", maxlen)
  build(sofar + "0", maxlen)

このアルゴリズムが有効なシーケンスのみを生成するという証明は、あなたに任されています。このアルゴリズムがすべての有効なシーケンスを生成するという証明と同じです。

于 2012-04-27T06:06:34.980 に答える
0

これらの値を配列に生成する関数と、配列内の値への現在のインデックスが「1」であるかどうかをチェックし、次の値が「1」であるかどうかをチェックする別の関数を用意するのはどうですか? true の場合、破棄します。そうでなければ、有効です。

于 2012-04-27T06:06:02.097 に答える