2

わかりました、これは宿題のように聞こえるでしょう。しかし、ここではどうにでもなります。C# を使用してこの問題を解決しようとしています。問題の説明からの抜粋を以下に示します。

入力 n が与えられると、印刷される数字の数 (1 を含む) を決定することができます。与えられた n に対して、これは n のサイクル長と呼ばれます。上記の例では、22 のサイクル長は 16 です。任意の 2 つの数値 i と j について、i と j の間のすべての数値の最大サイクル長を決定する必要があります。

質問

サイクルの長さを除いて、すべてを理解しています。私はそれを正確に理解していません。テキストの定義があいまいであることがわかりました。サイクルの長さは、シーケンス内の数字の数であるため、入力が 10 であると仮定すると、サイクルの長さは 8 になります。しかし、正確にはわかりません。あなたの側でコードは必要ありませんが、私が求めるのはガイダンスだけです。

さらに、標準入力と標準出力から読み取る方法は既に知っています。問題はプログラミング競技形式なので。

入力として n を与える一連の数字を表示する私の実装

static void collatz(ref int n)
{    
     if (n % 2 == 0)
     {
          n /= 2;
     }
     else
     {
          n = (3 * n) + 1;
     }
     Console.WriteLine(n);
}

static int GetCycleLength(int n)
{
     if (n > 0)
     {
          int count = 1;
          while (n != 1)
          {
               collatz(ref n);
               count++;
          }
          return count;
     }
     else
     {
          return -1;
     }
}

ノート

宿題じゃないけど宿題扱いしたいのでタグの一つに入れておきます。

4

4 に答える 4

3

動的計画法を使用する必要があります。つまり、数 j のために働いている場合、j のために働いているときに k に遭遇した場合です。次に、k の作業全体を再度繰り返すべきではありません。

したがって、j から開始して i まで下ります。数値 n のサイクル長を求めているとします。n のサイクル長を見つけているときに、n、n8、n7、n6、...、n1 という数字に遭遇したとします。次に、n のサイクル長は 9、n8 は 8、n7 は 7 です。このようなすべての数値のサイクル長を配列またはマップに格納します。また、異なる数のサイクル長を見つけるために同じ数に遭遇した場合は、可能な限りそれらを再利用してください。これにより、この問題の最適なソリューションが得られます。

http://en.wikipedia.org/wiki/Dynamic_programming#Fibonacci_sequenceで動的計画法の使用例を参照してください

于 2012-09-10T23:18:36.503 に答える
2

サイクルの長さは、最終的に 1 になるためにアルゴリズムを元の自然数/整数に適用する必要がある回数です。

例、7 から始める場合:

  1. 7 は奇数なので、アルゴリズム 3(7) + 1 = 22 を使用します。
  2. 22 は偶数なので、22/2 = 11 を使用します。
  3. 11 は奇数なので、アルゴリズム 3(11) + 1 = 34 を使用します。
  4. 34 は偶数なので、アルゴリズム 34/2 = 17 を使用します。
  5. 17 は奇数なので、アルゴリズム 3(17) + 1 = 52 を使用します。
  6. 52 は偶数なので、アルゴリズム 52/2 = 26 を使用します。
  7. 26 は偶数なので、アルゴリズム 26/2 = 13 を使用します。
  8. 13 は奇数なので、アルゴリズム 13(3) + 1 = 40 を使用します。
  9. 40 は偶数なので、アルゴリズム 40/2 = 20 を使用します。
  10. 20 は偶数なので、アルゴリズム 20/2 = 10 を使用します。
  11. 10 は偶数なので、アルゴリズム 10/2 = 5 を使用します。
  12. 5 は奇数なので、アルゴリズム 5(3) + 1 = 16 を使用します。
  13. 16 は偶数なので、アルゴリズム 16/2 = 8 を使用します。
  14. 8 は偶数なので、アルゴリズム 8/2 = 4 を使用します。
  15. 4 は偶数なので、アルゴリズム 4/2 = 2 を使用します。
  16. 2 は偶数なので、アルゴリズム 2/2 = 1 を使用します。

このアルゴリズムを 7 に16回適用し、1 になりました。つまり、16 がサイクルの長さです。

コード パフォーマンスのヒント- 乗算と除算の代わりに、collatz(ref int n)ビット演算を使用できます。これにより、パフォーマンスが大幅に向上します。

于 2012-09-10T23:23:52.550 に答える
1

特定の開始値 ( n) の場合、サイクルの長さは単純に、1 に到達するのに必要な数 (最後の 1 を含む) です。の場合10:

10 5 16 8 4 2 1

したがって、サイクルの長さは 7 です。

したがって、この問題では、 から までループしi、j反復する各整数のサイクル長を決定し、遭遇した最大サイクル長を返す必要があります。別の回答で述べられているように、動的計画法をチェックアウトすることをお勧めします（つまり、以前に計算されたサイクル長を保存し、これらの保存された値を将来の計算で利用します）。

于 2012-09-10T23:11:17.003 に答える
0

参照されているテキストは、サイクル長の定義についてあいまいではありません。「入力 n が与えられると、印刷される数字の数を決定することが可能です...与えられた n について、これは n のサイクル長と呼ばれます」。たとえば、入力が 20 の場合、参照手続きは を出力する20 10 5 16 8 4 2 1ので、「20 のサイクル長」は 8 です。ある意味では、プログラムはnの値の範囲について参照手続きをエミュレートし、最大値を見つけて出力します。サイクル長が発生しました。

動的計画法を使用するという提案は、少し誤解を招く可能性があることに注意してください。実際に使用できるのはmemoizationです。つまり、以前に処理された入力の結果のすべてまたは一部を記録します。結果を記録するのは面倒なので、プログラムがメモ化なしで十分に速い場合は、気にしないでください。問題は、「32ビット整数をオーバーフローする操作はない」と仮定することを示しています。それ以上の仮定を行わず、すべての中間結果を記録する場合、何十億もの異なる値を処理できる辞書データ構造が必要です。最大サイクル長について仮定すると、プログラムが失敗する可能性があります。とにかく、1 つのアプローチは、いくつかの大きな数 K を選択し、整数の配列 M を割り当てることです。を除いて、配列をすべてゼロに初期化しますM[1] = 1。コラッツ ルーチンでは、ステップ 4 を実行するたびに (つまり、n ← 3n+1) 1 をビットのスタックにプッシュします。(スタック内のビット数は、最大サイクル長以上でなければなりません。) ステップ 5 を実行するたびに (つまり、n ← n/2)、スタックに 0 をプッシュします。

任意のステップで が見つかった場合はM[n] > 0、n のサイクル長が になるように計算済みであることがわかりますc = L = M[n]。その時点で、ビット スタックをアンワインドして L を返すことができます。アンワインドでは、各 pop の後、計算n( n = 2*n0 をポップするかn = (n-1)/3、1 をポップするかのように)、 do ++c、および if n<Ksetを実行しM[n] = cます。

于 2012-09-11T00:25:22.757 に答える