學校聯歡晚會的時候,為了使每一個同學都能參與進來,主持人常常會帶著同學們玩擊鼓傳花的遊戲。遊戲規則是這樣的: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語言】我會發你係統學習資料以及交流學習的地址。
閱讀更多 編程學習 的文章