fermat分解的計劃代碼

Question

我想通過實現幾個算法來學習計劃。

FermatFactor(N): // N should be odd 

    a ← ceil(sqrt(N)) 
    b2 ← a*a - N 
    while b2 isn't a square: 

      a ← a + 1 // equivalently: b2 ← b2 + 2*a + 1 
      b2 ← a*a - N // a ← a + 1 

    endwhile 
    return a - sqrt(b2) // or a + sqrt(b2) 

我想在計劃中實現上述算法。我困在while循環中。任何幫助，將不勝感激。謝謝

Answer 1

而不是在Scheme中使用while循環，您只需使用遞歸。 Scheme具有尾遞歸，因此遞歸與其他語言中的循環結構一樣。

具體而言，在這種情況下，您可能會使用名爲「named let」的內容，這使得創建內聯遞歸變得很容易。上面的代碼方案的直接翻譯會導致這樣的：

(define (fermat-factor n) 
    (let* ((a (ceiling (sqrt n))) 
     (b (- (* a a) n))) 
    (let loop() 
     (cond 
     ((not (integer? (sqrt b))) 
     (set! a (+ a 1)) 
     (set! b (- (* a a) n)) 
     (loop)))) 
    (- a (sqrt b)))) 

這真的不是很習慣，不過，因爲它使用的突變（來電來set!），這是該算法完全是不必要的。更慣用的做法是這樣的：

(define (fermat-factor* n) 
    (let* ((a0 (ceiling (sqrt n))) 
     (b0 (- (* a0 a0) n))) 
    (let loop ((a a0) 
       (b b0)) 
     (if (integer? (sqrt b)) 
      (- a (sqrt b)) 
      (loop (+ a 1) 
       (- (* a a) n)))))) 

（初始let*的使用是必要的，因爲一個名爲讓利不允許連續綁定在let*的風格，let*不支持命名的讓利模式）

另請參閱What is "named let" and how do I use it to implement a map function?