2

好的，我知道这听起来像是家庭作业；但无论如何。我正在尝试使用 C#解决这个问题。问题描述的摘录如下所示：

给定输入 n，可以确定打印的数字数量（包括 1）。对于给定的 n，这称为 n 的周期长度。在上面的例子中，22 的循环长度是 16。对于任何两个数字 i 和 j，您要确定 i 和 j 之间所有数字的最大循环长度。

问题

我什么都懂，除了一件事，周期长度。我只是不完全理解。我发现文本对它的定义模棱两可。我假设，循环长度是序列中有多少个数字，所以可以说输入为 10，循环长度为 8。但我只是不确定。您不需要任何代码，但我只要求指导。

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

我显示以 n 作为输入的数字序列的实现

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

笔记

虽然不是作业，但我想把它当作作业，所以我把它作为标签之一。

4

4 回答 4

3

您应该使用动态编程。也就是说，如果您为数字 j 工作，并且在为 j 工作时遇到 k。那么你不应该再次为 k 重复整个工作。

所以从j开始，一直到i。假设您正在寻找数字 n 的循环长度。在计算 n 的循环长度时，假设您遇到以下数字：n、n8、n7、n6、...、n1。然后，n 的循环长度为 9，n8 的循环长度为 8，n7 的循环长度为 7。将所有此类数字的循环长度存储在数组或映射中。当您遇到相同的数字以查找任何不同数字的周期长度时，并在任何可能的地方重复使用它们。这将为您提供此问题的最佳解决方案。

请参阅http://en.wikipedia.org/wiki/Dynamic_programming#Fibonacci_sequence中的动态编程示例

于 2012-09-10T23:18:36.503 回答
2

循环长度是算法必须应用于原始自然数/整数才能最终达到 1 的次数。

例如，如果您从 7 开始：

  1. 7 是奇数，所以我们使用算法 3(7) + 1 = 22
  2. 22 是偶数所以我们使用 22/2 = 11
  3. 11 是奇数，所以我们使用算法 3(11) + 1 = 34
  4. 34 是偶数所以我们使用算法 34/2 = 17
  5. 17 是奇数，所以我们使用算法 3(17) + 1 = 52
  6. 52 是偶数所以我们使用算法 52/2 = 26
  7. 26 是偶数所以我们使用算法 26/2 = 13
  8. 13 是奇数，所以我们使用算法 13(3) + 1 = 40
  9. 40 是偶数所以我们使用算法 40/2 = 20
  10. 20 是偶数所以我们使用算法 20/2 = 10
  11. 10 是偶数所以我们使用算法 10/2 = 5
  12. 5 是奇数，所以我们使用算法 5(3) + 1 = 16
  13. 16 是偶数所以我们使用算法 16/2 = 8
  14. 8 是偶数所以我们使用算法 8/2 = 4
  15. 4 是偶数所以我们使用算法 4/2 = 2
  16. 2 是偶数所以我们使用算法 2/2 = 1

我们对数字 7 应用了16次算法，得到了 1。所以，16 是循环长度。

代码性能提示collatz(ref int n)-您可以使用按位运算来代替乘法和除法。这将大大提高性能。

于 2012-09-10T23:23:52.550 回答
1

对于特定的起始值 ( n)，循环长度只是达到 1 所需的数字（包括末尾的 1）。对于10：

10 5 16 8 4 2 1

所以循环长度为7。

因此，对于这个问题，您必须从 to 循环i，j确定您迭代的每个整数的循环长度，并返回您遇到的最大循环长度。您可能想要检查另一个答案提到的动态编程（即存储先前计算的周期长度，然后在将来的计算中使用这些存储的值）。

于 2012-09-10T23:11:17.003 回答
0

所提到的文本对周期长度的定义没有歧义；它说：“给定一个输入 n，可以确定打印数字的数量……对于给定的 n，这称为 n 的循环长度”。例如，给定输入 20，参考过程打印出20 10 5 16 8 4 2 1，因此“20 的周期长度”为 8。您的程序在某种意义上模拟了n值范围的参考过程，找到并打印最大值遇到的周期长度。

请注意，使用动态编程的建议可能会有点误导。您实际可以使用的是memoization，即记录先前处理的输入的全部或部分结果。记录结果很麻烦，所以如果你的程序足够快而没有记忆，那就不要费心了。问题是假设“没有操作溢出 32 位整数”。如果您不做进一步的假设并记录所有中间结果，您需要一个能够处理数十亿个不同值的字典数据结构。如果您对最大周期长度做出假设，您的程序可能会失败。无论如何，一种方法是选择一些大数 K 并分配一个整数数组 M；将数组初始化为全零，除了M[1] = 1. 在您的 Collat​​z 例程中，每次执行第 4 步（即n ← 3n+1) 将 1 压入位堆栈。（堆栈中的位数应不小于最大循环长度。）每次执行第 5 步（即n ← n/2）时，将 0 推入堆栈。

如果您M[n] > 0在任何一步找到，那么您就知道您已经计算出 n 的循环长度为c = L = M[n]。此时，您可以展开位堆栈并返回 L。在展开时，在每次弹出后，计算n（就像n = 2*n弹出 0 或n = (n-1)/3弹出 1）、do++c和 if n<Kset M[n] = c。

于 2012-09-11T00:25:22.757 回答