小疑点,大思路
小问题,大思路
看了所有汉诺塔的帖子,请不要转贴了
class Towers
{
public static void Main()
{
towers(4, 'a ', 'c ', 'b ');
Console.ReadLine();
}
public static void towers(int n, char fromPeg, char toPeg, char auxPeg)
{
if (n == 1)
{
Console.WriteLine( "move disk 1 from peg " + fromPeg + " to peg " + toPeg);
return;
}
towers(n - 1, fromPeg, auxPeg, toPeg);
Console.WriteLine( "move disk " + n + " from peg " + fromPeg + " to peg " + toPeg);
towers(n - 1, auxPeg, toPeg, fromPeg);
}
}
这个程序分三个步骤完成,第一步,执行第一个递归函数,第二步执行输出,第三步执行第三个递归函数,第一步是要完成n-1个塔向B柱转移,分解为n-2个塔向c转移(函数1),再把n-1向b柱转移(输出语句2),再把n-2向b柱转移(函数3),这个思想能搞明白,但每次调用的参数规律不知是不是,第一个函数acb,abc,acb,abc……
第二个函数是bca,acb,bca,acb…… 递归函数的参数是怎么确定的
------解决方案--------------------
// 如果n=1,则将圆盘从A直接移动到C。
// 如果n=2,则:
// 1.将A上的n-1(等于)个圆盘移到B上;
// 2.再将A上的一个圆盘移到C上;
// 3.最后将B上的n-1(等于)个圆盘移到C上。
// 如果n=3,则:
// A. 将A上的n-1(等于,令其为n`)个圆盘移到B(借助于C),步骤如下:
// (1)将A上的n`-1(等于)个圆盘移到C上。
// (2)将A上的一个圆盘移到B。
// (3)将C上的n`-1(等于)个圆盘移到B。
// B. 将A上的一个圆盘移到C。
// C. 将B上的n-1(等于,令其为n`)个圆盘移到C(借助A),步骤如下:
// (1)将B上的n`-1(等于)个圆盘移到A。
// (2)将B上的一个盘子移到C。
// (3)将A上的n`-1(等于)个圆盘移到C。
// 到此,完成了三个圆盘的移动过程。
// 从上面分析可以看出,当n大于等于时,移动的过程可分解为三个步骤:
// 第一步 把A上的n-1个圆盘移到B上;
// 第二步 把A上的一个圆盘移到C上;
// 第三步 把B上的n-1个圆盘移到C上;其中第一步和第三步是类同的。
// 当n=3时,第一步和第三步又分解为类同的三步,即把n`-1个圆盘从一个针移到另一个针上,这里
// 的n`=n-1。显然这是一个递归过程
// 从程序中可以看出,move函数是一个递归函数,它有四个形参n,x,y,z。n表示圆盘数,x,y,z分别表示三根
// 针。move 函数的功能是把x上的n个圆盘移动到z上。当n==1时,直接把x上的圆盘移至z上,输出x→z。如
// n!=1则分为三步:递归调用move函数,把n-1个圆盘从x移到y;输出x→z;递归调用move函数,把n-1个圆
看了所有汉诺塔的帖子,请不要转贴了
class Towers
{
public static void Main()
{
towers(4, 'a ', 'c ', 'b ');
Console.ReadLine();
}
public static void towers(int n, char fromPeg, char toPeg, char auxPeg)
{
if (n == 1)
{
Console.WriteLine( "move disk 1 from peg " + fromPeg + " to peg " + toPeg);
return;
}
towers(n - 1, fromPeg, auxPeg, toPeg);
Console.WriteLine( "move disk " + n + " from peg " + fromPeg + " to peg " + toPeg);
towers(n - 1, auxPeg, toPeg, fromPeg);
}
}
这个程序分三个步骤完成,第一步,执行第一个递归函数,第二步执行输出,第三步执行第三个递归函数,第一步是要完成n-1个塔向B柱转移,分解为n-2个塔向c转移(函数1),再把n-1向b柱转移(输出语句2),再把n-2向b柱转移(函数3),这个思想能搞明白,但每次调用的参数规律不知是不是,第一个函数acb,abc,acb,abc……
第二个函数是bca,acb,bca,acb…… 递归函数的参数是怎么确定的
------解决方案--------------------
// 如果n=1,则将圆盘从A直接移动到C。
// 如果n=2,则:
// 1.将A上的n-1(等于)个圆盘移到B上;
// 2.再将A上的一个圆盘移到C上;
// 3.最后将B上的n-1(等于)个圆盘移到C上。
// 如果n=3,则:
// A. 将A上的n-1(等于,令其为n`)个圆盘移到B(借助于C),步骤如下:
// (1)将A上的n`-1(等于)个圆盘移到C上。
// (2)将A上的一个圆盘移到B。
// (3)将C上的n`-1(等于)个圆盘移到B。
// B. 将A上的一个圆盘移到C。
// C. 将B上的n-1(等于,令其为n`)个圆盘移到C(借助A),步骤如下:
// (1)将B上的n`-1(等于)个圆盘移到A。
// (2)将B上的一个盘子移到C。
// (3)将A上的n`-1(等于)个圆盘移到C。
// 到此,完成了三个圆盘的移动过程。
// 从上面分析可以看出,当n大于等于时,移动的过程可分解为三个步骤:
// 第一步 把A上的n-1个圆盘移到B上;
// 第二步 把A上的一个圆盘移到C上;
// 第三步 把B上的n-1个圆盘移到C上;其中第一步和第三步是类同的。
// 当n=3时,第一步和第三步又分解为类同的三步,即把n`-1个圆盘从一个针移到另一个针上,这里
// 的n`=n-1。显然这是一个递归过程
// 从程序中可以看出,move函数是一个递归函数,它有四个形参n,x,y,z。n表示圆盘数,x,y,z分别表示三根
// 针。move 函数的功能是把x上的n个圆盘移动到z上。当n==1时,直接把x上的圆盘移至z上,输出x→z。如
// n!=1则分为三步:递归调用move函数,把n-1个圆盘从x移到y;输出x→z;递归调用move函数,把n-1个圆