問題タブ [binomial-coefficients]

私は、単語のリストを与えられたアルゴリズムを作成し、その単語のリスト内の 4 つの単語の一意の組み合わせを (順序に関係なく) チェックする必要があります。

チェックする組み合わせの数 はx、二項係数を使用して計算できます。つまりx = n!/(r!(n-r)!)、nはリスト内の単語の総数であり、rは各組み合わせの単語の数です。私の場合は常に 4 なので、関数はx = n!/(4!(n-4)!) = n!/(24(n-4)!)です。したがって、総単語数 がn増えると、チェックする組み合わせの数が階乗的に増えますよね？x

WolframAlphaがこの関数x = (n^4)/24 − (n^3)/4 + (11.n^2)/24 − n/4を それで、それはどれですか？n

これは、関数の成長を視覚化するためのグラフです (文字 x は l に切り替えられます)。

非常に大きな数、より具体的には「n over k」または C(n, k) の約数を見つけるために使用するアルゴリズムのヒントに興味があります。数値自体は非常に高い範囲に及ぶ可能性があるため、いわば「方程式」に時間の複雑さを取り入れる必要があります。

k に対する n の式は n です! / (k!(nk)!) そして、階乗が一種の「再帰的」であるという事実をどうにかして利用しようとしなければならないことを理解しています - しかし、私はまだ離散数学をあまり読んでいないので、問題は数学とプログラミングの両方です自然。

私が本当に探しているのは、私を正しい方向に導くヒントだけだと思います-私は本当に立ち往生しています。

nこのシリーズを解決する基本的な方法は既に試しましたが、 &の値が大きくなると時間がかかりますr。n時間の複雑さがOR r.Range r,n<=10^5の値に依存しない単一の式でこの式を減らす方法はありますか

注: ここで、つまり、このシリーズの最初の項のr < n合計を見つける必要があります。r+1

私はすでにこの質問を読みましたが、役に立ちません:

固定 n モジュロ m の最初の r 二項係数の合計を求めるアルゴリズム

私は何かをしようとしていますが、それは私の分野の外です。説明するために、単純化するために n=3 に設定します。ここで、n はこの例のパラメーターの総数です: A、B、C。これらのパラメーターは、ON と OFF (別名 0 または 1) の状態を持つことができます。この場合、これらのパラメーターの組み合わせの総数は 2^n = 8 であり、次のように視覚化できます。

もちろん、上記のリストは (2^n) で並べ替えることができます。= 40320通り。1 から 2^n までの数値を指定して、任意のパラメーター (0 または 1) の状態を計算できるアルゴリズムが必要です。たとえば、上記のテーブルを使用して 3 の数がある場合、A の状態が 1 で B と C が 0 であることを知っています。 n の値を指定するには、巨大なテーブルが必要です。

私はこれとインデックス作成を行う方法に慣れていないため、助けが必要です。

敬具

コマンドライン引数として指定されたファイル内の行で区切られた二項式のリストを読み込もうとしています。ファイルは次のようになります...

数字.txt

期待される出力:

私の出力:

「実際の」double変数値を正しく取得することに取り組んでいます。sscanf() も、x 係数の 1 つの先行ゼロ値を検出していません。これを修正するために sscanf() にできることはありますか?