Question

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

Answer 1

Пошагово распишем:
0. 52...12
1. 40...12
2. 28...12
3. 16...12
4. 4...12
5. 4...8
6. 4...4

В итоге исполнителю понадобится 6 шагов, чтобы уравнять количество фишек в кучке.

Ответ: 6. 

Answer 2

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

Найдем сначала НОД(52, 12). Для этого можно воспользоваться алгоритмом Евклида:

scssCopy code
НОД(52, 12) = НОД(12, 4) = НОД(4, 0) = 4

Таким образом, мы можем убрать из кучки с 52 фишками по 12 фишек, пока не останется ровно 4 фишки в каждой кучке.

Поскольку мы можем убрать по 12 фишек за один шаг, число шагов, которые потребуется сделать исполнителю, равно количеству шагов, необходимых для уменьшения кучки с 52 фишками до 4 фишек.

Для этого необходимо разделить 52 на 12 и взять целую часть от полученного результата:

arduinoCopy code
52 // 12 = 4

Таким образом, исполнителю потребуется 4 шага, чтобы уравнять количество фишек в кучках.