Алгоритмы и программы

Эта глава, с которой начинается изучение курса, служит двум основным целям:

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

Знание необходимых теоретических основ позволит во второй главе перейти к изучению методов построения программ и доказательства их правильности — теории, которая будет применяться для практического написания программ параллельно со знакомством с ней. Таким образом, два кажущиеся совершенно не связанными друг с другом потока изучения материала — теоретический и практический, сольются в один уже в следующей главе. Пока же читателю остается только поверить в то, что знание всего материала первой главы является необходимым условием для успешного перехода к изучению следующей.

И последнее замечание — чисто технологическое. На первой стадии изучения языка Java полезно отвлечься от того факта, что он является объектно-ориентированным, и сосредоточиться на содержательных проблемах корректной реализации алгоритма. Однако это не так просто сделать — написание даже самой простейшей программы на нем невозможно без понимания основных концепций ООП. Для частичного решения этой проблемы используется созданный специально для этих целей класс Xterm, ограждающий начинающего программиста от сложностей реального мира языка Java.

Предмет науки программирования

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

Этот пример вполне объясняет, почему описания последовательности действий, предназначенные для автоматического устройства, должны быть совершенно однозначны и заданы с помощью некоторой формальной системы обозначений. Очень часто создание таких описаний связано со значительными техническими и принципиальными трудностями. Данная проблема стала чрезвычайно актуальной в связи с повсеместным распространением электронных вычислительных машин (ЭВМ), часто используемых в качестве универсального исполнителя команд.

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

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

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

Подход, когда некоторое не до конца четко определенное понятие активно используют, в науке весьма типичен. Например, точные определения натуральных и действительных чисел не рассматривают ни только в средней школе, но даже и в большинстве ВУЗов. Более того, говорят, что сороконожка даже ходить разучилась, когда задумалась над тем, в каком порядке она переставляет ноги.

Пример и свойства алгоритма

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

Задача 1.1. Придумайте алгоритм, вводящий натуральное число, большее единицы,который находит наименьший простой делитель этого числа.

Алгоритм решения задачи.

Алгоритм П:

П1: Положить целое число $$i$$ равным двум и перейти на шаг П2.

П2: Если $$k$$ делится нацело на $$i$$, то завершить работу алгоритма, выдав в качестве результата $$i$$ ; иначе перейти на шаг П3.

П3: Увеличить значение $$i$$ на единицу и перейти на шаг П2.

Для того чтобы понять этот алгоритм, надо выступить в роли компьютера (или скорее даже универсального исполнителя команд), выполняя вручную указанную в нем последовательность действий для некоторых небольших значений $$k$$. Будем записывать значения величины $$i$$ после каждого шага алгоритма.

Подобное исследование дает основание полагать, что после завершения работы алгоритма переменная $$i$$ действительно будет содержать наименьший простой делитель исходного числа $$k$$. В данном случае это не сложно доказать и совершенно строго. Обязательно сделайте это.

Основные свойства любого алгоритма — это конечность, определенность, вход (ввод), выход (вывод) и эффективность. Рассмотрим их последовательно более подробно.

Конечность. Алгоритм должен всегда заканчиваться после выполнения конечного числа шагов. Алгоритм П удовлетворяет этому условию, так как величина $$i$$ вначале меньше $$k$$, ее значение увеличивается на единицу к каждому очередному выполнению шага П2, и поэтому выполнение алгоритма будет прекращено на шаге П2 при $$i = k$$, если $$k$$ — простое число, или ранее при составном $$k$$.

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

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

Вход (input). Алгоритм всегда имеет некоторое (иногда равное нулю) количество входных данных, то есть величин, передаваемых ему до начала работы. В алгоритме П, например, одна входная величина — целое число $$k$$, большее единицы. Примером алгоритма, имеющего пустое множество входных данных, может служить алгоритм, вычисляющий 1000-е простое число.

Выход (output). Алгоритм всегда обязан иметь одну или несколько выходных величин. В случае алгоритма П такой величиной является число $$i$$. Алгоритмы, не имеющие выходных данных, бесполезны на практике, и мы не будем их изучать.

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

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

Из вышесказанного следует, что на ЭВМ практически невозможно работать с действительными числами, что, по всей видимости, может показаться вам неправдоподобным. На самом деле это так. Более того, даже с настоящими целыми числами на компьютере работают не так уж и часто. Обычно вместо множеств целых $$\mathbb{Z}$$ и действительных $$\mathbb{R}$$ чисел приходится работать с их заменителями $$\mathbb{Z}_M$$ и $$\mathbb{R}_M$$ соответственно. Эти машинные аналоги часто вполне позволяют забыть о том, что мы имеем дело не с настоящими числами, но иногда особенности представления чисел в ЭВМ проявляются весьма неожиданным образом. Данной теме посвящена лекция 4 курса.

Понятие эффективности алгоритма имеет и свои количественные характеристики. Различают временную и емкостную эффективности. Первая из них характеризует время выполнения алгоритма, а вторая — требуемый для этого объем памяти. Важнейшие для практики вопросы оценки временной эффективности или сложности (complexity) алгоритмов рассматриваются ниже, в лекции 5.

Парадигмы программирования

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

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

C и Pascal являются примерами языков, предназначенных для директивного программирования (directive programming), когда разработчик программы использует процессно-ориентированную модель, то есть пытается создать код, должным образом воздействующий на данные. Активным началом при этом подходе считается программа (код), которая должна выполнить все необходимые для достижения нужного результата действия над пассивными данными.

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

Сейчас весьма распространенным стал объектно-ориентированный (object oriented) подход, реализуемый, например, языками C++ и Java. При этом, наоборот, первичными считаются объекты (данные), которые могут активно взаимодействовать друг с другом с помощью механизма передачи сообщений (называемого также и механизмом вызова методов). Функция программиста в этом случае подобна роли бога при сотворении Вселенной — он должен придумать и реализовать такие объекты, взаимодействие которых после старта программы приведет к достижению необходимого конечного результата.

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

Задача 1.2. Напишите программу, вводящую натуральное число, большее единицы, которая находит и печатает наименьший простой делитель этого числа.

Текст программы

public class MinDivider {
    public static void main(String[] args) throws Exception {    
        int k = Xterm.inputInt("Введите натуральное число," +
                               "большее единицы: ");
        int i = 2;
        while (k%i != 0)
            i++;
        Xterm.println("Наименьший простой делитель числа " +
                    k + " равен " + i);
    }
}

Функциональное и логическое программирование использует языки типа Lisp, Haskell и Prolog. Эта парадигма базируется на принципиально иной трактовке понятия программы. Здесь главным является точная формулировка задачи, а выбор и применение необходимого алгоритма для ее решения — проблема исполняющей системы, но не программиста.

Задачи для самостоятельного решения

Задача 1.3.Придумайте алгоритм, вводящий три целых числа и определяющий, есть ли среди введенных чисел одинаковые или нет.

Задача 1.4.Придумайте алгоритм, вводящий три целых числа, который находит второе по величине число, если оно существует.

Задача 1.5.Придумайте алгоритм, вводящий три целых числа, определяющий количество максимальных чисел среди введенных.

Задача 1.6.Придумайте алгоритм, вводящий действительное число, который рассматривает это число, как координаты точки на прямой, и находит расстояние от этой точки до отрезка [0,1].

Задача 1.7.Придумайте алгоритм, находящий n -ое простое число.

Функциональное программирование

Для того чтобы представить себе стиль, в котором пишутся программы при использовании функциональных языков, рассмотрим несколько примеров программ на языке Haskell. Сначала разберем две программы, вычисляющие факториал $$n$$! натурального числа $$n$$ в соответствии с его различными определениями.

Первое определение $$n!$$ имеет вид $$n! = 1 \cdot 2 \cdot \ldots \cdot n$$, а соответствующая ему программа не содержит ничего, кроме записи этого определения на языке Haskell:

f n = product [1..n]

Второе определение факториала расширяет область определения этой операции и является рекурсивным.

$$0! = 1,\\ n! = n \cdot (n-1)! \quad\text{для}\quad n > 0.$$

Программа, написанная в соответствии с ним, тоже является просто его переформулировкой:

f 0 = 1

f x = x * f (x-1)

В качестве значительно более сложного примера приведем текст программы, которая находит и печатает все варианты таких расстановок символов +, -,*,/ и круглых скобок в $$n$$ -значном номере билета, что результатом вычислений будет число 100. Операция деления при этом допустима только в случае деления нацело, а количество $$n$$ цифр в билете может быть произвольным. Программа решения этой задачи на языке Haskell является удивительно короткой:

Текст программы

tickets ds = (ds, foldl (\n c -> 10*n + digitToInt c) 0 ds) :
 [("("++ld++[op]++rd++")", f lv rv) |
    (op,f) <- [('+',(+)),('-',(-)),('*',(*)),('/',(div))],
      n<-[1..length ds-1], (ld,lv) <- tickets (take n ds),
        (rd,rv) <- tickets (drop n ds), op /= '/' || (rv /= 0
           lv `mod` rv == 0)]
happy = map fst . (filter ((==)100 . snd)) . tickets

При использовании директивного или объектно-ориентированного подходов и таких языков, как C, C++ или Java, размер программы, решающей данную задачу, будет гарантированно намного большим. Справедливости ради надо отметить, что интерпретаторы функциональных языков обычно работают достаточно медленно.

Для запуска этой программы на компьютере, где установлен интерпретатор hugs языка Haskell, достаточно запустить его (набрав hugs ), а затем выполнить команды загрузки файла с программой ( :load ticket ) и запуска ее на выполнение. Последняя команда должна содержать в качестве параметра последовательность цифр билета в кавычках. Вот пример задания и полученного результата:

Main> (happy "234112")
["((2*(3+41))+12)","((2+3)*((41-1)/2))","(((2*3)+(4*11))*2)",
"(((2+3)*(41-1))/2)"]
Elapsed time (ms): 33150 (user), 20 (system)
Main>

Для выхода из интерпретатора hugs используйте команду :quit, а мы далее в этой книге не будем больше касаться проблем, связанных с функциональным или логическим программированием, — этому будут посвящены отдельные дисциплины на старших курсах обучения.