กำหนดเมทริกซ์กำลังสอง[][] ที่มีจำนวนไม่เป็นลบเป็นองค์ประกอบ ยังได้รับคะแนนตัวแปร เป้าหมายคือการนับวิธีที่จะได้คะแนนที่กำหนดโดยการเพิ่มองค์ประกอบจากเมทริกซ์[][] ซึ่งอนุญาตให้ย้ายได้เท่านั้นคือการเคลื่อนไหวที่ถูกต้องและการเคลื่อนไหวลง
เริ่มต้นจาก matrix[0][0] ได้เฉพาะการย้ายไปที่ matrix[0][1] ( right move ) หรือย้ายไป matrix[1][0] ( down move ) และเพิ่มมูลค่าเพื่อให้ได้ sum=score
ให้เราเข้าใจด้วยตัวอย่าง
ตัวอย่าง
ป้อนข้อมูล - matrix[row][col] ={ {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
ป้อนข้อมูล - เมทริกซ์[แถว][col] ={ {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[row][col][size] และ check[row][col][size] การตรวจสอบอาร์เรย์จะทำเครื่องหมายเซลล์ของเมทริกซ์[][] หากเข้าชมว่าเป็นจริง Array arr[][][] ใช้เพื่อเก็บจำนวนวิธีในการเข้าถึงเซลล์เฉพาะจากเมทริกซ์[0][0] เราจะคำนวณวิธีการซ้ำๆ
- นำเมทริกซ์อาร์เรย์ 2 มิติมาใช้ในการเก็บตัวเลข
- ใช้คะแนนตัวแปรเป็นข้อมูลป้อนเข้า
- ใช้สองอาร์เรย์ int arr[row][col][size] และ bool check[row][col][size].
- Function matrix_score(int matrix[row][col], int rows, int cols, int sc) ใช้เพื่อคืนค่าจำนวนวิธีที่จะได้คะแนนในเมทริกซ์
- ถ้าคะแนน sc น้อยกว่า 0 ให้คืนค่า 0 (เพื่อสิ้นสุดการเรียกซ้ำหรือในกรณีที่ป้อนข้อมูลผิด)
- หากจำนวนแถวหรือคอลัมน์น้อยกว่า 0 ให้คืนค่า 0 (เพื่อสิ้นสุดการเรียกซ้ำ)
- หากเซลล์แรกเท่ากับ sc (คะแนนอินพุต) ให้คืนค่า 1 เป็นวิธีเดียว หากไม่เป็นเช่นนั้นให้คืนค่า 0
- ถ้าเซลล์ปัจจุบันถูกเข้าชมแล้ว ให้คืนค่าจำนวนวิธีที่เซลล์นี้เป็น arr[rows][cols][sc].
- หากไม่ถือเงื่อนไขข้างต้นทั้งหมด ให้ทำเครื่องหมายเซลล์ปัจจุบันเป็นเข้าชมแล้ว ใช้ check[rows][cols][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[rows][cols][sc] =temp_1 + temp_2.
- ในตอนท้าย ให้ส่งคืน arr[rows][cols][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
