Заметки о трёх парадигмах программирования

Abstract

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.