那年的埃菲尔

用户名：18839270274

访问量：19051

签　名：

我只是个蒟蒻(⊙o⊙);

等　　级
排　　名	190
经　　验	6652
参赛次数	1
文章发表	50
年　　龄	0
在职情况	学生
学　　校	郑州大学
专　　业	计算机科学与技术

　　自我简介：

欢迎加我QQ交流 540671670

TA的其他文章

文科生的悲哀-题解(C语言代码)
浏览：443

整除的尾数-题解(C语言代码)
浏览：241

蓝桥杯2014年第五届真题-兰顿蚂蚁-题解(C/C++语言代码)（简单解法）
浏览：476

你可能喜欢

C语言程序设计教程（第三版）课后习题9.10 （C语言代码）

Hanoi双塔问题-题解(C语言代码)

　　作者: 那年的埃菲尔　　　　发表时间：2020-01-21 20:35:17 浏览：454　|　评论：0　

#### 原题链接：[问题 1109: Hanoi双塔问题][18839270274]
[18839270274]: https://www.dotcpp.com/oj/problem1109.html "问题 1109: Hanoi双塔问题"

#### 解题思路：
类似大数运算。

双盘汉诺塔和单盘汉诺塔的移动次数只有一个区别，那就是双盘的比单盘的移动次数多一倍
现在来分析单盘的汉诺塔：

当只有一个盘的时候，只需要移动一次；

当有两个盘的时候，只需要移动三次，（最上层的那个盘需要移动两次，下面的那个盘移动一次）

当盘数为n时（n>=2），我们可以将上面的n-1层看成一个盘，由于初始摆放顺序是从上往下盘子由小到大，因此，无论上面的哪个盘都是小于最底下那个盘的，而上面n-1个盘组合成的大盘移动一次所需要搬动盘子的次数，实际上就是将这n-1个盘子从一个柱子搬到另一个柱子所需要搬动的次数，我们可以再根据刚刚所分析的方法，将n-1个盘子上面的n-1个盘子当做一个盘子，以此类推，直到上面的大盘只包含一个盘子

刚刚上面也分析到有两个盘子的时候，上面的那个盘子需要移动两次，下面的盘子是一次，设n个盘需要移动的次数是f(n),上面n-1个盘需要移动的次数是f(n-1)，那么就有递推式f(n)=2*f(n-1)+1;

输出双盘汉诺塔结果

#### 参考代码：
```c
//输入为一个正整数n，表示在A柱上放有2n个圆盘。
#include<stdio.h>
int main()
{
	int n;
	int a[1000];	//用于存放结果 
		a[0] = 1;		//初始是1，也就是只有一个盘的时候只需搬动一次
	int len = 1;			//存储数组a的长度
		scanf("%d",&n);
	int flag = 0,i,j = 0;
	
	for( i = 0 ; i < n-1 ; i++)
	{
		flag = 0;
		
		for( j = 0 ; j < len ; j++)
		{
			if( j == 0 )			
			//由于递推式是f(n)=2*f(n-1)+1,由于这里乘2是通过翻倍的方式的，因此1可直接在个位加上，后面就不用再单独进行相加
				flag = 2*a[j]+flag+1;
			else
				flag = 2*a[j]+flag;
				
				a[j] = flag%10;
				flag/=10;
		}
		
		if( flag != 0 )		//如果进位不等于0的话，说明最高位就是这个进位，因此将它放到最高位
			a[j++] = flag;
			
			len = j;		//len是数组长度，且是新长度 
	}
	 /*由于是双盘，实际上也就是在单盘的基础上乘2，下面的代码就是乘2*/
	for( j = 0 , flag = 0 ; j < len ; j++)
	{
		flag = 2*a[j]+flag;
		a[j] = flag%10;
		flag/=10;
	}
	
	if( flag!= 0 )
		a[j++] = flag;
	 	len = j;
	//输出结果 
	for( i = len-1 ; i >= 0 ; i--)
		printf("%d",a[i]);
		printf("\n");
	return 0;
 } 
```

0.0分

3 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

那年的埃菲尔

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题9.10 （C语言代码）

C语言程序设计教程（第三版）课后习题8.5 （C语言代码）

C语言程序设计教程（第三版）课后习题8.8 （C语言代码）

采药（C++代码）

点我有惊喜！你懂得！

Hanoi双塔问题-题解(C语言代码)

评论区

精彩推荐

C语言训练-谁家孩子跑最慢* （C语言代码）

C语言程序设计教程（第三版）课后习题12.5 （C语言代码）

C语言程序设计教程（第三版）课后习题6.3 （C语言代码）

C语言程序设计教程（第三版）课后习题11.5 （C语言代码）

2003年秋浙江省计算机等级考试二级C 编程题(2) （C语言代码）

C语言程序设计教程（第三版）课后习题8.6 （C语言代码）

ASCII帮了大忙

妹子杀手的故事（C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

用筛法求之N内的素数。（C++代码）

那年的埃菲尔

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题9.10 （C语言代码）

C语言程序设计教程（第三版）课后习题8.5 （C语言代码）

C语言程序设计教程（第三版）课后习题8.8 （C语言代码）

采药 （C++代码）

点我有惊喜！你懂得！

Hanoi双塔问题-题解(C语言代码)

评论区

精彩推荐

C语言训练-谁家孩子跑最慢* （C语言代码）

C语言程序设计教程（第三版）课后习题12.5 （C语言代码）

C语言程序设计教程（第三版）课后习题6.3 （C语言代码）

C语言程序设计教程（第三版）课后习题11.5 （C语言代码）

2003年秋浙江省计算机等级考试二级C 编程题(2) （C语言代码）

C语言程序设计教程（第三版）课后习题8.6 （C语言代码）

ASCII帮了大忙

妹子杀手的故事 （C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

用筛法求之N内的素数。 （C++代码）

采药（C++代码）

　　评论区

妹子杀手的故事（C语言代码）

用筛法求之N内的素数。（C++代码）