scheme解决约瑟夫环问题(续)
2023-03-14 10:21:11 时间
sicp的习题3.22,也就是以消息传递的风格重新实现队列,我的解答如下:
由此,我才知道自己竟然一直没有想到,scheme完全可以模拟单向循环链表,整整第三章都在讲引入赋值带来的影响,而我却视而不见。在引入了改变函数后,数据对象已经具有OO的性质,模拟链表、队列、table都变的易如反掌。首先,模拟节点对象,节点是一个序对,包括当前节点编号和下一个节点:
有了节点,实现了下单向循环链表:
make-cycle-list生成一个有N个元素的环形链表,比如(make-cycle-list 8)的结果如下
#0=(1 2 3 4 5 6 7 8 . #0#)
Drscheme形象地展示了这是一个循环的链表。那么约瑟夫环的问题就简单了:
(define (make-queue)
(let ((front-ptr '())
(rear-ptr '()))
(define (set-front-ptr! ptr) (set! front-ptr ptr))
(define (set-rear-ptr! ptr) (set! rear-ptr ptr))
(define (empty-queue?) (null? front-ptr))
(define (front-queue)
(if (empty-queue?)
(error "FRONT called with an empty queue")
(car front-ptr)))
(define (insert-queue! item)
(let ((new-pair (cons item '())))
(cond ((empty-queue?)
(set-front-ptr! new-pair)
(set-rear-ptr! new-pair))
(else
(set-cdr! rear-ptr new-pair)
(set-rear-ptr! new-pair)))))
(define (delete-queue!)
(cond ((empty-queue?)
(error "DELETE! called with an empty queue" queue))
(else
(set-front-ptr! (cdr front-ptr)))))
(define (dispatch m)
(cond ((eq? m 'front-queue) (front-queue))
((eq? m 'empty-queue?) (empty-queue?))
((eq? m 'insert-queue!) insert-queue!)
((eq? m 'delete-queue!) delete-queue!)
(else
(error "Unknow method" m))))
dispatch))
(define (front-queue z) (z 'front-queue))
(define (empty-queue? z) (z 'empty-queue?))
(define (insert-queue! z item) ((z 'insert-queue!) item))
(define (delete-queue! z) ((z 'delete-queue!)))
(let ((front-ptr '())
(rear-ptr '()))
(define (set-front-ptr! ptr) (set! front-ptr ptr))
(define (set-rear-ptr! ptr) (set! rear-ptr ptr))
(define (empty-queue?) (null? front-ptr))
(define (front-queue)
(if (empty-queue?)
(error "FRONT called with an empty queue")
(car front-ptr)))
(define (insert-queue! item)
(let ((new-pair (cons item '())))
(cond ((empty-queue?)
(set-front-ptr! new-pair)
(set-rear-ptr! new-pair))
(else
(set-cdr! rear-ptr new-pair)
(set-rear-ptr! new-pair)))))
(define (delete-queue!)
(cond ((empty-queue?)
(error "DELETE! called with an empty queue" queue))
(else
(set-front-ptr! (cdr front-ptr)))))
(define (dispatch m)
(cond ((eq? m 'front-queue) (front-queue))
((eq? m 'empty-queue?) (empty-queue?))
((eq? m 'insert-queue!) insert-queue!)
((eq? m 'delete-queue!) delete-queue!)
(else
(error "Unknow method" m))))
dispatch))
(define (front-queue z) (z 'front-queue))
(define (empty-queue? z) (z 'empty-queue?))
(define (insert-queue! z item) ((z 'insert-queue!) item))
(define (delete-queue! z) ((z 'delete-queue!)))
由此,我才知道自己竟然一直没有想到,scheme完全可以模拟单向循环链表,整整第三章都在讲引入赋值带来的影响,而我却视而不见。在引入了改变函数后,数据对象已经具有OO的性质,模拟链表、队列、table都变的易如反掌。首先,模拟节点对象,节点是一个序对,包括当前节点编号和下一个节点:
(define (make-node n next) (cons n next))
(define (set-next-node! node next) (set-cdr! node next))
(define (set-node-number! node n) (set-car! node n))
(define (get-number node) (car node))
(define (get-next-node node) (cdr node))
(define (set-next-node! node next) (set-cdr! node next))
(define (set-node-number! node n) (set-car! node n))
(define (get-number node) (car node))
(define (get-next-node node) (cdr node))
有了节点,实现了下单向循环链表:
(define (make-cycle-list n)
(let ((head (make-node 1 '())))
(define (make-list current i)
(let ((next-node (make-node (+ i 1) '())))
(cond ((= i n) current)
(else
(set-next-node! current next-node)
(make-list next-node (+ i 1))))))
(set-next-node! (make-list head 1) head)
head))
(let ((head (make-node 1 '())))
(define (make-list current i)
(let ((next-node (make-node (+ i 1) '())))
(cond ((= i n) current)
(else
(set-next-node! current next-node)
(make-list next-node (+ i 1))))))
(set-next-node! (make-list head 1) head)
head))
make-cycle-list生成一个有N个元素的环形链表,比如(make-cycle-list 8)的结果如下
#0=(1 2 3 4 5 6 7 8 . #0#)
Drscheme形象地展示了这是一个循环的链表。那么约瑟夫环的问题就简单了:
(define (josephus-cycle n m)
(let ((head (make-cycle-list n)))
(define (josephus-iter prev current i)
(let ((next-node (get-next-node current)))
(cond ((eq? next-node current) (get-number current))
((= 1 i)
(set-next-node! prev next-node)
(josephus-iter prev next-node m))
(else
(josephus-iter current next-node (- i 1))))))
(josephus-iter head head m)))
(let ((head (make-cycle-list n)))
(define (josephus-iter prev current i)
(let ((next-node (get-next-node current)))
(cond ((eq? next-node current) (get-number current))
((= 1 i)
(set-next-node! prev next-node)
(josephus-iter prev next-node m))
(else
(josephus-iter current next-node (- i 1))))))
(josephus-iter head head m)))
从head节点开始计数,每到m,就将当前节点删除(通过将前一个节点的next-node设置为current的下一个节点),最后剩下的节点的编号就是答案。
文章转自庄周梦蝶 ,原文发布时间 2008-04-16
相关文章
- 在 Go 里用 CGO?这 7 个问题你要关注!
- 9款优秀的去中心化通讯软件 Matrix 的客户端
- 求职数据分析,项目经验该怎么写
- 在OKR中,我看到了数据驱动业务的未来
- 火山引擎云原生大数据在金融行业的实践
- OpenHarmony富设备移植指南(二)—从postmarketOS获取移植资源
- 《数据成熟度指数》报告:64%的企业领袖认为大多数员工“不懂数据”
- OpenHarmony 小型系统兼容性测试指南
- 肯睿中国(Cloudera):2023年企业数字战略三大趋势预测
- 适用于 Linux 的十大命令行游戏
- GNOME 截图工具的新旧截图方式
- System76 即将推出的 COSMIC 桌面正在酝酿大变化
- 2GB 内存 8GB 存储即可流畅运行,Windows 11 极致精简版系统 Tiny11 发布
- 迎接 ecode:一个即将推出的具有全新图形用户界面框架的现代、轻量级代码编辑器
- loongarch架构介绍(三)—地址翻译
- Go 语言怎么解决编译器错误“err is shadowed during return”?
- 敏捷:可能被开发人员遗忘的部分
- Denodo预测2023年数据管理和分析的未来
- 利用数据推动可持续发展
- 在 Vue3 中实现 React 原生 Hooks(useState、useEffect),深入理解 React Hooks 的