【C】C语言之经典算法：河内之塔(1)

末蓝、 2022-04-08 12:16 186阅读 0赞

### 文章目录 ###

*   *  前言
     *  一、背景
     *  二、思路解析
     *  三、流程图解析
     *  四、代码附上
     *  五、结果
     *  六、参考链接

【C】C语言之经典算法：河内之塔(1)

## 前言 ##

博主开通了C语言算法专栏，旨在对于有关C语言的一些经典算法的学习。

## 一、背景 ##

> 算法一：河内之塔  
> 故事来源：  
>       说明河内之塔(Towers of Hanoi)是法国人M.Claus(Lucas)于1883年从泰国带至法国的，河内为越  
> 战时北越的首都，即现在的胡志明市；1883年法国数学家Edouard Lucas曾提及这个故事，据说创世  
> 纪时Benares有一座波罗教塔，是由三支钻石棒（Pag）所支撑，开始时神在第一根棒上放置64个由上  
> 至下依由小至大排列的金盘（Disc），并命令僧侣将所有的金盘从第一根石棒移至第三根石棒，且搬  
> 运过程中遵守大盘子在小盘子之下的原则，若每日仅搬一个盘子，则当盘子全数搬运完毕之时，此塔  
> 将毁损，而也就是世界末日来临之时。

## 二、思路解析 ##

> 思路分析：  
>        如果柱子标为ABC，要由A搬至C，在只有一个盘子时，就将它直接搬至C，当有两个盘子，就  
> 将B当作辅助柱。如果盘数超过2个，将第三个以下的盘子遮起来，就很简单了，每次处理两个盘子，  
> 也就是：A->B、A->C、B->C这三个步骤，而被遮住的部份，其实就是进入程式的递回处理。事实  
> 上，若有n个盘子，则移动完毕所需之次数为2^n -1，所以当盘数为64时，则所需次数为：  
> 264- 1 =18446744073709551615为5.05390248594782e+16年，也就是约5000世纪， 如果对这  
> 数字没什幺概念，就假设每秒钟搬一个盘子好了，也要约5850亿年左右。

思路总结：  
      将上面n-1个盘子看成一个盘子（做递归），第n个做为一个盘子，即移动两个盘子：  
      第一步：将n-1个从Ａ移到B  
      第二步：将第n个从A移到C  
      第三步：将n-1个从B移到C

## 三、流程图解析 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0ppYWppa2FuZ19qams_size_16_color_FFFFFF_t_70]

## 四、代码附上 ##

/* 算法一：河内之塔 故事来源： 说明河内之塔(Towers of Hanoi)是法国人M.Claus(Lucas)于1883年从泰国带至法国的，河内为越 战时北越的首都，即现在的胡志明市；1883年法国数学家Edouard Lucas曾提及这个故事，据说创世 纪时Benares有一座波罗教塔，是由三支钻石棒（Pag）所支撑，开始时神在第一根棒上放置64个由上 至下依由小至大排列的金盘（Disc），并命令僧侣将所有的金盘从第一根石棒移至第三根石棒，且搬 运过程中遵守大盘子在小盘子之下的原则，若每日仅搬一个盘子，则当盘子全数搬运完毕之时，此塔 将毁损，而也就是世界末日来临之时。 程序功能： A，B，C三个柱子，实现A柱子旁n个盘子一次搬一个搬至到C柱子 思路分析： 如果柱子标为ABC，要由A搬至C，在只有一个盘子时，就将它直接搬至C，当有两个盘子，就 将B当作辅助柱。如果盘数超过2个，将第三个以下的盘子遮起来，就很简单了，每次处理两个盘子， 也就是：A->B、A->C、B->C这三个步骤，而被遮住的部份，其实就是进入程式的递回处理。事实 上，若有n个盘子，则移动完毕所需之次数为2^n -1，所以当盘数为64时，则所需次数为： 264- 1 =18446744073709551615为5.05390248594782e+16年，也就是约5000世纪， 如果对这 数字没什幺概念，就假设每秒钟搬一个盘子好了，也要约5850亿年左右。 */
    
    #include <stdio.h>
    void hanoi(int n, char A, char B, char C);
    
    // 主函数
    int main(void) { 
      int n;
      printf("请输入盘数：");
      scanf("%d", &n); // 输入n
      hanoi(n, 'A', 'B', 'C');
    
      return 0;
    }
    
    // 定义函数
    void hanoi(int n, char A, char B, char C) { 
      if (n == 1) // 当盘数n=1时直接搬至：c
      { 
        printf("移动%d 从%c-->%c\n", n, A, C); // A-C
      } else { 
        hanoi(n - 1, A, C, B); // 调用函数
        printf("移动%d 从%c-->%c\n", n, A, C); // A-C
        hanoi(n - 1, B, A, C);// 调用函数
         
      }
    }

## 五、结果 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0ppYWppa2FuZ19qams_size_16_color_FFFFFF_t_70 1]

## 六、参考链接 ##

1、[https://blog.csdn.net/qq\_34637408/article/details/78445816][https_blog.csdn.net_qq_34637408_article_details_78445816]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0ppYWppa2FuZ19qams_size_16_color_FFFFFF_t_70]: /images/20220405/08b42cb671e44738b12e6a9e55f5f7fb.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0ppYWppa2FuZ19qams_size_16_color_FFFFFF_t_70 1]: /images/20220405/6e7bc03fc90840ccba6f1e0308b8423a.png
[https_blog.csdn.net_qq_34637408_article_details_78445816]: https://blog.csdn.net/qq_34637408/article/details/78445816