Eine Rekursion verwandtes Thema in C#

Question

Dies ist der Hintergrund dieser Frage:

Hintergrund jede ganze Zahl Nehmen n größer als 1 ist und wenden Sie den folgenden Algorithmus

1. Wenn n ungerade ist, dann ist n = n × 3 + 1 else n = n/2

2. Wenn n gleich 1 ist, dann stoppen, anderenfalls mit Schritt zu 1

Nachfolgend zeigt, was passiert, wenn ein Start-n von 6

6 unter Verwendung von - 3 bis 10 - 5 bis 16 - 8 - 4 - 2 - 1

Nach 8 Generationen des Algorithmus wir auf 1 erhalten. Es wird vermutet, dass es für jede Zahl größer als 1 ist die wiederholte Anwendung dieses Algorithmus wird schließlich 1.

die Frage zu bekommen, ist, wie kann ich eine Zahl finden, die genau 500 Generationen dauern bis 1 zu reduzieren?

Der folgende Code ist meine Version, aber anscheinend eine falsche Logik. Könnten Sie mir helfen, das zu korrigieren? Danke im Voraus.

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

Seit Titel Ihrer Frage ist ist "A Rekursion verwandtes Thema", ich gebe Ihnen eine rekursive Lösung.

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

Jetzt alle Nummer in einem bestimmten Bereich zu finden, dass die Rückkehr 1 nach exakt 500 Rekursion:

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

Ihr Problem ist ein Teil der Collatz-Vermutung (etwa rekursiv definierte Funktion), die noch nicht gelöst ist:

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

so denke ich, Brute-Force ist ein guter Ausweg:

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

Eine rekursive Lösung

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

Answer 4

zu testen

Das Problem beobachten em,

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

In der dritten Iteration wir die Zahl 10 treffen, der kleiner ist als 13

ist

Also anstatt die Sequenzzahl jedes Mal zu berechnen, können wir einen Cache verwenden.

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

Weitere Details finden project euler und this.