Page 78 - Bkhargava_-_Grokaem_algoritmy

«Разделяй и властвуй» 77

-

-

ЬС.Е УЧАСТКИ
с.лишком
НЕ К6АдРПНЬ\Е .а.омны Быть
МАЛЕНЬКИЕ
ОJI.ИНАКО6Ь\МИ

Как определить наибольший размер квадрата для участка? Воспользуйтесь
стратегией «разделяй и властвуй~! Алгоритмы на базе этой стратегии яв­
ляются рекурсивными.

Решение задачи методом «разделяй и властвуй~ состоит из двух шагов:
1. Сначала определяется базовый случай. Это должен быть простейший
случай из всех возможных.

2. Задача делится или сокращается до тех пор, пока не будет сведена к ба­
зовому случаю .
А теперь воспользуемся стратегией «разделяй и властвуй~ для поиска ре­
шения этой задачи. Каков самый большой размер квадрата, который может
использоваться?

Для начала нужно определить базовый случай. Самая простая ситуация -
если длина одной стороны кратна длине другой стороны.

50 м
г 2.5 м
----~--- ")
,., •• ,, ''•' i '1'·''1 •1'
~·,•.·.:·:.••,,•: .'11: ;" ~,'·'
•• ~· '\ •• • , , ,' : ' 1 ' ; • '• ' ~: :: 2.5 м
,, '' • ~ ',' '• '" '/' ~ •'• ,''' 't'
•'••,':•.•, ~. •,,:•\ ', '''•'
.:, '' / ' '', \ , '' \ ; " .. ,~,

Предположим, длина одной стороны составляет 25 м, а длина другой 50 м.
В этом случае размер самого большого участка составляет 25 м х 25 м, и на­
дел после деления будет состоять из двух участков.

www.trk.kg