c#中一个与递归相关的问题

本文关键字：递归 问题 一个 | 更新日期: 2023-09-27 18:27:34

这是这个问题的背景：

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

  1. 如果n是奇数，则n=n×3+1，否则n=n/2

  2. 如果n等于1，则停止，否则进入步骤1

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

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();
        }
    }
}

c#中一个与递归相关的问题

由于您的问题的标题是"递归相关问题"，我将为您提供递归解决方案。

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);
}

您的问题是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

观察问题，

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

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

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

    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;
    }

有关更多详细信息，请参阅项目euler和本。

递归解决方案

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;
                }
            }
相关文章：