Một đệ quy liên quan đến vấn đề trong C#

Question

Đây là nền cho câu hỏi này:

nền Đi bất kỳ số nguyên n lớn hơn 1 và áp dụng các thuật toán sau

1. Nếu n là số lẻ thì n = n × 3 + 1 khác n = n/2

2. Nếu n bằng 1 thì dừng lại, nếu không đi đến bước 1

Sau đây cho thấy những gì xảy ra khi sử dụng một n bắt đầu từ 6

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

Sau 8 thế hệ của thuật toán chúng tôi nhận tới 1. Người ta phỏng đoán rằng đối với mỗi số lớn hơn 1 ứng dụng lặp lại của thuật toán này sẽ cuối cùng nhận được 1.

Câu hỏi đặt ra là làm thế nào tôi có thể tìm được 500 số thế hệ để giảm xuống 1?

Mã bên dưới là phiên bản của tôi nhưng dường như có một số logic sai. Bạn có thể giúp tôi sửa lỗi này không? Cảm ơn trước.

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

Answer 1

Vì tiêu đề câu hỏi của bạn là "A đệ quy vấn đề liên quan", tôi sẽ cung cấp cho bạn một giải pháp đệ quy.

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

Bây giờ để tìm tất cả số trong một phạm vi nhất định, đó là sự trở lại 1 sau chính xác 500 recursions:

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

Answer 2

Vấn đề của bạn là một phần của Collatz phỏng đoán (chức năng về đệ quy được xác định) mà chưa được giải quyết chưa:

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

vì vậy tôi nghĩ brute force là một cách tốt ra:

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 

Answer 3

Một giải pháp đệ quy

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

     } 

để kiểm tra

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

Answer 4

Quan sát probl em,

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

Trong lần lặp thứ ba chúng tôi nhấn số 10, đó là nhỏ hơn 13

Vì vậy, thay vì tính số lượng chuỗi mỗi lần chúng tôi có thể sử dụng bộ nhớ cache.

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

Để biết thêm thông tin chi tiết tham khảo project euler và this.