«Е.А. Роганов Основы информатики и программирования Учебное пособие для студентов программистских специальностей Москва 2001 ББК 22.18 УДК 519.6 Р59 Е.А. Роганов. Основы информатики и программирования: Учебное пособие ...»

министерство образования российской федерации

московский государственный индустриальный университет

кафедра информационные системы и технологии

центр компьютерных технологий

Е.А. Роганов

Основы

информатики и программирования

Учебное пособие для студентов

программистских специальностей

Москва 2001

ББК 22.18

УДК 519.6

Р59

Е.А. Роганов. Основы информатики и программирования: Учебное пособие М.: МГИУ, 2001. 315 с.

Рис. 34, табл. 8, библиогр. список 14 наименований.

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

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

Рецензент: В.А. Васенин, д.ф.-м.н., проф., начальник Центра Телекоммуникаций и Технологий Интернет МГУ Оригинал-макет подготовлен автором с использованием издательской системы L TEX.

A ЛР №020407 от 12.02.97.

Подписано в печать 24.09.01. Сдано в производство 25.12.01.

Формат бумаги 60x90/16 Бум. множ.

Усл.печ.л. 19,75 Уч.-изд.л. 21,0 Тем. план 2001 г., №1-19/ Тираж 500 Заказ № 333/ РИЦ МГИУ, 109280, Москва, Автозаводская, c Е.А. Роганов, ISBN 5-276-00187- c МГИУ, c ЦКТ, Оглавление Предисловие Глава I. Введение в информатику и программирование § 1. Алгоритмы и программы 1. Предмет науки программирование 2. Пример и свойства алгоритма 3. Парадигмы программирования 4. Задачи для самостоятельного решения 5. Функциональное программирование § 2. Основы языка Java 1. Java язык ООП 2. Основные свойства программ и первые примеры 3. Типы, переменные и операторы 4. Использование класса Xterm 5. Логические и условные операторы 6. Задачи для самостоятельного решения 7. Реализация класса Xterm § 3. Высказывания и предикаты 1. Зачем программисту предикаты 2. Синтаксис языка предикатов 3. Семантика предикатов 4. Расширение понятия предиката 5. Приоритеты и ассоциативность операторов языка Java 6. Задачи для самостоятельного решения § 4. Особенности представления чисел в ЭВМ 1. Представление информации в компьютере 2. Целые числа 3. Вещественные числа 4. Арифметические и побитовые операторы языка Java 5. Задачи для самостоятельного решения 6. Числа произвольной длины и точности § 5. Рекурсия, итерация и оценки сложности алгоритмов 1. Рекурсия и итерация Оглавление 2. Особенности рекурсивных программ 3. Java и циклические конструкции 4. Основы оценок сложности алгоритмов 5. Массивы в языке Java 6. Исключительные ситуации и работа с последовательностями 7. Задачи для самостоятельного решения § 6. Спецификация программ и преобразователь предикатов 2. Спецификация программы и преобразователь предикатов wp Глава II. Построение программ § 3. Индуктивные функции на пространстве последовательностей 1. Критерий индуктивности и стационарные значения 2. Проектирование цикла при помощи инвариантa Глава III. Применение ООП к разработке программных § 1. Основы объектно-ориентированного программирования 3. Аналитическая геометрия и программирование 2. Грамматики языка правильных арифметических формул 5. Интерпретатор арифметических выражений 4. Некоторые технологические вопросы и оптимизация В книге сделана попытка обобщить многолетний опыт автора в преподавании информатики и программирования студентам первого курса Московского государственного индустриального университета специальностей Прикладная математика и информатика и Математическое обеспечение и администрирование информационных систем.

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

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

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

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

• активное использование математических методов, что предполагает глубокое изучение различных разделов математики;

• реальное овладение навыками практической работы, что требует выполнения многочисленных упражнений на программирование;

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

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

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

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

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

Предисловие Условия задач, исходные тексты программ, являющихся решениями части из них, и некоторые другие дополнительные методические материалы по курсу размещены на веб-сайте центра компьютерных технологий МГИУ (http://www.ctc.msiu.ru/materials/books.php).

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

И.В. Абрамов, который сейчас активно работает со студентами старших курсов, является человеком, впервые реализовавшим основные принципы преподавания блока программистских дисциплин в МГИУ. Именно его опыт помог мне на первых этапах работы по подготовке курса.

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

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

• подготовить необходимую теоретическую базу для последующего овладения различными методами обработки информации, навыками программирования в малом и построения правильных эффективных программ;

• дать минимально необходимые для практического программирования знания о языке Java и предоставить образцы небольших типовых программ.

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

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

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

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

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

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

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

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

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

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

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

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

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

Алгоритм П:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Сейчас весьма распространенным стал объектно-ориентированный (object oriented) подход, реализуемый, например, языками C++ и Java.

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

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

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

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

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

public class MinDivider { public static void main(String[] args) throws Exception { int k = Xterm.inputInt("Введите натуральное число," + Xterm.println("Наименьший простой делитель числа " + Функциональное и логическое программирование использует языки типа Lisp, Haskell и Prolog. Эта парадигма базируется на принципиально иной трактовке понятия программы. Здесь главным является точная формулировка задачи, а выбор и применение необходимого алгоритма для ее решения проблема исполняющей системы, но не программиста.

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

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

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

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

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

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

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

натурального числа n в соответствии с его различными определениями.

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

f n = product [1..n] Второе определение факториала расширяет область определения этой операции и является рекурсивным.

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

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

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

tickets ds = (ds, foldl (\n c -> 10*n + digitToInt c) 0 ds) :

[("("++ld++[op]++rd++")", f lv rv) | (op,f) = (больше или равно), математическими обозначениями для которых являются и.

Из простейших логических выражений, к которым относятся логические переменные и результаты сравнений, можно конструировать более сложные, используя следующие логические операторы: унарный оператор отрицания !, бинарные операторы логического И (And) &, логического Или (Or) |, исключающего Или (sl Xor) ^, равенства ==, неравенства !=, условного И (short circuit And) && и условного Или (short circuit Or) ||, а также тернарный оператор условия ?:.

В математической теории исчисления предикатов отрицание принято обозначать символом ¬ (или просто !), операторам логического Или и И соответствуют дизъюнкция и конъюнкция, а равенство (эквивалентность) обозначают символами, или просто =.

Отрицание логического выражения, имеющего значение F (Ложь), есть T (Истина), и наоборот. Дизъюнкция истинна, если истинен хотя бы один из ее аргументов, а конъюнкция только при истинности обоих.

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

Управляющая конструкция if-else в зависимости от значения логического выражения позволяет выполнять различные части программного кода. В общей форме этот оператор записывается следующим образом:

if (логическое_выражение) блок1; [ else блок2; ] 30 Глава I. Введение в информатику и программирование Если условие, задаваемое заключенным в круглые скобки логическим выражением истинно, то будет выполняться блок1, иначе блок2. Часть else может и отсутствовать.

Управляющие конструкции if и if-else могут быть вложенными, и с помощью блока (block) (заключения нескольких операторов в фигурные скобки) позволяют помещать в каждую из двух своих ветвей произвольное число операторов. Это позволяет разделить поток управления программы на произвольное число частей.

Эту же задачу часто удобнее решать с помощью оператора switch, общий вид которого таков:

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

Рассмотрим использование описанных операторов на примере решения следующих несложных задач.

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

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

public class MaxVal3 { public static void main(String[] args) throws Exception { int a = Xterm.inputInt("Введите первое число -> ");

int b = Xterm.inputInt("Введите второе число -> ");

int c = Xterm.inputInt("Введите третье число -> ");

Xterm.println("Максимальное число из введенных = "+max);

В этой программе переменной max сначала присваивается максимальное значение из двух чисел a и b, а затем, если третье число c больше этой величины, переменной max присваивается его значение.

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

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

Для экономии места приведем только содержательную часть решения этой задачи.

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

Приведенная программа является достаточно громоздкой. Гораздо понятнее следующее решение той же задачи.

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

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

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

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

public class Equal3v1 { public static void main(String[] args) throws Exception { int a = Xterm.inputInt("Введите первое число -> ");

int b = Xterm.inputInt("Введите второе число -> ");

32 Глава I. Введение в информатику и программирование int c = Xterm.inputInt("Введите третье число -> ");

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

Как это следует из определений, если первый операнд дизъюнкции истинен, то независимо от значения второго операнда результатом будет истина. Аналогично в случае конъюнкции при ложном первом операнде значение второго операнда на результат не влияет он всегда будет ложным. При выполнении условных операторов || и && исполняющая система Java не производит оценку второго операнда логического выражения, если результат ясен из значения первого операнда. Иногда это просто ускоряет вычисления, а иногда позволяет добиться и большего, как, например, в следующем программном фрагменте.

При a = 0 второй операнд оператора || вычисляться не будет и деления на ноль не произойдет, как это было бы в случае использования логического оператора Или |.

Можно изменить проверяемое условие среди чисел есть равные в рассмотренной выше программе на его отрицание среди чисел нет равных и переписать программу, заменяя оператор Или на И.

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

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

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

И, наконец, заметим, что программа запишется короче, если заменить в ней оператор if-else на тернарный оператор условия ?:, общая форма записи которого имеет следующий вид:

выражение1 ? выражение2 : выражение §2. Основы языка Java Если результат вычисления первого выражения истинен, то выполняется выражение2 (второй операнд), а иначе выражение3 (третий операнд). При использовании этой конструкции два последних ее выражения должны иметь один и тот же тип, в данном случае строковый.

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

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

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

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

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

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

Задача 2.11. Напишите программу, вводящую действительные коэффициенты a, b и c квадратного уравнения ax2 +bx+c = 0 с положительным дискриминантом, находящую оба корня этого уравнения.

7. Реализация класса Xterm. Эта секция содержит для справки программную реализацию класса Xterm, который мы будем активно использовать всю первую половину нашего курса.

import java.io.*;

// Класс, обеспечивающий вывод строк текста с возможностью // позиционирования и использования цветов, а также ввод чисел // целых типов int и long и вещественных float и double.

public class Xterm { private static final DataInputStream in = new DataInputStream(System.in);

private static final int MAXLEN = 255;

private static String inputString() throws IOException { byte buf[] = new byte[MAXLEN];

int i = in.read(buf);

return new String(buf,0,i-1);

// Имена цветов символов и фона public static final int Magenta = 5;

// Метод очистки экрана public static void clear() { System.out.print("\033[2J");

// Метод позиционирования курсора public static void setPosition(int x, int y) { System.out.print("\033[" + (y+1) + ";" + (x+1) + "H");

// Методы вывода строки public static void print(String txt) { System.out.print("\033[0m\033[30;1m"+txt+"\033[0m\033[30m");

public static void print(String txt, int fg) { System.out.print("\033[0m\033[" + (30+fg) public static void print(String txt, int fg, int bg) { System.out.print("\033[0m\033["+(bg==7?"":""+(40+bg)+";")+ public static void println(String txt) { public static void println(String txt, int fg) { public static void println(String txt, int fg, int bg) { // Методы ввода чисел типов int, long, float, double public static int inputInt() throws IOException, NumberFormatException { return Integer.valueOf(inputString()).intValue();

public static int inputInt(String prompt) throws IOException, NumberFormatException { print(prompt); return inputInt();

public static long inputLong() throws IOException, NumberFormatException { return Long.valueOf(inputString()).longValue();

public static long inputLong(String prompt) throws IOException, NumberFormatException { print(prompt); return inputLong();

public static float inputFloat() throws IOException, NumberFormatException { return Float.valueOf(inputString()).floatValue();

public static float inputFloat(String prompt) throws IOException, NumberFormatException { print(prompt); return inputFloat();

public static double inputDouble() throws IOException, NumberFormatException { return Double.valueOf(inputString()).doubleValue();

public static double inputDouble(String prompt) throws IOException, NumberFormatException { print(prompt); return inputDouble();

// Методы ввода строки, рассматриваемой как массив символов.

public static char[] inputChars() throws IOException { return (inputString()).toCharArray();

public static char[] inputChars(String prompt) throws IOException { print(prompt);

return (inputString()).toCharArray();

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

1. Зачем программисту предикаты. Все знают, что в программах бывают ошибки (bugs). Существуют специальные теории, посвященные 36 Глава I. Введение в информатику и программирование тому, как лучше их находить и исправлять (debugging дословно означает выведение клопов ). Зачастую нахождение ошибки очень нетривиальная задача, так как ее последствия могут сказываться совершенно в другом месте программы и быть весьма неожиданными.

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

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

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

– случайно выберите из банки два зерна и – если они одного цвета, отбросьте их, но положите в банку другое черное зерно (имеется достаточный запас черных зерен, чтобы делать это);

– если они разного цвета, поместите белое зерно обратно в банку и отбросьте черное зерно.

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

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

Знание теории позволяет получить ответ на вопрос задачи почти мгновенно, однако объяснить это решение практически невозможно без привлечения такого понятия, как инвариант цикла, речь о котором пойдет в нашем курсе значительно позже. Инвариант цикла это предикат, обладающий некоторыми специальными свойствами. Интересно, что при этом §3. Высказывания и предикаты Таблица 1. Вероятность правильной работы программы, содержащей n ветвлений даже пятиклассник может справиться с рассматриваемой задачей, решив ее как-то. Под этим понимается по существу правильное решение, правильность которого доказать абсолютно невозможно.

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

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

Вернемся к нашей модели. Если в программе 10 операторов if, то нужно выполнить 210 = 1024 теста, а если их 20, то уже 220 106 ! Можно ли надеяться на то, что в процессе тестирования реальной большой программы удастся проверить все возможные варианты ее работы? Нет, конечно. Именно поэтому так важно не делать ошибок, так как потом их скорее всего просто не обнаружить.

В заключение поговорим о правильности большой программы, состоящей из многих небольших частей. Предположим, что для каждой из этих частей мы можем гарантировать правильность ее работы с вероятностью 99%. Это значит, что в среднем только в одном случае из ста что-то может быть не так, а в 99 случаях каждая часть будет работать абсолютно правильно. Пусть всего таких частей n. Какова вероятность правильной работы программы в целом?

Это простейшая задача по курсу теории вероятностей и ответ у нее такой: P = pn. Здесь p вероятность правильной работы каждой из частей, а P вероятность правильной работы программы в целом. При p = 0.99 получаем результаты, приведенные в таблице 1.

При n = 100 программа будет работать правильно чуть более, чем в одной трети всех ситуаций, а при n = 1000 увидеть ее работающей вообще вряд ли удастся. Этот пример показывает, что нужно всеми силами стараться избегать написания почти правильных программ!

38 Глава I. Введение в информатику и программирование 2. Синтаксис языка предикатов. Так как нам предикаты нужны прежде всего для описания программ, введем следующее определение.

Определение 3.1. Высказывание или предикат это функция, действующая из некоторого множества значений переменных программы (идентификаторов) в множество из двух значений {T, F } (Да и Нет).

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

• значение переменной i равно двум;

• переменная k положительна, а значение переменной m при этом не превосходит 100;

• значения всех целочисленных переменных программы являются • неправда, что значение переменной i неположительно.

Чуть менее понятно, можно ли считать предикатами такие фразы:

• если предположить, что значение переменной i равно двум, то значения всех остальных целочисленных переменных программы будут неотрицательными;

• данная программа является правильной;

• данное высказывание ложно.

Особенно показательным является последний пример. Если мы согласимся с тем, что он представляет из себя предикат, то возникает естественный вопрос о его истинности. Предположение о том, что он истинен, заставляет считать его ложным, и наоборот. Получаемое противоречие говорит о том, что определение 3.1 не является достаточно корректным.

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

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

Определение 3.2. Алфавит произвольное непустое множество.

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

Определение 3.3. Символом алфавита называют любой его элемент, а цепочкой над алфавитом произвольную последовательность символов.

Цепочки часто называют также словами, фразами и предложениями.

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

Определение 3.4. Длиной || цепочки называется количество входящих в нее символов.

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

Определение 3.5. Операция : конкатенации двух цепочек определена следующем образом. Пусть 1 = a1 a2... an, 2 = Операция конкатенации, называемая также операцией сцепления или дописывания, обладает следующими свойствами.

Предложение 3.1. Для любых цепочек, 1, 2 и 3 справедливы следующие равенства:

Имея все эти определения, уже можно дать формальное определения языка над алфавитом.

Определение 3.6. Язык L это произвольное подмножество множества цепочек.

Если язык конечен, то есть состоит из конечного множества входящих в него цепочек, то его можно задать, просто перечислив все его элементы.

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

Определение 3.7. Пусть некоторый алфавит, N метаалфавит, т.е. какой-то другой алфавит, не пересекающийся с ( N = ).

Элементы метаалфавита N называются метасимволами. Грамматикой G называется набор (, N, P, S), где множество символов, N множество метасимволов, P множество правил вывода вида:, где 40 Глава I. Введение в информатику и программирование какой-то метасимвол, ( N ) произвольная цепочка над объединением двух алфавитов, и для каждого N встречается хотя бы одно правило с в левой части (до стрелочки), а S N так называемый стартовый метасимвол.

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

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

Определение 3.8. Языком L(G), порожденным грамматикой G, называется множество всех терминальных выводимых цепочек.

Для задания грамматики часто используют очень наглядную форму представления, называемую нормальной формой Бэкуса-Наура (НФБН).

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

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

Определение 3.9. Множество предикатов это язык, порожденный следующей грамматикой:

§3. Высказывания и предикаты Единственным метасимволом данной грамматики является e, а алфавит = {T, F, !,,,, &&,, =, (, )} Mid, где множество Mid состоит из всех возможных идентификаторов (имен) переменных программ логического типа.

Приведем пример цепочки вывода в данной грамматике: e (e показывает, что выражение ((a T ) a) является предикатом. Легко построить другой вывод этого же предиката: e (e e) ((e e) e) ((e T ) e) ((a T ) e) ((a T ) a). Существует и еще несколько других цепочек вывода для предиката ((a T ) a), отличающихся порядком замены метасимвола e на идентификатор a и значение T. Ясно, что в определенном смысле, который мы не будем сейчас уточнять, все эти цепочки эквивалентны. Говорят, что множество эквивалентных цепочек задает дерево вывода данного предиката, изображенное на рисунке 1.

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

Задача 3.2. Докажите, что выражение ((a b) = (b a)) является предикатом.

Решение. Для доказательства достаточно предъявить вывод в грамматике 3.9 предложенного выражения, что не слишком трудно: e (e = Покажем, как можно доказать, что выражение не является предикатом.

Задача 3.3. Докажите, что выражение a a не предикат.

42 Глава I. Введение в информатику и программирование

T T F T T T T T T

T F F T T F F F F

F T T T T F F T F

F F T F F F F T T

Решение. В самом деле, для того, чтобы в предикате появился символ, необходимо применить правило e (e e), а его применение вызывает появление пары скобок, которых нет в выражении a a. Ни один из терминальных символов, появившись в процессе вывода, не может измениться в дальнейшем (или исчезнуть). Таким образом, если 5-е правило грамматики 3.9 не применять, то мы не сумеем получить в итоговой цепочке символ, а если его применить хотя бы раз, то в цепочке будут присутствовать скобки. Полученное противоречие и показывает, что выражение a a предикатом не является.

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

Иными словами, нам необходимо придать смысл каждому из предикатов.

Сделаем это в три этапа, рассмотрев сначала простейшие предикаты T и F, затем константные предикаты, а уж затем определим значение произвольного высказывания.

Определение 3.10. Предикат F имеет значение F alse (Ложь), а предикат T значение T rue (Истина).

Определение 3.11. Назовем предикат константным, если в нем не содержится ни одного идентификатора. Значение любого такого предиката находится с помощью таблицы истинности 2 и дерева вывода для него.

Рассмотрим, например, константный предикат ((F T ) F ). Изобразим дерево вывода для него и будем, двигаясь снизу вверх, заменять результаты операций в соответствии с таблицей истинности, пока не дойдем до самого корня дерева. Это последнее значение и будет считаться значением предиката (см. рис. 2).

Для задания семантики предиката, содержащего переменные, нам необходимо следующее определение состояния.

§3. Высказывания и предикаты Рис. 2. Определение истинности предиката ((F T ) F ) Определение 3.12. Состояние s это отображение из множества идентификаторов в множество {T, F }. Пространство состояний переменных программы это прямое произведение множеств состояний всех переменных программы.

Теперь можно дать определение значения любого предиката в заданном состоянии.

Определение 3.13. Значение предиката e в состоянии s (записывается как e(s) или s(e)) совпадает со значением константного предиката, который получается из предиката e заменой всех идентификаторов на их значения в состоянии s.

Предикат ((a T ) b), например, в состоянии s = {(a, T ), (b, F )} имеет значение F, ибо именно таково значение константного предиката Из таблицы истинности следует, что операции дизъюнкции и условного Или, а также конъюнкции и условного И && попарно эквивалентны. Это действительно так, но только до тех пор, пока мы остаемся в рамках действия определения 3.12. Для нужд описания реального мира, однако, полезно его несколько ослабить и разрешить некоторым переменным оставаться неопределенными.

Определение 3.14. Состояние s в расширенном смысле отображение из множества идентификаторов в множество {T, F, U }, где символ U означает неопределенное (undened) значение.

Большинство предикатов не имеют определенного значения в таком состоянии, в котором не определены некоторые из переменных, входящих 44 Глава I. Введение в информатику и программирование Таблица 3. Таблица истинности для условных операторов Таблица 4. Таблица истинности предиката ((a b) = (b a)) в него. В частности, операции !,,, и = дают результат U, если хотя бы один из операндов имеет значение U. Совершенно другая ситуация с условными операторами. Для них справедлива таблица истинности 3.

Среди огромного множества всех предикатов особую роль играют те из них, которые всегда являются истинными, как, например ((!(!a)) = a).

Определение 3.15. Предикат называется тавтологией, если он истинен во всех состояниях, в которых он определен.

Один из простейших способов доказать, что предикат является тавтологией, это вычислить его значения во всех возможных состояниях. Таблица 4 является доказательством того факта, что предикат ((a b) = (b a)) тавтология.

Определение 3.16. Высказывания e1 и e2 эквивалентны, если предикат e1 = e2 является тавтологией.

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

Предложение 3.2. Законы коммутативности:

((e1 e2 ) = (e2 e1 ));

((e1 e2 ) = (e2 e1 ));

((e1 = e2 ) = (e2 = e1 )).

Предложение 3.3. Законы ассоциативности:

((e1 (e2 e3 )) = ((e1 e2 ) e3 ));

((e1 (e2 e3 )) = ((e1 e2 ) e3 ));

(e1 &&(e2 &&e3 )) = ((e1 &&e2 )&&e3 ));

((e1 (e2 e3 )) = ((e1 e2 ) e3 )).

Предложение 3.4. Законы дистрибутивности:

((e1 (e2 e3 )) = ((e1 e2 ) (e1 e3 )));

((e1 (e2 e3 )) = ((e1 e2 ) (e1 e3 )));

((e1 &&(e2 e3 )) = ((e1 &&e2 ) (e1 &&e3 )));

((e1 (e2 &&e3 )) = ((e1 e2 )&&(e1 e3 ))).

Предложение 3.5. Законы де Моргана:

((!(e1 e2 )) = ((!e1 ) (!e2 )));

((!(e1 e2 )) = ((!e1 ) (!e2 )));

((!(e1 &&e2 )) = ((!e1 ) (!e2 )));

((!(e1 e2 )) = ((!e1 )&&(!e2 ))).

Предложение 3.6. Закон отрицания:

((!(!e)) = e).

Предложение 3.7. Законы исключенного третьего:

(e (!e) = T );

(e (!e) = T ), если e определено.

Предложение 3.8. Законы противоречия:

(e (!e) = F );

(e&&(!e) = F ), если e определено.

Предложение 3.9. Закон импликации:

((e1 e2 ) = ((!e1 ) e2 )).

Предложение 3.10. Закон равенства:

((e1 = e2 ) = ((e1 e2 ) (e2 e1 ))).

Предложение 3.11. Законы упрощения дизъюнкции:

((e e) = e);

((e F ) = e);

((e1 (e1 e2 )) = e1 ).

Предложение 3.12. Законы упрощения конъюнкции:

((e e) = e);

((e T ) = e);

((e1 (e1 e2 )) = e1 ).

Предложение 3.13. Законы упрощения условного Или:

((e e) = e);

46 Глава I. Введение в информатику и программирование ((e T ) = T ), если e определено;

((e F ) = e);

((e1 (e1 &&e2 )) = e1 ).

Предложение 3.14. Законы упрощения условного И:

((e&&e) = e);

((e&&T ) = e);

((e&&F ) = F ), если e определено;

((e1 &&(e1 e2 )) = e1 ).

Предложение 3.15. Закон тождества:

(e = e).

4. Расширение понятия предиката. В реальных программах далеко не все переменные имеют логический тип, что означает невозможность их описания с помощью предикатов, введенных определением 3.9. Так, например, выражение i < 3 для целочисленной переменной i предикатом в смысле упомянутого определения заведомо не является, что плохо. Эти и некоторые другие причины побуждают расширить множество предикатов, что и будет сейчас сделано в три этапа.

Определение 3.17. Будем называть предикатом с переменными любых типов выражение, которое может быть получено из предиката P (в смысле определения 3.9) заменой произвольного идентификатора id на любое заключенное в скобки выражение логического типа с переменными различных типов. Вычисление значения получившегося предиката в произвольном состоянии немедленно сводится к вычислению значения исходного предиката P.

Начиная с этого момента выражение ((i < 3)(j = 0)) предикат, так как для него можно указать следующую цепочку вывода: e (e e) (id1 e) (id1 id2 ) ((i < 3) id2 ) ((i < 3) (j = 0)). Множеством состояний этого предиката является пространство Z 2, так как каждая из двух входящих в него целых переменных может изменяться независимо от другой. Если i и j следует заменить на Z2. M Примером предиката, который определен в состоянии, в котором одна из входящих в него переменных не является определенной, может служить выражение P = ((a = 0)||(b/a > 0)). В состоянии s = {(a, 0), (b, U )} он истинен: P (s) = T. Подобные предикаты возникают при описании фрагментов программ типа Следующим шагом в направлении расширения понятия предиката будет использование кванторов существования и всеобщности.

§3. Высказывания и предикаты Если P (x) предикат в смысле определения 3.17, зависящий от переменной x произвольного типа, а X некоторое множество, то будем считать предикатами выражения (x(x X P (x))) и (x(x X P (x))).

Первое из них означает, что существует хотя бы одно x X для которого выполнено P (x), а второе что для всех x X справедливо P (x).

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

Когда используемое множество X понятно из контекста, его опускают, что приводит к выражениям (x P (x)) и (x P (x)).

Кроме кванторов существования и всеобщности иногда используют еще один квантор квантор ! существования и единственности, который может быть определен с помощью двух основных кванторов следующим образом:

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

В предикате R = (i(m i < n xi > 0)) идентификатор i является связанным (квантором ), а идентификаторы m, n и x свободными.

Выражение (i > 0(i(m i < n xi > 0))) предикатом мы считать не можем, ибо i в нем является одновременно и свободным идентификатором и связанным, что недопустимо. Его легко слегка изменить так, чтобы оно стало предикатом: (i > 0 (k(m k < n x k > 0))) уже предикат.

Третьим шагом в направлении расширения множества языка предикатов будет ослабление требования на наличие в предикате всех тех скобок, которые возникают в процессе его вывода. Напомним, что с точки зрения определения 3.9 выражение a b, например, предикатом не является, что не слишком удобно с практической точки зрения.

Разрешим удалять из предиката все те пары скобок, которые можно опустить без потери его однозначного толкования. При этом семантика 48 Глава I. Введение в информатику и программирование полученного предиката определяется приоритетом операций: сначала вычисляются выражения внутри скобок, затем логические выражения, заменившие логические идентификаторы id в смысле определения 3.17, после этого кванторы существования и всеобщности, а затем логические операции !, && и, и, и, наконец, =.

Таким образом, мы принимаем следующее определение.

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

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

Рассмотрим, как решаются типичные задачи на вычисление значения предикатов в расширенном смысле в различных состояниях.

Задача 3.4. Вычислите значения предикатов P1 = (x = 0 x/(y2) = 0) и P2 = (x = 0 && x/(y 2) = 0) в состоянии s = {(x, 7), (y, 2)}.

Решение. Если восстановить в этих предикатах все недостающие скобки, то мы получим предикаты P3 = ((x = 0) ((x/(y 2)) = 0)) и P4 = ((x = 0)&&((x/(y 2)) = 0)) соответственно. В состоянии s выражение (x = 0) является ложным, ибо (7 = 0) = F, а x/(y 2) имеет значение U (не определено). В соответствии с таблицами истинности для операций и && можно сделать вывод, что P1 (s) = U, а P2 (s) = F.

Задача 3.5. Вычислите значения предиката P = (i 0 i 0)) (j j 2 k) в состоянии s = {(k, 0)}.

Решение. Предикат P представляет из себя конъюнкцию двух предикатов, первый из которых это i 0 i 9 i2 0, а второй в состоянии s совпадает с j j 2 0. Так как при i = 0 выполнено i2 0, то первый из них истинен, а истинность второго предиката не вызывает сомнений.

Таким образом, предикат P (s), являющийся конъюнкцией двух истинных выражений, сам является истинным, P (s) = T.

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

§3. Высказывания и предикаты Определение 3.19. Подстановкой Ee называется выражение, получающееся одновременной подстановкой e вместо всех свободных вхождений x в E.

Вот несколько простых примеров: (x + y)x = (z + y); для E = x < но Ek = E, так как i не свободно в E.

Для предикатов с кванторами справедливы дополнительные законы эквивалентности, называемые также правилами построения отрицания.

Предложение 3.16. Законы построения отрицания:

!(xP (x)) = x(!P (x));

!(xP (x)) = x(!P (x)).

5. Приоритеты и ассоциативность операторов языка Java. При вычислении значения выражения в языке Java важны не только приоритеты, но и ассоциативность операторов.

Определение 3.20. Оператор @ является левоассоциативным, если выражение a @ b @ c вычисляется, как (a @ b) @ c; правоассоциативным, если оно эквивалентно a @ (b @ c); неассоциативным если запись a @ b @ c не имеет смысла.

В этом определении символ @ означает любой из бинарных операторов языка.

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

В таблице 5 все операторы языка Java разбиты на группы с одинаковым приоритетом (операторы с приоритетом 1 выполняются в первую очередь), левоассоциативность обозначена символом, а правоассоциативность символом.

Таблица 5. Приоритеты и ассоциативность операторов Таблица 5. Приоритеты и ассоциативность операторов §4. Особенности представления чисел в ЭВМ Таблица 5. Приоритеты и ассоциативность операторов С логическими и условными операторами мы уже знакомы, семантика арифметических операторов объясняется в следующем параграфе, а с оператором instanceof мы разберемся в третьей главе книги.

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

Задача 3.6. Докажите, что выражение ((e1 (e2 e3 )) = ((e1 e2 ) (e1 e3 ))) является предикатом.

Задача 3.7. Докажите, что выражение ((a a) не предикат.

Задача 3.8. Изобразите деревья вывода для каждого из законов эквивалентности (см. страницу 42).

Задача 3.9. Покажите, что все законы эквивалентности (см. стр. 42) являются тавтологиями.

Задача 3.10. Решите задачу о банке с кофейными зернами (см.

стр. 34) § 4. Особенности представления чисел в ЭВМ Как уже отмечалось ранее, множествам целых Z и действительных R чисел в большинстве языков программирования соответствуют их машинные аналоги. В случае языка Java используемые в программах переменные величины и константы типов int и double принимают значения из множеств ZM и RM соответственно. В этом параграфе мы разберемся с тем, как именно устроены эти множества, и каковы последствия того, что программы оперируют не с настоящими числами, а с элементами указанных множеств. Однако сначала некоторые напоминания об информации вообще и ее представлении в ЭВМ.

1. Представление информации в компьютере. Любая информация (числовая, текстовая, звуковая, графическая и т.д.) в компьютере представляется (кодируется) в так называемой двоичной форме. Как оперативная, так и внешняя память, где и хранится вся информация, могут рассматриваться, как достаточно длинные последовательности из нулей и 52 Глава I. Введение в информатику и программирование единиц. Под внешней памятью подразумеваются такие носители информации, как магнитные и оптические диски, ленты и т.п.

Единицей измерения информации является бит (BInary digiT) именно такое количество информации содержится в ответе на вопрос:

нуль или один? Более крупными единицами измерения информации являются байт, килобайт (Kbyte), мегабайт (Mbyte), гигабайт (Gbyte) и терабайт (Tbyte). Один байт (byte) состоит из восьми бит, а каждая последующая величина больше предыдущей в 1024 раза.

Байта достаточно для хранения 256 различных значений, что позволяет размещать в нем любой из алфавитно-цифровых символов, если только мы можем ограничиться языками с небольшими алфавитами типа русского или английского. Первые 128 символов (занимающие семь младших бит) стандартизированы с помощью кодировки ASCII (American Standart Code for Information Interchange). Хуже обстоит дело с кодировками русского текста (символы русского алфавита расположены во второй половине таблицы из 256 символов) их несколько, а наиболее распространенные из них сейчас две Windows-1251 и KOI8-R.

Для кодирования всех возможных символов, используемых народами мира, одного байта мало необходимо использовать два последовательных (стандарт Unicode). Именно так и поступают при хранении символьных (char) значений в языке Java.

Полезно знать, что 210 = 1024 1000 = 103. Учитывая, что в книге среднего размера около 300000 букв, легко подсчитать, что, даже не используя никаких средств сжатия информации, на жестком диске современного персонального компьютера емкостью в 20 гигабайт можно разместить большую библиотеку из почти 70000 книг.

2. Целые числа. К целочисленным типам в языке Java относятся byte, short, int и long. Для хранения значений этих типов на любом компьютере отводится один, два, четыре и восемь байт соответственно. При этом применяется представление чисел в так называемом двоичном дополнительном коде.

Напомним, что используемая нами обычная система счисления является позиционной с основанием 10. Это значит, что в ней все натуральные числа представляются с помощью десяти цифр (от нуля до девяти включительно), а значение каждой из цифр числа зависит от позиции: самая правая цифра означает число единиц (100 ), вторая десятков (101 ), третья сотен (102 ) и так далее.

В p-ичной системе счисления все точно также, только число 10 в предыдущем абзаце нужно всюду заменить на p. Наряду с двоичной системой, в которой только две цифры (0 и 1), в информатике часто применяются §4. Особенности представления чисел в ЭВМ восьмеричная с цифрами от нуля до 7 и шестнадцатеричная. В последнем случае в качестве цифр от десяти до пятнадцати используются буквы от A до F соответственно.

При записи положительных целых чисел в системе счисления с основанием p (на компьютере p = 2) все их множество оказывается состоящим из элементов вида где величины i для всех i из диапазона от n 1 до нуля это цифры n-значного числа d в p-ичной системе счисления.

Перейдем теперь к вопросу представления отрицательных чисел. Для определенности рассмотрим тип byte, в котором любое число занимает ровно восемь бит. Из записи в двоичной системе счисления равенства (1) + 1 = 0 легко найти, какой вид должно иметь неизвестное нам пока двоичное представление xxxxxxxx числа 1:

xxxxxxxx + 00000001 = Ясно, что на месте символов xxxxxxxx должно быть расположено число 11111111. Правильным результатом при этом, конечно, следовало бы считать 100000000, а не 00000000, но ведь мы имеем дело с типом byte и, так как результат обязан разместиться в байте, единица исчезает.

Итак, число 1 должно кодироваться как 11111111. Дальнейшее уже совсем просто: для получения 2 нужно 1 уменьшить на единицу, что даст 11111110; число 3 представляется как 11111101 и т.д.

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

Легко видеть, что при этом самым маленьким отрицательным числом, которое принадлежит типу byte, является число 128 (двоичное представление 10000000), а самым большим число 127 (представление 01111111). Все представимые числа (а их 256) в данном случае могут быть получены как пересечение двух множеств: множества Z всех целых чисел и отрезка [128, 127]. Интересным является следующее наблюдение:

если число 01111111 увеличить на единицу, то получится 10000000, что означает следующее: 127 + 1 = 128 !

Итак, множество элементов типа byte можно представлять себе в виде свернутого в кольцо отрезка [128, 127]. Принципиально ничего не меняется и для типов short, int и long увеличивается только длина отрезка, который вырезается из действительной прямой перед сворачиванием его в кольцо. Минимальные и максимальные представимые значения для 54 Глава I. Введение в информатику и программирование каждого из этих типов в языке Java определены, как значения констант MIN_VALUE и MAX_VALUE в классах java.lang.Short, java.lang.Integer и java.lang.Long соответственно.

То, что для элементов множества ZM, являющегося машинным аналогом Z, нарушено фундаментальное свойство целых чисел x + 1 > x, способно привести к различным невероятным на первый взгляд результатам, однако гораздо более странные вещи происходят при работе с вещественными числами.

3. Вещественные числа. Обсуждаемые в данной секции вопросы значительно более полно рассмотрены в четвертой главе классической книги Кнута [7].

Для представления вещественных чисел в языке Java используют переменные и константы типов float и double. Величины первого из них занимают четыре байта, а второго восемь.

В отличие от множества целых чисел Z вещественные числа R обладают свойством полноты: между любыми двумя различными числами всегда найдется отличное от них третье. Понятно, что любой из способов представления бесконечного множества вещественных чисел с помощью некоторого конечного множества RM не даст возможности сохранить свойство полноты. Наиболее распространенным способом реализации вещественных чисел на ЭВМ является использование чисел с плавающей точкой. При этом множество RM оказывается состоящим из элементов вида где целые числа i для всех i из диапазона от 1 до n удовлетворяют соотношению 0 i p 1, а величина e лежит в диапазоне от L до U (L e U ). Число p является при этом основанием системы счисления (чаще всего это 2), константа n задает точность представления чисел (для типа double она больше, чем для float), а диапазон [L, U ] определяет область значений экспоненты (для типа double он также больше, чем для float).

Число ±( 1 + 2 +... + n ) принято называть мантиссой числа f с плавающей точкой. Часто требуют, чтобы для всех чисел f = 0 величина 1 была ненулевой. Такие числа с плавающей точкой называют нормализованными.

В языке Java для кодирования величин типов float и double также используют числа с плавающей точкой. При этом часть из имеющегося множества бит используют для размещения экспоненты e, а остальные биты для размещения мантиссы.

§4. Особенности представления чисел в ЭВМ Для того чтобы хорошо понять, что же представляет из себя множество RM нормализованных чисел с плавающей точкой, полезно изобразить его на числовой прямой для случая небольших n, L и U. Подобная задача приведена в конце параграфа. Сейчас же нам будет достаточно весьма качественного описания этого множества.

Так как RM симметрично относительно начала координат, то можно разобраться только с неотрицательными числами. Нуль, конечно же, принадлежит искомому множеству. Ближайшая к нулю следующая точка получается при 1 = 1, 2 = 3 =... = n = 0 и e = L. Это число для чисел типов float и double определено, как MIN_VALUE в классах java.lang.Float и java.lang.Double соответственно.

Правее располагается множество точек, следующих друг за другом с шагом 2Ln. Затем шаг увеличивается. Потом еще. И еще. При e = U расстояние между двумя соседними точками множества R M достигает 2U n. Самая правая точка множества получается при 1 = 2 =... = n = 1 и e = U. Для типов float и double это число определено, как MAX_VALUE в классах java.lang.Float и java.lang.Double.

Кроме перечисленных (и симметричных им отрицательных) значений в результате выполнения некоторых операций могут получиться также следующие особые значения: плюс бесконечность (POSITIVE_INFINITY), минус бесконечность (NEGATIVE_INFINITY), минус ноль и не число (NaN).

Например, при делении единицы на минус ноль получается минус бесконечность.

Описанные особенности множества машинных вещественных чисел RM приводят к тому, что не для всех его элементов верны следующие соотношения, всегда справедливые для множества настоящих вещественных чисел R:

Приведем несколько примеров, иллюстрирующих эти особенности множества RM.

Задача 4.1. Предъявите действительное (типа double) число x такое, что x + 1 = x, а (x · 2)/2 = x. Воспользуйтесь тем, что класс java.lang.Double определяет константу MAX_VALUE.

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

56 Глава I. Введение в информатику и программирование public class DblMaxVal { public static void main(String[] args) { double x = Double.MAX_VALUE;

Xterm.print("равны!\n", Xterm.Red);

Xterm.print(" величины x и (2.0*x)/2.0 ");

Xterm.print("различны\n", Xterm.Red);

Xterm.print("и равны соответственно");

Задача 4.2. Предъявите такие действительные (типа double) числа a, b и c такие, что a + (b + c) = (a + b) + c.

Достаточно вспомнить, что точки множества RM расположены на числовой прямой неравномерно.

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

public class DblNoAssociative { public static void main(String[] args) { Xterm.print(" величины 1.+(x+x) и (1.+x)+x ");

Xterm.print("различны\n", Xterm.Red);

Xterm.print("и равны соответственно");

Xterm.print(" " + y, Xterm.Red);

Xterm.print(" " + z + "\n", Xterm.Red);

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

Задача. Напишите программу, вводящую действительные коэффициенты a, b и c квадратного уравнения ax2 + bx + c = 0 с положительным дискриминантом, находящую оба корня этого уравнения.

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

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

public class SquareEquation { public static void main(String[] args) throws Exception { double a = Xterm.inputDouble("Введите число a -> ");

double b = Xterm.inputDouble("Введите число b -> ");

double c = Xterm.inputDouble("Введите число c -> ");

Xterm.println("Уравнение не квадратное", Xterm.Red);

вправо с присваиванием), >>> (сдвиг вправо с размножением нуля) и >>>= (сдвиг вправо с присваиванием с размножением нуля).

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

Например, 4^5 равняется 1 (ибо двоичные представления этих чисел есть соответственно 100 и 101).

У операторов сдвига второй аргумент показывает количество разрядов, на которое надо осуществить сдвиг в двоичном представлении первого операнда влево (для и >>>).

Легко понять, что сдвиг влево на n разрядов эквивалентен умножению на 2n, а сдвиг вправо делению на то же число.

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

Задача 4.3. Предъявите целое число x такое, что x + 1 < x.

Задача 4.4. Явно перечислите и изобразите на числовой прямой все точки множества RM, сделав следующие допущения: числа хранятся в нормализованной форме с плавающей точкой; для хранения как мантиссы, так и порядка числа отводится по три бита (из которых в обоих случаях один является знаковым); никаких особых значений нет.

Задача 4.5. Предъявите действительное (типа double) число x такое, что (x/2) · 2 = x. Воспользуйтесь тем, что класс java.lang.Double определяет константу MIN_VALUE.

60 Глава I. Введение в информатику и программирование Задача 4.6. Определите (приближенно) M ACHEP S (машинное эпсилон) для типов double и float. Машинным эпсилоном называется наибольшее число x данного типа, удовлетворяющее соотношению 1 + x = 1.

Задача 4.7. Предъявите последовательность чисел (типа float), при суммировании которой в прямом и обратном порядке результаты будут отличаться не менее, чем вдвое.

Задача 4.8. Напишите программу, вводящую действительные коэффициенты a, b и c квадратного уравнения ax2 + bx + c = 0 с положительным дискриминантом, находящую оба корня этого уравнения достаточно точно во всех случаях.

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

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

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

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

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

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

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

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

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

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

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

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

В качестве примера можно рассмотреть схему вычисления факториала натурального числа в соответствии с его другим определением: n! = 1 · 2 ·... · n. При написании программы в соответствии с ним нужно работать с двумя величинами целого типа ZM : числом i, которое будет играть роль счетчика и изменяться от 1 до n включительно, и величиной k, в которой будет накапливаться произведение чисел от 1 до i.

Пространством X в данном случае будет Z2, в качестве начальной точки в этом пространстве возьмем точку (1, 1) (что соответствует i = k = 1), а преобразование T : X X будет иметь вид T (i, k) = (i + 1, k i). В случае, например, трехкратного применения преобразования T получим T (T (T (1, 1))) = T (T (2, 1)) = T (3, 2) = (4, 6), что обеспечит вычисление факториала числа 3.

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

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

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

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

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

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

public class FactR { static int f(int x) { 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. Он, в свою §5. Рекурсия, итерация и оценки сложности алгоритмов очередь, вызовет f(0). В этот момент накопится уже пачка листов (ее называют стеком вызовов) целых четыре штуки. При этом вычисления на всех нижних листах приостановлены до завершения работы с верхними.

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

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

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

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

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

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

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

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

Заметим, что для отрицательных значений n Z данная программа должна была бы работать бесконечно долго (как принято говорить, должна зациклиться). Однако из-за того, что в реальности мы имеем дело с машинным заменителем множества целых чисел множеством 64 Глава I. Введение в информатику и программирование ZM, выполнение всегда завершится за конечное время, хотя полученный результат и не будет иметь никакого смысла.

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

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

В реальности, однако, быстрый рост функции n! и ограниченность множества ZM приводят к тому, что эта программа позволяет получить правильные результаты только при очень небольших значениях 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));

Обратите внимание, что при вычислении f5 в соответствии с этой программой понадобится найти f4 и f3. Определение f4, в свою очередь, потребует вычисления f3 и f2, и так далее. Внимательно изучение содержимого стека вызовов для этой задачи показывает, что для нахождения каждого следующего числа Фибоначчи требуется примерно вдвое большее время, чем для определения предыдущего. Для того, чтобы убедиться в этом, нарисуйте дерево, изображающее процесс вычисления f 7 с помощью данной программы.

§5. Рекурсия, итерация и оценки сложности алгоритмов 3. 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 { n = Xterm.inputInt("Введите n -> ");

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

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

Может показаться, что основываясь на ней, легко написать программу со сложностью (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 );

68 Глава I. Введение в информатику и программирование На самом деле эта программа использует вызов функции возведения в степень Math.pow(f,n), которая не может быть реализована быстрее, чем за логарифмическое время (log2 n). Про алгоритмы, в которых количество операций примерно пропорционально log n (в информатике принято не указывать основание двоичного логарифма) говорят, что они имеет логарифмическую сложность ((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 + ")");

Xterm.println(" не определено");

§5. Рекурсия, итерация и оценки сложности алгоритмов 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;

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

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

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

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

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

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

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

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

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