1

基本的に、1 に到達するのに 500 回の反復が必要な数を見つけるアルゴリズムを書きたいと思います。いくつかのバリエーションを試しましたが、うまくいきませんでした。

これまでの私のコードは次のとおりです。

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace sequence4
{
    class Program
    {
        static void Main(string[] args)
        {
            long startingNumber = 1;
            long count = 0;

            while (count != 500)
            {
                startingNumber = startingNumber * 2;
                count++;

                startingNumber = startingNumber / 3 - 1;
                count++;
            }
            Console.WriteLine(count);
            Console.WriteLine(startingNumber);
        }
    }
}

編集:コードの更新バージョン

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace sequence4
{
    class Program
    {
        static void Main(string[] args)
        {
            int number = 2;
            int count = 0;

            while (count != 500)
            {
                if (number % 2 == 0)
                {
                    number = 2 * number;
                    count++;
                }

                if (number % 2 != 0)
                {
                    number = (number / 3) - 1;
                    count++;
                }
            }
            Console.WriteLine(number);
            Console.WriteLine(count);
        }
    }
}
4

1 に答える 1

2

コラッツ予想の例は次のとおりです。

数7があり、コラッツ予想を使用して1に到達する必要があるとします。

  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 を使用します。

奇数の場合: x = 3n + 1
偶数の場合: x = n / 2

数値7に対してアルゴリズムを16回適用し、 1になりました。したがって、16はサイクルの長さです。

さて、上記の例では、ボトムラインから 500 倍まで逆に移動する必要があります。逆反復には、以下を使用します。

奇数の場合: x = (n - 1) / 3
偶数の場合: x = n * 2

次に、プログラムで次のように実装します。

using System;

namespace ConsoleApplication1
{
    class Program
    {
        static void Main(string[] args)
        {
            double output = 1;
            const int iterations = 500;
            for (var i = 1; i <= iterations; i++)
            {
                output = GetOutput(output);
                Console.WriteLine("Number after {0} iterations is: {1}", i, output);
            }
            Console.WriteLine("Required Number is: {0}", output);
            VerifyResult(output, iterations);
            Console.ReadKey();
        }

        private static double GetOutput(double input)
        {
            if (input == 1)
            {
                return 2;
            }
            var output = (input - 1) / 3;
            return output % 1 == 0 && output % 2 != 0 && output > 3 ? output : input * 2;
        }

        //To verify the above results we need this method
        private static void VerifyResult(double output, int iterations)
        {
            //-------------------------VERIFICATION-----------------------
            Console.WriteLine("Press any key to check iterations in reverse");
            Console.ReadKey();
            Console.WriteLine("Running validation process ...");
            var n = output;
            var max = n;
            var count = 0;
            Console.WriteLine("{0} (starting number in Collatz Sequence)", n);
            while (n > 1)
            {
                n = n % 2 == 0 ? n / 2 : 3 * n + 1;
                count++;
                if (n > max) max = n;
                Console.WriteLine(n);
            }
            if (count == iterations) //match here iterations and outputs
            {
                Console.WriteLine("\n\nCONGRATULATION! Verification results matched. :-)\n\n");
                Console.WriteLine("There are {0} cycle length in the sequence", count);
                Console.WriteLine("The largest number in the sequence is {0}", output);
                Console.WriteLine("\n\n-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-");
                Console.WriteLine("\n\nREQUIRED NUMBER: {0}\n\n", output);
                Console.WriteLine("-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-\n");
                Console.WriteLine("\nPress any key to exit");
            }
            else
            {
                Console.WriteLine("Oops... Verification results are not matching. :-(");
            }
        }
    }
}

例のソース: 3n+1 予想によるアルゴリズム ガイダンス

于 2015-08-19T15:22:25.413 に答える