3

次のようなセットがある{1,2,3}とします。連続する 3 つの数字を選択する方法は 1 つしかありません...それはセット {1,2,3} です...

{1,2,3,4} のセットには、次の 3 つの方法があります。123 234 1234

(技術的には、これらは順序付けられていない数字のセットですが、連続して記述すると役立ちます)

  • f(5) ; {1,2,3,4,5} -> 8 つの方法:123 1234 1235 12345 234 2345 345 1345
  • f(6) ; {1,2,3,4,5,6} -> 20通り: ...
  • f(7) ; {1,2,3,4,5,6,7} -> 47通り: ...

したがって、与えられた N に対して、力ずくで答えを得ることができ、3 つ以上の連続する番号を持つサブセットをすべて計算します。

ここでは、特定の N に対してそのようなすべてのサブセットの数を取得する手法であるパターンを見つけようとしています。

この問題をさらに一般化して、サイズ N のセット内で連続する m 個の数を発見する.

4

5 に答える 5

5

この問題と「どこかに少なくとも3つの連続1したsがあるN桁の2進数の数」との間に全単射があります（サブセットで除外されている場合は0、サブセットに含まれている場合は1）。 。

これは既知の問題であり、結果をグーグルで検索するのに十分な情報であるはずです。を検索するnumber of n-digit binary strings with m consecutive 1sと、2番目のヒットはr個の隣接する数字が1であるすべてのn桁の2進数を検索することです。

または、http：//oeis.org/search？q = 0％2C0％2C1％2C3％2C8％2C20％2C47（最初のいくつかの用語で行ったブルートフォーシングに基づく）として検索することもできます。の明示的な式で、トリボナッチ数の明示的な式については、ここ2^n - tribonacci(n+3)を参照してください。また、漸化式を与えます。与えられたアナロジーは、「公正なコインのn回のフリップ内で3つのヘッドを少なくとも1回実行する確率（2 ^ nから）」です。

一般的な問題の答えは2^n-F m（n + m）であると推測できます。ここで、F mはm番目の nステップのフィボナッチ数です（編集：そうです）

于 2012-09-07T06:39:29.457 に答える
0

少しのPythonコードで、これを調査できます。

y = set()

def cons(li, num):
    if len(li) < num:
        return
    if len(li) == num:
        y.add(tuple([i for i in li]))
    else:
        y.add(tuple([i for i in li]))
        cons(li[1:], num)
        cons(li[:-1], num)

このソリューションは非常に遅くなりますが（実際には、複雑さは指数関数的になります）、いくつかの小さなリストサイズで試してみてください。そうすれば、パターンを理解できるはずです。

于 2012-09-07T05:09:07.333 に答える
0

これは宿題のように聞こえるので、始めましょう。FoOne のアプローチは、ランの最低メンバーと最高メンバー、L と H を考えることです。セット サイズが N で、最小ランの長さが M の場合、L の可能な位置 P ごとに、 H あります....

于 2012-09-07T05:00:55.933 に答える
0

連続しているかどうかはわかりません。そうでない場合、{1, 2, 3, 4} には 4 つの可能性があります: {1, 2, 3} {2, 3, 4} {1, 3, 4} {1, 2, 3, 4}

N!/3! で解を計算できると思います。N！= N*(N-1) (N-2) ...*1.

于 2012-09-07T05:03:37.517 に答える
0

素早い回答：

Sequences(n) = (n-1)*(n-2) / 2

長い答え:

これは誘導によって行うことができます。最初に、問題の説明が十分に明確でないため、問題を再度述べます。

  • ルール 1: 連続する数字 1..n のすべてのセット (n は 2 以上)

  • ルール 2: 連続する数 m..m+q の部分集合 S(n) を数える (q は 2 以上)

S(n=3)

調べてみると、1つしか見つかりません - 123

S(n=4)

調べると3つ発見！- 123 234 および 1234

S(4) には S(3) と 2 つの新しいものが含まれていることに注意してください...どちらにも新しい数字 4 が含まれています... うーん。

S(n=5)

調べてみると、... S(n=4) と 345 2345 と 12345 が見つかりました。合計 3+3=6 です。

ここにパターンが形成されていると思います。新しい関数 T を定義しましょう。

  • ルール 3: S(n) = S(n-1) + T(n) ... ある T について

S(n) には数字 n が含まれていることがわかっており、S(n) には数字 n を含む長さ 3 から n までのすべてのシーケンスも (サブコンポーネントとして) 含まれていることがわかっているはずです。それらが S(n-1) にあるはずがないことはわかっているので、T(n) にある必要があります。

  • ルール 4: T(n) には、長さが 3 から n の n で終わるすべてのシーケンスが含まれます。

S(n) にはいくつのシーケンスがありますか?

S(3) S(4) と S(5) を振り返り、T(n) を組み込みましょう。

  • S(3) = S(3)
  • S(4) = S(3) + T(4)
  • S(5) = S(4) + T(5) = S(3) + T(4) + T(5)

一般化しましょう：

  • 4 から n までのすべての f に対して、S(n) = S(3) + T(f)。

では、与えられた T にはいくつありますか?

ルール 5 を振り返ってください - それはいくつのシーケンスを記述していますか?

T(4) の場合、3 つ以上の 4 で終わるすべてのシーケンスを記述します (つまり 234)。

T(5) の場合、3 つ以上の 5 で終わるすべてのシーケンスを記述します (つまり、345 2345 = 2)。

T count Examples
4 2     1234 234
5 3     12345 2345 345
6 4     123456 23456 3456 456

T(n) は単純に n-2 のように見えます。

そう

S(6) = T(6) + T(5) + T(4) + S(3)
  10 = 4    + 3    + 2    + 1

S(7) = 15 = 5 + 4 + 3 + 2 + 1 S(8) = 21 = 6 + 5 + 4 + 3 + 2 + 1

これを式にすると

2 * S(8) とは?

42 = 6 + 5 + 4 + 3 + 2 + 1 + 1 + 2 + 3 + 4 + 5 + 6

最大数と最小数の各ペアを追加します。

42 = 7 + 7 + 7 + 7 + 7 + 7

42 = 7 * 6

しかし、それは 2 * S(8) なので、

S(8) = 42/2 = 21 = 7 * 6 / 2

これは一般化します：

S(n) = (n-1)*(n-2) / 2

これが機能することを確認しましょう：

S(3) = 2*1/2 = 1
S(4) = 3*2/2 = 3
S(5) = 4*3/2 = 6
S(6) = 5*4/2 = 10

私は満足しています。

于 2012-09-07T06:47:39.713 に答える