Рубрики

Иосиф Флавий | Установите 1 (AO (n) решение)

В информатике и математике проблема Иосифа (или перестановка Иосифа) является теоретической проблемой. Ниже приводится постановка задачи:

В кругу стоят n человек, ожидающих казни. Отсчет начинается в некоторой точке круга и продолжается по кругу в фиксированном направлении. На каждом шаге пропускается определенное количество людей и выполняется следующий человек. Исключение происходит по кругу (который становится все меньше и меньше по мере удаления казненных людей), пока не останется только последний человек, которому предоставлена свобода. Учитывая общее количество человек n и число k, которое указывает, что k-1 человек пропущены, а k-й человек убит в кругу. Задача состоит в том, чтобы выбрать место в начальном круге, чтобы вы остались последним и выжили.

Например, если n = 5 и k = 2, то безопасное положение равно 3. Сначала убивают человека в положении 2, затем убивают человека в положении 4, затем убивают человека в положении 1. Наконец, человек в позиции 5 убит. Таким образом, человек на позиции 3 выживает.
Если n = 7 и k = 3, безопасная позиция равна 4. Лица на позициях 3, 6, 2, 7, 5, 1 убиты по порядку, а человек на позиции 4 выживает.

Задача имеет следующую рекурсивную структуру.

  josephus(n, k) = (josephus(n - 1, k) + k-1) % n + 1
  josephus(1, k) = 1

После того, как первый человек (kth от начала) убит, n-1 человек остаются. Поэтому мы вызываем Джозефуса (n — 1, k), чтобы получить позицию с n-1 человеком. Но позиция, возвращаемая Джозефусом (n — 1, k), будет учитывать позицию, начинающуюся с k% n + 1. Таким образом, мы должны внести коррективы в позицию, возвращенную Джозефусом (n — 1, k).

Ниже приводится простая рекурсивная реализация проблемы Иосифа. Реализация просто следует рекурсивной структуре, упомянутой выше.

С

#include <stdio.h>

  

int josephus(int n, int k)

{

  if (n == 1)

    return 1;

  else

    / * Позиция, возвращаемая Джозефусом (n - 1, k), корректируется, потому что

       рекурсивный вызов josephus (n - 1, k) считает исходную позицию

       k% n + 1 в качестве позиции 1 * /

    return (josephus(n - 1, k) + k-1) % n + 1;

}

  
// Программа драйвера для проверки вышеуказанной функции

int main()

{

  int n = 14;

  int k = 2;

  printf("The chosen place is %d", josephus(n, k));

  return 0;

}

Джава

// Java-код для проблемы Иосифа

import java.io.*;

  

class GFG {

  

static int josephus(int n, int k)

{

if (n == 1)

    return 1;

else

    / * Позиция, возвращаемая Иосифом (n - 1, k)

    настраивается потому что рекурсивный вызов

    Иосиф (n - 1, k) считает оригинал

    позиция k% n + 1 как позиция 1 * /

    return (josephus(n - 1, k) + k-1) % n + 1;

}

  
// Программа драйвера для проверки вышеуказанной функции

public static void main(String[] args)

{

int n = 14;

int k = 2;

System.out.println("The chosen place is " + josephus(n, k));

}
}

  
// Этот код предоставлен Prerna Saini

python3

# Python-код для проблемы Иосифа

  

def josephus(n, k):

  

      if (n == 1):

          return 1

      else:

      

      

          # Позиция, возвращаемая

          # josephus (n - 1, k) настроен

          # потому что рекурсивный вызов

          # josephus (n - 1, k) считает

          # исходная позиция

          # k% n + 1 в качестве позиции 1

          return (josephus(n - 1, k) + k-1) % n + 1

  
Программа # Driver для проверки вышеуказанной функции

  

n = 14

k = 2

  

print("The chosen place is ", josephus(n, k))

  
# Этот код предоставлен
# Сумит Садхакар

C #

// C # код для проблемы Иосифа

using System;

  

class GFG {

      

    static int josephus(int n, int k)

    {

        if (n == 1)

            return 1;

        else

            / * Позиция вернулась

            по Иосифу (n - 1, k)

            отрегулирован, потому что

            рекурсивный вызов Josephus (н

            - 1, к) считает

            исходная позиция k% n + 1

            как позиция 1 * /

            return (josephus(n - 1, k)

                       + k-1) % n + 1;

    }

      

    // Программа драйвера для тестирования выше

    // функция

    public static void Main()

    {

        int n = 14;

        int k = 2;

        Console.WriteLine("The chosen "

        + "place is " + josephus(n, k));

    }

}

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

PHP

<?php
// PHP-код для
// Проблема Иосифа

  

function josephus($n, $k)

{

    if ($n == 1)

        return 1;

    else

        / * Позиция, возвращаемая

           Иосиф (п - 1, к) является

           отрегулирован, потому что

           рекурсивный вызов Джозефуса

           (n - 1, k) считает

           исходная позиция k% n + 1

           как позиция 1 * /

        return (josephus($n - 1, $k) + 

                    $k - 1) % $n + 1;

}

  

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

    $n = 14;

    $k = 2;

    echo "The chosen place is ", josephus($n, $k);

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


Выход:

The chosen place is 13

Сложность времени: O (n)

Иосиф Флавий | Набор 2 (простое решение, когда k = 2)

Источник:
http://en.wikipedia.org/wiki/Josephus_problem

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

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

Иосиф Флавий | Установите 1 (AO (n) решение)

0.00 (0%) 0 votes