你知道如何編寫這個Scheme函數嗎？

Question

你能編寫一個函數，它有一個參數（正整數）和

• 由兩部分，如果它甚至或
• 乘以3，並增加了一個，如果是奇數

然後返回結果數字。

然後一個單獨的函數接受一個參數（一個正整數）並重復將它傳遞給前一個函數，直到它達到1（此時它停止）。該函數將返回它將其減少到1所需的步驟數。

然後另一個函數接受兩個參數a和b（兩個正整數都是< = b）並返回最大數量的重複Collat​​z步驟它需要將範圍內的任何單個數字減少到1（包括端點）。 （Collat​​z步驟是指前一個功能）。

最後，另一個採用兩個參數a和b（均爲< = b的正整數）的函數並返回a和b之間的數字（包括端點），以減少最大數量的Collat​​z步驟爲1.

這些功能與Collat​​z問題有關，我覺得它很有趣。 後續函數顯然會借用先前定義的其他函數。

任何想法如何在Scheme代碼中顯示此內容？

Answer 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環的尾遞歸版本：

(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))) 

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

我相信這是數論的一個偉大的未解問題。有一個假設，每次通過這個操作的次數都會減少到一次。

不過我真的不認爲方案是這個合適的工具，再加上因爲很多人都認定這是功課，而不是一個合法的問題，我將提供在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; 
} 

我不認爲它可能完全刪除分支。這是數論問題，因此它適用於極端（也可能是不必要的）優化。享受