Ю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 )

Related Images: