адача 41. Дан прямоугольник, длины сторон которого a и b представляют собой натуральные числа. Составить рекурсивную программу-функцию, подсчитывающую, на сколько квадратов с натуральными длинами сторон можно разрезать исходный прямоугольник, если каждый раз от него отрезать квадрат максимально возможной площади.

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

Рис. 9. Пример разрезания прямоугольника 13´5 на квадраты

В качестве базы рекурсии можно взять случай b=0. Если numsq(a,b) - функция, возвращающая решение задачи при заданных длинах a и b (b¹0) сторон исходного прямоугольника, то в любом случае имеем декомпозицию

 Отсюда окончательно получаем:

Контрольные примеры:  numsq(13, 5) = 6,     numsq(5, 13) = 6.

 Пусть в качестве решения задачи требуется выдать не только количество получающихся квадратов, но и размеры каждого из них. Более точно, должен быть возвращен двумерный массив ma[i,j] (i=0,1, ..., k; j=0, 1), где ma[i,0] - длина стороны очередного квадрата, а ma[i,1] - количества квадратов со стороной ma[i,0]. Соответствующая рекурсивная программа-функция могла бы выглядеть так:

Контрольный пример:

Заметим, что nums(a,b) всегда возвращает матрицу, в последней строке которой находятся нули.