Журналы
Email: Пароль: Войти Регистрация
E-mail: shilov@iis.nsk.su

Кандидат физ.-мат. наук, старший научный сотрудник Института систем информатики имени А.П. Ершова СО РАН

Статьи автора:

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

This paper is about programming paradigms, how different paradigms can fertilize each other. In particular the paper discusses a challenging contest programming problem and solves it in three programming paradigms: logic, functional and imperative. It can be considered as a case study of algorithm inversion, since we start with logic algorithm, that answers the question "Is balancing M times sufficient for detecting a single fake in a set of coins?", and finishes with imperative algorithm, that effectively computes the minimal number of balancing that is sufficient for detection the fake. Functional paradigm is used for developing an intermediate functional algorithm that also computes the minimal number of balancing, but inefficiently, while the efficient imperative algorithm is a Р’В«lazy memoizationР’В» of the functional one.

Ключевые слова: парадигмы программирования, императивное программирование, функциональное программирование, логическое программирование, мемоизация, динамическое программирование.
Keywords: programming paradigms, imperative programming, functional programming, logical programming, memoization, dynamic programming.
Для пополнения баланса выберите страну, оператора и отправьте СМС с кодом на указанный номер. Отправив одну смс, вы получаете доступ к одной статье.
Закрыть