0

結果を計算するアルゴリズムを作成しようとしています。しかし、組み合わせ論の助けが必要です。

1 から 10 までの 2 つの数を選択する必要があるとします。数え方の基本的な規則から、制限がない場合、可能な結果の数は 10 * 10 = 100 です。 2番目を選択した結果）。

最初の数が 2 番目の数よりも大きくなければならない場合、考えられる結果の数はいくつですか?

4

4 に答える 4

11

45.

10x10 ペアのグリッドを想像してください。1,1 から 10,10 までの A=B の対角線があるので、それらは A>B ではありません。この線は、他のケースを 2 つの半分に分割します。1 つは A>B の場合、もう 1 つは B < A の場合です。これらの各パーティションは同じサイズです。90 個の値が残っているので (対角線が 10 個)、A > B のペアは 45 個あります。

于 2010-01-17T04:06:25.813 に答える
6

選択した場合:

  • 1: 2 ～ 10 = 9 つの可能性
  • 2: 3 ～ 10 = 8 つの可能性
  • ...
  • 9:10=1の可能性

そう

9 + 8 + ... + 2 + 1 = 45

これは、合計が等しい等差数列と呼ばれます。

f(n) = n * (n+1) / 2 = 9 * 10 / 2 = 45
于 2010-01-17T04:06:04.300 に答える
0

私は言うだろう 

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

ここで、n は組み合わせる必要がある異なる数の数に等しくなります。したがって、n = 10 の場合は次のようになります。

10 * (10-1) / 2 = 45
于 2011-01-26T18:11:29.380 に答える
0

あなたの質問は二項係数に該当します。一度に 2 つずつ取得された 10 個のアイテムの一意の組み合わせの総数を計算するには、式 N! / (K! (N - K)!) を使用できます。N に 10、K に 2 を代入すると、45 になります。

二項係数を操作するための一般的な関数を処理するクラスを作成しました。これは、これが該当するタイプの問題です。次のタスクを実行します。

  1. 任意の N choose K について、すべての K-index を適切な形式でファイルに出力します。K インデックスは、よりわかりやすい文字列または文字で置き換えることができます。この方法により、この種の問題を簡単に解決できます。

  2. K インデックスを、並べ替えられた二項係数テーブル内のエントリの適切なインデックスに変換します。この手法は、反復に依存する以前に公開された手法よりもはるかに高速です。これは、パスカルの三角形に固有の数学的性質を使用して行われます。私の論文はこれについて語っています。この手法を発見して公開したのは私が最初だと思いますが、間違っている可能性があります。

  3. ソートされた二項係数テーブルのインデックスを対応する K インデックスに変換します。

  4. Mark Dominusメソッドを使用して二項係数を計算します。これは、オーバーフローする可能性がはるかに低く、より大きな数で機能します。

  5. このクラスは .NET C# で記述されており、一般的なリストを使用して、問題に関連するオブジェクト (存在する場合) を管理する方法を提供します。このクラスのコンストラクターは、InitTable と呼ばれる bool 値を受け取ります。これが true の場合、管理対象のオブジェクトを保持する汎用リストが作成されます。この値が false の場合、テーブルは作成されません。上記の 4 つの方法を実行するためにテーブルを作成する必要はありません。テーブルにアクセスするためのアクセサ メソッドが用意されています。

  6. クラスとそのメソッドの使用方法を示す関連するテスト クラスがあります。2 つのケースで広範囲にテストされており、既知のバグはありません。

このクラスについて読んでコードをダウンロードするには、二項係数の表化を参照してください。

このクラスを C++ に変換するのは難しくありません。

于 2012-09-25T08:21:29.893 に答える