-7

你能写一个接受一个参数（一个正整数）的函数吗？

  • 如果是偶数，则将其除以二，或
  • 将其乘以三，如果是奇数则加一

然后返回结果数字。

然后是一个单独的函数，它接受一个参数（一个正整数）并反复将其传递给前一个函数，直到它达到 1（此时它停止）。该函数将返回将其减少到 1 所需的步数。

然后是另一个函数，它接受两个参数 a 和 b（都是 a <= b 的正整数）并返回将范围内的任何单个数字减少到 1（包括端点）所需的最大重复 Collat​​z 步骤数。（Collat​​z 步骤参考前面的函数）。

最后，另一个函数接受两个参数 a 和 b（都是 a <= b 的正整数）并返回 a 和 b 之间的数字（包括端点），该数字需要最大的 Collat​​z 步数减少到 1。

这些函数与 Collat​​z 问题有关，我觉得很有趣。后续函数显然会借用之前定义的其他函数。

知道我们如何在 Scheme 代码中显示这一点吗？

4

3 回答 3

3

我相信这是数论中一个很大的未解决问题。有一个假设是，当它通过这个操作足够的次数时，每个数字都会减少到一个。

但是我真的不认为方案是解决这个问题的正确工具，而且由于很多人认为这是家庭作业而不是一个合法的问题，我将在 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;
}

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

于 2008-11-02T01:36:32.713 回答
1

对于其他两个函数，使用 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)))
于 2008-11-02T01:27:02.327 回答
0

执行一次迭代的函数：

(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 范围，尾递归：

(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)))
于 2008-11-02T01:10:54.543 回答