Дано прямокутник, довжини сторін якого А та В є
натуральними числами. Скласти програму, яка знаходитиме, на скільки квадратів,
сторони яких виражаються натуральними числами, можна розрізати цей прямокутник,
якщо від нього щоразу відрізається квадрат максимальної площі.
Ідея розв’язання. Задача є класичним прикладом
використання добре відомого алгоритму Евкліда, який ще називається «жадібним».
Очевидно, що сторона квадрата максимальної площі
буде дорівнювати меншій стороні прямокутника (нехай А). «Відрізавши» цей
квадрат від прямокутника (В=В-А), ми дістанемо новий прямокутник. До нового
прямокутника застосуємо ту ж саму дію. Цей процес буде продовжуватись до тих
пір, поки прямокутник не «виродиться» у квадрат.
Малюнок, який ілюструє роботу програми для випадку А=3, В=4