Постановка задачи, как правило, оставляет программисту возможность выбора пути для ее решения. Свидетельством тому служит разнообразие алгоритмических механизмов, включая не только упомянутые нами выше, но и некоторые другие. Возникают ли сомнения в том, что они должны входить в арсенал программиста?

В самом деле, "сходу" написанная программа вполне может оказаться неэффективной. Но всякий ли программист удосуживается выяснить это? К сожалению, с характерными примерами "скрытой" неэффективности нам неоднократно приходилось сталкиваться, обсуждая с юными кодировщиками предложенные ими алгоритмические и программные решения. Наиболее популярны при этом доводы, что готовая программа, во-первых, работает, во-вторых, работает быстро, и вообще, мол, "чего вы от меня (или от нее, то бишь, программы) хотите".

Действительно, представленный продукт выглядит работоспособным, и трудно убедить кодировщика, что ему стоит поразмыслить еще. Дело в том, что уровень сложности учебных задач, с которыми начинающим программистам приходится иметь дело, не слишком высок. Если приходится строить алгоритм полиномиальной сложности, то обычно она не превышает O(n²), в крайнем случае, O(n³). А мы уже знаем, что при небольших значениях n реальное время выполнения такого вычислительного процесса не дает повода для поисков лучшего решения. В то же время, подготовкой сколько-нибудь значительного набора данных, с целью проверки поведения программы при больших n, те же программисты себя не утруждают. Что касается сложности экспоненциальной, то таких задач в учебном плане, - мы имеем в виду обыкновенный школьный курс информатики, - довольно мало, если они вообще представлены.

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

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

Разумеется, обсуждение эффективности только начинается с появлением циклической обработки. И нам надо идти дальше. Заманчивой выглядит идея Вирта, вынесенная в эпиграф. Но цель, которую мы преследуем в этом разделе, гораздо скромнее: мы не замахиваемся на "целый" курс, а хотим лишь продемонстрировать различия в алгоритмическом содержании задач, возникающих перед программистом. Что нам мешает проделать нечто подобное, - или хотя бы попытаться, - на основе объекта, знакомого любому читателю, - таблицы умножения!? Итак, предлагаем отнестись к дальнейшим рассуждениям как к некоему развернутому упражнению по конструированию алгоритмов.

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

Назад

Затягивает, не оторвешься - казуальные игры бесплатно. Новые казуальные игры.

Все сложное просто!