Поставим перед собой задачу: найти НОД (наибольший общий делитель) двух натуральных чисел A и B.
Чтобы решить ее, нужно понять, что значит найти НОД. На самом деле мы должны найти такое число D, что A и B делятся на него без остатка, при этом D является максимальным из подходящих под последнее условие чисел.
Перепишем в виде формулы: пусть A и B - натуральные числа, gcd(A, B) - это их НОД, а D1, D2, …, Dn - это их общие делители, тогда gcd(A, B) = max{D1, D2, … Dn}, где для i=1..n выполняется A mod Di = 0 и B mod Di = 0, где A mod B - остаток от деления A на B.
Теперь напишем первую версию нашего алгоритма (на языке C):
Становится очевидно, что перебирать все возможные делители - это долго, поэтому подумаем в сторону сокращения времени поиска.
И тут возникает мысль: "А что, если представить числа A и B в качестве высоты и ширины какой-либо сетки?". В таком случае нашей целью станет найти такой квадрат, что он будет иметь наибольший размер в пределах сетки, но также будет возможность заполнить такими квадратами всю сетку, ставя их друг за другом. Попытайтесь теперь осознать, почему все так сработает. Теперь попытаемся развить данную идею и рассмотрим следующий пример для НОД(8, 6):
Нарисуем сетку 8x6, в которой все клетки имеют одинаковый размер. Теперь заметим, что если взять квадрат 6x6 и отсечь его от нашей сетки 8x6, то размер квадрата, подходящего под условия, поставленные ранее, будет сохраняться.
Итак, теперь делаем вывод, что если мы возьмем min(A, B) = A, то всегда будем получать НОД(A, B) = НОД(A, B - A). Теперь возьмем малую сетку и повернем ее так, чтобы слева у нас была большая сторона, а снизу - меньшая.
Теперь опять распиливаем данную сетку на сетки 2x2 и 4x2, берем верхнюю и получаем сетку 4x2, которую опять делим на 2 части и в итоге получаем сетку 2x2.
Как только мы получаем квадрат, мы можем с уверенностью сказать, что он является искомым, а значит длина его стороны - это и есть НОД, то есть НОД(8, 6) = 2.
Зная это, перепишем алгоритм:
Но давайте посмотрим на код повнимательнее. Если A = B, то мы просто возвращаем A, но если пропустить эту строку и пойти дальше, то мы дойдем до вызова smart_gcd(B, 0), где B (второй аргумент) становится равным 0, поэтому мы можем сделать следующий вывод: если заменить вторую строку на if (b == 0) return a; , то мы получим тот же самый алгоритм, только на один рекурсивный вызов станет больше.
Двинемся дальше и заметим, что, если A > B как минимум в k раз, то есть A > kB, где k - натуральное, наш алгоритм будет из A вычитать B все k раз, поэтому мы сразу сможем заменить A - B на A mod B, чтобы сократить количество рекурсивных вызовов. В итоге получаем:
Поясню, что мы проверяем теперь не A = B, а B = 0, чтобы не делить на 0 в последней строке.
Но мы можем сделать еще лучше, убрав первую строку, так как в последней строке мы получим A mod B = A при A < B и следовательно получим вызов smartest_gcd(B, A), который мы производим на первой строке.
В итоге мы получили маленький по размерам, оптимизированный и красивый код.
Какой же вывод мы можем сделать?
1) Задача может иметь не одно, а сразу несколько решений
2) Эти решения могут быть лучше в плане:
- производительности
- расширяемости и поддержки
- читабельности
- тестируемости
- размера
- доказуемости.
Поэтому дизайн в вычислениях на компьютерах - это о нахождении множества способов решения проблемы и о понимании какие из них хуже, а какие из них лучше.