home

หน้าแรก
 Computer >> คอมพิวเตอร์ >  >> การเขียนโปรแกรม >> C++

ความน่าจะเป็นของอัศวินในกระดานหมากรุกใน C++

สมมติว่าเรามีกระดานหมากรุก NxN หนึ่งอัน อัศวินจะเริ่มต้นที่แถวที่ r และคอลัมน์ที่ c และพยายามทำให้การเคลื่อนไหว K ถูกต้อง ในที่นี้ แถวและคอลัมน์จะถูกสร้างดัชนี 0 ดังนั้น สี่เหลี่ยมด้านซ้ายบนคือ (0, 0) และสี่เหลี่ยมด้านขวาล่างคือ (N-1, N-1)

อัศวินสามารถเคลื่อนที่ได้ 8 เซลล์จากเซลล์ ซึ่งสามารถแสดงในแผนภาพนี้ -

ความน่าจะเป็นของอัศวินในกระดานหมากรุกใน C++

แต่ละครั้งที่อัศวินจะเคลื่อนที่ มันจะเลือกหนึ่งในแปดท่าที่เป็นไปได้แบบสุ่ม อัศวินยังคงเคลื่อนที่ต่อไปจนกว่าจะเคลื่อนตัว K หรือเคลื่อนออกจากกระดานหมากรุก เราต้องหาความน่าจะเป็นที่อัศวินยังคงอยู่บนกระดานหลังจากที่มันหยุดเคลื่อนไหว

ดังนั้นหากอินพุตเป็น 3, 2, 0, 0 เอาต์พุตจะเป็น 0.0625 เนื่องจากมีสองการเคลื่อนไหว (ไปที่ (1,2), (2,1)) ที่จะทำให้อัศวินอยู่บนกระดาน จากนี้ไปแต่ละตำแหน่ง ยังมีสองท่าที่จะทำให้อัศวินอยู่บนกระดาน ดังนั้น ความน่าจะเป็นทั้งหมดที่อัศวินจะอยู่บนกระดานจึงเท่ากับ 0.0625

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

  • กำหนด dir อาร์เรย์ทิศทางเดียว นี่คือ [[-2,-1], [-2, 1],[2,-1], [2, 1], [1,2], [1, -2], [-1,2], [-1,-2]]
  • กำหนดวิธีการแบบเรียกซ้ำแก้ปัญหา () ซึ่งจะใช้ x, y, n, k และอาร์เรย์ 3 มิติ dp
  • ถ้า x>=n หรือ y>=n หรือ x <0 หรือ y <0 ให้คืนค่า 0
  • ถ้า k เป็น 0 ให้คืนค่า 1
  • ถ้า dp[k,x,y] ไม่ใช่ -1 ให้คืนค่า dp[k,x,y]
  • dp[k, x, y] :=0
  • สำหรับฉันอยู่ในช่วง 0 ถึง 7
    • dp[k,x,y] :=Solve(x+dir[i,0], y + dir[i, 1], n, k – 1, dp)
  • ส่งคืน dp[k,x,y]
  • จากวิธีหลัก ให้ทำดังนี้
  • สร้างอาร์เรย์ 3 มิติของขนาด (k + 1) x N x N เติมด้วย – 1
  • ผลตอบแทนการแก้(r, c, N, k, dp) / (8^K)

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

ตัวอย่าง

#include <bits/stdc++.h>
using namespace std;
int dir[8][2] = {{-2, -1}, {-2, 1}, {2, -1}, {2, 1}, {1, 2}, {1, -2}, {-1, 2}, {-1, -2}};
class Solution {
   public:
   double solve(int x, int y, int n, int k, vector < vector < vector < double > > >& dp){
      if(x >= n || y >= n || x < 0 || y < 0 ) return 0.0;
      if(k == 0) return 1.0;
      if(dp[k][x][y] != -1) return dp[k][x][y];
      dp[k][x][y] = 0;
      for(int i = 0; i < 8; i++){
         dp[k][x][y] += solve(x + dir[i][0], y + dir[i][1], n, k - 1, dp);
      }
      return dp[k][x][y];
   }
   double knightProbability(int N, int K, int r, int c) {
      vector < vector < vector < double > > > dp (K + 1, vector < vector < double > >(N, vector < double >(N, -1))) ;
      return solve(r, c, N, K, dp) / pow(8, K);
   }
};
main(){
   Solution ob;
   cout << (ob.knightProbability(3, 2, 0, 0));
}

อินพุต

3
2
0
0

ผลลัพธ์

0.0625