递归函数的关键在于第n项问题与第n-1项问题的关系在哪先以能够说明问题的三圆盘汉诺塔为例子最终目的是将三个圆盘全部挪到第三根柱子第二根也行此时这两根空柱子是等价的由于大圆盘必须在下面可以得到的首要目标是把三号盘放到柱子3易得三号盘放到柱子3的前提是一号盘与二号盘在柱子2三号盘到达柱子3后的目标是把在柱子2的一号盘和二号盘挪到柱子3经过这个过程可以把n个盘子从柱子1挪到柱子3的步骤拆为三步1将n-1个盘挪到柱子22将n号盘挪到柱子33将n-1个盘挪到柱子3此时发现将n-1个盘子挪到柱子2本质上与将n个盘子挪到柱子3类似由此递归成立而且可以推测出递归到最后的问题是将一个盘子挪到某个柱子上。#include stdio.h void move(int n ,int pole1,int pole2) { static int step 1; printf(%03d:[disk %d] : %c -- %c\n,step,n,pole1,pole2); } //起始柱 辅助柱 目标柱 void hanoi(int n, int A, int B, int C) { if (1n) { move(n,A,C); }else { hanoi(n-1,A,C,B); //n-1 先挪走 puts(-------); move(n,A,C); // 将第n个 挪到 目标柱 puts(-------); hanoi(n-1,B,A,C); } } int main(void) { int n 0; printf(Input numbers of disk: ); scanf(%d,n); hanoi(n,A,B,C); return 0; }
递归函数的关键在于第n项问题与第n-1项问题的关系在哪先以能够说明问题的三圆盘汉诺塔为例子最终目的是将三个圆盘全部挪到第三根柱子第二根也行此时这两根空柱子是等价的由于大圆盘必须在下面可以得到的首要目标是把三号盘放到柱子3易得三号盘放到柱子3的前提是一号盘与二号盘在柱子2三号盘到达柱子3后的目标是把在柱子2的一号盘和二号盘挪到柱子3经过这个过程可以把n个盘子从柱子1挪到柱子3的步骤拆为三步1将n-1个盘挪到柱子22将n号盘挪到柱子33将n-1个盘挪到柱子3此时发现将n-1个盘子挪到柱子2本质上与将n个盘子挪到柱子3类似由此递归成立而且可以推测出递归到最后的问题是将一个盘子挪到某个柱子上。#include stdio.h void move(int n ,int pole1,int pole2) { static int step 1; printf(%03d:[disk %d] : %c -- %c\n,step,n,pole1,pole2); } //起始柱 辅助柱 目标柱 void hanoi(int n, int A, int B, int C) { if (1n) { move(n,A,C); }else { hanoi(n-1,A,C,B); //n-1 先挪走 puts(-------); move(n,A,C); // 将第n个 挪到 目标柱 puts(-------); hanoi(n-1,B,A,C); } } int main(void) { int n 0; printf(Input numbers of disk: ); scanf(%d,n); hanoi(n,A,B,C); return 0; }
