-7

1 つの引数 (正の整数) を受け取り、

  • 偶数の場合は 2 で割る、または
  • 3 倍し、奇数の場合は 1 を加算します

結果の数値を返します。

次に、1 つの引数 (正の整数) を受け取り、それを 1 に達するまで (その時点で停止する) 前の関数に繰り返し渡す別の関数。この関数は、それを 1 に減らすのにかかったステップ数を返します。

次に、2 つの引数 a と b (両方とも a <= b の正の整数) を取り、範囲内の任意の単一の数値 (エンドポイントを含む) を 1 に減らすために必要な反復コラッツ ステップの最大数を返す別の関数。(Collat​​z ステップは前の関数を指します)。

そして最後に、2 つの引数 a と b (両方とも a <= b の正の整数) を取り、1 に削減されるコラッツ ステップの最大数を取る a と b (エンドポイントを含む) の間の数を返す別の関数。

これらの関数はコラッツ問題に関係しており、非常に興味深いと思います。後続の関数は、明らかに以前に定義された他の関数を借用します。

これをSchemeコードでどのように示すことができるでしょうか?

4

3 に答える 3

3

これは数論の大きな未解決の問題だと思います。この操作を十分な回数実行すると、すべての数値が 1 になるという仮説があります。

ただし、スキームがこれに適したツールであるとは本当に思いません。さらに、多くの人がこれは宿題であり、正当な質問ではないと判断したため、cで解決策を提供します

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

これにより、番号が 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

他の 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)))
于 2008-11-02T01:27:02.327 に答える
0

1回の反復を実行する関数:

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