행 개수가 'r'이고 열 개수가 'c'인 행렬 M[r][c]가 주어지면 주어진 행렬이 마르코프 행렬인지 확인해야 합니다. 입력 행렬이 Markov 행렬이면 출력 "It is a Markov matrix"를 출력하고 Markov 행렬이 아니면 "It's not not Markov matrix"를 출력합니다.
마르코프 행렬
이제 마르코프 행렬이란 무엇입니까? 행렬 M은 각 행의 합이 1일 경우에만 마르코프 행렬입니다.
아래 주어진 예와 같이 -
$$\begin{bmatrix}0.2 &0.3 &0.5 \\0.1 &0.7 &0.2 \\0.4 &0.5 &0.1 \\\end{bmatrix}\\$$
위의 예에서 각 행을 합산하면 -
1st row sum = 0.2+0.3+0.5 = 1.0 2nd row sum = 0.1+0.7+0.2 = 1.0 3rd row sum = 0.4+0.5+0.1 = 1.0
여기서 모든 행의 합은 1.0이므로 위의 행렬은 Markov 행렬입니다.
예시
Input: m[][] = { {0.2, 0.3, 0.5} , {0.1, 0.7, 0.2}, {0.4, 0.5, 0.1}} Output: It is a Markov matrix Input: m[][] = { {0, 0, 1} , {0, 0.7, 0.3}, {0.5, 0.5, 0}} Output: It is a Markov matrix
접근
우리는 또 다른 1차원 행렬을 만들고 그 행렬에 있는 모든 행의 합을 저장할 것입니다. 그런 다음 전체 배열을 반복한 다음 배열의 모든 요소가 1인지 여부를 찾습니다. 1이면 주어진 행렬이 Markov 행렬이고 그렇지 않으면 행렬이 Markov 행렬이 아닙니다.
알고리즘
Start Step 1 -> Define macro as #define n 3 Step 2 -> declare function to check for markov matrix bool check(double arr[][n]) Loop For int i = 0 and i <n and i++ Declare double sum = 0 Loop For int j = 0 and j < n and j++ Set sum = sum + arr[i][j] If (sum != 1) return false End End Return true Step 3 -> In main () Declare double arr[3][3] = { { 0, 0, 1 }, { 0.5, 0, 0.5 }, { 0.9, 0, 0.1 } } If (check(arr)) Print its a markov matrix Else Print its not a markov matrix Stop
예시
#include <iostream> using namespace std; #define n 3 //check for markov matrix bool check(double arr[][n]){ for (int i = 0; i <n; i++){ double sum = 0; for (int j = 0; j < n; j++) sum = sum + arr[i][j]; if (sum != 1) return false; } return true; } int main(){ double arr[3][3] = { { 0, 0, 1 }, { 0.5, 0, 0.5 }, { 0.9, 0, 0.1 } }; if (check(arr)) cout << "its a markov matrix "; else cout << "its not a markov matrix "; }
출력
its a markov matrix