Грокаем а Иллюстрированное пособие для программистов и любопытствующих

640 /А 640 /И *Щ0 м


???
В
400 м
НОВЫЙ НАДЕЛ, КОТОРЫЙ ТОЖЕ НУЖНО РАЗБИТЬ НА УЧАСТКИ

исходном наделе можно разместить два участка 640 х 640, и еще останется место. Тут-то и наступает момент истины. Нераспределенный остаток — это тоже надел земли, который нужно разделить. Так почему бы не применить к нему тот же алгоритм?
Итак, мы начали с надела 1680 * 640, который необходимо разделить на участки. Но теперь разделить нужно меньший сегмент — 640 х 400. Если
вы найдете самый большой участок, подходящий для этого размера, это будет самый большой участок, подходящий для всей фермы. Мы только что сократили задачу с размера 1680 * 640 до 640 х 400!
АЛГОРИТМ ЕВКЛИДА
«Если вы найдете самый большой участок, подходящий для этого размера, это будет самый большой участок, подходящий для всей фермы». Если истинность этого утверждения для вас неочевидна, не огорчайтесь. Она действительно не очевидна. К сожалению, дока­зательство получится слишком длинным, чтобы его можно было бы привести в книге, поэтому вам придется просто поверить мне на сло­во. Если вас интересует доказательство, поищите «алгоритм Евкли­да». Хорошее объяснение содержится на сайте Khan Academy: https:// www.khanacademy.org/computing/computer-science/cryptography/ modarithmetic/a/the-euclidean-algorithm.
П
^ г«о м | «оо м
рименим тот же алгоритм снова. Если начать с участка 640 х 400, то размеры самого большого квадрата, который можно создать, составляют 400 х 400 м.
«
Остается меньший сегмент с размерами 400 х 240 м.



00 /и
О
г<ю м 1€>о м 160 м

тсекая поделенную часть, мы приходим к еще меньшему размеру сегмента, 240 х 160 м.
После очередного отсечения получается еще меньший сегмент.
'
&0 М

«1 *.',1 I п •• V
160 АЛ
БАЗОВЫЙ СЛУЧАЛ!
Эге, да мы пришли к базовому случаю: 160 кратно 80. Если разбить этот сегмент на квадраты, ничего лишнего не останется!
Ч I
-
30 АЛ

СО
ао ал ао м
Итак, для исходного надела земли самый большой размер участка будет равен 80 х 80 м.
Вспомните, как работает стратегия «разделяй и властвуй»:

1. 
   Определите простейший случай как базовый.
   
2. 
   Придумайте, как свести задачу к базовому случаю.
   

«Разделяй и властвуй» — не простой алгоритм, который можно применить для решения задачи. Скорее, это подход к решению задачи. Рассмотрим еще один пример.
И
2 4 6

&0 м



меется массив чисел.
Нужно просуммировать все числа и вернуть сумму. Сделать это в цикле совсем не сложно: