Korean, Edit

C 言語のコラッツ予想

上位カテゴリ : 【C言語】 【C言語目次】(https://jb243.github.io/pages/10802)

a. GitHub


コラッツ予想は、1937 年にこの予想を最初に提案したローター・コラッツにちなんで名付けられ、3n+1 問題またはヘイルストーン列問題としても知られています。コラッツ予想は、任意の自然数に対して、次のアルゴリズムは常に終了すると述べています。

  1. 入力 n を取得します。

  2. n が 1 の場合は停止します。

  3. n が奇数の場合は、3n + 1 を計算します。

  4. n が偶数の場合は、2 で割ります。

  5. 手順 2 ～ 4 を繰り返します。

例として n = 22 を使用すると、アルゴリズムは次の一連の値を生成します。

22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1

このアルゴリズムは、通常扱う範囲 (最大 20 × 258) 内のほとんどの数値に対して終了しますが、考えられるすべての入力に対して終了することは証明されていません。それは解決不可能な問題ではないかと疑問に思う人もいます。次のアルゴリズムには、自然数 a および b (最大約 10,000,000) の中で最も長い周期を持つ数を見つけるアプローチが含まれています。このアルゴリズムの最適化は個別に検討してください。さらに、C2アルゴリズムを適用することで、特定の数値の周期を出力することができます。


「」c #include #include #include #define count_set 200000000 /* このコードは、コラッツの問題で定義された a と b の間の n の配列の最小の長さを示します。 仮定: すべてのカウントは「short」データ型の最大値を下回ります。 手順は次のようになります。 1（オーバー） 2→1(オーバー) 3→10→5→16→8→4→2（オーバー） 4（オーバー） 5（オーバー） 6→3(オーバー) 7 → 22 → 11 → 34 → 17 → 52 → 26 → 13 → 40 → 20 → 10 (オーバー) */

short set[count_set + 1] = {0, }; int カウント; void C2(long long int n){ カウント++; if(n == 1); else if(n % 2 == 0) C2(n / 2); それ以外の場合は C2(3 * n + 1); }

int C(long long int n){ if(n > count_set){ // “n > count_set” は、大きすぎる数値が出現したことを意味します。 カウント = 0; C2(n); 戻り数; } if(set[n] != 0) return set[n];

// set[n] = 0 の場合、set[n] には適切な数値を入力する必要があります。 if(n % 2 == 1) set[n] = C(3 * n + 1) + 1; // n は奇数です それ以外の場合、set[n] = C(n / 2) + 1; // n は偶数です セット[n]を返します; }

int main(int argc, char *argv[]) { Long Long int i、a、b

、max_order = 1、max = 1; scanf(“%lld %lld”, &a, &b); セット[1] = 1; for(i = a; i <= b; i ++){ set[i] = C(i); if(set[i] > max){ max_order = i; 最大 = セット[i]; } } printf(“%lld %lld”, max_order, max); 0を返します。 } 「」


入力: 2016.03.01 11:34

results matching ""

    No results matching ""