什么是范围内最大的Collat​​z序列的数字？

Question

我必须使用递归编写一个程序，该程序给定n返回最小值m，1≤m≤n，该递归生成了最长的collat​​z步骤序列，

例如20，必须返回的数字为18，因为18和19两者都产生最多的步骤（20）至1，但是18个较小。 我们得到了几个正确的答案的示例：

*Main> longestSequenceTo 13
9
*Main> longestSequenceTo 30
27
*Main> longestSequenceTo 88
73
*Main> longestSequenceTo 1121
871

我最大的问题是我们不允许使用列表，而我们对Haskell的了解仍然非常基本。 我设法将Collat​​z的猜想写为一个功能，我想我知道我的主要功能上的递归条件应该是什么：

collatz :: Integer->Integer
collatz 1 = 0
collatz n | even n = 1 + collatz (div n 2)
          | otherwise = 1 + collatz (3*n+1)

我认为我的功能应该看起来像：

longestSequence n | collatz n <= collatz (n-1) = 
                  | otherwise = 

我的问题是我不知道如何“存储” “实际n，而不是要获得数字达到1的步骤数量

Answer 1

在您“认为您的最长序列n函数的方式”中，您仅将n的值与n-1 。最长的序列可能位于其他地方。此外，对于每个N，您都会两次计算Collat​​z长度。您只需要计算n的长度，然后将其与到目前为止找到的最大值进行比较。

考虑以下过程，该过程将找到最大序列长度最高为n，而无需使用列表：

maxLength n = go 0 1
    where
        go z x  | x==n   = z'
                | True   = go z' x'
            where
                value = collatz x
                z' = if value > z then value else z
                x' = succ x

您可以跟踪到目前为止找到的最大值，并使用变量z。然后，您可以使用x和z的修改值进行下一个运行。当x等于n时，将获得结果。

但是您真正追求的不是长度，而是先产生该长度的人...您可以提出所需的更改z和z'以跟踪最大长度和产生的数字n？尝试在下面的提示下完成功能：z将具有（value，x）的元组形式：

whoHitsFirstMaxLength n = go ??? 1
    where
        go z x  | x==n   = ???
                | True   = go z' x'
            where
                value = collatz x
                z' = if value > ??? then ??? else z
                x' = succ x

Answer 2

首先，我们将您运行的值命名，因此我们可以在思考过程的单独步骤中决定如何处理它们：

longestSequence n =
  let
    this = collatz n 
    that = collatz (n-1) 
  in
     ....

因此，现在我们可以看到您正在倒计时；让我们算一下：

longestSequence n = go 1
  where
  go k = let
           this = collatz k 
           that = collatz (k+1) 
         in
            ....

但这仅为我们提供了两个值的collat​​z长度的值；我们需要所有这些；救援递归！ -

longestSequence n = postprocess $ go 1
  where 
  go k | k > n = (n, -1)
  go k = let
           this = collatz k 
           that = go (k+1) 
         in
            ....
  postprocess x = ...

现在有正确的结构。它为 和最长序列 k+1（从技术上讲，它调用go go go）在GO）。

换句话说，如果您知道 k+1 和 n n 之间的数字（以及长度）该序列），您知道 k 的顺序长度，您可以决定 k and n 具有最长的序列（并且也知道的长度为序列），然后返回 。

我还写了更多答案关于递归方法背后的思维过程解决问题，查看它们是否有帮助。