#1776. 标准汉诺塔问题

标准汉诺塔问题

题目描述

楚继光报怨道:“能量盘为什么要这样移动?真够麻烦的。”

“因为这样移动,暗含宇宙运行的奥义,它能够产生巨大的魔法力,将修罗王的魔法炮阵灭成渣。”墨老师一副高深莫测的神情。

如图所示,已知魔法学院的防御系统的能量模块上有三根柱子a\red ab\red bc\red c,能量盘为中间有孔的圆盘状,能量盘直径依次递减,初始时b\red b柱、c\red c柱为空,所有盘片套在a\red a柱上,并且上面的盘片总是比下面的盘片小,现需将a\red a柱上的能量盘通过b\red b柱移到c\red c柱上,规则是每次移动只能移动最上面的能量盘,而且保持任何柱子上的能量盘的排列均是上面的盘片比下面的盘片要小。试问需要移动多少次?

img

输入格式

一个整数n\red n,表示n\red n个盘。

输出格式

一个整数,表示需要移动的次数。

样例

输入样例

输出样例