C++의 점 N에서 N이 이동한 후 모든 점에 도달할 확률 찾기

숫자 N이 있다고 가정해 보겠습니다. 이것은 숫자 줄에 있는 사람의 초기 위치를 나타냅니다. 왼쪽으로 갈 확률인 L도 있습니다. N 지점에서 N 이동을 완료한 후 숫자 라인의 모든 지점에 도달할 확률을 찾아야 합니다. 각 이동은 왼쪽 또는 오른쪽이 될 수 있습니다.

따라서 입력이 n =2, l =0.5와 같으면 출력은 [0.25, 0, 0.5, 0, 0.25]

가 됩니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

높음 :=1 - 낮음
n+1 x 2*n+1 크기의 배열 A를 정의하고 0으로 채움
A[1, n + 1] =높음, A[1, n - 1] =낮음
i:=2 초기화의 경우, i <=n일 때 업데이트(i를 1만큼 증가), −
- j:=1 초기화의 경우 j −=2 * n일 때 업데이트(j를 1만큼 증가), −
  - A[i, j] :=A[i, j] + (A[i - 1, j - 1] * 높음)
- j 초기화의 경우 :=2 * n - 1, j>=0일 때 업데이트(j를 1만큼 감소), −
  - A[i, j] :=A[i, j] + (A[i - 1, j + 1] * 낮음)
initialize i :=0의 경우 i − 2*n+1일 때 업데이트(i를 1만큼 증가), −
- 디스플레이 A[n, i]

예시

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

#include <bits/stdc++.h>
using namespace std;
void find_prob(int n, double low) {
   double high = 1 - low;
   double A[n + 1][2 * n + 1] = {{0}};
   A[1][n + 1] = high;
   A[1][n - 1] = low;
   for (int i = 2; i <= n; i++) {
      for (int j = 1; j <= 2 * n; j++)
         A[i][j] += (A[i - 1][j - 1] * high);
      for (int j = 2 * n - 1; j >= 0; j--)
         A[i][j] += (A[i - 1][j + 1] * low);
   }
   for (int i = 0; i < 2*n+1; i++)
      cout << A[n][i] << endl;
}
int main() {
   int n = 2;
   double low = 0.6;
   find_prob(n, low);
}

입력

2, 0.6

출력