你知道这个Scheme函数怎么写吗？

Question

Closed. This question needs to be more focused. It is not currently accepting answers.

---

想要改进这个问题？通过编辑这篇文章来更新问题，使其仅关注一个问题。

8 年前已关闭。

Answer 1

我相信这是数论中一个尚未解决的重大问题。 有一个假设，每个数字经过此操作足够多的次数后都会减少到一。

然而，我真的不认为计划是解决这个问题的正确工具，而且由于很多人已经决定这是家庭作业而不是一个合法的问题，我将在 c 中提供我的解决方案，

inline unsigned int step(unsigned int i)
{
    return (i&0x1)*(i*3+1)+((i+1)&0x1)*(i>>1);
}

这将在数字上迈出一步（没有分支！！！）。 整个计算的方法如下：

unsigned int collatz(unsigned int i)
{
    unsigned int cur = i;
    unsigned steps = 0;
    while((cur=step(cur))!=1) steps++;
    return steps;
}

我认为不可能完全删除分支。 这是数论问题，因此它适合极端（并且可能不必要）优化。 享受

Answer 2

对于其他两个函数，使用foldl：

(define (listfrom a b)
  (if (= a b)
      (cons a empty)
      (cons a (listfrom (+ 1 a) b))))

(define (max-collatz a b)
  (foldl max 0 (map collatz-loop (listfrom a b))))

(define (max-collatz-num a b)
  (foldl (lambda (c r)
           (if (> (collatz-loop c) (collatz-loop r)) c r))
         a
         (listfrom a b)))    

Answer 3

执行一次迭代的函数：

(define (collatz x)
  (if (even? x)
      (/ x 2)
      (+ (* x 3) 1)))

该函数接受一个输入并循环直到达到 1。该函数返回达到该状态所需的迭代次数（尝试绘制此图 - 它看起来很酷）：

(define (collatz-loop x)
  (if (= x 1) 1
      (+ (collatz-loop (collatz x)) 1)))

根据要求，这里有一个尾部 - collat​​z-loop 的递归版本：

(define (collatz-loop x)
  (define (internal x counter)
    (if (= x 1) counter
    (internal (collatz x) (+ counter 1))))
  (internal x 1))

该函数采用一个范围并返回需要最多步数到达末尾的数字以及步数：

(define (collatz-range a b)
  (if (= a b)
      (cons a (collatz-loop a))
      (let ((this (collatz-loop a))
        (rest (collatz-range (+ a 1) b)))
        (if (< this (cdr rest)) rest
            (cons a this)))))

(collatz-range 1 20) ; returns (18 . 21), which means that (collatz-loop 18) returns 21

这是 collat​​z-range，尾递归：

(define (collatz-range a b)
  (define (internal a best)
    (if (< b a) best
        (internal (+ a 1)
        (let ((x (collatz-loop a)))
          (if (< x (cdr best))
              best
              (cons a x))))))
  (internal a (cons -1 -1)))