问题标签 [collatz]

我正在学习 Haskell 并一直试图理解类型系统。

我正在尝试编写一个函数，该函数返回“半或三加一”系列的长度作为输入。这是我使用递归方法对该函数的尝试（该函数仅对整数输入有效）：

这是我尝试在 GHC 6.12.3 中加载此文件时遇到的错误

take (truncate (5/2)) [1,2,3]有效，因此我无法理解此错误消息。我哪里错了？

我在运行“编程挑战”一书中的“3n+1 问题”时遇到问题。

我已经尝试了可以​​在谷歌上找到的所有 Java 解决方案（甚至是 Stack Overflow 上的解决方案），但没有一个有效，它们都报告“错误答案”。我还找到了一个可行的 C++ 解决方案，将其翻译成 Java，同样的事情：“错误答案”。

我正在使用 Programming Challenges for Java submits中的模板，我可以发誓我的算法是正确的，我能想到的唯一可能的问题是读取输入或写入输出的代码，但我想不通出去。这是我的代码，任何帮助将不胜感激：

我能够在大约 5 分钟内使用 Java 解决 Collat​​z 猜想算法（不，我没有试图证明它）。

现在我正在学习 C# 来制作 Web 应用程序，但我在做同样的事情时遇到了麻烦。我只是想让用户输入一个数字，单击一个按钮，然后将输出打印到一个文本框中。

Click这是我正在使用的按钮事件处理程序方法：

这是 Collat​​z 方法：

编辑 当我使用 VS.net 调试器并输入像 2 这样的数字时，我得到 NO 输出和 NO 错误。我只能永远等待。如果它是一个无限循环，我最终会得到一个错误，对吧？

不，这不是一个家庭作业问题（虽然是 2 年前我在 JAVA 中做的 :)。）我正在独立学习 C#。

这是一个面试问题，似乎与 Project Euler Problem 14有关

Collat​​z 猜想说，如果你做以下事情

你最终得到 1。

例如，5 -> 16 -> 8 -> 4 -> 2 -> 1

假设猜想为真，每个数字都有一个链长：达到 1 所需的步数。（1 的链长为 0）。

现在，问题是给定自然数 n、m 和一个自然数 k，给出一个算法来找到 1 到 n 之间的所有数字，使得这些数字的链长 <= k。还有一个限制是任何这些数字的链只能包含 1 到 m 之间的数字（即你不能超过 m）。

一个简单的方法是暴力破解它，并将其与记忆结合起来。

面试官说有一个O(S)时间算法，其中S是我们需要输出的数字个数。

有谁知道它可能是什么？

I am trying to create a simple program to apply the statement of the Collatz Conjecture to an integer that the user can enter, I have:

However it is saying there is a syntax error in the line:

I can't see what mistake ther is in this line.

Also as I haven't been able to test it yet, does this look as though it will work ok?

我正在使用Collat​​z 猜想进行数学公平项目，我想制作一个反向图，你可以在维基百科上找到，尽管我发现我在代码中的某个地方搞砸了并且它没有显示所有反向值（例如，它会从数组中找到一个奇数，然后是相同的值 *2，但不会超过该值）。

剧透警告：这与Project Euler的问题 14有关。

以下代码需要大约 15 秒才能运行。我有一个在 1 秒内运行的非递归 Java 解决方案。我想我应该能够让这段代码更接近那个。

我已经分析+RHS -p并注意到分配的内存很大，并且随着输入的增长而增长。n = 100,000分配了 1gb（！），分配了13gb n = 1,000,000（！！）。

话又说回来，-sstderr尽管分配了很多字节，但总内存使用量为 1mb，生产力为 95%+，所以可能 13gb 是红鲱鱼。

我能想到几种可能：

1. 有些事情没有它需要的那么严格。我已经发现了 foldl1'，但也许我需要做更多？是否可以标记collatz 为严格（这是否有意义？

2. collatz不是尾调用优化。我认为应该是，但不知道如何确认。

3. 编译器没有做一些我认为应该做的优化——例如collatz，任何时候只有两个结果需要在内存中（最大和当前）

有什么建议么？

这几乎与为什么这个 Haskell 表达式这么慢？，尽管我会注意到快速 Java 解决方案不必执行任何记忆。有什么方法可以加快速度而不必求助于它？

作为参考，这是我的分析输出：

和-sstderr：

和 Java 解决方案（不是我的，取自 Project Euler 论坛，删除了记忆）：

我在 Scheme 中写过 Collat​​z 猜想：

这是一个尾递归调用，但是当我调用 (C 121) 时出现堆栈溢出：

为什么正确的尾递归会导致溢出？如您所见，我使用 Guile 作为 Scheme 解释器（版本 1.8.7）。

我正在尝试在 Haskell 中实现一个简单的 dp 算法（这是针对 Project Euler 的 Collat​​z 猜想问题）；这是等效的c ++：

所以我在 Haskell 中编写的代码最终看起来像这样：

（我认为我只是在这里重新实现了一个状态单子，但暂时不要介意。）调用solve的代码试图找到它可以为最多K = 1e6的参数提供的最大值：

上面编写的代码因堆栈溢出而失败。这是意料之中的，我理解，因为它建立了一个非常大的未评估的重击。所以我尝试使用

在 foldl' 中，它计算 K=1e5 的正确答案。但这对于 K=1e6 失败（12 秒内堆栈溢出）。然后我尝试使用

在求解的最后一行，但这没有任何区别（仍然是堆栈溢出）。然后我尝试使用

这非常慢，大概是因为 deepseq 遍历了整个 map mem''，使得算法的时间复杂度是二次的，而不是 n*log(n)。

实现这一点的正确方法是什么？我被卡住了，因为我无法弄清楚如何使整个计算变得严格，而且我不太确定计算的哪一部分导致堆栈溢出，但我怀疑它是地图。我可以使用例如数组，但我想了解我在这里做错了什么。

我一直在 Haskell 中解决Project Euler #14一段时间，但由于某种原因，我无法让它工作。不久前我使用 Groovy 解决了这个问题，我想我在这里使用的方法基本相同。然而，即使只是找到前 10,000 个长度，程序运行速度也非常慢，我现在真的不知道为什么。我认为我正在使用记忆化，但即使 GHCI 中的数据集很小，我的内存也会用完。

到目前为止，这是我想出的。

我会跑去map collatz [1..1000000]寻找问题的答案，但map collatz [1..10000]给了我一个内存不足的错误，并且还需要几秒钟才能完成运行。

如果有人能给我一些关于这个程序的问题的见解，那就太好了！我已经尝试了很多东西，但我只是卡住了，需要帮助。

谢谢！