Рекурсия, итерация и оценки сложности алгоритмов

Более подробное изложение материала, рассматриваемого в данном параграфе, может быть найдено в книгах [9] и [4]. Вопросы, связанные с асимптотическими оценками сложности алгоритмов, подробно изложены в классической книге Кнута [6] и, охватывающем тематику двух первых курсов цикла программистских дисциплин, прекрасном издании [8].

Рекурсия и итерация

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

Определение 5.1. Рекурсия — это такой способ организации обработки данных, при котором программа вызывает сама себя непосредственно, либо с помощью других программ.

Определение 5.2. Итерация — способ организации обработки данных, при котором определенные действия повторяются многократно, не приводя при этом к рекурсивным вызовам программ.

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

Факториал $$n$$! целого неотрицательного числа $$n$$ задается следующими соотношениями:

Числами Фибоначчи $$f_n$$ называют последовательность величин 0, 1, 1, 2, 3, 5, 8, $$\ldots$$, определяемую равенствами:

Математическая модель итерации сводится к повторению некоторого преобразования (отображения) $$T\colon X \rightarrow X$$ на множестве переменных программы $$X$$ (прямом произведении множеств значений отдельных переменных). Программной реализацией итерации является обычно некоторый цикл, тело которого осуществляет преобразование $$T$$.

В качестве примера можно рассмотреть схему вычисления факториала натурального числа в соответствии с его другим определением: $$n! = 1 \cdot 2 \cdot \ldots \cdot n$$. При написании программы в соответствии с ним нужно работать с двумя величинами целого типа $$\mathbb{Z}_M$$: числом $$i$$, которое будет играть роль счетчика и изменяться от 1 до $$n$$ включительно, и величиной $$k$$, в которой будет накапливаться произведение чисел от 1 до $$i$$.

Пространством $$X$$ в данном случае будет $$\mathbb{Z}^2_M$$, в качестве начальной точки в этом пространстве возьмем точку $$(1, 1)$$ (что соответствует $$i = k = 1$$ ), а преобразование $$T\colon X \rightarrow X$$ будет иметь вид $$T(i,k) = (i+1,k*i)$$. В случае, например, трехкратного применения преобразования $$T$$ получим $$T(T(T(1,1))) = T(T(2,1)) = T(3,2) = (4,6)$$, что обеспечит вычисление факториала числа 3.

Рекурсия и итерация взаимозаменяемы. Более точно, справедливо следующее утверждение.

Теорема 5.1. Любой алгоритм, реализованный в рекурсивной форме, может быть переписан в итерационном виде, и наоборот.

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

Особенности рекурсивных программ

Решая некоторую задачу, рекурсивный алгоритм вызывает сам себя для решения ее подзадач. Вот классический пример.

Задача 5.1. Напишите рекурсивную программу, вычисляющую факториал введенного натурального числа.

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

public class FactR {
    static int f(int x) {
        return (x == 0) ? 1 : x * f(x-1);
    }	
    public static void main(String[] args) throws Exception {    
        Xterm.println("n!=" + f(Xterm.inputInt("n=")));
    }
}

Организация рекурсивных вычислений на языке Java не требует использования никаких специальных конструкций — достаточно известного нам вызова метода. В приведенной программе метод f получает на вход целое число x и рекурсивно вычисляет его факториал. Рассмотрим процесс выполнения данной программы для $$n=3$$ более подробно.

Вызов метода f с аргументом 3 представим в виде листа бумаги, на котором указано входное значение (число 3). Универсальный исполнитель должен выполнить предписанные действия на этом листе бумаги и получить итоговый результат. Так как число 3 отлично от нуля, универсальный исполнитель попытается умножить число 3 на f(2), но последняя величина для ее вычисления требует вызова метода f с аргументом 2.

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

Вычисление f(2) потребует нахождения f(1), что вызовет появление еще одного листа бумаги — третьего экземпляра метода f. Он, в свою очередь, вызовет f(0). В этот момент накопится уже пачка листов (ее называют стеком вызовов ) — целых четыре штуки. При этом вычисления на всех нижних листах приостановлены до завершения работы с верхними.

Далее события будут развиваться следующим образом. Метод f, вызванный с нулевым аргументом, самостоятельно вычисляет и возвращает с помощью оператора return результат — число 1. Верхний элемент из стека вызовов методов после этого удаляется и возобновляются вычисления величины f(1). Этот процесс продолжается до тех пор, пока стек вызовов не станет пустым, что произойдет по завершению вычисления значения f(3). Итоговое значение 6 будет возвращено в метод main, который его и напечатает.

При написании рекурсивных программ обычно необходимо исследовать два основных вопроса:

а) всегда ли и почему программа заканчивает работу?

б) почему после окончания работы программы будет получен требуемый результат?

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

Рассмотрим следующее утверждение $$P$$, зависящее от числа $$n$$: программа завершает свою работу для входного значения $$n$$ за конечное время. Для того чтобы доказать истинность утверждения $$P(n)$$ для всех целых неотрицательных чисел с помощью метода математической индукции достаточно проверить его истинность при нулевом значении $$n$$ (база индукции) и убедиться в справедливости индуктивного перехода, что требует проверки истинности предиката $$P(n) \Rightarrow P(n+1)$$.

При нулевом значении аргумента программа завершает свою работу немедленно, поэтому утверждение $$P(0)$$ истинно и база индукции проверена.

Пусть утверждение $$P(n)$$ истинно при некотором значении $$n$$. Покажем, что и $$P(n+1)$$ тогда истинно. Для вычисления f(n+1) в соответствии с текстом программы нужно перемножить n+1 и f(n). Истинность $$P(n)$$ гарантирует нам вычисление второго множителя за конечное время, а так как перемножение двух чисел тоже требует конечного времени, то и $$P(n+1)$$ истинно, что и завершает доказательство завершения работы программы при всех целых неотрицательных значениях аргумента.

Заметим, что для отрицательных значений $$n\in\mathbb{Z}$$ данная программа должна была бы работать бесконечно долго (как принято говорить, должна зациклиться ). Однако из-за того, что в реальности мы имеем дело с машинным заменителем множества целых чисел — множеством $$\mathbb{Z}_M$$, выполнение всегда завершится за конечное время, хотя полученный результат и не будет иметь никакого смысла.

Доказательство правильности вычисляемого приведенной программой значения проводится совершенно аналогично. Рассмотрим утверждение $$P(n) =$$ ( для входного значения $$n$$ результатом является $$n$$!) и докажем его истинность по индукции.

Истинность $$P(0)$$ (база индукции) проверяется непосредственно, а для проверки корректности индуктивного перехода напишем следующую цепочку равенств: $$P(n+1) = (n+1)\cdot P(n) = (n+1) \cdot n! = (n+1)$$!, первое из которых следует из текста программы, второе — из предположения индукции, а третье — из определения факториала. Это завершает доказательство теоретической правильности написанной программы.

В реальности, однако, быстрый рост функции $$n$$! и ограниченность множества $$\mathbb{Z}_M$$ приводят к тому, что эта программа позволяет получить правильные результаты только при очень небольших значениях $$n$$. Уже при $$n=13$$ печатаемое ей значение 1932053504 отличается от правильного 6227020800, а при $$n=17$$ программа выдает даже отрицательный результат!

Рассмотрим еще одну задачу.

Задача 5.2. Напишите рекурсивную программу, печатающую $$n$$ -ое число Фибоначчи.

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

public class FibR {
    static int fib(int x) {
        return (x > 1) ? fib(x-2) + fib(x-1) : (x == 1) ? 1 : 0;
    }	
    public static void main(String[] args) throws Exception {    
        int n = Xterm.inputInt("Введите n -> ");
        Xterm.println("fib(" + n + ") = " + fib(n));
    }
}

Обратите внимание, что при вычислении $$f_5$$ в соответствии с этой программой понадобится найти $$f_4$$ и $$f_3$$. Определение $$f_4$$, в свою очередь, потребует вычисления $$f_3$$ и $$f_2$$, и так далее. Внимательно изучение содержимого стека вызовов для этой задачи показывает, что для нахождения каждого следующего числа Фибоначчи требуется примерно вдвое большее время, чем для определения предыдущего. Для того, чтобы убедиться в этом, нарисуйте дерево, изображающее процесс вычисления $$f_7$$ с помощью данной программы.

Java и циклические конструкции

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

Язык Java предусматривает три различных оператора цикла: while, do-while и for. Первый из них обычно используют в ситуации, когда тело цикла нужно выполнить нуль или более раз, а второй применяется, если его выполнение хотя бы раз обязательно. Третий из операторов является наиболее универсальным и используется в различных ситуациях.

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

В качестве первого примера рассмотрим опять задачу вычисления факториала и программу, реализующую предложенную выше схему применения преобразования $$T(i,k) = (i+1,k*i)$$.

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

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

public class FactIv1 {
    public static void main(String[] args) throws Exception {    
        int n, i, k;
        n = Xterm.inputInt("Введите n -> ");
        i = k = 1;
        while (i <= n) {
            k *= i;
            i += 1;
        }
        Xterm.println("" + n + "! = " + k);
    }
}

Конструкцию while в ней можно заменить на do-while:

Фрагмент программы (FactIv2.java)

do {
            k *= i;
            i += 1;
        } while (i <= n);

А еще лучше воспользоваться циклом for:

Фрагмент программы (FactIv3.java)

int i, k, n = Xterm.inputInt("Введите n -> ");
        for (i = k = 1; i <= n; i++)
            k *= i;
        Xterm.println("" + n + "! = " + k);

Основы оценок сложности алгоритмов

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

Нахождение точной зависимости $$T(n)$$ для конкретной программы — задача достаточно сложная. По этой причине обычно ограничиваются асимптотическими оценками этой функции, то есть описанием ее примерного поведения при больших значениях параметра $$n$$. Иногда для асимптотических оценок используют традиционное отношение $$O$$ (читается "О большое") между двумя функциями $$f(n) = O(g(n))$$, определение которого можно найти в любом учебнике по математическому анализу, хотя чаще применяют отношение эквивалентности $$\Theta$$ (читается "тэта большое"). Его формальное определение есть, например, в книге [8], хотя нам пока достаточно будет понимания данного вопроса в общих чертах.

В качестве первого примера вернемся к только что рассмотренным программам нахождения факториала числа. Легко видеть, что количество операций, которые должны быть выполнены для нахождения факториала $$n$$! числа $$n$$ в первом приближении прямо пропорционально этому числу, ибо количество повторений цикла (итераций) в данной программе равно $$n$$. В подобной ситуации принято говорить, что программа (или алгоритм) имеет линейную сложность (сложность $$O(n)$$ или $$\Theta(n)$$ ).

Можно ли вычислить факториал быстрее? Оказывается, да. Можно написать такую программу, которая будет давать правильный результат для тех же значений $$n$$, для которых это делают все приведенные выше программы, не используя при этом ни итерации, ни рекурсии. Ее сложность будет $$\Theta(1)$$, что фактически означает организацию вычислений по некоторой формуле без применения циклов и рекурсивных вызовов!

Не менее интересен и пример вычисления $$n$$ -го числа Фибоначчи. В процессе ее исследования фактически уже было выяснено, что ее сложность является экспоненциальной и равна $$\Theta(2^n)$$. Подобные программы практически не применимы на практике. В этом очень легко убедиться, попробовав вычислить с ее помощью 40-е число Фибоначчи. По этой причине вполне актуальна следующая задача.

Задача 5.4. Напишите программу, печатающую $$n$$ -ое число Фибоначчи, которая имела бы линейную сложность.

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

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

public class FibIv1 {
    public static void main(String[] args) throws Exception {    
        int n = Xterm.inputInt("Введите n -> ");
        Xterm.print("f(" + n + ")");
        if (n < 0) {
            Xterm.print(" не определено\n");
        } else if (n < 2) {
            Xterm.println(" = " + n);
        } else {
            long i = 0;  
            long j = 1;  
            long k;
            int  m = n;  
            while (--m > 0) {
                k  = j;
                j += i;
                i  = k;
            }	    
            Xterm.println(" = " + j);
        }
    }
}

Следующий вопрос вполне естественен — а можно ли находить числа Фибоначчи еще быстрее?

После изучения определенных разделов математики совсем просто вывести следующую формулу для $$n$$ -ого числа Фибоначчи $$f_n$$, которую легко проверить для небольших значений $$n$$:

Может показаться, что основываясь на ней, легко написать программу со сложностью $$\Theta(1)$$, не использующую итерации или рекурсии.

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

public class FibIv2 {
    public static void main(String[] args) throws Exception {    
        int    n = Xterm.inputInt("Введите n -> ");
        double f = ( 1.0 + Math.sqrt(5.) ) / 2.0;
        int    j = (int)( Math.pow(f,n) / Math.sqrt(5.) + 0.5 );

        Xterm.println("f(" + n + ") = " + j);
    }
}

На самом деле эта программа использует вызов функции возведения в степень { Math.pow(f,n) }, которая не может быть реализована быстрее, чем за логарифмическое время ( $$\log_2 n$$ ). Про алгоритмы, в которых количество операций примерно пропорционально $$\log n$$ (в информатике принято не указывать основание двоичного логарифма) говорят, что они имеет логарифмическую сложность ( $$\Theta(\log n)$$ ).

Для вычисления $$n$$ -го числа Фибоначчи существует такой алгоритм, программную реализацию которого мы приведем без дополнительных комментариев, — иначе нужно объяснять слишком много (связь чисел Фибоначчи со степенями некоторой матрицы порядка два, использование классов для работы с матрицами, алгоритм быстрого возведения матрицы в степень).

Задача 5.5. Напишите программу, печатающую $$n$$ -ое число Фибоначчи, которая имела бы логарифмическую сложность.

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

public class FibIv3 {
    public static void main(String[] args) throws Exception {    
        int n = Xterm.inputInt("Введите n -> ");
        Xterm.print("f(" + n + ")");
        if (n < 0) {
            Xterm.println(" не определено");
        } else if (n < 2) {
            Xterm.println(" = " + n);
        } else {
            Matrix b = new Matrix(1, 0, 0, 1);
            Matrix c = new Matrix(1, 1, 1, 0);
            while (n>0) {
                if ((n1) == 0) {
                    n >>>= 1; c.square();
                } else {
                    n  -=  1; b.mul(c);
                }
            }
            Xterm.println(" = " + b.fib());
        }
    }
}
class Matrix {
    private long a, b, c, d;
    
    public Matrix(long a, long b, long c, long d) {
        this.a = a; this.b = b; this.c = c; this.d = d;
    }
    public void mul(Matrix m) {	
        long a1 = a*m.a+b*m.c;  long b1 = a*m.b+b*m.d;
        long c1 = c*m.a+d*m.c;  long d1 = c*m.b+d*m.d;
        a = a1; b = b1; c = c1; d = d1;
    }
    public void square() {
        mul(this);
    }
    public long fib() {
        return b;
    }
}

Если попробовать посчитать десятимиллионное число Фибоначчи с помощью этой и предыдущей программ, то разница во времени счета будет вполне очевидной. К сожалению, результат будет неверным (в обоих случаях) в силу ограниченности диапазона чисел типа long.

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

Рассмотрим четыре алгоритма решения одной и той же задачи, имеющие сложности $$\log n$$, $$n$$, $$n^2$$ и $$2^n$$ соответственно. Предположим, что второй из этих алгоритмов требует для своего выполнения на некотором компьютере при значении параметра $$n=10^3$$ ровно одну минуту времени. Тогда времена выполнения всех этих четырех алгоритмов на том же компьютере при различных значениях параметра будут примерно такими, как в таблице 5.1.

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

С увеличением быстродействия компьютеров возрастают и значения параметров, для которых работа того или иного алгоритма завершается за приемлемое время. Таким образом, увеличивается среднее значение величины $$n$$, и, следовательно, возрастает величина отношения времен выполнения быстрого и медленного алгоритмов. Чем быстрее компьютер, тем больше относительный проигрыш при использовании плохого алгоритма!

Массивы в языке Java

Язык Java, так же как и многие другие языки, позволяет работать с массивами элементов различных типов. Массив (array) используют, когда возникает необходимость хранить несколько однотипных значений, например, 50 целых чисел или 100 наименований книг, так как было бы неудобно использовать в таких случаях различные имена для всех этих переменных. В ближайшее время мы будем работать только с одномерными массивами и не будем пользоваться тем, что массивы — динамические структуры данных. Об этом речь пойдет в третьей главе книги.

Рассмотрим следующую простейшую задачу на работу с массивом целых чисел.

Задача 5.6. Напишите программу, которая вводит с клавиатуры непустой массив целых чисел, печатает его, затем инвертирует (то есть меняет местами первый элемент с последним, второй — с предпоследним и т.д.), и вновь печатает.

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

public class InvArr {
    public static void main(String[] args) throws Exception {    
        int n, i, a[];
        n = Xterm.inputInt("Введите длину массива n -> ");
        a = new int[n];

        for (i=0; i<n; i++)
            a[i] = Xterm.inputInt("Введите a[" + i + "] -> ");
        Xterm.print("Введенный массив a =");
        for (i=0; i<n; i++)
            Xterm.print(" " + a[i]);

        Xterm.print("\nИнвертированный массив a =");
        for (i=0; i<n/2; i++) {
            int j = a[i]; a[i] = a[n-1-i]; a[n-1-i] = j;
        }
        for (i=0; i<n; i++)
            Xterm.print(" " + a[i]);
        Xterm.print("\n");
    }
}

Как видно из текста этой программы, для того чтобы завести массив, необходимо объявить его и зарезервировать затем память для его элементов с помощью оператора new. В этом случае все они будут автоматически проинициализированы нулевыми значениями. Массив из трех целых чисел, содержащий величины 3, 7 и 11, можно задать так:

Элементы любого массива нумеруются с нуля, а для доступа к $$i$$ -му его элементу используется выражение $$a[i]$$. Язык Java отслеживает все попытки обратиться к несуществующему элементу массива — при попытке работать, скажем с $$a[n]$$, возникает исключительная ситуация ( выход индекса за границу массива ), так как последний элемент имеет индекс $$n-1$$, а не $$n$$.

В качестве более содержательного комментария к программе инвертирования массива заметим, что выполнение цикла, переставляющего элементы, завершается, как только будет достигнута середина массива. Если условие продолжения цикла $$i<n/2$$ заменить на $$i<n$$, то процесс обмена не завершится после того, как массив уже будет инвертирован, и обмен элементов продолжится, что приведет к двукратному инвертированию массива, что эквивалентно тождественному преобразованию.

Рассмотрим еще одну задачу.

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

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

public class MaxArr {
    public static void main(String[] args) throws Exception {    
        int n, i, a[];
        n = Xterm.inputInt("Введите длину массива n -> ");
        a = new int[n];
        for (i=0; i<n; i++)
            a[i] = Xterm.inputInt("Введите a[" + i + "] -> ");
        int max = a[0];
        for (i=1; i<n; i++)
            if (a[i] > max)
                max = a[i];
        Xterm.println("Максимальный элемент массива = " + max);
    }
}

В заключение рассмотрим задачу, включающую дополнительное требование на структуру программы.

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

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

public class NumMaxArr {
    public static void main(String[] args) throws Exception {    
        int n, i, a[];
        n = Xterm.inputInt("Введите длину массива n -> ");
        a = new int[n];
        int max  = Integer.MIN_VALUE;
        int nMax = 0;
        for (i=0; i<n; i++) {
            a[i] = Xterm.inputInt("Введите a[" + i + "] -> ");
            if (a[i] > max) {
                max  = a[i];
                nMax = 1;
            } else if (a[i] == max)
                nMax += 1;
        }
        Xterm.println("Количество макс. элементов = " + nMax);   
    }
}

Использование константы Integer.MIN_VALUE позволяет избежать необходимости присваивания переменной max значения нулевого элемента массива до начала циклического просмотра остальных элементов.

Можно заметить, что при решении этой задачи массив по существу не используется. Если в этой программе удалить описание массива a, заменив его на описание целой переменной a, и произвести замену всех вхождений выражения a[i] на a, то программа останется работающей.

Задача сортировки является классической задачей на массивы.

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

Приведенный ниже алгоритм, который последовательно обменивает все соседние пары элементов, расположенных в неправильном порядке, является одним из самых медленных алгоритмов сортировки среди всех широко известных — его асимптотическая сложность является квадратичной ( $$\Theta(n^2)$$ ).

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

public class Sort {
    private static void sort(int[] a, int n) {
        int i, j, t;
        for (i=0; i<n-1; i+=1) 
            for (j=n-1; j>i; j-=1)
                if (a[j] < a[j-1]) {
                    t=a[j]; a[j]=a[j-1]; a[j-1]=t;
                }
    }
    public static void main(String[] args) throws Exception {    
        int n, i, a[];
        n = Xterm.inputInt("Введите длину массива n -> ");
        a = new int[n];
        for (i=0; i<n; i++)
            a[i] = Xterm.inputInt("Введите a[" + i + "] -> ");
    
        Xterm.print("Исходный массив\n");
        for (i=0; i<n; i++)
            Xterm.print(" " + a[i]);
        Xterm.print("\n");
    
        sort(a, n);
        Xterm.print("Отсортированный массив\n");
        for (i=0; i<n; i++)
            Xterm.print(" " + a[i]);
        Xterm.print("\n");
    }
}

Исключительные ситуации и работа с последовательностями

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

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

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

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

public class NumMaxSeqv1 {
    public static void main(String[] args) {    
        int max  = Integer.MIN_VALUE;
        int nMax = 0;
        try {
            while (true) {
                int x = Xterm.inputInt("Очередной элемент x -> ");
                if (x > max) {
                    max  = x;
                    nMax = 1;
                } else if (x == max)
                    nMax += 1;
                Xterm.println("Количество макс. элементов = "
                            + nMax);
            }
        } catch(Exception e) {
            ;
        }
    }
}

Эта программа использует конструкцию try-catch, предназначенную для обработки исключительных ситуаций (называемых и просто исключениями). Интерпретатор байт-кода пытается выполнить все действия, указанные в блоке try ( try переводится именно так — пытаться ). Если это удается, то содержимое блока catch не оказывает никакого влияния на ход выполнения программы. Однако, если в процессе выполнения блока try возникает исключительная ситуация — нечто препятствующее продолжению нормального выполнения программы, то управление немедленно передается блоку catch ( catch означает поймать ).

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

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

Фрагмент программы (NumMaxSeqv2.java)

try {
            while (true) {
                int x = Xterm.inputInt("Очередной элемент x -> ");
                if (x > max) {
                    max  = x;
                    nMax = 1;
                } else if (x == max)
                    nMax += 1;
            }
        } catch(Exception e) {
            Xterm.println("\nКоличество макс. элементов = "
                        + nMax);
        }

Заметьте, что для программ, предусматривающих обработку исключительных ситуаций, теряет свою актуальность совет о необходимости дописывания фразы throws Exception в строку, начинающую определение метода main.

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

Задача 5.11. Напишите программу, вычисляющую факториал введенного натурального числа, не использующую ни итерации, ни рекурсии (имеющую сложность $$\Theta(1)$$ ).

Указание Воспользуйтесь тем, что факториал — очень быстро растущая функция, а множество $$\mathbb{Z}_M$$ — ограничено, и поэтому любая программа, работающая с величинами типа int, способна вычислить факториал только очень небольших чисел.

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

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

Указание Можете попробовать разобраться в программе, решающей задачу 5.5. В ней выполняется более сложное действие — квадратная матрица возводится в степень $$n$$ за логарифмическое время.

Задача 5.14. Напишите программу, вводящую целое число $$a$$ и натуральное $$n$$, вычисляющую и печатающую степень $$a^n$$ без использования вызова функции возведения в степень.

Задача 5.15. Напишите программу (быстрое возведение в степень), возводящую целое число $$a$$ в целую неотрицательную степень $$b$$ без вызова функции возведения в степень с временной сложностью $$\Theta(\log b)$$.

Задача 5.16. Напишите программу, печатающую сумму квадратов всех натуральных чисел от 1 до введенного натурального $$n$$, которая имела бы константную сложность, т.е. не использовала бы ни итерации, ни рекурсии.

Задача 5.17. Напишите программу, вводящую натуральное число, и печатающую Yes, если оно является простым и No иначе.

Задача 5.18. Напишите программу, печатающую $$n$$ -ое простое число.

Задача 5.19. Напишите рекурсивную программу, печатающую биноминальный коэффициент $$C_n^k$$ для целых $$n$$ и $$k$$, где $$0\leqslant k\leqslant n$$. Для неотрицательных $$n$$ и $$k$$ имеют место следующие соотношения: $$C_n^0 = C_n^n = 1$$, $$C_{n+1}^{k+1} = C_n^{k+1} + C_n^k$$.

Задача 5.20. Напишите программу, вводящую имя пользователя (с применением метода inputChars ), которая затем приветствует его.

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

Задача 5.22. Напишите программу, которая вводит с клавиатуры непустой массив целых чисел, и печатает Yes, если массив симметричен, и No иначе.

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

Задача 5.24. Напишите программу, которая вводит с клавиатуры непустой массив целых чисел, циклически сдвигает элементы массива вправо на $$k$$ позиций, и печатает результат. Число $$k$$ вводится с клавиатуры, а сложность программы должна быть $$\Theta(n)$$.

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

Задача 5.26. Напишите программу (линейный поиск), определяющую первое вхождение заданного целого числа $$x$$ в массив целых чисел, заведомо содержащий это число.

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

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

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

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

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

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

Задача 5.33. Напишите программу, вводящую фразу русского языка (с использованием метода inputChars ), которая определяет, является ли введенная фраза палиндромом.

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