私の友人の一人が最近この質問をされました：
長さ「K」のバイナリ文字列がいくつ可能かを数えなければなりません。制約: すべての 0 のすぐ左に 1 があります。
3282 次
2 に答える
2
この質問は言い換えることができます: 2 つの連続する 0 がない場合、長さ K のバイナリ シーケンスはいくつ可能ですが、最初の要素は 1 である必要があります (そうでない場合、制約は失敗します)。最初の要素については忘れましょう (常に固定されているため、それを行うことができます)。次に、「0 が連続しない、長さ K-1 のバイナリ シーケンスの数はいくつですか」という非常に有名なタスクを取得しました。説明は、たとえばここにあります
すると、答えは F(K+1) になります。ここで、F(K) は (1 1 2 ...) から始まる K 番目のフィボナッチ数です。
于 2012-08-14T08:04:15.560 に答える
0
∑ From n=0 to ⌊K/2⌋ of (K-n)Cn; n は文字列内のゼロの数です
アイデアは、すべての 0 を 1 でグループ化し、文字列の組み合わせの数を見つけることです。n 個のゼロの場合、それらにグループ化された n 個のものが存在するため、文字列は (kn) 要素の長さになります。各ゼロのすぐ左に十分な数のゼロがないため、 K / 2個を超えるゼロは存在できません。
たとえば111111[10][10]1[10]、K = 13 の場合、n = 3
于 2012-08-14T20:31:38.007 に答える