ゴロム系列

コロンバス数列 - コロンバス数列は、n 番目の項目の値が整数 n が配列内に出現する回数である非減少整数列です。順序。

コロンブス数列のいくつかの用語は、

1, 2, 2, 3, 3, 4, 4, 4, 5, 5, 5, 6, 6, 6, 6, 7, 7, 7, 7, 8, 8, 8, 8, 9 、9、9、9、10、10、10、10、…

ここでは、5 番目の項目が 3 であり、5 もシーケンス内に 3 回出現していることがわかります。

6 番目の項目は 4 で、6 もシーケンス内に 4 回現れます。

Columbus シーケンスのプロパティ - シーケンスの最初の項目は 1 で、n 番目の項目はシーケンス内の n - n 番目の項目以下の項目の数です。

＃＃＃問題文＃＃＃

整数 n を与えます。コロンブス数列の最初の n 項を見つけます。

例 1

リーリー リーリー

例 2

リーリー リーリー

方法 1: 再帰を使用する

Columbus シーケンスのプロパティを使用すると、シーケンスの最初の項目は 1 になります。 n 番目の項を見つけるには、次のプロパティを使用します。 n 番目の項は、n - n 番目の項までのシーケンス内の 1 以下の項の数です。

このメソッドを再帰関数に適用すると、n 番目の項目がシーケンス内で n - golomb(golomb(n - 1)) 回以上出現する最小の正の整数である場合、このプロパティが満たされていることを確認します。 () は、コロンブス数列の n 番目の項を見つける再帰関数です。

疑似コード

リーリー

例: C 実装

次のプログラムでは、再帰を使用してコロンブス数列を見つけます。

リーリー ＃＃＃出力＃＃＃ リーリー

時間計算量 - O(n^2)。各項目は前の項目を再帰的に計算することによって計算されるため。

空間の複雑さ - O(n)

方法 2: メモ化を使用した再帰

再帰コードを覚えておくために、上記のコードで以前に再帰的に計算された値を保存するマップを作成します。次に、各数値を計算するときに、最初に前の数値が計算されているかどうかを確認し、計算されている場合は前の計算結果を取得し、そうでない場合は計算を実行します。

疑似コード

リーリー

例: C 実装

次のプログラムでは、以前の計算結果がマップに保存され、項目を計算するときにアクセスできます。

リーリー ＃＃＃出力＃＃＃ リーリー

時間計算量 - O(nlogn)

空間の複雑さ - O(n)

方法 3: 動的プログラミング

動的計画法を使用して、サイズ n 1 * 1 の dp テーブルを作成します。次に、上で使用したプロパティ (n 番目の数値は 1 golomb(n - golomb(golomb(n - 1))) を使用して、シーケンス内のすべての数値をカウントし、ベクトルに格納します。

疑似コード

リーリー

例: C 実装

次のプログラムでは、動的計画法を使用してこの問題を解決します。

リーリー ＃＃＃出力＃＃＃ リーリー ＃＃＃結論は＃＃＃

要約すると、コロンブス数列を見つけるには、コロンブス数列の n 番目の数値のプロパティを使用して数列内のすべての数値を見つけ、時間計算量が O(n^2) から O までのさまざまな方法を使用します。 (n) 。

以上がゴロム系列の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。