Метод декомпизации.Его применение на примере бинарного поиска

Метод декомпизации. Его применение на примере решение задачи о Ханойской башне

Анализ эфиктивности рекурсивных алгоритмов..Когда рекурсия не нужна

Рекурсивное программирование дает нам общий подход к решению задач – разбиению их на аналогичные подзадачи меньшей размерности, либо на задачи, представляющие собой шаги в возможных направлениях ее решения. Так или иначе, рекурсивные вызовы образуют древовидную структуру, количество вершин в которой определяет эффективность алгоритма (выражаемую обычно через трудоемкость). Разница между различными типами алгоритмов состоит в способе получения подзадач, их размерности, способе соединения полученных результатов.

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

Основные методы проектирования алгоритмов

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

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

Основные типы данных

В языке определены следующие базовые типы данных:

целый