N を K 個の非ゼロ整数として表すさまざまな方法

「N を K 個の非ゼロ整数として表すさまざまな方法」という質問は、実際の多くの使用例に応用できます。

暗号化 - 暗号化では、数値 N を K 個の非ゼロ整数の合計としてエンコードするという概念を使用して、特定の暗号化方法が設計されています。

整数 N を K 個の非ゼロ整数の合計として表すことは、最適化手法のさまざまな最適化問題の部分問題に現れる可能性があります。

機械学習- 機械学習では、整数 N を K 個の非ゼロ整数の合計として表す問題を使用して、データ ポイントの分布を記述する特徴ベクトルを作成できます。

説明

の中国語訳は次のとおりです:

説明

それでは、問題を解読してみましょう。

2 つの正の整数 N と K があり、その合計が N に等しい K 個の非ゼロ整数を見つける必要があるとします。たとえば、N=10 および K=3 の場合、合計が 10 に等しい 3 つの非ゼロ整数を見つける必要があります。この場合に考えられる解決策は-

です。 リーリー

これらのソリューションには、K=3 個のゼロ以外の整数があり、合計すると N=10 になることに注意してください。

この問題を解決するにはさまざまな方法があります。それぞれについて説明しましょう。

再帰的メソッド

再帰的手法の段階的なアルゴリズムを使用して、K 個の非ゼロ整数で N を表すさまざまな方法を見つけます。

• main関数にNとKの値を入力します。

• 関数 f(N, K) を作成します。この関数は、N を K 個の非ゼロ整数として表現できる方法の合計数を返します。

• K = 1 の場合、N が 0 を超える場合は 1 を返し、それ以外の場合は 0 を返します。 （基本的な状況）。

• N == 0 または K > N の場合、0 を返します。 （基本的な状況）。

• 結果を保存する変数 count を作成します。

• 変数 count の値を 0 に設定します。

• 各整数の 1 から min(N-K 1, N-1) まで I

• f (N-i, K-1) を再帰的に計算します。

• 結果をカウントに追加します。

• カウントを返します。

例

上記のアルゴリズムの実装

リーリー ＃＃＃出力＃＃＃ リーリー ＃＃＃複雑＃＃＃

時間計算量

: O(N ^ K).

空間の複雑さ: O(K)

二項係数の式 星条旗の組み合わせ法を使用すると、正の整数 N を K 個の非ゼロ整数の合計として表現できる式を得ることができます。

N 個の星 (*) の行が、指定された整数の N 個のパーティション単位を表すと想像してください。 K-1 個の垂直バー (|) を使用して星を K 個のセグメントに配置し、パーティションの K 個の非ゼロ整数を表すことができます。

例として、10 を 3 つのゼロ以外の整数に分割します。次のアスタリスクとダッシュは、このプロセスを示すために使用できます-

* * | * * * | * * * * *

この図の最初の部分は数字の 2 を示し、2 番目の部分は数字 3 を示し、3 番目の部分は数字 5 を示しています。

K-1 個のバーを N 個の星の列に配置する方法の数は、N を K 個の非ゼロ整数で表す方法の数に等しい。この量を計算するには、$\mathrm{C(N\: \:K\:-\:1,\:K\:-\:1)}$ という式を使用します。

二項係数式 $\mathrm{C(n,k)\:=\:n!\:/(k!*(n-k)!)}$ によると。

ただし、この場合、0 が含まれる可能性を除外する必要があります。加数の 1 つとして 0 を含む除算を除外するには、次の方法を使用できます。

N から 1 を引くと、N-1 が得られます。

• N-1 を K-1 の非負の整数に除算します。

• 手順 2 で取得した K-1 個の非負整数すべてに 1 を加算して K 個の非ゼロ整数を取得し、それらの合計は N になります。

• この方法が機能する理由は、各加数の可能な最小値が 1 であるため (ゼロ以外の整数にしたいため)、N から 1 を引いて、 K は数値を加算します。
  したがって、次の式が得られます:ウェイ = C(N-1, K-1)

6 を 4 つのゼロ以外の整数で表す方法の数を見つけたいとします。以前に導出された式、つまり-

を使用できます。

C(N-1, K-1) = C(6-1, 4-1) = C(5, 3) = 10

これは、6 を 4 つのゼロ以外の整数に分割する方法が 10 通りあることを示しています。

彼らは -

1 1 1 3

• 1 1 2 2

• 1 1 3 1

• 1 2 1 2

• 1 2 2 1

• 1 3 1 1

• 2 1 1 2

• 2 1 2 1

• 2 2 1 1

• 3 1 1 1

＃＃＃方法＃＃＃
• 上記の方法を実装するための段階的なアルゴリズムについて説明します -

main関数にNとKの値を入力します。

上記の式を使用してメソッドの数を計算します。

• 変数ウェイの値を出力します。

• それでは、コードを書いてみましょう。 ＃＃＃＃＃＃例＃＃＃
二項係数法を使用したコード実装
• リーリー ＃＃＃出力＃＃＃ リーリー ＃＃＃複雑＃＃＃
  時間計算量
: O( K).

空間複雑度

: O(1)

＃＃＃結論は＃＃＃

この記事では、N を K 個の非ゼロ整数の合計として表現する方法を説明しようとします。この記事がこの概念をより深く理解するのに役立つことを願っています。

以上がN を K 個の非ゼロ整数として表すさまざまな方法の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。