记得上学时候当时解汉诺塔问题是没有解出来的,这几天看递归,想起来了,再尝试一下吧.想啊想,想啊想,很遗憾,最后还是没能出来正确的结果,很是郁闷.
研究了一下别人解法,发现我的错误在于归纳n与n-1的情况是出错了,也就是如何用n-1来表示n.其实现在看做好递归有两点比较关键,一时总结好n的表达式,用n-1表示;第二就是结束条件要写好.就是这两条了,其实递归的思路比较简单,难就难在这两点.汉诺塔之所以不太好解,也在于题目本身并没有显式给出n与n-1的关系.
汉诺塔解法如下(C#):
string Road;
private void Hanoi(int n,char A,char B,char C)
{
if(n==1)
{
MoveTo(A,C);
return;
}
else
{
Hanoi(n-1,A,C,B);
MoveTo(A,C);
Hanoi(n-1,B,A,C);
}
}
private void MoveTo(char A,char C)
{
Road=Road+A.ToString()+"->"+B.ToString();
}