(и решение загадки замка)

Поскольку этот алгоритм исходит от Евклида, отца геометрии, неудивительно, что он основан на геометрии. Сегодня мы визуально пройдемся по алгоритму Евклида и, надеюсь, получим полезные сведения.

Визуальное изучение алгоритма

Для разминки давайте найдем наибольший общий делитель 16 и 38, используя прямоугольник размером 16x38:

Шаг 1: перепишите 38 как произведение 16 и целого числа плюс остаток.

Графически это означает выяснение того, сколько квадратов 16x16 умещается в прямоугольнике.

Два квадрата 16x16 помещаются в прямоугольник, оставляя без затенения прямоугольник единиц размером 16 на 6.

Эти значения представлены на первом формальном шаге алгоритма:

Шаг 2: повторите процесс еще раз, разделив незатененную область на самые большие квадраты, которые мы можем сделать.

В этом случае мы можем разместить два блока 6х6 в незатененной области.

И вот следующий формальный шаг алгоритма:

В результате на этот раз получится еще один незатененный прямоугольник с площадью 4x6 единиц.

Шаг 3: сбросьте алгоритм, чтобы найти наибольший общий делитель 6 и 4. Например, поместите один квадрат 4x4 в оставшийся незатененный прямоугольник 4x6.

Шаг 4. Наконец, у нас есть прямоугольник 4x2, оставленный незатененным. Мы можем разместить два квадрата 2x2 в области 4x2. Это наш последний шаг, поскольку он не оставляет нам остатка.

Теперь, когда исходный прямоугольник 16x38 полностью закрашен, мы подошли к концу алгоритма. Картинка наглядно показывает нам, что самый большой квадрат, который может покрыть весь прямоугольник 16x38, - это квадрат 2x2.

Это означает, что наибольший общий делитель 16 и 38 равен 2.

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

Решение загадки замка

из последнего поста

В последнем посте я загадал вам загадку для размышлений. Ключ к разгадке - буквально истолковать следующее утверждение:

«… даже если бы вы могли без отдыха менять числа со скоростью одно число в секунду, вам все равно потребовалось бы сто лет, чтобы найти правильную комбинацию».

Следовательно, если мы предположим, что заключенный вводит комбинации в порядке, начинающемся с 0000000001, правильная комбинация блокировки - это количество секунд в 100 годах (без учета високосных лет).

Следующий урок: Использование деревьев факторов для поиска GCF и LCM

Спасибо за внимание!

Нажмите ❤, чтобы сообщить мне, что вы узнали что-то новое!