資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟
心理學
社會研究
時尚研究
法律研究計算在遊戲中達到給定分數的方法數
讓我們考慮這樣一個遊戲，在這個遊戲中，玩家可以在每次移動中透過 3、5 或 10 獲得一些分數。還給定了一個目標分數。我們的任務是找出用這三個點達到該目標分數的可能方法有多少種。
透過動態規劃方法，我們將建立一個從 0 到 n 的所有分數列表，並且對於 3、5、10 的每個值，我們只需更新表即可。
輸入和輸出
Input: The maximum score to reach using 3, 5 and 10. Let the input is 50. Output: Number of ways to reach using (3, 5, 10)50: 14
演算法
countWays(n)
只有 3 個可能的分數，它們是 3、5 和 10
輸入：n 是要達到的最高分數。
輸出 − 達到目標分數 n 的可能方法數。
Begin create table of size n+1 set all table entries to 0 table[0] := 1 for i := 3 to n, do table[i] := table[i] + table[i-3] done for i := 5 to n, do table[i] := table[i] + table[i-5] done for i := 10 to n, do table[i] := table[i] + table[i-10] done return table[n] End
示例
#include <iostream>
using namespace std;
// Returns number of ways to reach score n
int countWay(int n) {
int table[n+1], i; //table to store count for each value of i
for(int i = 0; i<=n; i++) {
table[i] = 0; // Initialize all table values as 0
}
table[0] = 1; //set for 1 for input as 0
for (i=3; i<=n; i++) //try to solve using 3
table[i] += table[i-3];
for (i=5; i<=n; i++) //try to solve using 5
table[i] += table[i-5];
for (i=10; i<=n; i++) //try to solve using 10
table[i] += table[i-10];
return table[n];
}
int main() {
int n;
cout << "Enter max score: ";
cin >> n;
cout << "Number of ways to reach using (3, 5, 10)" << n <<": " << countWay(n);
}輸出
Enter max score: 50 Number of ways to reach using (3, 5, 10)50: 14
更新日期： 16-6-2020
581 次瀏覽
廣告