Задача тижня 20.02.12 – 26.02.12

Лічилка

Діти вирішили зіграти в хованки. Для того щоб вибрати, хто буде водити, вони стали в коло і почали проговорювати лічилку по складах. Той, на кого прийшовся останній склад лічилки, виходив з кола, і рахування продовжувалося з наступної дитини в колі. Врешті решт у колі залишилися одна дитина, яка й буде водити.

1. Створіть програму, яка за заданими кількістю дітей N і кількістю складів у лічилці M, знайде дитину, яка буде водити, тобто знайде значення P її порядкового номеру у колі відносно першої дитини, з якої починали рахувати.

Вхідні дані

Значення N – натуральне число не більше 10000, вводиться з клавіатури або задається як константа;
Значення M – натуральне число не більше 10000, вводиться з клавіатури;

Вихідні дані (виводяться на екран)

Значення P – натуральне число, виводиться на екран.

2. Заповніть тестову таблицю за результатами роботи програми:

Аналіз розв’язку задачі «Лічилка»

Ця задача носить ім’я відомого історика першого століття Йосифа Флавія. Її формулювання пов’язано з такою легендою. Під час іудейської війни загін Йосифа, що складався з 41 особи, був оточений римлянами. Не маючи намірів здаватися у полон, воїни вирішили вишикуватися у коло та вбивати кожного третього з живих до тих пір, поки не залишиться жодної людини. Йосиф, маючи неабиякі математичні здібності, швидко розрахував, де йому потрібно стати, щоб залишитися живим.

Для вирішення задачі спочатку змінимо нумерацію дітей: зменшимо номери на 1, тобто будемо рахувати від 0. Номер дитини, яка буде водити, позначимо як P_M(N), оскільки він залежить від значень M і N. Розглянемо декілька випадків.

Якщо N=1, то у нас усього одна дитина – вона і залишиться: P_M(1)=0. Запам’ятаємо, що для будь-якого M значення P_M(1) дорівнює нулю.

Якщо N=2, усе буде вирішувати парність числа M: якщо M – парне, то залишиться дитина з номером 0, а якщо M – непарне, то з номером 1. Тому порядковий номер дитини, що залишається у цьому випадку, P_M(2)= 0 + M  mod 2. Ми записали формулу в такому вигляді (а не просто P_M(2)= M mod 2), щоб підкреслити, що рахунок починається з дитини з номером 0.

Якщо N=3, то першою з кола вийде дитина з номером (M-1) mod 3. У колі залишаться дві дитини – така ж сама ситуація, як минулого разу, але тепер починаємо рахувати з наступної дитини, яка має номер M mod 3. Щоб знайти, хто ж залишиться, здійснимо “зсув” попередньої формули для N=2 на M mod 3. Отже, порядковий номер дитини, що залишиться, буде:

P_M(3) = (P_M(2) + M mod 3) mod 3=(P_M(2) + M) mod 3

Отже, за індукцією можна вивести загальну рекурентну формулу для N>1:

P_M(N)=(P_M(N-1)+ M) mod N.

Кінцеве значення, одержане у такий спосіб, слід збільшити на одиницю, щоб повернутися до вихідної нумерації дітей.

Наприклад, для п’яти дітей (N=5) у колі і лічилки з 7 складів (M=7) матимемо:

P₇(5)=

=(P₇(4)+ 7) mod 5 =

=((P₇(3)+ 7) mod 4 +7) mod 5=

=(((P₇(2)+7) mod 3 +7) mod 4 +7) mod 5=

=((((P₇(1)+7) mod 2 +7) mod 3 +7) mod 4 +7) mod 5

Значення останнього виразу обчислюємо, оскільки знаємо, що P₇(1)=0:

P₇(5)=((((0+7) mod 2 +7) mod 3 +7) mod 4 +7) mod 5=3

Отже, водитиме дитина з номером 4 (збільшуємо результат на 1).

Запишемо загальну формулу в розгорнутому вигляді:

P_M(N)= (((…((0+ M) mod 2 + M) mod 3 + … + M) mod (N-1)+ M) mod N

Як бачимо, для складання алгоритму обчислення значення P слід скористатися циклом.

Змінній-лічильнику надаватимемо значення від 2 до N.

Таблиця за результатами роботи програми:

Журі оцінило надіслані розв’язки наступним чином: