重複減法迭代模？

Question

我正在嘗試編寫一個迭代過程，以使用內置過程中的模，餘數或/，在方案中執行模算術，而不使用。但是我遇到了一些問題，而試圖寫的代碼，它看起來像這樣至今：

(define (mod a b) 
    (define (mod-iter a b) 
     (cond ((= b 0) 0) 
       ((< b 0) (+ old_b new_b)))) 
    (mod-iter a (- a b))) 

正如你所看到的，我跑進需要到B的初始值添加到當前的問題b的價值。我不知道如何去做。此外，當我離開第二個條件的答案是原始數據（只是爲了確保enitre程序工作），我會得到一個「未指定返回值」的錯誤，我不知道爲什麼會發生，因爲我的代碼的其餘部分循環（或似乎？） 先謝謝你對此有任何見解。

Answer 1

當您使用參數(a b)定義mod-iter函數時，您正在映射mod中定義的參數。爲了避免陰影，使用不同的標識符，因此：

(define (mod a b) 
    (define (mod-iter ax bx) 
    (cond ((= bx 0) 0) 
      ((< bx 0) (+ b bx)))) 
    (mod-iter a (- a b))) 

注意，這看起來並不像正確的算法（沒有遞歸調用）。你如何處理(> bx 0)的常見情況？你需要這樣的東西：

(define (mod a b) 
    (define (mod-iter ax bx) 
    (cond ((= bx 0) 0) 
      ((< bx 0) (+ b bx)) 
      ((> bx 0) ...)))  ;; <- something here with mod-iter? 
    (mod-iter a (- a b))) 

Answer 2

首先，如果你不想捕獲一個變量名稱，在內部函數中使用不同的變量名稱。其次，我認爲與內置版本相比，論據是錯誤的。 （模5 6）是5和（模6 5）是1.無論如何，這是在一個邏輯時間的變化。基於生成b（2 4 8 16 32 ...）的權力列表的基礎是b是2，一直到剛好低於a的值。然後通過機會性減去這些反轉的值。那樣的問題（mod（expt 267 34）85）會很快返回答案。 （幾百原始函數調用vs幾百萬）

(define (mod a-in b-in) 
(letrec ((a (abs a-in)) 
      (sign (if (< 0 b-in) - +)) 
      (b (abs b-in)) 
     (powers-list-calc 
     (lambda (next-exponent) 
      (cond ((> b a) '()) 
      ((= next-exponent 0) 
      (error "Number 0 passed as the second argument to mod 
       is not in the correct range")) 
        (else (cons next-exponent (powers-list (* b next-exponent)))))))) 
    (let ((powers-list (reverse (powers-list-calc b)))) 
     (sign 
    (let loop ((a a) (powers-L powers-list)) 
      (cond ((null? powers-L) a) 
       ((> a (car powers-L)) 
      (loop (- a (car powers-L)) powers-L)) 
       (else (loop a (cdr powers-L)))))))))