文档章节

河内塔问题(C++版)

o
 osc_a22drz29
发布于 2019/03/24 14:35
字数 517
阅读 5
收藏 0
c++

上次,我们讲了汉诺塔,今天我们来讲一讲和汉诺塔类似的题目《河内塔问题》

题目描述 Description

一位法国数学家曾编写过一个印度的古老传说:在世界中心贝拿勒斯(在印度北部)的圣庙里,一块黄铜板上插着三根宝石针。印度教的主神梵天在创造世界的时候,在其中一根针上从下到上地穿好了由大到小的64片金片,这就是所谓的汉诺塔。不论白天黑夜,总有一个僧侣在按照下面的法则移动这些金片:一次只移动一片,不管在哪根针上,小片必须在大片上面。僧侣们预言,当所有的金片都从梵天穿好的那根针上移到另外一根针上时,世界就将在一声霹雳中消灭,而梵塔、庙宇和众生也都将同归于尽。

河内塔(又称汉诺塔)问题,就是在一块木板上有三个立柱,在柱1上放着若干个圆盘,小的在上面,大的在下面(初始状态)。请将在柱1上的三个圆盘移到柱3上面(目标状态)。 移动规则是: (1) 每次只能移动一个圆盘; (2) 大圆盘不能放到小圆盘的上面。 请你计算至少需要移动多少次才能将柱1上的n个圆从小到大的圆盘移动到柱3上。

输入描述 Input Description

n

输出描述 Output Description

将柱1上的n个圆从小到大的圆盘移动到柱3上的最少移动次数

样例输入 Sample Input

3

样例输出 Sample Output

7

 

参考答案(C++版)Reference answer (C++ version):

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 int k=0;
 4 void f(int n,char a,char b,char c)
 5 {
 6     if(n==0)return;
 7     f(n-1,a,c,b);
 8     k++;
 9     f(n-1,c,b,a);
10 }
11 int main()
12 {
13     int n;
14     cin>>n;
15     f(n,'a','b','c');
16     cout<<k;
17 }

 

o
粉丝 0
博文 500
码字总数 0
作品 0
私信 提问
加载中
请先登录后再评论。

暂无文章

Java 获取资源文件路径

1 问题描述 通过源码运行时,一般使用如下方式读取资源文件: String str = "1.jpg"; 资源文件与源码文件放在同一目录下,或者拥有同一父级目录: String str = "a/b/1.jpg"; 这样直接编译...

氷泠
8分钟前
4
0
Linux程序移植到Android上

序言: 由于本人还是比较偏重于先说明原理在说明实际操作步骤,要知其然更要知其所以然,如下图所示: 传统的linux系统中的程序基本都依赖于glibc(至于什么是glibc可以百度去),而右边AOS...

shzwork
20分钟前
17
0
git 为项目设置用户名/邮箱/密码

1.找到项目所在目录下的 .git,进入.git文件夹,然后执行如下命令分别设置用户名和邮箱 git config user.name "Affandi" git config user.email "123333333@qq.com" 然后执行命令查看con......

有时很滑稽
52分钟前
0
0
如何从int转换为String? - How do I convert from int to String?

问题: I'm working on a project where all conversions from int to String are done like this: 我正在一个项目中,所有从int到String转换都是这样完成的: int i = 5;String strI = "" ......

javail
今天
10
0
Vue+Spring Data JPA+MySQL 增查改删

视频讲解: https://www.bilibili.com/video/BV16i4y1G7i2/ 工程概述: 前后端分离,进行简单增查改删(CRUD) 前端使用VUE 后端使用Spring Data JPA 数据库使用MySQL #EmployeeController.jav...

潘文海
今天
13
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部