авторефераты диссертаций БЕСПЛАТНАЯ БИБЛИОТЕКА РОССИИ

КОНФЕРЕНЦИИ, КНИГИ, ПОСОБИЯ, НАУЧНЫЕ ИЗДАНИЯ

<< ГЛАВНАЯ
АГРОИНЖЕНЕРИЯ
АСТРОНОМИЯ
БЕЗОПАСНОСТЬ
БИОЛОГИЯ
ЗЕМЛЯ
ИНФОРМАТИКА
ИСКУССТВОВЕДЕНИЕ
ИСТОРИЯ
КУЛЬТУРОЛОГИЯ
МАШИНОСТРОЕНИЕ
МЕДИЦИНА
МЕТАЛЛУРГИЯ
МЕХАНИКА
ПЕДАГОГИКА
ПОЛИТИКА
ПРИБОРОСТРОЕНИЕ
ПРОДОВОЛЬСТВИЕ
ПСИХОЛОГИЯ
РАДИОТЕХНИКА
СЕЛЬСКОЕ ХОЗЯЙСТВО
СОЦИОЛОГИЯ
СТРОИТЕЛЬСТВО
ТЕХНИЧЕСКИЕ НАУКИ
ТРАНСПОРТ
ФАРМАЦЕВТИКА
ФИЗИКА
ФИЗИОЛОГИЯ
ФИЛОЛОГИЯ
ФИЛОСОФИЯ
ХИМИЯ
ЭКОНОМИКА
ЭЛЕКТРОТЕХНИКА
ЭНЕРГЕТИКА
ЮРИСПРУДЕНЦИЯ
ЯЗЫКОЗНАНИЕ
РАЗНОЕ
КОНТАКТЫ


Pages:   || 2 | 3 | 4 | 5 |   ...   | 7 |
-- [ Страница 1 ] --

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

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

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

центр компьютерных

технологий

Е.А. Роганов

Основы

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

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

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

Москва 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. Спецификация программ и преобразователь предикатов 1. Предикаты и документирование программ 2. Спецификация программы и преобразователь предикатов wp 3. Определение простейших операторов языка Java 4. Оператор if и слабейшее предусловие 5. Циклы в терминах wp 6. Вычисление слабейшего предусловия 7. Задачи для самостоятельного решения § 7. Все задачи главы 1. Задачи на составление алгоритмов 2. Простейшие задачи на программирование 3. Задачи на предикаты 4. Задачи на особенности представления чисел в ЭВМ 5. Задачи на рекурсию и итерацию 6. Задачи на массивы 7. Задачи на последовательности Глава II. Построение программ § 1. Базисные схемы обработки информации 1. Рекурсия и итерация 2. Инвариант и ограничивающая функция цикла 3. Схема вычисления инвариантной функции 4. Функции на пространстве последовательностей 5. Задачи для самостоятельного решения § 2. Проектирование цикла при помощи инварианта 1. Условия правильности цикла 2. Теория воздушного шарика 3. Устранение конъюнктивного члена 4. Замена константы переменной 5. Расширение области значения переменной 6. Задачи для самостоятельного решения § 3. Индуктивные функции на пространстве последовательностей 1. Критерий индуктивности и стационарные значения 2. Индуктивные расширения 3. Критерий минимальности 4. Применение теории индуктивных функций Оглавление 5. Задачи для самостоятельного решения § 4. Все задачи главы 1. Задачи на рекурсию 2. Проектирование цикла при помощи инвариантa 3. Схема вычисления инвариантной функции 4. Задачи на индуктивные функции Глава III. Применение ООП к разработке программных проектов § 1. Основы объектно-ориентированного программирования 1. Основные концепции ООП 2. Классы и объекты в языке Java 3. Контейнеры 4. Реализации контейнеров на базе вектора 5. Словарик ООП 6. Свойства классов и объектов в языке Java 7. Задачи для самостоятельного решения § 2. Проект Выпуклая оболочка 1. Постановка задачи 2. Проектирование сверху вниз 3. Аналитическая геометрия и программирование 4. Реализация класса Polygon 5. Аплеты и работа с ними 6. Задачи для самостоятельного решения 7. Текст эталонного проекта § 3. Проект Компилятор формул 1. Стековый калькулятор 2. Грамматики языка правильных арифметических формул 3. Рекурсивный компилятор формул 4. Стековый компилятор формул 5. Интерпретатор арифметических выражений 6. Задачи для самостоятельного решения 7. Тексты эталонных проектов § 4. Проект Изображение полиэдра 1. Постановка задачи 2. Проектирование основных классов 3. Работа с тенями от граней 4. Некоторые технологические вопросы и оптимизация 5. Задачи для самостоятельного решения 6. Полный текст проекта § 5. Дополнительные задачи Оглавление Литература Предисловие В книге сделана попытка обобщить многолетний опыт автора в пре подавании информатики и программирования студентам первого курса Московского государственного индустриального университета специаль ностей Прикладная математика и информатика и Математическое обеспечение и администрирование информационных систем.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Москва, 2001 Е. Роганов Глава I Введение в информатику и программирование Эта глава, с которой начинается изучение курса, служит двум основ ным целям:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Алгоритм П:

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

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

иначе перейти на шаг П3.

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

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

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

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

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

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

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

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

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

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

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

Из вышесказанного следует, что на ЭВМ практически невозможно работать с действительными числами, что, по всей видимости, может показаться вам неправдоподобным. На самом деле это так. Более того, даже с настоящими целыми числами на компьютере работают не так уж и часто. Обычно вместо множеств целых 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("Введите натуральное число," + "большее единицы: ");

int i = 2;

while (k%i != 0) §1. Алгоритмы и программы i++;

Xterm.println("Наименьший простой делитель числа " + k + " равен " + i);

} } Функциональное и логическое программирование использует языки ти па 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] Второе определение факториала расширяет область определения этой операции и является рекурсивным.

0! = 1, n! = n · (n 1)! для n 0.

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

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

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

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

[("("++ld++[op]++rd++")", f lv rv) | (op,f) - [(’+’,(+)),(’-’,(-)),(’*’,(*)),(’/’,(div))], n-[1..length ds-1], (ld,lv) - tickets (take n ds), (rd,rv) - tickets (drop n ds), op /= ’/’ || (rv /= && lv ‘mod‘ rv == 0)] happy = map fst. (filter ((==)100. snd)). tickets При использовании директивного или объектно-ориентированного подходов и таких языков, как C, C++ или Java, размер программы, ре шающей данную задачу, будет гарантированно намного бльшим. Спра о ведливости ради надо отметить, что интерпретаторы функциональных языков обычно работают достаточно медленно.

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

Main (happy "234112") ["((2*(3+41))+12)","((2+3)*((41-1)/2))","(((2*3)+(4*11))*2)", "(((2+3)*(41-1))/2)"] Elapsed time (ms): 33150 (user), 20 (system) Main Для выхода из интерпретатора hugs используйте команду :quit, а мы далее в этой книге не будем больше касаться проблем, связанных с функциональным или логическим программированием, этому будут посвящены отдельные дисциплины на старших курсах обучения.

§2. Основы языка Java § 2. Основы языка Java Литературы, содержащей описание языка Java, сейчас достаточно много. На первой стадии знакомства с ним можно воспользоваться любым изданием, однако такие книги, как [11], [13] и [10] из библиографического списка, приведенного на странице 297, заведомо окажутся полезными и в дальнейшем.

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

• Java является современным объектно-ориентированным языком;

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

• Java позволяет создавать аплеты, являющиеся небольшими, на дежными, динамичными и не зависящими от платформы сете выми приложениями, которые встраиваются в веб-страницы сети Интернет.

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

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

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

Важно то, что объекты это не только некоторые значения (данные).

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

20 Глава I. Введение в информатику и программирование Объекты представляют собой объединение структур данных, содержащих информацию, и методов и функций для управления этими данными.

Произвольный объектно-ориентированный язык программирования характеризуют три основных свойства:

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

в языке Java это достигается путем введения механизма классов;

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

при этом возможно переопреде ление или добавление новых данных и методов;

в результате со здается так называемая иерархия классов;

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

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

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

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

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

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

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

§2. Основы языка Java времена работы быстрой и обычной программ, упорядочивающих в по рядке возрастания миллион чисел, отличаются в 50000 раз!

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

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

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

• всем константам, отличным от нуля и единицы, присваивайте имена;

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

• применяйте разумное форматирование текста программы;

• там, где это необходимо, используйте комментарии.

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

В соответствии с давно установившейся традицией рассмотрим в ка честве первой задачи следующую.

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

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

public class Hello { public static void main(String[] args) { 22 Глава I. Введение в информатику и программирование System.out.println("Здравствуй, мир!");

} } Приведенный выше текст обязательно должен содержаться в файле с именем Hello.java (обратите внимание на то, что первая буква в имени является прописной, а остальные строчными).

Как и большинство других языков, Java допускает произвольное фор матирование текста программы. Это означает, что любую программу в принципе можно записать в одну длинную строку или, наоборот, макси мально растянуть по вертикали, размещая на каждой строке только по одной лексеме минимальной неделимой единице языка. Приведенная выше программа состоит из следующей цепочки лексем: ключевые сло ва public, class, идентификатор Hello, разделитель {, ключевые сло ва public, static и void, идентификатор main, разделитель (, иденти фикатор String, разделители [ и ], идентификатор args, разделители ) и {, идентификатор System, разделитель., идентификатор out, раз делитель., идентификатор println, разделитель (, строковый литерал "Здравствуй, мир!", разделители ), ;

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

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

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

Последовательное выполнение двух команд javac Hello.java и java Hello должно привести к тому, что на экране появится результат работы программы строка Здравствуй, мир!

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

§2. Основы языка Java Задача 2.2. Напишите программу, печатающую на экране красивое поздравление с новым учебным годом.

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

public class NewYear { // magic !

public static void main(String[] args) { Xterm.clear();

Xterm.setPosition(25,8);

Xterm.print("С новым годом ", Xterm.Red);

Xterm.print("(учебным)", Xterm.Blue);

Xterm.print("!", Xterm.Red);

Xterm.setPosition(0,16);

/* Конец программы */ } } В этой программе используются два вида комментариев из трех, суще ствующих в языке Java. Текст, расположенный после символов // вплоть до конца строки, и произвольное количество строк текста между симво лами /* и */, компилятором просто игнорируются. Знакомство с третьим видом комментариев, предназначенным для автоматического документи рования программ, отложим до третьей главы книги. Второй из коммен тариев, включенных в приведенную выше программу, является типичным примером комментария, ухудшающего код. Не включайте в свои програм мы бесполезные комментарии!

Некоторые фрагменты этой (и многих последующих) программы обсу ждаться до начала третьей главы не будут. Только тогда, после полноцен ного знакомства с основными концепциями объектно-ориентированного программирования на языке Java, можно будет разобраться с тем, что же означает строка public static void main(String[] args). Пока мы будем просто считать, что так надо!

Содержательная же часть приведенной программы (тело функции main, т.е. текст, расположенный между внутренними фигурными скоб ками) сейчас будет подробно разобрана. Рекомендуется откомпилировать и запустить эту программу для того, чтобы увидеть результат ее рабо ты, это поможет лучше понять ее. При этом следует иметь в виду, что кроме файла NewYear.java в данном случае необходим еще и файл Xterm.java (его содержимое приведено для справки в последней секции данного параграфа на странице 31).

24 Глава I. Введение в информатику и программирование Объект, с которым ведется работа в программе, Xterm. Подробно он рассматривается чуть ниже (см. стр. 24), а пока отметим только то, что он определяет терминал, обеспечивающий ввод чисел и вывод строк текста.

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

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

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

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

Некоторые из методов требуют для своего выполнения указания до полнительных объектов. Такие дополнительные объекты называют пара метрами или аргументами и перечисляют их через запятую в круглых скобках после имени метода. В случае метода без параметров скобки тем не менее обязательны. Завершается любой оператор в языке Java точкой с запятой.

Рассматриваемая программа содержит вызов трех различных мето дов класса Xterm: clear, setPosition и print. Первый из них очищает окно терминала и не имеет параметров, второй перемещает курсор в пози цию, задаваемую параметрами метода, а третий позволяет вывести строку текста. При этом первый параметр метода print определяет выводимую строку, а второй задает цвет символов.

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

3. Типы, переменные и операторы. Типы данных в языке Java под разделяются на простые (primitive) и ссылочные (reference). К простым относятся величины логического типа boolean, символьного char, целых §2. Основы языка Java типов byte, short, int и long, и типов для представления действительных чисел float и double. Ссылочные типы позволяют работать с объектами и массивами.

Множество всех объектов с одинаковым пространством состояний и одинаковым набором методов называется классом (class). Почти все, с чем приходится иметь дело в языке Java, это объекты различных классов.

Логический тип предназначен для хранения величин, имеющих значе ния F alse (Ложь) или T rue (Истина), а символьный тип позволяет хра нить многочисленные символы различных алфавитов всех народов мира.

Особенностям представления числовых типов и работе с ними посвящен следующий параграф.

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

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

тип идентификатор [= значение] [, идентификатор [= значение ]...];

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

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

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

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

26 Глава I. Введение в информатику и программирование double f = 1.0, g = 1;

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

double f = 1.1;

int n = (int) f, m = (int) (f + 0.8);

Для преобразования типа переменной или какого-то выражения необ ходимо перед ним указать в круглых скобках новый тип. В приведенном выше примере обе целочисленные переменные (m и n) окажутся равными единице.

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

Существует и другая классификация операторов: они делятся на ариф метические, битовые, операторы отношения и логические. Арифметиче ские и битовые операторы разбираются в §4 после знакомства с представ лением чисел в ЭВМ, а логические операторы и операторы отношения в конце текущего параграфа.

4. Использование класса Xterm. Методы clear и setPosition этого класса были полностью описаны ранее, а вот об уже встречавшемся ме тоде print было рассказано далеко не все. Начнем с того, что в классе Xterm имеется целых три метода с именем print: с одним, двумя и тремя аргументами. Первый аргумент выводимая строка, второй (в случае его наличия) определяет цвет символов, а третий (если он есть) цвет фона.

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

public static final int Black = 0;

public static final int Red = 1;

public static final int Green = 2;

public static final int Yellow = 3;

public static final int Blue = 4;

public static final int Magenta = 5;

public static final int Cyan = 6;

§2. Основы языка Java public static final int White = 7;

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

2+2 // "i = " + "c" // "i = c" "i = " + 2 // "i = 2" "x = " + (3./2.) // "x = 1.5" "" + (3./2.) // "1.5" 2 + "i = " // Ошибка!

Используя этот оператор и метод print класса Xterm, можно выводить значения переменных любого из простых типов. Полезно знать, что "" обозначает пустую строку, а печать "\n" приводит к тому, что курсор терминала перемещается в начало следующей строки.

Для того чтобы не добавлять постоянно к выводимой строке "\n", можно пользоваться методами println, действие которых в остальном совершенно аналогично работе методов print.

Оставшиеся неразобранными методы класса Xterm предназначены для ввода целых и действительных чисел. Они позволяют работать в величи нами типов int, long, float и double. Их имена вполне естественны:

inputInt, inputLong, inputFloat и inputDouble соответственно. Все эти методы возвращают в качестве результата введенное число, если только в процессе ввода не произошла какая-либо ошибка. При этом предпола гается, что за один раз может быть введено только одно число, и ввод завершается нажатием на клавишу Enter.

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

Исключительная ситуация возникает, например, в случае ошибочно го или целенаправленного ввода буквенных или управляющих символов, а также при вводе пустой строки. Про работу с исключительными ситу ациями будет рассказано позже (стр. 71), а пока необходимо запомнить, что в том случае, когда программа использует ввод чисел, строку public static void main(String[] args) следует заменить на public static void main(String[] args) throws Exception Все четыре метода ввода чисел и метод ввода строки символов, опреде ленные в классе Xterm, являются перегруженными (overload). Перегрузка 28 Глава I. Введение в информатику и программирование методов это своеобразное проявление полиморфизма, когда два или бо лее различных методов имеют одно и то же имя и различаются только количеством или типами аргументов. Методы ввода класса Xterm позво ляют указывать в качестве аргумента строку, которая будет выведена в качестве подсказки. Это весьма удобно, так как позволяет при выполне нии программы явно увидеть, когда именно следует вводить ту или иную информацию.


Использование класса Xterm для организации операций ввода/вывода будет проиллюстрировано при решении следующей задачи.

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

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

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

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

Xterm.println("До обмена: a = " + a + ";

b = " + b);

int c = a;

a = b;

b = c;

Xterm.println("После обмена: a = " + a + ";

b = " + b);

} } Эта программа использует третью переменную c для того, чтобы со хранить в ней начальное значение переменной a, которое иначе оказалось бы утерянным при выполнении оператора присваивания a = b;

. Попро буйте придумать какой-либо способ обменять значения двух переменных без введения третьей.

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

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

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

Следует помнить, что при использовании этих операторов для величин ссылочных типов, проверяется факт равенства (или неравенства) ссылок, а не содержимого объектов. Сравнение на равенство двух экземпляров совершенно одинаковых объектов, в частности, даст результат 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, общий вид которого таков:

switch (выражение) { case значение1:

блок 1;

break;

case значение2:

блок 2;

break;

...

case значениеN:

блокN;

break;

default:

блок N+1;

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

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

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

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

public class MaxVal3 { §2. Основы языка Java public static void main(String[] args) throws Exception { int a = Xterm.inputInt("Введите первое число - ");

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

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

int max;

if (a b) max = a;

else max = b;

if (c max) max = c;

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("Введите третье число - ");

if ( (a == b) || (a == c) || (b == c) ) Xterm.println("Yes");

else Xterm.println("No");

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

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

if (a==0 || b/a 0) x = y;

При 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);

} Глава I. Введение в информатику и программирование // Имена цветов символов и фона public static final int Black = 0;

public static final int Red = 1;

public static final int Green = 2;

public static final int Yellow = 3;

public static final int Blue = 4;

public static final int Magenta = 5;

public static final int Cyan = 6;

public static final int White = 7;

// Метод очистки экрана 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) +";

1m" + txt + "\033[0m\033[30m");

} public static void print(String txt, int fg, int bg) { System.out.print("\033[0m\033["+(bg==7?"":""+(40+bg)+";

")+ (30+fg)+";

1m" + txt + "\033[0m\033[30m");

} public static void println(String txt) { print(txt + "\n");

} public static void println(String txt, int fg) { print(txt + "\n");

} public static void println(String txt, int fg, int bg) { print(txt + "\n");

} // Методы ввода чисел типов 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();

§3. Высказывания и предикаты } 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();

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

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

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

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

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

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

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

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

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

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

Теперь рассмотрим вопрос о том, насколько сложно протестировать уже написанную программу. При этом мы будем предполагать для про стоты, что для линейной программы (без ветвлений) достаточно всего одного теста, для программы с одним оператором 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. Символом алфавита называют любой его эле мент, а цепочкой над алфавитом произвольную последовательность символов.

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

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

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

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

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

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

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

1) = =, 2) (1 2 ) 3 = 1 (2 3 ).

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

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

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

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

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

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

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

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

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

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

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

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

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

(1-е правило: истина) e T (2-е правило: ложь) | F (3-е правило: идентификатор) | id (4-е правило: отрицание) | (!e) (5-е правило: дизъюнкция) | (e e) (6-е правило: условное Или) | (e e) (7-е правило: конъюнкция) | (e e) (8-е правило: условное И) | (e&&e) (9-е правило: импликация) | (e e) (10-е правило: эквивалентность) | (e = e) §3. Высказывания и предикаты e e e ee ( ( a vT ) = a ) Рис. 1. Дерево вывода предиката ((a T ) a) Единственным метасимволом данной грамматики является e, а алфа вит = {T, F, !,,,, &&,, =, (, )} Mid, где множество Mid состоит из всех возможных идентификаторов (имен) переменных программ логиче ского типа.

Приведем пример цепочки вывода в данной грамматике: e (e e) ((e e) e) ((a e) e) ((a T ) e) ((a T ) a). Этo показывает, что выражение ((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 = e) ((e e) = e) ((e e) = (e e)) ((a e) = (e e)) ((a b) = (e e)) ((a b) = (b e)) ((a b) = (b a)).

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

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

42 Глава I. Введение в информатику и программирование Таблица 2. Таблица истинности !b bc bc bc b=c b c bc b&&c 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).



Pages:   || 2 | 3 | 4 | 5 |   ...   | 7 |
 





 
© 2013 www.libed.ru - «Бесплатная библиотека научно-практических конференций»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.