От прямоугольника отрезали квадрат со стороной, равной меньшей стороне прямоугольника. От...

Question

От прямоугольника отрезали квадрат со стороной, равной меньшей стороне прямоугольника. От оставшейся части прямоугольника снова отрезали квадрат со стороной, равной меньшей стороне получившегося прямоугольника. И наконец, в третий раз от оставшейся части прямоугольника отрезали квадрат со стороной, равной меньшей стороне прямоугольника,получившегося после второго разрезания. После этого остался квадрат со стороной 1 см. Какие размеры имел первоначальный прямоугольник?

Answer 1

разрезанияпрямоугольника размером 13´5 (a=13, b=5) на требуемые квадраты. В данном случае их оказалось 6. Ясен и рекурсивный алгоритм решения задачи. Пусть, например, a>b. Тогда отрезавотпрямоугольникаa>b. Тогда отрезав от прямоугольника floor(a/b) квадратов со сторонами длиной b, снова окажемся перед исходной задачей, в которой a=b и b=mod(a,b) (b=a-floor(a/b)×b) .