Еще один пример использования рекурсивных определений для построения алгоритмов приведен в следующей задаче.
адача
43. Центр тяжести многоугольника. Пусть
n-угольник Q
задан своими вершинами Qk и
q = (qi,k) (i = 0, 1; k = 0,
1, ... , n-1; n³1)
- матрица их
прямоугольных координат:
Qk = (q0,k, q1,k ) (k = 0, 1, ... , n-1).
Составить рекурсивную программу-функцию определения координат центра тяжести O многоугольника Q.
Решение. Будем исходить из такого рекурсивного определения центра тяжести многоугольника, согласующегося с физическим понятием центра тяжести системы материальных точек:
 | центр тяжести отрезка (двуугольника) Q = Q0 Q1 есть середина отрезка [Q0, Q1] (база рекурсии); |
| центр тяжести n-угольника Q0 Q1 ... Qn-2 Qn-1 строится так. Пусть уже построена точка P - центр тяжести (n-1)-угольника Q0 Q1 ... Qn-2. Тогда искомый центр тяжести O есть точка отрезка [P, Qn-1], делящая его в отношении (n-1):1, считая от вершины Qn-1 (декомпозиция задачи). |
Из рекурсивности конструктивного определения понятия центра тяжести O многоугольника Q сразу же возникает справедливость следующего рекурсивного алгоритма вычисления координат O:
Контрольные примеры:
