Материал: 7 - Презентация - Дженерики, Абстрактные типы данных, Стек, Очередь

Центрдистанционногообучения

Применение: Решение проблемы Джосефуса (1/5)

nГруппа детей садятся в кругу и передают друг-другу по-очереди предмет, условно называемый "картошка",

по кругу.

nИгра в Картошку начинается с какого-то одного

ребенка в кругу, а затем все дети продолжают передавать картошку, до тех пор, пока ведущий не позвонит в колокол, в этот момент ребенок, который

держит картофель должен покинуть игру, после

передачи картофеля к следующему ребенку в кругу.

nПосле того, как проигравший ребенок выходит из круга, дети смыкают круг и игра повторяется

56 online.mirea.ru

Центрдистанционногообучения

Применение: Проблема Джосефуса (2/5)

nЭтот процесс затем продолжается до тех пор, пока не останется один - последний ребенок, который будет объявлен победителем.

nЕсли ведущий игры всегда использует следующую стратегию: колокольчик звонит после того, как картофель был принят k раз, то для некоторого фиксированного k, определяющего победителя для данного списка детей известна как проблема

Иосифа

57 online.mirea.ru

Центрдистанционногообучения

Применение: Проблема Джосефуса (3/5)

import net.datastructures.*;

/**Решениезадачи Джозефуса спомощьюочереди . */ public class Josephus {

public static <E> E Josephus(Queue<E> Q, int k) { if (Q.isEmpty()) return null;

while (Q.size() > 1) { System.out.println(" Queue: " + Q + " k

= " + k);

//Перемещаемэлементизначалакконцу

for (int i=0; i < k; i++) Q.enqueue(Q.dequeue()); // удаляемначальныйэлементизколлекции

E e = Q.dequeue() ; System.out.println(" " + e + " is out");

}

return Q.dequeue(); //победитель!

}

58 online.mirea.ru

Центрдистанционногообучения

Применение: Проблема Джосефуса (4/5)

/** Созданиеочередиизмассиваобъектов */ public static <E> Queue<E> buildQueue(E a[])

{

Queue<E> Q = new NodeQueue<E>();

for (int i=0; i<a.length; i++) Q.enqueue(a[i]);

}return Q;

public static void main(String[] args) {

String[] a1 = {"Alice", "Bob", "Cindy", "Doug", "Ed", “Fred"};

String[] a2 = {"Gene", "Hope", "Irene", "Jack", "Kim", "Lance"};

59 online.mirea.ru

Центрдистанционногообучения

Применение: Проблема Джосефуса (5/5)

String[] a3 = {"Mike", "Roberto"};

System.out.println("First winner is " +

Josephus(buildQueue(a1), 3));

System.out.println("Second winner is " +

Josephus(buildQueue(a2), 10));

System.out.println("Third winner is " + Josephus(buildQueue(a3), 7));

} }

online.mirea.ru