A19850. 击鼓传花
填空题
容易
知识点
题目描述
击鼓传花
题目描述
击鼓传花，也称传彩球，是中国传统的民间游戏。现在编号为1至n的n名同学按编号次序顺时针围坐成一圈，小明坐在1号位置，他左手边是2号，右手边是n号。彩花开始在小明手里，鼓声响起之后，小明可以把花传递给2号同学，也可以传递给n号同学，接到花的同学可以随意选择向左还是向右传递。鼓声停止时，花在谁的手里谁就要表演节目。请问有多少种传递方法使得从小明手里开始传递的花，传了m次后，又回到小明手里。
两种传递方法被认为不同，当且仅当这两种方法中，接到球的同学按照顺序组成的序列是不同的。比如3个同学1号、2号、3号，小明为1号，球传了2次回到小明手里方法有1->2->1，和1->3->1两种，球传了3次回到小明手里的方式有1->2->3->1和1->3->2->1两种。
输入格式
仅一行，正整数n和m。（3<=n，m<=10）。
输出格式
一个整数，表示传递m次后花又回到小明手里的传递方法数。
输入样例1
6 5输出样例1
0输入样例2
4 4输出样例2
8提示
样例1说明：6个人传5次，不可能回到1号，答案是0；
样例2说明：4个人传4次，共有8种方法1->2->1->2->1，1->2->3->2->1，1->2->3->4->1，1->2->1->4->1，1->4->1->4->1，1->4->3->4->1，1->4->3->2->1，1->4->1->2->1。
参考答案
#include <stdio.h>
#include <iostream>
#include <algorithm>
using namespace std;
int main(int argc, char *argv[])
{
int i,j,k,x,m,n;
int dp[31][31];
scanf("%d %d",&n,&m);//n个人,传m次
memset(dp,0,sizeof(dp));
dp[0][1]=1;
for(i=1;i<=m;i++){
for(j=1;j<=n;j++){
if(j==n) dp[i][j]=dp[i-1][1]+dp[i-1][n-1];//最后一个人
else if(j==1) dp[i][j]=dp[i-1][2]+dp[i-1][n];//第一个人
else dp[i][j]=dp[i-1][j+1]+dp[i-1][j-1];
}
}
printf("%d\n",dp[m][1]);
return 0;
}
上一题
下一题