Ю5.11

Задача: Задача Иосифа. По кругу располагается  [latex]n[/latex]  человек. Ведущий считает по кругу и выводит («казнит»)  [latex]m[/latex]-го человека*. Круг смыкается, счет возобновляется со следующего после «казнённого»; так продолжается, пока «в живых» не остаётся только 1 человек. Найти номер этого человека, [а так-же для заданного  [latex]n[/latex]  найти такое  [latex]m>1[/latex] , при котором в живых остаётся первый]**.

* — m не может превышать n по условию.

** — вторая часть задачи.

Тесты:   

Ввод Вывод Комментарий
2 1 2 [2] Работает
3 3 2 [не существует] Работает
271 42 121 [69] Работает
271 69 1 [69] Работает

Объяснение переменных:

bool existing - булева переменная для фиксирования существования второй части задачи. vector <int> a — вектор, по задаче представляет собой нумерацию людей.

unsigned int n, m — переменные, где n и m соответсвуют условию задачи.

int JeosifFunc(a, n, m) — функция, которая выполняет основной алгоритм задачи.

 

 Код: Проверить на ideone.

Алгоритм выполнения описан в комментариях в коде.

 

Особенности:

  1. В коде очень легко запутаться, т.к. нумерация «слотов» вектора начинается с нуля, следовательно везде по коду мы должны это учитывать. Это здорово мешает в понимании кода.
  2. Алгоритм выполнения первой задачи заключен в функцию. Без этого хода нельзя было бы выполнить вторую часть задания методом, представленным выше.
    if( JeosifFunc(a, n, k) == 1 )
Божик Семен
Божик Семен

Latest posts by Божик Семен (see all)

One thought on “Ю5.11

  1. Красивое решение — очень оригинальный момент с тасовкой вектора — и это прекрасно работает (хотя и неоптимально по временным затратам). Но вот формула m=a.size()%m-1; неверная — из-за этого конец процесса неверен. Всего-то нужно сделать m=m%a.size(); ведь подсчет по кругу это и есть взятие по модулю (размера круга).

    В общем засчитаю пока 8 баллов.