Posted on 2008-03-20 19:15
dennis 閱讀(746)
評論(2) 編輯 收藏 所屬分類:
計算機科學與基礎
看了javaeye上一個解決約瑟夫環的問題的帖子，就想能不能用scheme來解決。如果采用推導出的數學公式來處理當然很簡單了：
(define (joseph n m)
(define (joseph-iter init s)
(if (> init n)
(+ s 1)
(joseph-iter (+ init 1) (remainder (+ s m) init))))
(joseph-iter 2 0))
我想是否可以用一般的模擬算法來實現？也就是模擬一個循環鏈表，每次刪除第m個元素。弄了個比較丑陋的實現：
(define (enumrate-interval low high)
(if (> low high)
'()
(cons low (enumrate-interval (+ low 1) high))))
(define (delete-last list)
(if (eq? (cdr list) '())
'()
(cons (car list) (delete-last (cdr list)))))
(define (joseph-iter init list it)
(let ((m (remainder it (length list))))
(cond ((= m 0) (delete-last list))
((= m 1) (append (cdr list) (reverse init)))
(else
(joseph-iter (cons (car list) init) (cdr list) (- m 1))))))
(define (joseph n m)
(define (joseph-list list m)
(display list)
(newline)
(if (eq? (cdr list) '())
(car list)
(joseph-list (joseph-iter '() list m) m)))
計算（joseph 8 3)的過程如下：
(1 2 3 4 5 6 7 8)
(4 5 6 7 8 1 2)
(7 8 1 2 4 5)
(2 4 5 7 8)
(7 8 2 4)
(4 7 8)
(4 7)
(7)
7
看了這個計算過程就知道我這個方法多糟糕，每次都重新構造列表。不知道看blog的大大們有沒有更好的思路？