C语言汉诺塔数列(循环版,递归版)

简介: C语言汉诺塔数列(循环版,递归版)

C语言汉诺塔数列(循环版)

汉诺塔是一个源于印度古老传说的益智玩具。据说大梵天创造世界的时候做了三根金刚石柱子,在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘,大梵天命令僧侣把圆盘移到另一根柱子上,并且规定:在小圆盘上不能放大圆盘,每次只能移动一个圆盘。当所有圆盘都移到另一根柱子上时,世界就会毁灭。

1, 3, 7, 15, 31, 63, 127, 255, 511, 1023, …

第 1 项为 1,表明移动 1 片圆盘的汉诺塔需 1 步;第 2 项为 3,表明移动 2 片圆盘的汉诺塔需 3 步;……,以此类推。请编写递归函数,求汉诺塔数列中任一项的值。

函数原型

double NumHanoi(int index);

说明:参数 index 为索引号(正整数),函数值为汉诺塔数列第 index 项的值。

要求:不要使用选择语句。不要调用 pow、exp 等数学函数

裁判程序

#include <stdio.h>
double NumHanoi(int index);
int main()
{
    int n;
    scanf("%d", &n);
    printf("%.15g\n", NumHanoi(n));
    return 0;
}

/* 你提交的代码将被嵌在这里 */

输入样例1

3

输出样例1

7

输入样例2

45

输出样例2

35184372088831

提交代码:

算法思路:该算法的思路为,通过分析题目的情况,然后可以得到的这个汉诺塔的公式为2^n - 1,对于汉诺塔的总层数。

double NumHanoi(int index)
{
  int i = 1;
  double result = 1;
  while (i < index)
  {
    result = 2 * result + 1;
    i++;
  }
  return result;
}

递归版

汉诺塔问题

分数 10

作者 李祥

单位 湖北经济学院

汉诺塔是一个源于印度古老传说的益智玩具。据说大梵天创造世界的时候做了三根金刚石柱子,在一根柱子上从下往上按照大小顺序摞着 64 片黄金圆盘,大梵天命令僧侣把圆盘移到另一根柱子上,并且规定:在小圆盘上不能放大圆盘,每次只能移动一个圆盘。当所有圆盘都移到另一根柱子上时,世界就会毁灭。

请编写函数,完成移动汉诺塔的任务。

函数原型

void MoveTower(int num, char src, char dst, char trs);

说明:参数 num 为金片数,src、dst 和 trs 分别为起始柱、目的柱和过渡柱。若金片数大于 0,则函数将金片组成的汉诺塔由起始柱利用过渡柱最终搬到目的柱,否则什么也不做。

下面的程序,输入汉诺塔圆片的数量,输出移动汉诺塔的步骤。

裁判程序

`

#include <stdio.h>

void MoveTower(int num, char src, char dst, char trs);

int main()

{

int n;

char s, d, t;

scanf(“%d %c %c %c”, &n, &s, &d, &t);

MoveTower(n, s, d, t);

return 0;

}

`

/* 你提交的代码将被嵌在这里 */

输入格式

圆盘数

起始柱 目的柱 过渡柱

输出格式

移动汉诺塔的步骤

每行显示一步操作,具体格式为:

盘片号: 起始柱 -> 目的柱

其中盘片号从 1 开始由小到大顺序编号。

输入样例

3

a c b

输出样例

1: a -> c

2: a -> b

1: c -> b

3: a -> c

1: b -> a

2: b -> c

1: a -> c

提交代码

void MoveTower(int num, char src, char dst, char trs)
{
  if(num > 0)
  {
    MoveTower(num - 1,src,trs,dst);
    printf("%d: %c -> %c\n",num,src,dst);
    MoveTower(num - 1,trs,dst,src);
  }
}


相关文章
|
8天前
|
C语言
爱上C语言:分支与循环(分支篇)多个if与if — else if区别
爱上C语言:分支与循环(分支篇)多个if与if — else if区别
|
29天前
|
C语言
利用C语言中的while语句实现循环
利用C语言中的while语句实现循环
18 0
|
1月前
|
C语言
C语言的循环程序
C语言的循环程序
11 0
|
1月前
|
机器学习/深度学习 存储 C语言
c语言从入门到实战——函数递归
函数递归是指一个函数直接或间接地调用自身,以解决问题的一种方法。在C语言中,函数递归可以用来计算阶乘、斐波那契数列等数学问题。 函数递归是一种编程技术,其中函数直接或间接地调用自身来解决问题。它常用于处理可以分解为更小同类问题的复杂问题,如排序、搜索树等。递归的基本思想是将问题分解为更简单的子问题,然后组合子问题的解来得到原问题的解。然而,递归需要小心处理终止条件,否则可能导致无限循环。此外,递归可能消耗大量内存,因为它需要存储每个递归调用的状态。因此,在使用递归时,应仔细考虑其效率和适用性。
30 0
|
1月前
|
C语言
介绍c语言中的分支,循环
介绍c语言中的分支,循环
22 0
|
1月前
|
C语言
C语言递归问题【青蛙跳台阶】和【汉诺塔】
C语言递归问题【青蛙跳台阶】和【汉诺塔】
|
15天前
|
C语言
【C语言】“分⽀与循环第一章:开启创新之门,探索无尽可能性的第一篇章“2
【C语言】“分⽀与循环第一章:开启创新之门,探索无尽可能性的第一篇章“2
|
16天前
|
C语言 索引
【C语言】C语言⻘蛙跳台阶问题--递归问题
【C语言】C语言⻘蛙跳台阶问题--递归问题
|
29天前
|
算法 大数据 Serverless
C语言递归
C语言递归
10 0
|
1月前
|
机器学习/深度学习 程序员 编译器
c语言从入门到实战——分支和循环
C语言是结构化的程序设计语言,这里的结构指的是顺序结构、选择结构、循环结构,C语言是能够实 现这三种结构的,其实我们如果仔细分析,我们日常所见的事情都可以拆分为这三种结构或者这三种结构的组合。 我们可以使用 if 、 switch 实现分支结构,使用 for 、 while 、 do while 实现循环结构。
77 0
c语言从入门到实战——分支和循环