學校聯歡晚會的時候，為了使每一個同學都能參與進來，主持人常常會帶著同學們玩擊鼓傳花的遊戲。遊戲規則是這樣的：n個同學坐著圍成一個圓圈，指定一個同學手裡拿著一束花，主持人在旁邊背對著大家開始擊鼓，鼓聲開始之後拿著花的同學開始傳花，每個同學都可以把花傳給自己左右的兩個同學中的一個（左右任意），當主持人停止擊鼓時，傳花停止，此時，正拿著花沒傳出去的那個同學就要給大家表演一個節目。
聰明的小賽提出一個有趣的問題：有多少種不同的方法可以使得從小賽手裡開始傳的花，傳了m次以後，又回到小賽手裡。對於傳遞的方法當且僅當這兩種方法中，接到花的同學按接球順序組成的序列是不同的，才視作兩種傳花的方法不同。比如有3個同學1號、2號、3號，並假設小賽為1號，花傳了3次回到小賽手裡的方式有1->2->3->1和1->3->2->1，共2種。
輸入：輸入共一行，有兩個用空格隔開的整數n，m（3<=n<=30，1<=m<=30）
樣例輸入：3 3
輸出：輸出共一行，有一個整數，表示符合題意的方法數
樣例輸出：2
這個程序有一個優化點：result數組是可以變為兩行的滾動數組的，畢竟計算結果時，當前行只依賴它的前一行，實現方式i%2做為result數組的第一個下標。
#include
#include
using namespace std;
int main() {
int n = 0, m = 0;
cin >> n >> m;
vector
result.resize(m + 1);
for (size_t i = 0; i result[i].resize(n + 1, 0); } // 同學編號從1-n // result[m][n] 經過m步從第n個同學到達第一個同學
result[1][1] = 0;
result[1][n] = 1;
result[0][1] = 1;
// 第j個同學通過i步到第1個同學 = 第j+1(右邊同學)通過i-1步到達第一個同學方式數 + 第j-1(左邊同學)通過i-1步到達第一個同學方式數
for (int i = 1; i <= m; ++i) {
// 如果第1個同學經過j步到達第1個同學 = 第j+1(右邊同學)通過i-1步到達第一個同學方式數 + 第n(左邊同學)通過i-1步到達第一個同學
方式數
result[i-1][0] = result[i-1][n];
for (int j = 1; j <= n; ++j) {
// 對j+1求餘，因為當j==n時有
// result[i][n] = result[i-1][j-1] + result[i-1][1];
result[i][j] = result[i-1][j-1] + result[i-1][(j+1) % n];
}
}
for (int i = 0; i < result.size(); ++i) {
for (int j = 0; j < result[i].size(); ++j) {
std::cout << result[i][j] << " ";
}
std::cout << std::endl;
}
// 輸出第一個同學經過M步，又把花傳到自己手裡面
cout << result[m][1] << endl;
}
怎麼樣？是不是也想嘗試著自己做一款小遊戲了呢？
最後祝所有程序員都能夠走上人生巔峰，讓代碼將夢想照進現實。如果大家對於學習C語言的學習方法，學習路線還有以後發展問題有任何疑問可以隨時問我，工作不忙的時候希望可以給大家解惑。關注我的頭條號，私信給我【C語言】我會發你係統學習資料以及交流學習的地址。
閱讀更多 編程學習 的文章
