Меню
Главная

Статистика

 

 


Алгоритм A4-1.

Примем следующую формулировку: "вычислить по входным значениям пары натуральных чисел соответствующее выходное значение - их произведение".

На ключевое слово "вычислить" обратите внимание: его присутствие отражается в том, как построен следующий алгоритм.

Вернувшись на сколько-то лет назад, каждый из нас вспомнит, как его учили решать эту задачу в первом классе. Предположим, в порядке обсуждения, что входной тест включает числа 5 и 6 (очевидно, годится и любая другая пара однозначных чисел).

Возьмем кучку из 5 спичек; добавим к ним еще 5 из второй кучки; затем еще пять из третьей; и так далее, пока не соберем спички из всех 6 кучек вместе. Сколько всего у нас получилось спичек? Возможно, для умножения 5´6 вам предлагали в детстве интерпретацию "5 куч по 6 спичек", но автора учили именно так, - впрочем, сути это не меняет.

номер кучи 1 2 3 4 5 6
количество спичек в куче 5 5 5 5 5 5
Рис. 1.

Такое объяснение, или нечто в том же роде, описывает алгоритм умножения двух сомножителей, - первого на второй, - в классе натуральных чисел. Трудоемкость этого алгоритма составляет O(n), где n - второй сомножитель.

Алгоритм A4-2.

Несколько больше проблем вызовет ситуация большого числа кучек (пусть в новом примере их 26) и спичек в них (по 15 в каждой). Теперь уместно вспомнить алгоритм умножения "в столбик".

*   1 5
    2 6
+   9 0
  3 0  
= 3 9 0
Рис. 2.

Умножая здесь 6 на 15, по ходу вычислений мы должны умножить 6 на 5 (или 5 на 6), что позволяет свести многие шаги алгоритма A4-2 к вызовам алгоритма A4-1. Можно предположить, что в свое время этот вариант алгоритма был одним из первых опытов читателя в применении метода сведения задачи к подзадачам.


Алгоритм A4-3.

Чем нас не устраивает, - или может не устроить, при наличии лучшего решения, - алгоритм A4-2? Естественно, многократными вызовами алгоритма A4-1, чья эффективность сомнительна. Здесь-то, наконец, нам и пригодится таблица умножения.

Значение, которое постановка задачи предлагает вычислить, таблицей предоставляется непосредственно - на пересечении 5-й строки и 6-го столбца. Все бы хорошо, но остальные строки и столбцы оказываются "лишними", создавая проблему выбора именно той пары, которая нужна. Так возникают две однотипные подзадачи (вновь: декомпозиция!) - поиска 5-й, сверху, строки и, после этого, поиска в ней 6-го, слева, числа.

  1 2 3 4 5 6 7 8 9
1 1 2 3 4 5 6 7 8 9
2 2 4 6 8 10 12 14 16 18
3 3 6 9 12 15 18 21 24 27
4 4 8 12 16 20 24 28 32 36
5 5 10 15 20 25 30 35 40 45
6 6 12 18 24 30 36 42 48 54
7 7 14 21 28 35 42 49 56 63
8 8 16 24 32 40 48 56 64 72
9 9 18 27 36 45 54 63 72 81
Рис. 3.

Такой поиск отнюдь не является примитивной операцией. Он требует циклической обработки кандидатов в определенной последовательности, - в нашем случае, перебор и проверку строк с 1-й по 5-ю, затем столбцов с 1-го по 6-й. Легко заметить, что очередность кандидатов в последовательности может быть установлена и иначе: скажем, от нижней строки - вверх и, затем, от правого крайнего столбца - влево. Но характер этих отличий лишь технический, они никак не влияют на оценку трудоемкости перебора входящих в последовательность элементов.

Нас же, разумеется, интересует алгоритмическое отличие. Принципиально иначе работает метод "разделяй и властвуй", хотя здесь мы его только упомянем, оставляя обсуждение механизма на будущее.

Таким образом, в нашей классификации надо предусмотреть место не единственному в своем роде механизму - последовательному поиску, а целому семейству алгоритмов поиска, в котором, кстати, есть и другие представители помимо двух уже упомянутых. Вот и технология поиска в таблице, - в данном случае, - разбивается на две самостоятельных подзадачи поиска в линейном массиве.

Вернемся еще раз к исходной постановке задачи. Оказывается, мы ее "незаметно" подменили, - как только появилась таблица. Фактически, модификация формулировки связана с замещением ключевого слова "вычислить" словом "найти". То есть, соответствующая постановка задачи, как только ее дополнили подходящей структурой данных, сразу подсказала нам иное алгоритмическое решение. О структурах данных мы поговорим ниже, а пока попробуем развить это соображение дальше.

Назад
Обеды: доставка обедов новости. почитать о ведение учета. тут. Межкомнатные двери производсво россии. Тесты