• R语言
  • 用R搬运汉诺塔盘子(递归演示)

看到有人讨论递归,就想起这个用于讨论递归的经典问题:

三根柱子,N个大小不同的盘子,大盘子不能叠到小盘子上,每次只能把某根柱子的最上面的一个盘子移动到另一个柱子的最上面,开始所有盘子都在第一根柱子处,求解从把所有盘子移动到另一根柱子的方法。详细内容可参考:

http://en.wikipedia.org/wiki/Tower_of_Hanoi

http://zh.wikipedia.org/wiki/%E6%B1%89%E8%AF%BA%E5%A1%94

直接贴代码(很简单,我就不写注释了):

<br />
hanoi <- function(n) {<br />
        tower <- list(1:n, NULL, NULL)<br />
        color <- rainbow(n)<br />
        bgcolor <- par('bg')<br />
        if (bgcolor == 'transparent') bgcolor <- 'white'</p>
<p>        draw.hanoi <- function() {<br />
                for (i in 1:3) {<br />
                        screen(i)<br />
                        plot(c(-n, n), c(0, n + 2), type = 'n', xlab = '', ylab = '')<br />
                        rect(-n, 0, n, n + 2, border = bgcolor, col = bgcolor)<br />
                        if (length(tower[[i]]) > 0) {<br />
                                barplot(rev(tower[[i]]), add = TRUE, horiz = TRUE, col = color[rev(tower[[i]])])<br />
                                barplot(-rev(tower[[i]]), add = TRUE, horiz = TRUE, col = color[rev(tower[[i]])])<br />
                        }<br />
                }<br />
        }   </p>
<p>        move.hanoi <- function(k, from, to, via) {<br />
                if (k > 1) {<br />
                        move.hanoi(k - 1, from, via, to)<br />
                        move.hanoi(1, from, to, via)<br />
                        move.hanoi(k - 1, via, to, from)<br />
                } else {<br />
                        cat('Move ', tower[[from]][1], ' from ', LETTERS[from], ' to ', LETTERS[to], '\n')<br />
                        tower[[to]] <<- c(tower[[from]][1], tower[[to]])<br />
                        tower[[from]] <<- tower[[from]][-1]<br />
                        draw.hanoi()<br />
                        Sys.sleep(.5)<br />
                }<br />
        }   </p>
<p>        close.screen(all = TRUE)<br />
        split.screen(c(1,3))</p>
<p>        draw.hanoi()<br />
        move.hanoi(n, 1, 2, 3)<br />
}</p>
<p>hanoi(7)<br />
</p>

这段代码我只在Linux下测试通过,效果凑合,Windows下没测试。

我之前想写,没写出来。呵呵,加入fun吧[s:11]

可不可以自己点鼠标操作呢,像文曲星上那种小游戏?

精彩! Yan兄简单介绍下R的GUI programming吧

哈哈,期待下次R会上linlin的精彩演讲!

回复 第3楼 的 cloud_wei:收录请自便,我一向支持copyleft[s:17]。

回复 第4楼 的 cloud_wei:点鼠标很容易实现,用locator()就足够,但那样就不是在演示递归了。

回复 第5楼 的 easttiger:这个程序只是很浅显地使用了barplot(这是我找到的最接近盘子的图),要论道图形,还真只有谢老大有资格。

回复 第6楼 的 刘思喆:说来惭愧,眼看天气越来越暖和了,离暑假也越来越近了,可我至今还没想清楚可以演讲些什么,似乎我总在瞎折腾各种东西,却没有一个方面研究得深入的。[s:18]

回复 第7楼 的 yanlinlin82:我真切地感到谢老大和其他各位老大应该联手写一本"R:How to Program"

回复 第9楼 的 easttiger:其实一直幻想着可以以COS的名义出版一部书……

回复 第10楼 的 Ihavenothing:要不今年暑假...

不瞒你们说,我这些天还真是在和颜站长商量写书这件事。论坛上有很多有趣并且有意义的帖子,可以汇集成册,作为统计计算的一些例子,但我也有所顾虑。既然这件事已经被提出来了,那就公开讨论一下好了。我另开贴。

回复 第3楼 的 cloud_wei:收吧,赶紧,我觉得这个包该发布到CRAN了。

回复 第12楼 的 谢益辉:恩,开始收集和整理一些素材了,不过最近忙于各种杂事,进展非常缓慢[s:18]……

回复 第7楼 的 yanlinlin82:你直接加入,当我们的领导吧。要弄的好看一些的话,还得设置盘子的大小等等。光是柱形图貌似还韵味不足。我觉得该游戏应该既让玩家玩得高兴,也让玩家知道最优的步骤。

回复 第11楼 的 easttiger:强烈支持,暑假里大家都稍微闲了点,尤其是大四毕业生。当然,现在有时间的可以早些准备。

回复 第12楼 的 谢益辉:既然要出书,那么书的定位、架构、内容、格式、作者等等都应该仔细斟酌斟酌了。cos上的优秀帖子还是有限,并且有些还不太适合放在书里面,比如大段大段的code。要出本像样的书,估计还得费很大功夫,并且出的书应该和现有的中文版有所区别。我觉得大家可以分成小团队,各个小团队负责一块,以已有的外文R书籍、理论书籍为主要参考。

写书是个好事,但如果又是什么语言与统计分析之类的就太无聊了,论坛上高手那么多,能否写一本定位在高端客户的书,尤其是数据管理与GUI方面的内容。建议用电子文档,这样无论代码多少,图像有多大都可以放置,复杂不要紧,只要能说明白就行。强烈盼望中。

推荐两种风格, 第一种是Deitel的How to program系列, 特点是从0开始,由浅入深,内容翔实, 兼具教科书和reference风格.

http://dc143.4shared.com/download/178778310/8b78b872/java-how-to-program-7th-editio.pdf?tsid=20100324-003945-6724d4bc

另一种是Schaum's outline series, 特点是起点更低, 当读者一无所知开始讲起, 当然结尾程度也不高, 这一系列的书文句通畅, 逻辑上没有歧义, 可以看出编辑专门花力气对文章进行修改以保证读者能够读懂.

http://dc182.4shared.com/download/187572285/260fbea9/Schaums_Programming_with_C_--_.pdf?tsid=20100324-003238-a793f32

回复 第12楼 的 谢益辉:很期待谢老师和各位老师们能尽快出书

7 个月 后

老师布置作业让写个不用recursive的Hanoi。终于写完了,就把它帖在这吧,尽管有点狗尾续貂的感觉。只是为了给自己点“成就感”。。。

</p>
<p>hanoi.whi<-function(n,from,via,to){<br />
	pegs=list(1:n,NULL,NULL)<br />
 hanoi.move<-function(n,from,via,to){<br />
	if(n<2||n%%1!=0) stop("n should be an integer bigger than 1")<br />
	if(n%%2==1){<br />
		while(length(pegs[[from]])!=0||length(pegs[[via]])!=0){<br />
			if(length(pegs[[from]])!=0&&length(pegs[[to]])!=0&&pegs[[from]][1]<pegs[[to]][1]||length(pegs[[to]])==0){<br />
				cat("Move the disk of size",pegs[[from]][1],"from",LETTERS[from],"to",LETTERS[to],"\n")<br />
				pegs[[to]]<<-c(pegs[[from]][1],pegs[[to]])<br />
				pegs[[from]]<<-pegs[[from]][-1]<br />
				} else if(length(pegs[[from]])!=0&&length(pegs[[to]])!=0&&pegs[[from]][1]>pegs[[to]][1]||length(pegs[[from]])==0){<br />
				cat("Move the disk of size",pegs[[to]][1],"from",LETTERS[to],"to",LETTERS[from],"\n")<br />
				pegs[[from]]<<-c(pegs[[to]][1],pegs[[from]])<br />
				pegs[[to]]<<-pegs[[to]][-1]<br />
				}<br />
			if(length(pegs[[from]])==0&&length(pegs[[via]])==0) break;<br />
			if(length(pegs[[from]])!=0&&length(pegs[[via]])!=0&&pegs[[from]][1]<pegs[[via]][1]||length(pegs[[via]])==0){<br />
				cat("Move the disk of size",pegs[[from]][1],"from",LETTERS[from],"to",LETTERS[via],"\n")<br />
				pegs[[via]]<<-c(pegs[[from]][1],pegs[[via]])<br />
				pegs[[from]]<<-pegs[[from]][-1]<br />
				} else if(length(pegs[[from]])!=0&&length(pegs[[via]])!=0&&pegs[[from]][1]>pegs[[via]][1]||length(pegs[[from]])==0){<br />
				cat("Move the disk of size",pegs[[via]][1],"from",LETTERS[via],"to",LETTERS[from],"\n")<br />
				pegs[[from]]<<-c(pegs[[via]][1],pegs[[from]])<br />
				pegs[[via]]<<-pegs[[via]][-1]<br />
				}<br />
			if(length(pegs[[via]])!=0&&length(pegs[[to]])!=0&&pegs[[via]][1]<pegs[[to]][1]||length(pegs[[to]])==0){<br />
				cat("Move the disk of size",pegs[[via]][1],"from",LETTERS[via],"to",LETTERS[to],"\n")<br />
				pegs[[to]]<<-c(pegs[[via]][1],pegs[[to]])<br />
				pegs[[via]]<<-pegs[[via]][-1]<br />
				} else if(length(pegs[[via]])!=0&&length(pegs[[to]])!=0&&pegs[[via]][1]>pegs[[to]][1]||length(pegs[[via]])==0){<br />
				cat("Move the disk of size",pegs[[to]][1],"from",LETTERS[to],"to",LETTERS[via],"\n")<br />
				pegs[[via]]<<-c(pegs[[to]][1],pegs[[via]])<br />
				pegs[[to]]<<-pegs[[to]][-1]<br />
				}<br />
		}<br />
	} else {<br />
		while(length(pegs[[from]])!=0||length(pegs[[via]])!=0){<br />
			if(length(pegs[[from]])!=0&&length(pegs[[via]])!=0&&pegs[[from]][1]<pegs[[via]][1]||length(pegs[[via]])==0){<br />
				cat("Move the disk of size",pegs[[from]][1],"from",LETTERS[from],"to",LETTERS[via],"\n")<br />
				pegs[[via]]<<-c(pegs[[from]][1],pegs[[via]])<br />
				pegs[[from]]<<-pegs[[from]][-1]<br />
				} else if(length(pegs[[from]])!=0&&length(pegs[[via]])!=0&&pegs[[from]][1]>pegs[[via]][1]||length(pegs[[from]])==0){<br />
				cat("Move the disk of size",pegs[[via]][1],"from",LETTERS[via],"to",LETTERS[from],"\n")<br />
				pegs[[from]]<<-c(pegs[[via]][1],pegs[[from]])<br />
				pegs[[via]]<<-pegs[[via]][-1]<br />
				}<br />
			if(length(pegs[[from]])!=0&&length(pegs[[to]])!=0&&pegs[[from]][1]<pegs[[to]][1]||length(pegs[[to]])==0){<br />
				cat("Move the disk of size",pegs[[from]][1],"from",LETTERS[from],"to",LETTERS[to],"\n")<br />
				pegs[[to]]<<-c(pegs[[from]][1],pegs[[to]])<br />
				pegs[[from]]<<-pegs[[from]][-1]<br />
				} else if(length(pegs[[from]])!=0&&length(pegs[[to]])!=0&&pegs[[from]][1]>pegs[[to]][1]||length(pegs[[from]])==0){<br />
				cat("Move the disk of size",pegs[[to]][1],"from",LETTERS[to],"to",LETTERS[from],"\n")<br />
				pegs[[from]]<<-c(pegs[[to]][1],pegs[[from]])<br />
				pegs[[to]]<<-pegs[[to]][-1]<br />
				}</p>
<p>			if(length(pegs[[via]])!=0&&length(pegs[[to]])!=0&&pegs[[via]][1]<pegs[[to]][1]||length(pegs[[to]])==0){<br />
				cat("Move the disk of size",pegs[[via]][1],"from",LETTERS[via],"to",LETTERS[to],"\n")<br />
				pegs[[to]]<<-c(pegs[[via]][1],pegs[[to]])<br />
				pegs[[via]]<<-pegs[[via]][-1]<br />
				} else if(length(pegs[[via]])!=0&&length(pegs[[to]])!=0&&pegs[[via]][1]>pegs[[to]][1]||length(pegs[[via]])==0){<br />
				cat("Move the disk of size",pegs[[to]][1],"from",LETTERS[to],"to",LETTERS[via],"\n")<br />
				pegs[[via]]<<-c(pegs[[to]][1],pegs[[via]])<br />
				pegs[[to]]<<-pegs[[to]][-1]<br />
				}<br />
		}<br />
		}</p>
<p>	}<br />
	hanoi.move(n,from,via,to)<br />
}</p>
<p>hanoi.whi(3,1,2,3)<br />
</p>