用分治算法解决汉诺塔问题

2021-03-27 06:26

阅读:785

标签:分治   VID   大于   一个   func   模式   str   int   设置   

分治算法的介绍

基本思想:分而治之(Divide and conquer)

模式:

  1. 设置一个阈值N0
  2. 当问题规模p小于N0时,采用基本子算法
  3. 当规模大于N0时,将问题分解再合并

汉诺塔问题

思路:

  1. 当片数n=1时:将一片从A移动到C
  2. 当片数n>=2时:
    • 将所有片看作两部分,最下面一片为单独一部分,
    • 上面一部分从A移动到B,下面一部分从A移动到C
    • 再将上面一部分从B移动到C

代码解决:

func tower(i int,a,b,c string){
	if i==1{
		fmt.Println("plate 1: ",a," -> ",c)
	}
	if i>=2 {
		tower(i-1, a, c, b)
		fmt.Println("plate",i,":",a," -> ",c)
		tower(i-1,b,a,c)
	}
}

用分治算法解决汉诺塔问题

标签:分治   VID   大于   一个   func   模式   str   int   设置   

原文地址:https://www.cnblogs.com/sjx13/p/13664076.html


评论


亲,登录后才可以留言!