Рубрики

Вероятность того, что Рыцарь останется на шахматной доске

Учитывая NxN шахматную доску и рыцаря в позиции (x, y). Рыцарь должен сделать ровно K шагов, где на каждом шаге он случайным образом выбирает любое из 8 направлений. Какова вероятность того, что Рыцарь останется на шахматной доске после выполнения K шагов, с условием, что он не сможет снова войти в доску после того, как покинет ее?

Примеры:

Let's take:
8x8 chessboard,
initial position of the knight : (0, 0),
number of steps : 1
At each step, the Knight has 8 different positions to choose from. 
If it starts from (0, 0), after taking one step it will lie inside the board only at 2 out of 8 positions, and will lie outside at other positions. So, the probability is 2/8 = 0.25

Одна вещь, которую мы можем наблюдать, состоит в том, что на каждом шагу у Рыцаря есть 8 вариантов выбора. Предположим, рыцарь должен сделать k шагов, а после K-го шага рыцарь достигает (x, y). Существует 8 различных позиций, из которых Рыцарь может достичь (x, y) за один шаг, и они: (x + 1, y + 2), (x + 2, y + 1), (x + 2, у-1), (х + 1, у-2), (х-1, у-2), (х-2, у-1), (х-2, у + 1), (х-1, у + 2).
Что если мы уже знали вероятности достижения этих 8 позиций после шагов К-1? Тогда конечная вероятность после K шагов будет просто равна (вероятность достижения каждой из этих 8 позиций после K-1 шагов) / 8;
Здесь мы делим на 8, потому что каждая из этих 8 позиций имеет 8 вариантов, а позиция (x, y) — одна из них.
Для позиций, которые лежат вне доски, мы либо примем их вероятности за 0, либо просто пренебрегаем ими.

Поскольку нам необходимо отслеживать вероятности в каждой позиции для каждого количества шагов, нам необходимо динамическое программирование для решения этой проблемы.
Мы собираемся взять массив dp [x] [y] [steps], в котором будет храниться вероятность достижения (x, y) после (шагов) количества ходов.
Базовый случай: если количество шагов равно 0, то вероятность того, что Рыцарь останется внутри доски, равна 1.

Вот реализация:

C ++

// C ++ программа для поиска вероятности
// Рыцарь останется внутри шахматной доски после
// делаем ровно K шагов
#include <bits/stdc++.h>

using namespace std;

  
// размер шахматной доски
#define N 8

  
// вектор направления для рыцаря

int dx[] = { 1, 2, 2, 1, -1, -2, -2, -1 };

int dy[] = { 2, 1, -1, -2, -2, -1, 1, 2 };

  
// возвращает true, если конь находится внутри шахматной доски

bool inside(int x, int y)

{

    return (x >= 0 and x < N and y >= 0 and y < N);

}

  
// Подход снизу вверх для нахождения вероятности
// выйти из шахматной доски.

double findProb(int start_x, int start_y, int steps)

{

    // массив dp

    double dp1[N][N][N];

  

    // на 0 шагов, каждая позиция

    // будет иметь вероятность 1

    for (int i = 0; i < N; ++i)

        for (int j = 0; j < N; ++j)

            dp1[i][j][0] = 1;

  

    // для каждого количества шагов s

    for (int s = 1; s <= steps; ++s)

    {

        // для каждой позиции (x, y) после

        // количество шагов

        for (int x = 0; x < N; ++x)

        {

            for (int y = 0; y < N; ++y)

            {

                double prob = 0.0;

  

                // для каждой позиции, достижимой из (x, y)

                for (int i = 0; i < 8; ++i)

                {

                    int nx = x + dx[i];

                    int ny = y + dy[i];

  

                    // если эта позиция лежит внутри доски

                    if (inside(nx, ny))

                        prob += dp1[nx][ny][s-1] / 8.0;

                }

  

                // сохранить результат

                dp1[x][y][s] = prob;

            }

        }

    }

  

    // вернуть результат

    return dp1[start_x][start_y][steps];

}

  
// Драйвер программы

int main()

{

    // количество шагов

    int K = 3;

  

    cout << findProb(0, 0, K) << endl;

  

    return 0;

}

Джава

// Java программа для поиска вероятности
// Рыцаря, чтобы остаться внутри
// шахматная доска после взятия точно K
// количество шагов

class GFG {

      

    // размер шахматной доски

    static final int N = 8;

  

    // вектор направления для рыцаря

    static int dx[] = { 1, 2, 2, 1

                     -1, -2, -2, -1 };

                       

    static int dy[] = { 2, 1, -1, -2,

                       -2, -1, 1, 2 };

  

    // возвращает истину, если рыцарь

    // внутри шахматной доски

    static boolean inside(int x, int y)

    {

        return (x >= 0 && x < N && 

                       y >= 0 && y < N);

    }

  

    // Подход снизу вверх для поиска

    // вероятность выхода из

    // шахматная доска.

    static double findProb(int start_x, 

                  int start_y, int steps)

    {

          

        // массив dp

        double dp1[][][] = new double[N][N][N];

  

        // на 0 шагов, каждая позиция

        // будет иметь вероятность 1

        for (int i = 0; i < N; ++i)

            for (int j = 0; j < N; ++j)

                dp1[i][j][0] = 1;

  

        // для каждого количества шагов s

        for (int s = 1; s <= steps; ++s) {

              

            // для каждой позиции (x, y) после

            // количество шагов

            for (int x = 0; x < N; ++x) {

                  

                for (int y = 0; y < N; ++y) {

                      

                    double prob = 0.0;

  

                    // для каждой достижимой позиции

                    // из (х, у)

                    for (int i = 0; i < 8; ++i) {

                        int nx = x + dx[i];

                        int ny = y + dy[i];

  

                        // если эта позиция ложь

                        // внутри доски

                        if (inside(nx, ny))

                            prob += dp1[nx][ny][s - 1

                                                / 8.0;

                    }

  

                    // сохранить результат

                    dp1[x][y][s] = prob;

                }

            }

        }

  

        // вернуть результат

        return dp1[start_x][start_y][steps];

    }

      

    // Код драйвера

    public static void main(String[] args)

    {

          

        // количество шагов

        int K = 3;

  

        System.out.println(findProb(0, 0, K));

    }

}

  
// Этот код предоставлен Anant Agarwal.

python3

# Python3 программа для поиска вероятности
# Рыцарь остается внутри шахматной доски
# после выполнения ровно K шагов

  
# размер шахматной доски

N = 8

  
# Вектор направления для Рыцаря

dx = [ 1, 2, 2, 1, -1, -2, -2, -1 ]

dy = [ 2, 1, -1, -2, -2, -1, 1, 2 ]

  
# возвращает true, если рыцарь
# находится внутри шахматной доски

def inside(x, y):

  

    return (x >= 0 and x < N and y >= 0 and y < N)

  
# Подход снизу вверх для поиска
# вероятность выхода из шахматной доски.

def findProb(start_x, start_y, steps):

  

    # dp array

    dp1 = [[[0 for i in range(N + 1)]

               for j in range(N + 1)]

               for k in range(N + 1)]

  

    # Для 0 количество шагов, каждый

    # позиция будет иметь вероятность 1

    for i in range(N):

          

        for j in range(N):

            dp1[i][j][0] = 1

  

    # для каждого количества шагов с

    for s in range(1, steps + 1):

      

        # для каждой позиции (x, y) после

        # s количество шагов

        for x in range(N):

              

            for y in range(N):

                prob = 0.0

  

                # Для каждой позиции, достижимой из (x, y)

                for i in range(8):

                    nx = x + dx[i]

                    ny = y + dy[i]

  

                    # если эта позиция лежит внутри доски

                    if (inside(nx, ny)):

                        prob += dp1[nx][ny][s-1] / 8.0

                  

                # сохранить результат

                dp1[x][y][s] = prob

              

    # вернуть результат

    return dp1[start_x][start_y][steps]

  
# Код драйвера

  
количество шагов

K = 3

print(findProb(0, 0, K))

  

  
# Этот код предоставлен Anant Agarwal.

C #

// C # программа для поиска
// Вероятность Рыцаря
// оставаться внутри
// шахматная доска после взятия
// ровно K количество шагов

using System;

  

class GFG

{

  

    // размер шахматной доски

    static int N = 8;

  

    // вектор направления

    // для рыцаря

    static int []dx = {1, 2, 2, 1, 

                      -1, -2, -2, -1};

                      

    static int []dy = {2, 1, -1, -2,

                      -2, -1, 1, 2};

  

    // возвращает true, если

    // рыцарь внутри

    // шахматная доска

    static bool inside(int x, int y)

    {

        return (x >= 0 && x < N && 

                y >= 0 && y < N);

    }

  

    // Подход снизу вверх для

    // найти вероятность

    // выйти из шахматной доски.

    static double findProb(int start_x, 

                           int start_y, 

                           int steps)

    {

          

        // массив dp

        double [,,]dp1 = new double[N, N, N];

  

        // на 0 шагов

        // каждая позиция будет иметь

        // вероятность 1

        for (int i = 0; i < N; ++i)

            for (int j = 0; j < N; ++j)

                dp1[i, j, 0] = 1;

  

        // для каждого номера

        // шагов s

        for (int s = 1; s <= steps; ++s) 

        {

              

            // для каждой позиции (x, y)

            // после количества шагов

            for (int x = 0; x < N; ++x) 

            {

                for (int y = 0; y < N; ++y) 

                {

                    double prob = 0.0;

  

                    // для каждой позиции

                    // достижимо из (x, y)

                    for (int i = 0; i < 8; ++i)

                    {

                        int nx = x + dx[i];

                        int ny = y + dy[i];

  

                        // если эта позиция ложь

                        // внутри доски

                        if (inside(nx, ny))

                            prob += dp1[nx, ny, s - 1] 

                                                / 8.0;

                    }

  

                    // сохранить результат

                    dp1[x, y, s] = prob;

                }

            }

        }

  

        // вернуть результат

        return dp1[start_x, 

                   start_y, steps];

    }

      

    // Код драйвера

    static void Main()

    {

        // количество шагов

        int K = 3;

  

        Console.WriteLine(findProb(0, 0, K));

    }

}

  
// Этот код добавлен
// Sam007

PHP

<?php 
// PHP программа для поиска вероятности
// Рыцаря, чтобы остаться внутри
// шахматная доска после взятия точно K
// количество шагов

  
// размер шахматной доски

$N = 8;

  
// вектор направления для рыцаря

$dx = array(1, 2, 2, 1, -1, -2, -2, -1 );

$dy = array(2, 1, -1, -2, -2, -1, 1, 2 );

  
// возвращает истину, если рыцарь
// внутри шахматной доски

function inside($x, $y)

{

    global $N;

    return ($x >= 0 and $x < $N and 

            $y >= 0 and $y < $N);

}

  
// Подход снизу вверх для поиска
// вероятность выхода из шахматной доски.

function findProb($start_x, $start_y, $steps)

{

    global $N, $dx, $dy;

      

    // массив dp

    $dp1 = array_fill(0, $N

           array_fill(0, $N

           array_fill(0, $N, NULL)));

  

    // на 0 шагов, каждый

    // позиция будет иметь вероятность 1

    for ($i = 0; $i < $N; ++$i)

        for ($j = 0; $j < $N; ++$j)

            $dp1[$i][$j][0] = 1;

  

    // для каждого количества шагов s

    for ($s = 1; $s <= $steps; ++$s)

    {

        // для каждой позиции (x, y) после

        // количество шагов

        for ($x = 0; $x < $N; ++$x)

        {

            for ($y = 0; $y < $N; ++$y)

            {

                $prob = 0.0;

  

                // для каждой позиции

                // достижимо из (x, y)

                for ($i = 0; $i < 8; ++$i)

                {

                    $nx = $x + $dx[$i];

                    $ny = $y + $dy[$i];

  

                    // если эта позиция лежит внутри

                    // доска

                    if (inside($nx, $ny))

                        $prob += $dp1[$nx][$ny][$s - 1] / 8.0;

                }

  

                // сохранить результат

                $dp1[$x][$y][$s] = $prob;

            }

        }

    }

  

    // вернуть результат

    return $dp1[$start_x][$start_y][$steps];

}

  
// Код драйвера

  
// количество шагов

$K = 3;

  

echo findProb(0, 0, $K) . "\n";

  
// Этот код предоставлен ita_c
?>


Выход:

0.125

Сложность времени : O (NxNxKx8), которая равна O (NxNxK), где N — размер платы, а K — количество шагов.
Космическая сложность : O (NxNxK)

Эта статья предоставлена Avinash Kumar Saw . Если вы как GeeksforGeeks и хотели бы внести свой вклад, вы также можете написать статью с помощью contribute.geeksforgeeks.org или по почте статьи contribute@geeksforgeeks.org. Смотрите свою статью, появляющуюся на главной странице GeeksforGeeks, и помогите другим вундеркиндам.

Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

Вероятность того, что Рыцарь останется на шахматной доске

0.00 (0%) 0 votes