用3N + 1猜想算法指导 [英] Algorithm guidance with 3n+1 Conjecture

问题描述

好吧，我知道这是怎么回事听起来像功课;但在这里不用任何方式。我试图解决使用C＃这问题。从问题的描述中摘录如下：

Okay, I know this is going to sound like homework; but here goes any way. I am trying to solve this problem using C#. The excerpt from the problem description is shown below:

给定输入的n，它就可能确定数的数   印刷（包括1）。对于一个给定的n这就是所谓的   周期长度为n的。在上面的例子中，22的周期长度为16。   对于任意两个数字i和j你确定i和j之间在所有数字的最大周期长度。

Given an input n, it is possible to determine the number of numbers printed (including the 1). For a given n this is called the cycle-length of n. In the example above, the cycle length of 22 is 16. For any two numbers i and j you are to determine the maximum cycle length over all numbers between i and j.

我明白了一切，除了一件事，周期长。我只是不明白它到底。我觉得文字是不明确的关于它的定义。 我认为，该周期长度是众多的数字是如何的顺序，以便可以说输入是10周期长度是8。但是，我只是不知道是什么。没有code，需要你的一部分，但指导是我问。

Question

I understand everything except for one thing, the cycle length. I just don't understand it exactly. I find that the text is ambiguous about the definition of it. I assume, that the cycle length is how many numbers were in the sequence so lets say that the input is 10 the cycle length would be 8. But I am just not exactly sure. No code is required on your part but guidance is all I ask.

另外，我已经知道了如何从标准输入和输出读取。既然问题出在编程竞赛的格式。

In addition, I already know how to read from standard input and output. Since the problem is in programming competition format.

static void collatz(ref int n)
{    
     if (n % 2 == 0)
     {
          n /= 2;
     }
     else
     {
          n = (3 * n) + 1;
     }
     Console.WriteLine(n);
}

static int GetCycleLength(int n)
{
     if (n > 0)
     {
          int count = 1;
          while (n != 1)
          {
               collatz(ref n);
               count++;
          }
          return count;
     }
     else
     {
          return -1;
     }
}

注意

虽然不做作业，我想对待家庭作业，所以我把作为标签之一。

Notes

Although it is not homework, I want to treat as homework, so I put as one of the tags.

推荐答案

您应该使用动态规划。这是说，如果你对一个数j工作，而工作的j如果遇到ķ。然后，你应该不会再再重复整个工作对于k。

You should use dynamic programming. That is say, if you work for a number j and while working for j if you encounter k. Then you should not again repeat whole work for k again.

所以从第j开始并深入到我。假设你正在寻找周期长度为n个。虽然寻找周期长度为N，假设你遇到数字：N，N8，N7，N6，...，N1。然后，你周期长度为n为9和N8是8和N7是7.商店周期长度对所有这样的数字以阵列或地图。而当你遇到相同的号码查找周期长度有什么不同数量重用它们无处不在的可能。这会给你这个问题的最佳解决方案。

So start from j and go down to i. Suppose you are finding cycle length for a number n. While finding cycle length for n, suppose you encounter numbers: n, n8, n7, n6, ..., n1. Then you cycle length for n is 9 and for n8 is 8 and for n7 is 7. Store cycle length for all such numbers in an array or map. And reuse them everywhere possible when you encounter same numbers for finding cycle length for any different number. This would give you an optimal solution for this problem.

查看示例使用动态规划的 http://en.wikipedia.org/wiki/ Dynamic_programming＃Fibonacci_sequence

See an example use of dynamic programming at http://en.wikipedia.org/wiki/Dynamic_programming#Fibonacci_sequence

这篇关于用3N + 1猜想算法指导的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！