ค้นหาความน่าจะเป็นที่จะไปถึงทุกจุดหลังจาก N เคลื่อนที่จากจุด N ใน C++

สมมติว่าเรามีตัวเลข N ซึ่งแสดงถึงตำแหน่งเริ่มต้นของบุคคลบนเส้นจำนวน นอกจากนี้เรายังมี L ซึ่งเป็นความน่าจะเป็นของคนที่จะไปทางซ้าย เราต้องหาความน่าจะเป็นที่จะไปถึงทุกจุดบนเส้นจำนวนหลังจากเสร็จสิ้นการเคลื่อนที่ N จากจุด N การย้ายแต่ละครั้งสามารถไปทางซ้ายหรือทางขวาได้

ดังนั้น หากอินพุตเป็น n =2, l =0.5 เอาต์พุตจะเป็น [0.25, 0, 0.5, 0, 0.25]

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

สูง :=1 - ต่ำ
กำหนดขนาดอาร์เรย์ A:n+1 x 2*n+1 และเติมด้วย 0
A[1, n + 1] =สูง, A[1, n - 1] =ต่ำ
สำหรับการเริ่มต้น i :=2 เมื่อฉัน <=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] * ต่ำ)
สำหรับการเริ่มต้น 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

ผลลัพธ์