資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究C++中計算矩陣中達到給定分數的路徑數
給定一個包含非負數作為元素的方陣[][]。還給定一個變數分數。目標是透過新增矩陣[][]中的元素來計算達到給定分數的路徑數，使得只允許向右移動和向下移動。
從矩陣[0][0]開始，只能移動到矩陣[0][1]（向右移動）或移動到矩陣[1][0]（向下移動），並將值新增到總和=分數中。
讓我們透過例子來理解。
例如
輸入 - 矩陣[行][列] = { {1, 1}, { 1, 1} } 分數=3
輸出 - 達到矩陣中給定分數的路徑數為：2
解釋 - 分數可以透過以下方式達到
路徑 1：新增索引 (0,0) + (0,1) + (1,1) 處的元素 = 1+1+1 = 3
路徑 2：新增索引 (0,0) + (1,0) + (1,1) 處的元素 = 1+1+1 = 3
輸入 - 矩陣[行][列] = { {1,1,2},{ 2,1,1}, {1,2,2} } 分數=7
輸出 - 達到矩陣中給定分數的路徑數為：2
解釋 - 分數可以透過以下方式達到
路徑 1：新增索引 (0,0) + (0,1) + (1,1) + (1,2) + (2,2) 處的元素 = 1+1+1+2+2 = 7
路徑 2：新增索引 (0,0) + (0,1) + (1,1) + (2,1) + (2,2) 處的元素 = 1+1+1+2+2 = 7
下面程式中使用的方法如下
在這種方法中，我們將使用動態規劃來解決問題。我們將使用兩個陣列 arr[行][列][大小] 和 check[行][列][大小]。陣列 check 將標記矩陣[][] 的單元格，如果它們被訪問則為真。陣列 arr[][][] 用於儲存從矩陣[0][0] 到達特定單元格的路徑數。我們將遞迴地計算路徑數。
- 取二維陣列 matrix 用於儲存數字。
- 取變數 score 作為輸入。
- 取兩個陣列 int arr[行][列][大小] 和 bool check[行][列][大小]。
- 函式 matrix_score(int matrix[行][列], int rows, int cols, int sc) 用於返回達到矩陣中給定分數的路徑數。
- 如果分數 sc 小於 0，則返回 0。（結束遞迴或在輸入錯誤的情況下）
- 如果行數或列數小於 0，則返回 0。（結束遞迴）。
- 如果第一個單元格等於 sc（輸入分數），則返回 1 作為唯一路徑。如果不是，則返回 0。
- 如果當前單元格已被訪問，則返回此單元格的路徑數，作為 arr[行][列][sc]。
- 如果以上所有條件都不成立，則將當前單元格標記為已訪問。使用 check[行][列][sc] = true。
- 計算 temp_1 = matrix_score(matrix, rows-1, cols, sc-matrix[rows][cols])
- 計算 temp_2 = matrix_score(matrix, rows, cols-1, sc-matrix[rows][cols])
- 將路徑數設定為 arr[行][列][sc] = temp_1 + temp_2。
- 最後返回 arr[行][列][sc]。
例子
#include <iostream>
using namespace std;
#define row 2
#define col 2
#define size 30
int arr[row][col][size];
bool check[row][col][size];
int matrix_score(int matrix[row][col], int rows, int cols, int ways) {
if (ways < 0) {
return 0;
}
if (rows < 0 || cols < 0) {
return 0;
}
if (rows == 0) {
if (cols == 0) {
if (ways == matrix[0][0]) {
return 1;
} else {
return 0;
}
}
}
if (check[rows][cols][ways]) {
return arr[rows][cols][ways];
}
check[rows][cols][ways] = true;
int temp_1 = matrix_score(matrix, rows - 1, cols, ways - matrix[rows][cols]);
int temp_2 = matrix_score(matrix, rows, cols - 1, ways - matrix[rows][cols]);
arr[rows][cols][ways] = temp_1 + temp_2;
return arr[rows][cols][ways];
}
int main() {
int matrix[row][col] = {
{
1,
1
},
{
1,
1
}
};
int ways = 3;
cout << "Count of number of ways to reach a given score in a Matrix are: " << matrix_score(matrix, row - 1, col - 1, ways);
return 0;
}如果我們執行上述程式碼，它將生成以下輸出：
輸出
Count of number of ways to reach a given score in a Matrix are: 2
更新於: 2021年1月29日
128 次檢視
廣告