c# - c# 中与递归相关的问题

Question

这是这个问题的背景：

背景取任何大于1的整数n并应用以下算法

如果 n 是奇数，则 n = n × 3 + 1 否则 n = n / 2
如果 n 等于 1 则停止，否则转到步骤 1

下面演示了使用 6 的起始 n 时会发生什么

6 - 3 - 10 - 5 - 16 - 8 - 4 - 2 - 1

经过 8 代算法，我们得到了 1。据推测，对于每个大于 1 的数，该算法的重复应用最终会得到 1。

问题是我怎样才能找到一个需要 500 代才能减少到 1 的数字？

下面的代码是我的版本，但似乎有一些错误的逻辑。你能帮我纠正这个吗？提前致谢。

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

namespace Sequence1
{
    class Program
    {
        static void Main(string[] args)
        {
            int start = 1;
            int flag = 0;
            int value;
            while(true){
                int temp = (start - 1) / 3;
                string sta = temp.ToString();
                    if (Int32.TryParse(sta, out value) )
                    {
                        if (((start - 1) / 3) % 2 == 1)
                        {
                            start = (start - 1) / 3;
                            flag++;
                            if (flag == 500)
                            {
                                break;
                            }
                        }
                        else
                        {
                            start = start * 2;
                            flag++;
                            if (flag == 500)
                            {
                                break;
                            }
                        }
                    }
                    else 
                    {
                        start = start * 2;
                        flag++;
                        if (flag == 500)
                        {
                            break;
                        }
                    }

                }


            Console.WriteLine("result is {0}", start);
            Console.ReadLine();
        }
    }
}

score 9 · Accepted Answer

由于您的问题的标题是“A recursion related issue”，我会给您一个递归解决方案。

int Process(int input, int maxRecursionDepth)
{
    // condition to break recursion
    if (maxRecursionDepth == 0 || input == 1)
        return input;

    if (input % 2 == 1) // odd case
        return Process(input * 3 + 1, maxRecursionDepth - 1);
    else // even case
        return Process(input / 2, maxRecursionDepth - 1);
}

现在要查找指定范围内的所有数字，在 500 次递归后返回 1：

int startRange = 1, endRange = 1000;
int maxDepth = 500;

List<int> resultList = new List<int>();
for (int i = startRange; i <= endRange; i++)
{
    if (Process(i, maxDepth) == 1)
        resultList.Add(i);
}

score 4 · Accepted Answer

您的问题是尚未解决的 Collatz 猜想（关于递归定义的函数）的一部分：

http://en.wikipedia.org/wiki/Collatz_conjecture

所以我认为蛮力是一个很好的出路：

public static int GetMinNumber(int generations) {
  if (generations < 0)
    throw new ArgumentOutOfRangeException("generations");

  // Memoization will be quite good here
  // but since it takes about 1 second (on my computer) to solve the problem
  // and it's a throwaway code (all you need is a number "1979515")
  // I haven't done the memoization

  for (int result = 1; ; ++result) {
    int n = result;
    int itterations = 0;

    while (n != 1) {
      n = (n % 2) == 0 ? n / 2 : 3 * n + 1;
      itterations += 1;

      if (itterations > generations)
        break;
    }

    if (itterations == generations)
      return result;
  }
}

...

int test1 = GetMinNumber(8);   // <- 6
int test2 = GetMinNumber(500); // <- 1979515

score 3 · Accepted Answer

观察问题，

13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1

在第三次迭代中，我们达到了小于 13 的数字 10

因此，我们可以使用缓存而不是每次都计算序列计数。

    static int GetMinCollatz(int maxChain)
    {
        const long number = 1000000;
       
        int minNumber = 0;
        // Temporary values
        int tempCount = 0;
        long temp = 0;
        // Cache 
        int[] sequenceCache = new int[number + 1];
        // Fill the array with -1
        for (int index = 0; index < sequenceCache.Length; index++)
        {
            sequenceCache[index] = -1;
        }
        sequenceCache[1] = 1;

        for (int index = 2; index <= number; index++)
        {
            tempCount = 0;
            temp = index;
            // If the number is repeated then we can find 
            // sequence count from cache
            while (temp != 1 && temp >= index)
            {
                if (temp % 2 == 0)
                    temp = temp / 2;
                else
                    temp = temp * 3 + 1;
                tempCount++;
            }
            sequenceCache[index] = tempCount + sequenceCache[temp];
            if (sequenceCache[index] == maxChain)
            {
                minNumber = index;
            }
        }
       
        return minNumber;
    }

有关更多详细信息，请参阅project euler和this。

score 1 · Accepted Answer

递归解决方案

private void ReduceTo1(int input, ref int totalCount)
        {
            totalCount++;
            if (input % 2 == 0)
            {
                input = input / 2;
            }
            else
            {
                input = input * 3 + 1;
            }
            if (input != 1)
                ReduceTo1(input, ref totalCount);               

        }

去测试

int desireValue = 0;
            for (int i = 1; i < 100000; i++)
            {
                int totalCount = 0;
                ReduceTo1(i, ref totalCount);
                if (totalCount >= 500)
                {
                    desireValue = i;
                    break;
                }
            }

c# - c# 中与递归相关的问题

4 回答 4

Related

Reference