57
WIKIOI-1148 傳球遊戲
題目描述 Description
上體育課的時候，小蠻的老師經常帶著同學們一起做遊戲。這次，老師帶著同學們一起做傳球遊戲。
遊戲規則是這樣的：n個同學站成一個圓圈，其中的一個同學手裏拿著一個球，當老師吹哨子時開始傳球，每個同學可以把球傳給自己左右的兩個同學中的一個（左右任意），當老師再次吹哨子時，傳球停止，此時，拿著球沒傳出去的那個同學就是敗者，要給大家表演一個節目。
聰明的小蠻提出一個有趣的問題：有多少種不同的傳球方法可以使得從小蠻手裏開始傳的球，傳了m次以後，又回到小蠻手裏。兩種傳球的方法被視作不同的方法，當且僅當這兩種方法中，接到球的同學按接球順序組成的序列是不同的。比如有3個同學1號、2號、3號，並假設小蠻為1號，球傳了3次回到小蠻手裏的方式有1->2->3->1和1->3->2->1，共2種。
輸入描述 Input Description
共一行，有兩個用空格隔開的整數n，m（3<=n<=30，1<=m<=30）。
輸出描述 Output Description
共一行，有一個整數，表示符合題意的方法數。
樣例輸入 Sample Input
3 3
樣例輸出 Sample Output
2
數據範圍及提示 Data Size & Hint
40%的數據滿足：3<=n<=30，1<=m<=20
100%的數據滿足：3<=n<=30，1<=m<=30
用深入搜索超時：
#include<stdio.h>
int m,mix=0;
void Found(int x,int sum,int n)
{
if(sum==m&&x==1)
{mix++;return;}
if(sum>m)
return;
if(x!=1&&x!=n)
{
Found(x+1,sum+1,n);
Found(x-1,sum+1,n);
}
if(x==1)
{
Found(x+1,sum+1,n);
Found(n,sum+1,n);
}
if(x==n)
{
Found(1,sum+1,n);
Found(x-1,sum+1,n);
}
}
int main()
{
int i,j,n;
scanf("%d%d",&n,&m);
Found(1,0,n);
printf("%d\n",mix);
return 0;
}
AC代碼：
//動態規劃
#include<stdio.h>
int dp[100][100];
int main()
{
int i,j,n,m;
scanf("%d%d",&n,&m);
dp[0][1]=1;
for(i=1;i<=m;i++)//i代表第i次傳遞，j代表第j人
for(j=1;j<=n;j++)
{
if(j-1<1)
dp[i][j]=dp[i-1][n]+dp[i-1][j+1];
else if(j==n)
dp[i][j]=dp[i-1][1]+dp[i-1][j-1];
else dp[i][j]=dp[i-1][j+1]+dp[i-1][j-1];//狀態轉移方程
}
printf("%d\n",dp[m][1]);
return 0;
}
最後更新：2017-04-03 12:55:22