【c语言】每日一题之汉诺塔类型-Toy模板网

这篇具有很好参考价值的文章主要介绍了【c语言】每日一题之汉诺塔类型。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

前言

大佬们，我又回来了，最近也在忙自己的学业，忙着生活对线，也参加了今年的蓝桥杯其他的组，发现今年太难了，摆烂了。但我想到了读者你们，从今天开始继续更新博客。通过写一篇我随便写的有趣的题，打开今年的博客之旅。
【c语言】每日一题之汉诺塔类型

题目说明

BC161 大吉大利，今晚吃鸡

描述

糖和抖m在玩个游戏，规定谁输了就要请谁吃顿大餐：抖m给糖a b c三个驻，并在a柱上放置了数量为n的圆盘，圆盘的大小从上到下依次增大，现在要做的事就是把a柱的圆盘全部移到c柱，移动的过程中保持小盘在上，大盘在下，且限定圆盘只能够移动到相邻的柱子，即a柱子上的圆盘只能够移动到b，b柱子上的圆盘只能够移动到a或者c，c同理。现在请你设计一个程序，计算所需移动的最小步数，帮助糖赢得大餐！

输入描述：
每一行输出有一个整数n(0<=n<26), 直至文件末尾。
输出描述：
对于每一组数据，输出一行，输出移动的最小步数M。

题目分析

对于本题，本质上和汉诺塔十分相似。我主要想说说怎么去求解其递推关系。

汉诺塔问题

相传在古印度圣庙中，有一种被称为汉诺塔(Hanoi)的游戏。该游戏是在一块铜板装置上，有三根杆(编号A、B、C)，在A杆自下而上、由大到小按顺序放置64个金盘(如下图)。游戏的目标：把A杆上的金盘全部移到C杆上，并仍保持原有顺序叠好。操作规则：每次只能移动一个盘子，并且在移动过程中三根杆上都始终保持大盘在下，小盘在上，操作过程中盘子可以置于A、B、C任一杆上。

我们先来对汉诺塔的步数进行一下递推。
对于n个盘子，我们可以把它分成个盘子和最后一个大盘子。设为移动所需步数,那么对于个盘子来说所做的事情就是将个盘子借助C柱移动到B柱上,这一过程移动的步数为,下一步我们将大盘子移动到C柱上，此时需要一步，最后，我们再将个盘子借助A柱移动到C柱上，此时需要的步数仍为。综合以上分析，。对两边同时加上1可以凑成一个等比数列，然后就可以求出其通项公式。

对于本题，我们依然可以按照刚才的思路来进行递推。
同样的，对于n个盘子，我们可以把它分成个盘子和最后一个大盘子。
同样设为移动所需步数。

将个盘子借助B柱移动到C柱上,这一过程移动的步数极为
将大盘子由A柱移动到B柱上，此时需要一步
将个盘子借助B柱移动到A柱上,这一过程移动的步数同样为
将大盘子由B柱移动到C柱上，此时需要一步
将个盘子借助B柱子移动到C柱上，此时需要的步数仍为。
综合以上分析，。同样，对两边同时加上1可以凑成一个等比数列，最后求出其通项公式即为。

题目代码展示

#include<stdio.h>
int main()
{
    int n=0;
    while(scanf("%d",&n)!=EOF)
    {
    int i=0;
    int num=1;

    for(i=0;i<n;i++)
    {
        num*=3;
     
    }
    printf("%d\n",num-1);
   
    }
}