[数据结构与算法]科拉茨猜想，统计最终变成1所运算的次数，以及数列是否有重复

?

科拉茨猜想（Collatz Conjecture）3N+1 问题

任取一个正整数，如果这个数是偶数，则除以二。如果是奇数，乘以3再加1。重复上述步骤，最后起始数都会变成1时停止。这就是著名的科拉茨猜想。

这可能不是世界上最有趣的游戏，但请你多玩一会儿。我向你保证，这将是很有趣。

例如，如果我们从7开始，我们会得到下面的数列（从现在开始，我们称它为科拉茨序列）。

7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1.如果我们从19开始，我们得到：

19, 58, 29, 88, 44, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1.请注意，在某一时刻，我们在上述两个序列中都得到了数字22，因此它们的“尾巴”是一样的。

问题是：我们总是在1处结束吗？

信不信由你，上述问题是一个深奥的谜题。尽管很多非常聪明的数学家做出了巨大的努力，但这个问题仍然没有得到解决。

这个问题被称为 "科拉茨猜想"。

解决方案

那么，解是什么样子的呢？我们需要证明两件事。首先，我们需要证明所有数列都是有界的。换句话说，不存在无限的科拉茨数列。我所说的无限是指序列中的数字集是无限大的。第二，我们需要证明不可能出现循环。也就是说，在科拉茨数列中，我们永远不会遇到一个数字两次。如果我们从1开始，那么4，2，1的序列就会无限期地重复。

当然，还有另一种解决办法。这个猜想可能是错的，数学家试图验证它，取的起始值约为2^68。1958年，波利亚猜想（Pòlya conjecture）被一个大约1.845×10^361的反例所推翻，这比2^68这数字大得多。

实际上，这里还可能发生另一件事。数学家们往往不大谈论这个问题，因为这是很悲伤的想法。科拉茨猜想在我们的公理系统中可能是无法解决的，也就是说，无论我们如何努力，我们都无法破解它。

我们并不是证明科拉茨猜想，只是测试下 递归 和循环的算法用时，以及产生的数列队列。

新建控制台应用程序CollatzConjectureDemo，测试科拉茨猜想运算次数以及产生的数列是否存在重复元素。

测试程序如下：

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

namespace CollatzConjectureDemo
{
    class Program
    {
        static void Main(string[] args)
        {
            //科拉茨猜想: 任取一个正整数，如果这个数是偶数，则除以2。如果是奇数，乘以3再加1。重复上述步骤，最后起始数都会变成1。
            Console.SetWindowSize(120, 50);
            Task taskRecursion = Task.Run(() => { AlgorithmTimespan(CalculateCollatzConjectureUseRecursive, nameof(CalculateCollatzConjectureUseRecursive)); });
            Task taskIterator = Task.Run(() => { AlgorithmTimespan(CalculateCollatzConjecture, nameof(CalculateCollatzConjecture)); });
            Task.WaitAll(taskIterator, taskRecursion);
            Console.ReadLine();
        }

        /// <summary>
        /// 算法用时
        /// </summary>
        /// <param name="CalculateMethod">计算方法</param>
        /// <param name="methodName"></param>
        static void AlgorithmTimespan(Func<int, List<int>> CalculateMethod, string methodName)
        {
            Stopwatch stopwatch = Stopwatch.StartNew();
            for (int number = 100; number < 120; number++)
            {
                List<int> list = CalculateMethod(number);
                Console.WriteLine($"【{methodName.PadRight(38)}】数字【{number}】，是否存在重复：{list.ExistDuplicate()},轮回个数:【{list.Count}】【{string.Join(",", list)}】");
            }
            Console.WriteLine($"【{methodName.PadRight(38)}】，对【20】个数字进行科拉茨猜想运算,用时【{stopwatch.Elapsed.TotalMilliseconds}】ms");
        }

        /// <summary>
        /// 【循环方法】返回科拉茨猜想依次变成1的数列顺序
        /// </summary>
        /// <param name="startingNumber"></param>
        /// <returns></returns>
        static List<int> CalculateCollatzConjecture(int startingNumber)
        {
            List<int> list = new List<int>();
            while (startingNumber > 1)
            {
                if ((startingNumber & 1) == 0)
                {
                    //如果是偶数,就除以2
                    startingNumber = startingNumber / 2;
                }
                else
                {
                    //如果是奇数，乘以3再加1，运算后，又变成偶数了
                    startingNumber = startingNumber * 3 + 1;
                }
                list.Add(startingNumber);
            }
            return list;
        }

        /// <summary>
        /// 【递归方法】返回科拉茨猜想依次变成1的数列顺序
        /// </summary>
        /// <param name="startingNumber"></param>
        /// <returns></returns>
        static List<int> CalculateCollatzConjectureUseRecursive(int startingNumber)
        {
            List<int> list = new List<int>();
            CalculateCollatzConjectureRecursive(startingNumber, ref list);
            return list;
        }

        /// <summary>
        /// 【递归方法】返回科拉茨猜想依次变成1的数列顺序
        /// </summary>
        /// <param name="startingNumber"></param>
        /// <param name="list"></param>
        static void CalculateCollatzConjectureRecursive(int startingNumber, ref List<int> list)
        {
            if (startingNumber > 1)
            {
                if ((startingNumber & 1) == 0)
                {
                    //如果是偶数,就除以2
                    list.Add(startingNumber / 2);
                    CalculateCollatzConjectureRecursive(startingNumber / 2, ref list);
                }
                else
                {
                    //如果是奇数，乘以3再加1，运算后，又变成偶数了
                    list.Add(startingNumber * 3 + 1);
                    CalculateCollatzConjectureRecursive(startingNumber * 3 + 1, ref list);
                }
            }
        }
    }

    /// <summary>
? ? /// 判断集中中是否存在重复的元素
? ? /// </summary>
? ? public static class DuplicateUtil
    {
? ? ? ? /// <summary>
? ? ? ? /// 扩展方法：判断集合中是否存在重复的元素
? ? ? ? /// 扩展方法：方法所在的类（类名可以是任意的）一定是静态的,参数指代某种类型的扩展方法,类型前面加this关键字，比如Method(this T)代表类型T的扩展方法Method。
? ? ? ? /// </summary>
? ? ? ? /// <typeparam name="T"></typeparam>
? ? ? ? /// <param name="list"></param>
? ? ? ? /// <returns></returns>
? ? ? ? public static bool ExistDuplicate<T>(this IEnumerable<T> list)
        {
            HashSet<T> hashset = new HashSet<T>();
            return list.Any(e => !hashset.Add(e));
        }

? ? ? ? /// <summary>
? ? ? ? /// 判断是否有重复的元素，并 返回第一个重复的元素
? ? ? ? /// </summary>
? ? ? ? /// <typeparam name="T"></typeparam>
? ? ? ? /// <param name="list"></param>
? ? ? ? /// <param name="t"></param>
? ? ? ? /// <returns></returns>
? ? ? ? public static bool ExistDuplicate<T>(IEnumerable<T> list, out T t)
        {
            t = default(T);
            if (list == null)
            {
                return false;
            }
            HashSet<T> hashset = new HashSet<T>();
            foreach (T item in list)
            {
? ? ? ? ? ? ? ? //如果添加数据失败，说明有重复的元素
? ? ? ? ? ? ? ? if (!hashset.Add(item))
                {
                    t = item;
                    return true;
                }
            }
            return false;
        }
    }
}

运行结果

?