1734: 【基础】传手巾游戏 【递推】【含视频教程】

Memory Limit:128 MB Time Limit:1.000 S
Judge Style:Text Compare Creator:
Submit:1 Solved:1

Description

有N个小朋友围成一圈在做传手巾的游戏,游戏规定,每个人手中的手巾只能传递给自己右边的第一个人或者第二个人。

问手巾从小强手中传出,已经一圈又回到小强手中,共有多少种不同的传法?

Input

输入N,N<=30

Output

输出不同传法的数量

Sample Input Copy

10

Sample Output Copy

89

HINT

关于此题解法的小学6年级的递推与归纳的视频教程:

http://v.youku.com/v_show/id_XMzU0MTkyNTI=.html

Source/Category