Главная Учебники - Разные Лекции (разные) - часть 17
|
Методические указания к выполнению контрольных работ по дисциплине "Основы программирования" Основы программирования"
В контрольной работе необходимо использовать основные алгоритмические конструкции для построения алгоритмов, составлять алгоритмы, подбирать тесты для проверки алгоритмов, проводить доказательство правильности для алгоритма. Для выполнения контрольной работы необходимо использовать учебное пособие [1] и практикум [2] (см. список литературы). Основные темы, которые входят в данную дисциплину:
1. Основные понятия алгоритмизации. 2. Особенности алгоритмов. 3. Форма записи алгоритмов. Блок-схема алгоритма. 4. Понятие алгоритма в терминах математической теории множеств. 5. Математические методы, используемые при анализе алгоритмов. 6. Методы доказательства корректности алгоритма. Задания для контрольных работ
Студент должен выполнить самостоятельно задание. Номер задачи для каждого студента определяется числом i – номером варианта. Номер варианта – это номер студента в журнале. Если это число больше 15, то для определения номера задачи от числа iнужно вычесть 15 или 30. Например, по выбору преподавателя необходимо выполнить задание 1-1 или задание 1-3. В задании 1-1 необходимосоставить алгоритм решения задачи нахождения суммы nслагаемых числового ряда и алгоритм представить в виде блок-схемы. В задании 1-3 необходимо найти формулу для нахождения n-го слагаемого представленного числового ряда. Доказать, что эта формула верна. Составить алгоритм нахождения суммы числового ряда с заданной точностью. Алгоритм представить в виде блок-схемы. Список литературы
Основная:
1. Емельянов А.А., Власова Е.А., Денисов Д.В., Емельянова Н.З. Основы программирования для информатиков и инженеров: Часть 1 / Под ред. А.А. Емельянова. – М.: ММИЭИФП, 2004. – 208 с. 2. Емельянов А.А., Власова Е.А., Емельянова Н.З. Практикум по основам программирования для информатиков и инженеров / Под ред. А.А. Емельянова. – М.: ММИЭИФП, 2004. – 162 с. 3. Вирт Н. Алгоритмы и структуры данных: Пер. с англ. – М.: Мир, 1989. – 360 с. 4. Кнут Д. Искусство программирования для ЭВМ: в 3т. – М.: Мир, 1978. Дополнительная:
5. Зелковиц М., Шоу А., Гэннон Дж. Принципы разработки программного обеспечения: Пер. с англ. – М.: Мир, 1982. – 386 с. 6. Лэнгсам И., Огенстайн М., Тененбаум А. Структуры данных для персональных ЭВМ. – М.: Мир, 1989. 7. Сибуя М., Ямамото Т. Алгоритмы обработки данных. – М.: Мир, 1986. 8. Фокс Дж. Программное обеспечение и его разработка: Пер. с англ. – М.: Мир, 1985. – 368 с. УЧЕБНАЯ ПРОГРАММА
Цель дисциплины, её место в учебном процессе
Цель
: изучение основ алгоритмизации и программирования с использованием современного языка программирования С++, изучение структур данных, модульного программирования, освоение работы с массивами, структурами, списками. Задачи:
составлять программы на алгоритмическом языке С++, знать принципы работы в среде программирования VisualC
++, работать с массивами, структурами, списками, осуществлять отладку программ в среде программирования VisualC
++. Сфера профессионального использования
Язык «С++» (по-русски произносится как «си плюс плюс») в настоящее время является одним из самых популярных языков программирования. Это универсальный язык программирования, для которого характерны экономичность выражения, современный поток управления и структуры данных, богатый набор операторов. Язык «C++» не является ни языком «очень высокого уровня», ни «большим» языком, и не предназначается для некоторой специальной области применения, а отсутствие ограничений и общность языка делают его более удобным и эффективным для многих задач, чем языки, предположительно более мощные. По разнообразному количеству средств, предоставляемых программистам, его можно считать одним из самых эффективных языков, но, иногда, – и самых эффектных, и самых сложных. Для изучения данной дисциплины студент должен знать:
· математика; · информатика (школьный курс); · основы программирования. Содержание дисциплины
Структура программы на языке С++. Среда программирования Visual
C++. Переменные и константы. Оператор цикла. Работа с массивами. Массивы символов. Функции. Тема 2. Типы операции и выражения
Имена переменных. Типы и размеры данных. Константы. Описания Арифметические операции. Операции отношения и логические операции. Преобразование типов. Операции увеличения и уменьшения. Побитовые логические операции. Операции и выражения присваивания. Условные выражения. Старшинство и порядок вычисления. Тема 3.Поток управления
Операторы и блоки. Конструкция if-else. Конструкция else-if. Переключатель switch. Циклы while и for. Цикл do-while. Оператор break. Оператор continue. Оператор goto и метки. Тема 4.Функции и структура программ
Основные сведения. Функции, возвращающие нецелые значения. Аргументы функций. Внешние переменные. Правила, определяющие область действия. Статические переменные. Регистровые переменные. Рекурсия. Препроцессор языка «C». Заголовочные файлы. Тема 5. Указатели и массивы
Указатели и адреса. Указатели и аргументы функций. Указатели и массивы. Адресная арифметика. Указатели символов и функции. Многомерные массивы. Массивы указателей; указатели указателей. Указатели и многомерные массивы. Командная строка аргументов. Указатели на функции. Тема 6. Структуры
Основные сведения. Структуры и функции. Массивы структур. Указатели на структуры. Структуры, ссылающиеся на себя; двоичные деревья. Поиск в таблице. Битовые поля. Объединения. Тема 7. Динамическое распределение памяти. Работа со списками
Динамическое выделение и освобождение памяти. Понятие списка; основные виды списковых образований. Создание и удаление списка. Программы позиционирования для работы со списками. Тема8. Ввод, вывод и форматные преобразования данных
Стандартный ввод и вывод. Форматный ввод и вывод. Форматные преобразования в памяти. Доступ к файлам. Обработка ошибок. Ввод и вывод строк. Проверка вида символов и преобразования. Обращение к системе. Управление памятью. Учебно-методическая и научная литература
3.1. Емельянов А.А., Власова Е.А., Денисов Д.В., Емельянова Н.З. Основы программирования для информатиков и инженеров: Часть 1 / Под ред. А.А. Емельянова. – М.: ММИЭИФП, 2004. – 208 с. 3.2. Березин Б.И., Березин С.Б. Начальный курс С и С++. – М.: ДИАЛОГ-МИФИ, 1996. – 288 с. 3.3. Джехани Н. Программирование на языке Си. - М.: Радио и связь, 1988.3.4. Керниган Б., Ритчи Д. Язык программирования Си.\ Пер. с англ., 3-е изд. испр. - СПб.: «Невский Диалект», 2001. – 352 с. 3.5. Крупник А. Изучаем С++. – СПб.:Питер, 2003. – 251 с. 3.6.Культин Н.Б. С/С++ в задачах и примерах. – СПб.: БХВ-Петербург, 2003. – 288 с. 3.7. Подбельский В.В. Язык Си++. - М.: Финансы и статистика, 1995. 3.8. Уэйт М., Прата С., Мартин Д. Язык.Си. Руководство для начинающих: Пер. с англ. - М.: Мир, 1988. - 512 с. УЧЕБНОЕ ПОСОБИЕ
В первой части книги в систематической форме излагаются основы теории алгоритмизации и практики программирования на языке «С». Даются рекомендации: как надо программировать, как разрабатывать программу, как ее писать, как отлаживать. Рассмотрены основы адресной арифметики, структуры данных, работа со списками. Практические примеры ориентированы на работу в среде Visual C++. В следующих двух частях будут изложены объектно-ориентированное программирование на С++ и программирование Windows-приложений на С/С++. Книга ориентирована на студентов вузов, обучающихся по специальностям «Прикладная информатика (по областям)» и «Информационные системы». СОДЕРЖАНИЕ
ПРЕДИСЛОВИЕ
. 6 ВВЕДЕНИЕ
8 В.1. Том Сойер рисует на заборе
. 8 В.2. Сид выполняет команды
.. 9 В.3. Программисты
.. 10 В.4. Язык С++
. 11 1. ТЕОРЕТИЧЕСКИЕ ОСНОВЫ АЛГОРИТМИЗАЦИИ И
.. 12 ПРОГРАММИРОВАНИЯ
.. 12 1.1. Основные понятия алгоритмизации
. 12 1.2. Особенности алгоритмов. Программы
.. 16 1.3. Математическая индукция
. 23 1.4. Обобщенный алгоритм Евклида
. 26 2. ПЕРВЫЕ ШАГИ «НАЧИНАЮЩИХ»
. 33 2.1. Давайте начнем, пожалуй!
34 2.2. Переменные и арифметика
. 37 2.3. Оператор for
42 2.4. Символические константы
.. 43 2.5. Набор полезных программ
. 44 2.6. Массивы
.. 52 2.7. Функции
. 55 2.8. Аргументы: вызов по значению
.. 57 2.9. Массивы символов
. 58 2.10. Область действия: внешние переменные
. 61 2.11. Некоторые оптимистичные выводы
.. 64 3. ТИПЫ, ОПЕРАЦИИ И ВЫРАЖЕНИЯ
.. 66 3.1. Имена переменных
. 66 3.2. Типы и размеры данных
. 66 3.3. Константы
.. 68 3.4. Описания
. 70 3.5. Арифметические операции
. 71 3.6. Операции отношения и логические операции
. 72 3.7. Преобразование типов
. 73 3.8. Операции увеличения и уменьшения
. 77 3.9. Побитовые логические операции
. 80 3.10. Операции и выражения присваивания
. 82 3.11. Условные выражения
. 83 3.12. Старшинство и порядок вычисления
. 85 4. ПОТОК УПРАВЛЕНИЯ
.. 88 4.1. Операторы и блоки
. 88 4.2. Конструкция if-else
. 88 4.3. Конструкция else-if
90 4.4. Переключатель switch
. 92 4.5. Циклы
while
и
for
94 4.6.
Цикл
do-while
. 98 4.7.
Оператор
break
. 99 4.8. Оператор continue
. 100 4.9. Оператор goto и метки
. 101 5. ФУНКЦИИ И СТРУКТУРА ПРОГРАММ
.. 103 5.1. Основные сведения
. 103 5.2. Функции, возвращающие нецелые значения
. 107 5.3. Еще об аргументах функций
. 110 5.4. Внешние переменные
. 111 5.5. Правила, определяющие область действия
. 116 5.6. Статические переменные
. 120 5.8. Блочная структура
. 122 5.9. Инициализация
. 123 5.10. Рекурсия
. 126 5.11. Препроцессор языка «C»
. 128 5.12. Заголовочные файлы
.. 130 6. УКАЗАТЕЛИ И МАССИВЫ
.. 132 6.1. Указатели и адреса
. 132 6.2. Указатели и аргументы функций
. 134 6.3. Указатели и массивы
.. 136 6.4. Адресная арифметика
. 139 6.5. Указатели символов и функции
. 143 6.6. Указатели – не целые
. 146 6.7. Многомерные массивы
.. 147 6.8. Массивы указателей; указатели указателей
. 150 6.9. Инициализация массивов указателей
. 154 6.10. Указатели и многомерные массивы
.. 155 6.11. Командная строка аргументов
. 156 6.12. Указатели на функции
. 160 7. СТРУКТУРЫ
.. 164 7.1. Основные сведения
. 164 7.2. Структуры и функции
. 166 7.3. Массивы структур
. 169 7.4. Указатели на структуры
.. 174 7.5. Структуры, ссылающиеся на себя; двоичные деревья
. 176 7.6. Поиск в таблице
. 181 7.7. Битовые поля
. 184 7.8. Объединения
. 186 7.9. Определение «нового» типа данных
. 188 8. ДИНАМИЧЕСКОЕ РАСПРЕДЕЛЕНИЕ ПАМЯТИ.
190 РАБОТА СО СПИСКАМИ
.. 190 8.1. Динамическое выделение и освобождение памяти
. 190 8.2. Понятие списка; основные виды списковых образований
. 191 8.3. Создание и удаление списка
. 194 8.4. Программы позиционирования для работы со списками
. 197 9. ВВОД, ВЫВОД И ФОРМАТНЫЕ ПРЕОБРАЗОВАНИЯ
.. 200 ДАННЫХ
.. 200 9.1. Обращение к стандартной библиотеке
. 200 9.3. Форматный вывод: функция printf
203 9.4. Форматный ввод: функция scanf
205 9.5. Форматные преобразования в памяти
. 208 9.6. Доступ к файлам
. 209 9.7. Обработка ошибок: stderr и exit
212 9.8. Ввод и вывод строк
. 213 9.9. Несколько разнообразных функций
. 215 ЛИТЕРАТУРА
.. 217 Современный специалист по прикладной информатике или инженер по информационным системам должен уметь программировать. Ему не обязательно быть профессиональным системным программистом или «хакером». Дело в том, что и при разработке, и при эксплуатации сложных компьютерных систем требуется адаптировать соответствующее программное обеспечение. При этом нужно написать или изменить какую-то программу, создать новый программный интерфейс для работы с профессионально-ориентированной компьютерной системой, перепрограммировать систему контроля данных, написать новую программу загрузки базы данных и др. Практика показывает, что в последнее время большинство таких работ проводится с применением языка «С++» (по-русски произносится как «си плюс плюс»), который в настоящее время является одним из самых популярных языков программирования. Это универсальный язык, для которого характерны экономичность выражения, современный поток управления и структуры данных, богатый набор операторов. Язык «C++» не является ни языком «очень высокого уровня», ни «большим» языком, и не предназначается для некоторой специальной области применения, но отсутствие ограничений и общность языка делают его более удобным и эффективным для многих задач, чем языки, предположительно более мощные. По разнообразному количеству средств, предоставляемых программистам, его можно считать одним из самых эффективных языков, но, иногда, – и самых эффектных, и самых сложных. Все перечисленные обстоятельства объясняют, почему нами этот язык выбран в качестве базового. В язык «C++» в качестве основного, базового средства включен более старый язык «C» (по-русски произносится как «си», поэтому некоторые авторы пишут его название как «Си»), который первоначально предназначался для написания операционной системы U
nix
; он был разработан и реализован Деннисом Ричи. Операционные системы U
nix
и Windows
, компиляторы с языка «C++» и большинство прикладных программных систем сейчас создаются на языке «C++». Этот язык, однако, не связан с какими-либо определенными аппаратными средствами или системами, и на нем легко писать программы, которые можно пропускать без изменений на любом компьютере или ЭВМ, имеющей C-компилятор. Целью первого учебного курса «Основы алгоритмизации и программирования» является обучение основам программирования. В это время студент, не будучи асом алгоритмизации, не сможет по достоинству оценить возможности объектно-ориентированного программирования, предоставляемые «C++». Поэтому сначала обучение ведется на классическом языке «С» (он входит в состав любой версии «С++) с минимальным привлечением дополнительных средств, имеющихся в «C++». В результате второго учебного курса студенты, получившие изрядный опыт по описанию алгоритмов средствами традиционного языка «C», совершенствуют свое мастерство, и средствами объектно-ориентированного программирования языка «C++» делают программы более эффективными и компактными. Третий учебный курс «Программирование приложений для Windows
» предназначен для развития навыков реализации реальных проектов, создания Windows-приложений (Windows applications). При этом используются все ранее изученные средства. В соответствии с этими тремя курсами учебно-методическое обеспечение также разделено на 3 части. Мы не претендуем на оригинальность изложения теоретического материала по программированию. При создании данного учебного пособия нами использовались хрестоматийным образом данные из книг, пособий и справочников известных авторов: М.И. Болски, Б. Кернигана, Д. Кнута, Д. Дж. Круглински, А.Б. Крупника, Д. Ритчи, Г. Шилдта. В качестве основного методического приема используется прагматический подход, изложенный в знаменитой книге Б. Кернигана и Д. Ритчи «Язык программирования Си», – это обучение на «живых» примерах. Однако имеется и оригинальный материал. Например, глава 8 «Динамическое распределение памяти. Работа со списками» (в первой части книги), а также весь практикум по программированию. Учебное пособие предназначено для студентов младших курсов компьютерных специальностей. Редактор, п
рофессор
А.А. Емельянов В.1. Том Сойер рисует на заборе
«Том появился на тротуаре с ведром извёстки и длинной кистью в руках. Он оглядел забор, и всякая радость отлетела от него, а дух погрузился в глубочайшую тоску. Тридцать ярдов дощатого забора в девять футов вышиной! Жизнь показалась ему пустой, а существование – тяжким бременем». Марк Твен,
«Приключения Тома Сойера
» Память компьютера похожа на длинный-предлинный забор, правда, покрашенный совсем не так, как хотелось бы тетушке Полли. Представим себе, что Том со своими дружками покрыли известкой не все доски забора, а, скажем, только первую, вторую, четвертую, седьмую... и т. д.: 1 1 0 1 0 0 1 0 1 1 0 0 1 1 1 0 1 1 0 0 1 1 0 0 Поступая так, Том Сойер и его команда, конечно же, не подозревали, что полосатый забор можно рассматривать как двоичный код, в котором единице соответствует светлая, а нулю – темная, непокрашенная доска. Каждая доска может быть только в двух состояниях, следовательно, она способна нести один бит информации. Число различных состояний двух идущих подряд досок уже равно четырем, поскольку каждому из двух состояний первой доски соответствуют два состояния второй. Легко понять, что восемь идущих подряд досок можно выкрасить 2 ´ 2 ´ 2 ´ 2 ´ 2 ´ 2 ´ 2 ´ 2 = 28
= 256 способами. Иными словами, в восьми битах можно уместить 256 разных чисел (от 0 до 255, например), а этого вполне достаточно, чтобы закодировать любую букву. Поскольку «забор» в нашем примере состоит из 24 досок (цифр), он пригоден для того, чтобы закодировать сразу три буквы. Какие же буквы показаны на заборе? Ответ на этот вопрос зависит от договоренности: какому числу соответствует та или иная буква. Первое число (11010010) на заборе равно (в привычном нам десятичном представлении) 210, второе (11001110) – это 206, третье (11001100) равно 204. И вся эта тройка соответствует в операционной системе Windows
, скорее всего установленной у вас на компьютере, слову «ТОМ». Цифра 8 возникла в нашем шуточном примере не случайно. Ведь восемь битов (досок в заборе тетушки Полли) составляют байт
– ячейку памяти минимального размера, к которой имеет доступ компьютер. Можно сказать, что память компьютера состоит из последовательности идущих друг за другом ячеек – байтов. В этих ячейках хранятся нули и единицы, которые могут быть чем угодно: буквами, цифрами или выполняемыми компьютером командами. Представим себе, что компьютерная программа написана на заборе, а роль процессора
играет образцовый брат Тома – Сид. Том сидит на бочке и жует яблоко, а Сид отправляется к тому месту забора, где записана первая команда. Стоит еще раз подчеркнуть: в памяти компьютера, как и на заборе, хранятся последовательности нулей и единиц. Поэтому нужно заранее знать, с какой ячейки (байта) 5
начинается программа, чтобы не перепутать команды процессора и данные. Итак, предположим, что команда начинается с 31-го байта, то есть с 241-й доски забора. Подойдя к ней, Сид ищет число, там записанное, в специальной справочной таблице, которую вынужден носить с собой. Из этой таблицы он узнает, что делать дальше. Может, например, оказаться, что прочитанный Сидом байт – лишь часть команды процессора, и чтобы выполнить ее, необходимо знать содержимое нескольких следующих ячеек. Команды, выполняемые Сидом, весьма разнообразны. Простейшая команда просто велит ему перейти к другой ячейке. Если ее номер равен 20, Сиду нужно будет сделать несколько шагов к началу забора, а если это Представим себе, что перед выполнением программы в пятнадцатой ячейке хранится число 10. Раз оно больше нуля, Сид перейдет к двадцатому байту, выполнит команды, записанные в ячейках с номерами 21¸30, и, если содержимое 15-й ячейки не изменилось, 31-й байт вновь отошлет его назад, и так он будет крутиться, пока хватит сил. Если же команды, хранящиеся в байтах 21¸30, после многих пробежек Сида запишут нуль в ячейку 15, тот вместо двадцатого байта перейдет к следующей команде, начало которой хранится в ячейке 32. Иными словами, Сид будет выполнять команды последовательно, одну за другой, пока ему не прикажут перейти к иной ячейке, и после очередной пробежки вдоль забора он снова начнет выполнять команды последовательно. И так будет продолжаться до тех пор, пока он не наткнется на команду «Стоп». Впрочем, еще раньше он может встретить число, которого нет в его таблице, или же предписание перейти к Комбинация Тома, Сида и забора, с которой мы только что познакомились, мало похожа на реальный компьютер, хотя в ней, как ни странно, есть все его главные компоненты: память (забор), процессор, выполняющий записанные в памяти команды и пользующийся хранящимися там же данными (Сид), и операционная система, показывающая процессору начало программы (Том). Первые два компонента (процессор и память) представляют собой мертвый набор микросхем, третья же (операционная система) оживляет эту груду железа, делает возможным запуск программ, взаимодействие со вспомогательными устройствами памяти (жесткими дисками) и многое другое. Собственно, операционная система, – это тоже программа, только самая главная, управляющая другими, прикладными
программами, такими как MS
Word
или Excel
. Итак, для работы компьютера необходимы программы, создаваемые людьми, но процессор компьютера, как мы знаем, понимает только двоичные коды. И первые (сейчас уже легендарные) программисты вынуждены были выписывать на бланках длинные последовательности нулей и единиц. Эта работа была крайне напряженной – не только потому, что люди плохо воспринимают двоичные коды, но и потому, что записанные таким образом программы очень трудно менять. Ведь включение какой-то команды «растягивает программу», команды наползают на данные, а перенос данных в другое место памяти меняет номера ячеек, к которым обращается программа! Все это делает программирование в двоичных кодах крайне ненадежным, изнурительным и опасным. Вот почему очень скоро программисты занялись облегчением собственного труда. И поскольку были они программистами, то и придумали для собственной пользы специальные программы – ассемблеры, которые могли перевести команды процессора, записанные «человеческим» языком – с помощью букв и десятичных чисел, – в двоичные коды, понимаемые процессором. Ассемблеры были гигантским шагом вперед, но и они требовали от первых программистов мыслить на языке машины, а не человека. Программирование на ассемблере требовало знания многочисленных команд процессора, причем программа, написанная для одного процессора, не могла быть выполнена другим процессором с иной системой команд. Поэтому вслед за ассемблерами были изобретены компиляторы –
программы, которые воспринимали язык программирования, понятный человеку и не зависящий от конкретного процессора. Чтобы такое стало возможным, нужно было один раз «помучиться» и написать (на языке ассемблера) компилятор для данного процессора, а затем уже пользоваться языком, понятным и человеку, и компилятору, или, как говорят, языком высокого уровня.
К числу таких языков относятся Pascal, Fortran, С и, конечно же, C++. Создавая ассемблеры и компиляторы, программисты в миллионы раз расширили свои возможности. Число команд, записанных двоичными кодами, едва ли может превысить несколько тысяч. А на языках высокого уровня уже написаны и работают гигантские программы, в которых десятки, сотни миллионов строк. Особенно пригоден для разработки очень больших программ язык высокого уровня C++. В нём есть возможность создавать объекты –
аналоги тех многочисленных вещей, которые нас окружают. И телевизор, и стиральная машина, и компьютер, и тостер имеют внутреннее устройство, нам недоступное, а также интерфейс,
то есть кнопки, ручки и т.д., с помощью которых этими объектами можно управлять. Нажимая кнопку на пульте управления, мы не задумываемся о том, как устроен телевизор, нам достаточно знать, что эта
кнопка переключит телевизор на ОРТ, а вот эта
увеличит громкость. Как и домашние вещи, объекты языка C++ имеют внутреннее устройство, скрытое от непосвященных, и интерфейс – так называемые собственные функции,
или методы,
с помощью которых такими объектами можно управлять. Собственные функции похожи на кнопки пульта управления телевизора. Пользуясь собственными функциями, мы не думаем о внутреннем устройстве объекта. Сам объект может быть гораздо сложнее телевизора, и, возможно, его разрабатывали десятки высококвалифицированных программистов, однако собственные функции этого объекта очень просты, и, чтобы научиться ими пользоваться, достаточно пары часов. Разработка программы на языке C++ обычно начинается с тщательного анализа задачи, выделения в ней объектов и разработки соответствующих интерфейсов. Далее каждый объект можно создавать независимо от других. Остальные программисты, занятые использованием
самих объектов, вовсе не обязаны ждать, пока их создадут. Им достаточно знать только интерфейс
этих пока не существующих объектов и спокойно писать свою часть программы. Это значит, что C++ позволяет разбить сложную задачу на множество мелких и наладить промышленное, почти конвейерное, производство больших программ. 1. ТЕОРЕТИЧЕСКИЕ ОСНОВЫ АЛГОРИТМИЗАЦИИ И
1.1. Основные понятия алгоритмизации
«Многие не сведущие в математике люди думают, что поскольку назначение аналитической машины Бэббиджа – выдавать результаты в численном виде, то природа происходящих в ней процессов должна быть арифметической и численной, а не алгебраической и аналитической. Но они ошибаются. Машина может упорядочивать и комбинировать числовые значения так же, как и буквы или любые другие символы общего характера. В сущности, при выполнении соответствующих условий она могла бы выдавать результаты и в алгебраическом виде». Августа Ада, графиня Лавлейс
(1844
) Основоположницей программирования считают Августу Аду – дочь великого английского поэта Дж. Г. Байрона. В 19 веке в Англии впервые появилось настоящее арифметическое устройство – аналитическая машина Бэббиджа: с регистрами, сумматором и другими атрибутами, присущими процессору современного компьютера. Программы для такого устройства расписывались на бумаге. Каждая операция совершалась поворотом особой ручки или нажатием рычага такой машины. Большинство идей и принципов программирования для аналитической машины Бэббиджа было рассмотрено в книге Августы Ады*
«Комментарии». Позднее появился особый вид деятельности – программирование, а в последствии возникла профессия программиста. Понятие «алгоритм» является основным для всей области компьютерного программирования, поэтому начать мы должны с тщательного анализа этого термина. Слово «алгоритм» (англ.
algorithm
) уже само по себе представляет большой интерес. Историки-математики обнаружили истинное происхождение этого слова: оно берет начало от имени автора знаменитого персидского учебника по математике, Абу Абд Аллах Мухаммед ибн Муса аль-Хорезми (ок. 825 г.). Аль-Хорезми написал знаменитую книгу «Книга о восстановлении и противопоставлении» (перс. Китаб аль-джебр валь-мукабала
). От названия этой книги, которая была посвящена решению линейных и квадратных уравнений, произошло еще одно слово – «алгебра». В старинном немецком математическом словаре Vollstandiges
mathematisches
Lexicon
(Лейпциг, 1747) дается следующее толкосание латинского слова algorithmus
:
«Этот термин включает в себя понятие о четырех типах арифметических операций, а именно: о сложении, умножении, вычитании и делении». Латинское выражение algorithmus
infinitesimalis
в то время использовалось для определения способов выполнения действий с бесконечно малыми величинами, открытых великим математиком Лейбницем. Пример 1-1
. Алгоритм Евклида. Приблизительно через 100 лет после появления аналитической машины Бэббиджа была создана первая электронная вычислительная машина – специально для выполнения атомного проекта в Лос-Аламосе (США). В это время (конец 40-х – начало 50-х годов 19 века) слово «алгоритм» чаще всего ассоциировалось с алгоритмом Евклида, который представляет собой процесс нахождения наибольшего общего делителя двух чисел. Этот алгоритм далее будем называть «алгоритмом Е». Сущность алгоритма Е
: даны два целых положительных числа т
и п.
Требуется найти их наибольший общий делитель, т.е. наибольшее целое положительное число, которое нацело делит оба числа т
и п
. Алгоритм состоит из трех элементарных типовых действий: Е1, Е2 и Е3 (рис. 1.1). Действие
Е1. Нахождение остатка. Разделим m
на п
, и пусть остаток от деления будет равен r
, где Действие
Е2. Сравнение с нулем. Если r
=
0, то выполнение алгоритма прекращается; п
– это искомое значение. Действие
Е3. Замещение. Присвоить m
¬ n
, n
¬ r
и вернуться к шагу E1. ô
Разумеется, у Евклида этот алгоритм сформулирован не совсем так. Приведенная выше формулировка иллюстрирует стиль, в котором алгоритмы будут представлены на протяжении всей этой книги. Каждому рассматриваемому алгоритму присваивается идентифицирующая буква (в предыдущем примере использовалась буква Е), а шагам алгоритма – эта же буква в сочетании с числом (El, Е2, ЕЗ). Каждый шаг любого алгоритма, например Е1 в вышеприведенном алгоритме, начинается фразой, которая как можно более кратко выражает содержание данного шага. Обычно эта фраза отражается также в сопровождающей алгоритм блок-схеме,
такой как на рис. 1.1, чтобы читатель мог легко представить себе описанный алгоритм. За краткой фразой следует формулировка (выраженная с помощью слов и символов) действия,
которое нужно выполнить, или решения, которое нужно принять. Могут присутствовать также заключенные в круглые Стрелка «¬», используемая на шаге ЕЗ, обозначает важнейшую операцию замещения,
которую иногда называют присвоением
или подстановкой:
запись m
¬ n
указывает, что значение переменной т
замещается текущим значением переменной п
. В начале работы алгоритма Е, т
и п
– это заданные первоначальные значения, но по окончании его работы эти переменные будут иметь, вообще говоря, совершенно другие значения. Стрелка используется для того, чтобы отличать операцию замещения от отношения равенства. Мы не будем говорить: «Установим т
= п
», а, вероятно, спросим: «Действительно ли т
= п
?». Знак «=» обозначает условие, которое можно проверить, а знак «¬» – действие, которое можно выполнить. Операция увеличение п на единицу
обозначается через п
¬ п
+1 и читается так: «п
замещается значением п
+1» или «п
принимает значение п
+1». Вообще говоря, запись «переменная ¬ формула» означает, что формула будет вычислена на основании текущих значений всех входящих в нее переменных, а полученный результат будет присвоен переменной, стоящей слева от стрелки (таким образом, вычисленный по формуле результат заменит собой предыдущее значение переменной слева). Лица, не имеющие достаточного опыта программирования, иногда говорят, что «п
переходит в п+
1» и для обозначения операции увеличения п
на единицу используют запись п
® п+
1. Такая система обозначений и формулировок противоречит стандартным соглашениям и может привести только к путанице, поэтому ее следует избегать. Обратите внимание, что на шаге ЕЗ очень важен порядок действий. Действительно, две записи: 1) «присвоить m
¬ n
, n
¬ r
» и 2) «присвоить n
¬ r
, m
¬ n
» – это совсем не одно и то же. Из второй записи следует, что предыдущее значение n
будет потеряно до того, как его смогут присвоить т.
На самом деле эквивалентом второй записи будет «присвоить n
¬ r
, т
¬ r
».
Когда нескольким переменным присваивается одно и то же значение, в одном выражении можно использовать несколько стрелок. Так, например, операцию « n
¬ r
, т
¬ r
» можно записать как « n
¬ т
¬r
». Операцию взаимного обмена значениями двух переменных можно записать так: «Обмен т
« n
». Ее можно записать и с помощью новой переменной t
следующим образом: "Присвоить t
¬ т
, т
¬ п
, п
¬ t
.
Выполнение алгоритма начинается с шага, имеющего наименьший номер (обычно это шаг 1). Затем последовательно выполняются следующие шаги, если нет каких-либо указаний, нарушающих естественный порядок выполнения. На шаге ЕЗ указание «Вернуться к шагу Е1» явным образом определяет порядок вычислений. На шаге Е2 действию предшествует условие «Если r
=
0» и если r
# 0, то оставшаяся часть предложения не применяется и нет указаний на выполнение в этом случае каких-либо действий. Конечно, мы могли бы добавить дополнительное предложение «Если r
# 0, то перейти к шагу ЕЗ», но это совершенно излишне. Жирная вертикальная черточка «ô
», помещенная в конце шага ЕЗ, обозначает окончание алгоритма и продолжение текста. Итак, мы обсудили практически все соглашения об обозначениях, которые используются в алгоритмах, приведенных в книге. Осталось выяснить только, как обозначать величины с индексами (или «подстрочными» индексами), которые являются элементами упорядоченного массива. Предположим, у нас есть п
величин: v
1
, v
2
, …, vn
.
Для обозначения j
-го элемента вместо записи vj
часто используется запись v
[j
].
Аналогично массив иногда предпочитают обозначать как а
[i
, j
], вместо того чтобы использовать два подстрочных индекса, как в записи aij
. Иногда для обозначения переменных используются имена, состоящие из нескольких букв, обычно прописных. Например, TEMP может быть именем переменной, использующейся для временного хранения вычисленного значения, a PRIME [К] может обозначать k
-е простое число, и т.д. До сих пор мы говорили о форме записи
алгоритмов, а теперь давайте попробуем выполнить
один из них. Хочу сразу заметить, что читателю не
следует рассчитывать на то, что алгоритмы можно читать, как роман. Такое чтение приведет к тому, что вам будет трудно понять, что же на самом деле происходит при выполнении алгоритма. Чтобы проверить алгоритм, в нем нужно разобраться, и лучший способ понять, как он работает, – испытать его. Поэтому нужно взять карандаш и бумагу и прорабатывать от начала до конца каждый алгоритм сразу же, как только он встретится в тексте. Обычно к примеру алгоритма прилагается схема, в противном случае читатель легко сможет представить ее. Это самый простой и доступный способ разобраться в алгоритме, в то время как все остальные подходы оказываются неэффективными. Итак, давайте в качестве примера разберем алгоритм Е. Предположим, что m
= 119 и n
= 544. Начнем с шага Е1. Деление m
на n
в этом случае выполняется просто, даже очень просто, так как частное равно нулю, а остаток – это 119. Таким образом, r
¬ 119. Переходим к шагу Е2. Поскольку r
# 0, на этом шаге никакие действия не выполняются. На шаге ЕЗ присваиваем т
¬ 544, п
¬ 119. Очевидно, что если первоначально m
< п
, то частное на шаге Е1 всегда оказывается равным нулю и в ходе выполнения алгоритма всегда происходит взаимный обмен значений переменных тип, хотя и таким громоздким способом. Поэтому можно добавить дополнительный шаг: Действие
Е0. Гарантировать, что m
> п
. Если m
< п
, то выполнить взаимный обмен т
« n
. В результате алгоритм изменится незначительно (разве что увеличится на один шаг), но зато время его выполнения сократится примерно в половине случаев. Вернемся к шагу Е1. Находим, что
Поэтому r
¬ 68. В результате на шаге Е2 снова не выполняются никакие действия, а на шаге ЕЗ присваиваем т
¬ 119, п
¬ 68. В следующих циклах сначала получаем r
¬ 51 и т
¬ 68, п
¬ 51, а затем: r
¬ 17 и т
¬ 51, п
¬ 17. Наконец, в результате деления 51 на 17 получаем: r
¬ 0. Таким образом, на шаге Е2 выполнение алгоритма прекращается. Наибольший общий делитель 119 и 544 равен 17. Вот что такое алгоритм. 1.2. Особенности алгоритмов. Программы
Современное значение слова «алгоритм» во многом аналогично таким понятиям, как рецепт, процесс, метод, способ, процедура, программа
. Но все-таки, слово «algorithm» имеет дополнительный смысловой оттенок. Алгоритм – это не просто набор конечного числа правил, задающих последовательность выполнения операций для решения задачи определенного типа. Помимо этого, он имеет пять важных особенностей. 1. Конечность.
Алгоритм всегда должен заканчиваться после выполнения конечного числа шагов. Алгоритм Е удовлетворяет этому условию, потому что после шага Е1 значение r
меньше,
чем п.
Поэтому если r
# 0, то в следующем цикле на шаге Е1 значение п уменьшается.
Убывающая последовательность положительных целых чисел имеет конечное число членов, поэтому шаг Е1 может выполняться только конечное число раз для любого первоначально заданного значения п. Но нужно иметь в виду, что количество шагов может быть сколь угодно большим; выбор слишком больших значений тип приведет к тому, что шаг Е1 будет выполняться более миллиона раз. Процедура, обладающая всеми характеристиками алгоритма, за исключением, возможно, конечности, называется методом вычислений.
Евклид предложил не только алгоритм нахождения наибольшего общего делителя, но и аналогичное ему геометрическое построение «наибольшей общей меры» длин двух отрезков прямой; это уже метод вычислений, выполнение которого не заканчивается, если заданные длины оказываются несоизмеримыми. 2. Определенность.
Каждый шаг алгоритма должен быть точно определен. Действия, которые нужно выполнить, должны быть строго и недвусмысленно определены для каждого возможного случая. Чтобы преодолеть это затруднение, для описания алгоритмов были разработаны формально определенные языки программирования,
или машинные языки,
в которых каждый оператор имеет строго определенное значение. Определение
: метод вычислений, выраженный на языке программирования, называется программой.
Рассмотрим в качестве примера алгоритм Е. Применительно к шагу Е1 критерий определенности означает, что читатель обязан точно понимать, что значит разделить т
на п
и что такое остаток. Но в действительности нет никакого общепринятого соглашения по поводу того, что это означает, если m
и п
не являются целыми положительными числами. Каким будет остаток от деления -8 на -p ? Что понимать под остатком от деления 59/13 на нуль? Поэтому в данном случае критерий определенности означает следующее: мы должны быть уверены, что в каждом случае выполнения шага Е1 значениями т
и п
всегда будут целые положительные числа. Если сначала по предположению это верно, то после шага Е1 r
– это целое неотрицательное число; при условии перехода к шагу ЕЗ оно является также ненулевым. Таким образом, поставленное требование выполнено и т
и п
– это действительно целые положительные числа. 3. Ввод
. Алгоритм имеет некоторое (возможно, равное нулю) число входных данных,
т.е. величин, которые задаются до начала его работы или определяются динамически во время его работы. Эти входные данные берутся из определенного набора объектов. Например, в алгоритме Е есть два входных значения, а именно m
и п
, которые принадлежат множеству целых положительных
чисел. 4. Вывод.
У алгоритма есть одно или несколько выходных данных,
т.е. величин, имеющих вполне определенную связь с входными данными. У алгоритма Е имеется только одно выходное значение, а именно п
, получаемое на шаге Е2. Это наибольший общий делитель двух входных значений. Можно легко доказать,
что это число действительно является наибольшим общим делителем. После шага Е1 имеем:
где q
– некоторое целое число. Если r
= 0, то т
кратно п
и, очевидно, в этом случае n
– наибольший общий делитель для m
и п.
Если r
# 0, то любой делитель обоих чисел m
и п
должен быть также делителем для
а любой делитель для п
и r
– также делителем для:
Таким образом, множество делителей чисел {т
, п
} совпадает с множеством делителей чисел {п
, r
}. Следовательно, пары чисел {т
, п
} и {п
, r
} имеют один и тот же наибольший
общий делитель. Таким образом, шаг ЕЗ не изменяет ответа исходной задачи. 5. Эффективность.
Алгоритм обычно считается эффективным,
если все его операторы достаточно просты для того, чтобы их можно было точно выполнить в течение конечного промежутка времени с помощью карандаша и бумаги. В алгоритме Е используются только следующие операции: деление одного целого положительного числа на другое, сравнение с нулем и присвоение одной переменной значения другой. Эти операции являются эффективными, так как целые числа можно представить на бумаге с помощью конечного числа знаков и так как существует по меньшей мере один способ деления одного целого числа на другое – «алгоритм деления». Но те же самые операции были бы неэффективными,
если бы они выполнялись над действительными числами, представляющими собой бесконечные десятичные дроби, либо над величинами, выражающими длины физических отрезков прямой, которые нельзя измерить абсолютно точно. Приведем еще один пример неэффективного шага: «Если 4 – это наибольшее целое n
, при котором существует решение уравнения wn
+
xn
+
yn
=
zn
для целых положительных чисел w
, x
, y
и z
, то перейти к шагу Е4». Подобная операция не может считаться эффективной до тех пор, пока кто-либо не разработает алгоритм, позволяющий определить, действительно ли 4 является наибольшим целым числом с требуемым свойством. Попробуем сравнить понятие «алгоритм» с рецептом из кулинарной книги. Предполагается, что рецепт обладает свойством конечности (хотя и говорят, что «кто над чайником стоит, у того он не кипит»), имеет · входные данные (такие, например, как яйца, мука и т.д.), · выходные данные (обед «на скорую руку» и т.п.), · но хорошо известно, что ему не хватает определенности. Инструкции из кулинарных рецептов очень часто бывают неопределенными, например: «Добавьте щепотку соли». «Щепотка» определяется как количество, «меньшее 1/8 чайной ложки», и что такое соль, вероятно, тоже известно всем. Но куда именно нужно добавить соль – сверху? сбоку? Инструкции «Слегка потрясите, пока смесь не станет рассыпчатой» и «Подогрейте коньяк в маленькой кастрюльке» будут вполне понятны опытному повару, но они не годятся для алгоритма. Алгоритм должен быть определен настолько четко, чтобы его указаниям мог следовать даже компьютер. Тем не менее, программист может многому научиться, прочитав хорошую поваренную книгу. Следует отметить, что для практических целей ограничение, состоящее в конечности алгоритма, в сущности, является недостаточно жестким. Используемый на практике алгоритм должен иметь не просто конечное, а достаточно ограниченное,
разумное число шагов. Например, алгоритм определения того, может ли игра в шахматы всегда быть выиграна белыми при условии, что не было сделано ни одной ошибки. Этот алгоритм позволил бы решить проблему, представляющую огромный интерес для тысяч людей, но можно биться об заклад, что окончательный ответ на данный вопрос мы не узнаем никогда. Все дело в том, что для выполнения указанного алгоритма требуется невероятно большой промежуток времени, хотя сам алгоритм и является конечным. На практике нам нужны не просто алгоритмы, а хорошие
алгоритмы в широком смысле этого слова. Одним из критериев качества алгоритма является время, необходимое для его выполнения; данную характеристику можно оценить по тому, сколько раз выполняется каждый шаг. Другими критериями являются адаптируемость алгоритма к различным компьютерам (или переносимость, мобильность программ, как на языке С++), его простота, изящество и т.д. Часто решить одну и ту же проблему можно с помощью нескольких алгоритмов и нужно выбрать наилучший из них. Таким образом, мы попадаем в чрезвычайно интересную и крайне важную область анализа алгоритмов.
Предмет этой области состоит в том, чтобы для заданного алгоритма определить рабочие характеристики. В качестве примера давайте исследуем с этой точки зрения алгоритм Евклида. Предположим, нам нужно решить следующую задачу: «Пусть задано значение n
, а т
может быть любым целым положительным числом. Тогда чему равно среднее
число Тп
выполнений шага Е1 алгоритма Е?». Прежде всего необходимо убедиться в том, что задача имеет смысл, поскольку нам предстоит найти среднее при бесконечно большом количестве значений т. Но совершенно очевидно, что после первого выполнения шага Е1 значение будет иметь только остаток от деления т
на п.
Поэтому все, что мы должны сделать для нахождения значения Тп
, – это испытать алгоритм для m
= 1, m
= 2, ..
., m
= п
, подсчитать суммарное число выполнений шага Е1 и разделить его на п.
А теперь рассмотрим еще один важный вопрос, касающийся поведения Тп
как функции от п
: можно ли ее аппроксимировать, например, функцией
На самом деле это чрезвычайно сложная и интересная математическая проблема, которая еще не решена окончательно. Можно доказать, что при больших значениях п
Тп
ведет себя, как функция
т.е. она пропорциональна натуральному логарифму п.
Заметим, что коэффициент пропорциональности k
нельзя просто взять и угадать; чтобы определить его, нужно затратить определенные усилия. Для обозначения области подобных исследований используется термин анализ алгоритмов.
Основная идея заключается в том, чтобы взять конкретный алгоритм и определить его количественные характеристики. Время от времени мы будем также выяснять, является ли алгоритм оптимальным в некотором смысле. Теория алгоритмов
– это совершенно другая область, в которой, в первую очередь, рассматриваются вопросы существования или не существования эффективных алгоритмов вычисления определенных величин. До сих пор наше обсуждение алгоритмов носило достаточно общий характер, и, вероятно, «математически настроенный» читатель утвердился в мысли, что все предыдущие комментарии представляют собой очень шаткий фундамент для построения какой-либо теории алгоритмов. Поэтому давайте подведем итог данного раздела, кратко описав метод, с помощью которого понятие алгоритма можно строго обосновать в терминах математической теории множеств. Формально определим метод вычислений
как четверку ( Q
, I
, W, f
), где Q
– это множество, содержащее подмножества I
и W, а f
– функция, переводящая множество Q
в себя. Кроме того, f
оставляет неподвижными точки множества W, т.е. f
(q
) равно q
для всех элементов q
из множества W. Эти четыре элемента Q
, I
, W и f
представляют соответственно состояния вычисления, ввод, вывод и правило вычислений. Каждое входное значение х
из множества I
определяет вычисляемую последовательность
x
0
, x
1
, x
2
, … следующим образом: x
0
= х
и xk
+1
= f
(xk
) для k
³
0. (1.1) Говорят, что вычисляемая последовательность заканчивается через
k
шагов,
если k
– это наименьшее целое число, для которого xk
принадлежит W, и что она дает выходное значение xk
для заданного х.
(Заметим, что если xk
принадлежит W, то и xk
+1
принадлежит W, так как в этом случае xk
+1
= xk
). Некоторые вычисляемые последовательности могут никогда не заканчиваться, но алгоритм
– это метод вычислений, который заканчивается через конечное число шагов для всех х
из I
. Например, алгоритм Е в этих терминах можно формализовать следующим образом. Пусть элементами множества Q
будут все величины (n
), все упорядоченные пары (m
,n
) и все упорядоченные четверки (m
,n
,r
,1), (m
,n
,r
,2) и (m
,n
,p
,3), где m
, n
и р
– это целые положительные числа, а r
– неотрицательное целое число. Пусть I
– это подмножество всех пар (m
,n
), а W – подмножество всех величин (n
). Определим функцию f
следующим образом: Соответствие между данной записью и алгоритмом Е очевидно. В этой формулировке понятия «алгоритм» не содержится ограничение, касающееся эффективности, о котором упоминалось ранее. Например, Q
может быть множеством бесконечных последовательностей, которые нельзя вычислить с помощью карандаша и бумаги, а f
может включать операции, которые не всегда возможно выполнить. Если мы хотим ограничить понятие «алгоритм» таким образом, чтобы в нем могли содержаться только элементарные операции, то введем ограничения на элементы Q
, I
, W и f
, например, следующим образом. Пусть А
– это ограниченное множество букв, а L – множество всех строк, определенных на множестве А
(т.е. множество всех упорядоченных последовательностей x
0
, x
1
, x
2
, …, где n
³0 и xj
принадлежит А
для 1 £ j
£ п.
Идея заключается в следующем: закодировать состояния вычисления таким образом, чтобы они были представлены строками из множества L.
Теперь пусть N
– целое неотрицательное число, а Q
– множество всех пар (s, j
), где s принадлежит L, a j
– целое число, 0 £ j
£ N.
Пусть I
– подмножество пар из Q
, для которых j
=
0, а W – подмножество пар из Q
, для которых j
= N.
Если q и s – строки из L, то мы будем говорить, что q входит в s, если s имеет вид aqw, где a и w – некоторые строки. И в завершение определим функцию f
с помощью строк qj
, fj
и целых чисел aj
, bj
, 0 £ j
£ N
, следующим образом: если qj
не входит в s если a является самой короткой (1.3) строкой, для которой s = a qj
w Метод вычислений, удовлетворяющий этому определению, безусловно, является эффективным. Кроме того, опыт показывает, что в таком виде можно представить любую задачу, которая решается с помощью карандаша и бумаги. Упражнение 1.1
. В тексте показано, как взаимно заменить значения переменных типе помощью символа замены, а именно – полагая t
¬ m
, m
¬ п
, п
¬ t
.
Покажите, как в результате ряда замен можно преобразовать четверку
переменных (a
,b
,c
,d
) в (b
,c
,d
,a
). Другими словами, новое значение переменной а
должно стать равным первоначальному значению 6 и т.д. Постарайтесь выполнить преобразование с помощью минимального числа замен. Упражнение 1.2
. Докажите, что в начале выполнения шага El m
всегда больше п
, за исключением, возможно, только первого случая выполнения этого шага. Упражнение 1.3
. Измените алгоритм Е (из соображений эффективности) таким образом, чтобы исключить из него все тривиальные операции замены типа « m
¬ n
». Запишите этот новый алгоритм в стиле алгоритма Е и назовите его алгоритмом F. Упражнение 1.4
. Чему равен наибольший общий делитель чисел 2 166 и 6 099? Упражнение 1.5
. Чему равно T
5
(среднее число случаев выполнения шага Е1 при n
= 5)? Упражнение 1.6
. Пусть т
известно, а n
– любое целое положительное число. Пусть Um
– среднее число случаев выполнения шага Е1 из алгоритма Е. Покажите, что Um
четко определено. Существует ли какая-либо связь между Um
и Tm
? Упражнение 1.7
. Придумайте эффективный формальный алгоритм вычисления наибольшего общего делителя целых положительных чисел т
и п
, определив соответствующим образом qj
, fj
, aj
, bj
(как в формулах (1.3)). Пусть входные данные представлены строкой am
bn
, т.е. за а
, взятым т
раз, следует b
, взятое n
раз. Постарайтесь найти самое простое решение, насколько это возможно. Указание
: воспользуйтесь алгоритмом Е, но вместо деления на шаге El присвойте r
¬ | т
-
п
|, п
¬ min(m
, п
). Математические методы, используемые при анализе алгоритмов, имеют свои отличительные особенности. Например, нам довольно часто придется выполнять суммирование конечного числа рациональных чисел или решать рекуррентные уравнения. Подобные темы обычно очень поверхностно освещаются при чтении математических дисциплин, поэтому назначение следующих разделов – не только потренироваться в использовании обозначений, но и проиллюстрировать типы и методы вычислений, которые будут нам особенно необходимы. Пусть Р
(п
) – это некоторое утверждение, касающееся целого числа п
, например: «n
умножить на (n
+ 3) – четное число» или «если п
³ 10, то 2n
> n
3
». Предположим, нам нужно доказать, что утверждение Р(п) верно для всех положительных целых чисел п.
Существует важный метод доказательства этого факта, который состоит в следующем: (а) Доказать, что Р(1) верно. (b) Доказать, что «если Р
(1), Р
(2), ..., Р
(п
) справедливы, то Р
(п+
1) также справедливо»; это доказательство должно иметь силу для любого целого положительного числа п
. Пример 1-2
. Нечетные числа в сумме дают квадрат. В качестве примера рассмотрим следующие известные с древних времен равенства, которые многие исследователи открывали независимо друг от друга: 1 = 12
, 1 + 3 = 22
, 1 + 3 + 5 = 32
, (1.4) 1 + 3 + 5 + 7=42
, 1 + 3 + 5 + 7 + 9 = 52
. В общем виде эти равенства можно записать следующим образом: 1 + 3 + ××× + (2n
– 1) = n
2
. (1.5) Обозначим это утверждение как Р
(п
) и докажем, что оно верно для любого положительного n
. Согласно методу, описанному выше, имеем следующее. (а) «Р(1) верно, так как 1 = 12
» (b) «Если все утверждения Р(1), ..., Р(п
) справедливы, то, в частности, верно и Р(п
); следовательно, выполняется соотношение (1.5). Добавляя к обеим частям этого уравнения 2п
+ 1, получаем: 1 + 3 + ××× + (2п
- 1) + (2п
+ 1) = п
2
+ 2 п
+ 1 = (п
+ 1)2
. Таким образом, утверждение Р(п
+ 1) также справедливо». Этот метод можно считать алгоритмической процедурой доказательства.
В самом деле, следующий алгоритм дает доказательство утверждения Р(п
) для любого целого положительного п
в предположении, что этапы нашего доказательства (а) и (b) уже выполнены. Действие
I 1. Доказать Р(1). Присвоить k
¬ 1 и в соответствии с п. (а) выдать доказательство утверждения Р(1). Действие
I 2. k
= n
? Если k
=
n
, закончить выполнение алгоритма; требуемое доказательство выдано. Действие
I 3. Доказать P
(k
+
1). Согласно п. (b) выдать доказательство того, что «Если все утверждения Р
(1), ..., P
(k
) справедливы, то P
(k
+ 1) также справедливо». Вывести фразу «Мы уже доказали, что если утверждения Р
(1
), ..., P
(k
) верны, то верно и P
(k
+1)». Действие
I 4. Увеличить k
.
Увеличить k
на 1 и перейти к шагу I 2. ô
Поскольку этот алгоритм выдает доказательство утверждения Р
(п
) для любого заданного п,
метод доказательства, сформулированный в пп. (а) и (b), логически обоснован. Он называется доказательством методом математической индукции.
Понятие математической индукции следует отличать от того, что в научной практике обычно называют индуктивным методом. Данный метод заключается в том, что ученый делает некоторые наблюдения и создает «по индукции» общую теорию или выдвигает гипотезу, объясняющую эти факты. Например, на основании пяти соотношений (1.4), приведенных выше, мы могли бы сформулировать соотношение (1.5). В этом смысле индукция – не более чем догадка или попытка объяснить конкретную ситуацию; математики называют это эмпирическим результатом или предположением. Для того чтобы прояснить суть дела, рассмотрим еще один поучительный пример. Пусть р
(п
) обозначает количество разбиений
числа п
, т.е. количество различных способов записи числа п
в виде суммы целых положительных чисел (порядок слагаемых значения не имеет). Так как для числа 5 существует ровно семь таких способов записи, т.е. 1 + 1 + 1 + 1 + 1 = 2 + 1 + 1 + 1 = 2 + 2 + 1 = 3 + 1 + 1 = 3 + 2 = 4 + 1 = 5 , то р(5) = 7. На самом деле установить первые пять значений функции р
(п
) довольно легко: р
(1) = 1, р
(2) = 2, р
(3)=3, р
(4) = 5, р
(5) = 7. Замечание
. На этом основании мы могли бы предварительно сформулировать по индукции некорректное предположение о том, что последовательность р
(2), р
(3), ... пробегает множество простых чисел.
Для проверки данной гипотезы продолжаем вычисления и находим р(6) = 11. – Ура! – Это подтверждает наше предположение. Но, к сожалению, оказывается, что р
(7) равно 15. Увы, все идет насмарку, и приходится начинать сначала. Из математической литературы известно, что значения р
(n
) отличаются довольно сложным поведением. Математическая индукция не имеет ничего общего с тем индуктивным методом, который мы только что описали. «Индукцией» этот метод назван только потому, что сначала нужно выдвинуть предположение о том, что
нужно доказать, а затем
уже применять метод математической индукции. Начиная с этого момента, слово «индукция» будет использоваться только для обозначения доказательства методом математической индукции. Есть еще одно доказательство соотношения (1.5). На рис. 1.3 для п =
6 показано, что п
2
клеток разбиты на группы 1 + 3 + (2n
– 1) клеток. Но, в конечном счете, этот рисунок можно считать «доказательством» только в случае, если мы покажем, что данное построение можно выполнить для любого п
. А это, в сущности, и будет доказательством по индукции. Пример 1-3
. Числа Фибоначчи. Определим последовательность Фибоначчи
F
0
, F
1
, F
2
, ...
, F
2
с помощью такого правила: F
0
=
0, F
1
=
1, а каждый последующий член равен сумме двух предыдущих. Таким образом, первые члены этой последовательности выглядят так: 0, 1, 1, 2, 3, 5, 8, 13, ... . Далее введем обозначение: Докажем, что неравенство Если n
= 1, то F
1
=
1 = f0
= f n
– 1
, поэтому п. (а) выполнен. Переходя к п. (б), заметим сначала, что Р
(2) также справедливо, поскольку F
1
= 1 < 1.6 < f1
= f 2 – 1
.
А теперь, если все Р
(1), Р
(2), ..., Р
(п
) справедливы и п
> 1, то мы знаем, в частности, что справедливы Р
(п
– 1) и Р
(п
).
Поэтому
Важное свойство числа ф,
которое и является причиной первоочередного выбора этого числа для данной задачи, состоит в том, что 1 + f =
f2
. (1.8) Подставив (1.8) в (1.7), получим 1.4. Обобщенный алгоритм Евклида
Пример 1-4
. Математическую индукцию можно использовать также для доказательства фактов, касающихся алгоритмов.
Давайте рассмотрим следующее обобщение алгоритма Евклида. Алгоритм Е
(обобщенный алгоритм Евклида
).
Даны два целых положительных числа m
и b
. Требуется найти их наибольший общий делитель d
и два целых числа а
и b
, таких, что am
+
bn
= d
.
Действие
E l. Инициализация. Присвоить а
' ¬ b
¬ 1, а
¬ b
' ¬ 0, с
¬ т
, d
¬ n
. Действие
Е 2. Деление. Пусть q
и r
– это частное и остаток от деления с
на d
соответственно. Тогда с =
qd
+
r
, где 0 £ r
<
d
. Действие
Е З. Остаток – это нуль? Если r
= 0, то выполнение алгоритма прекращается; в этом случае имеем am
+
bn
=
d
, как и требовалось. Действие
Е 4. Повторение цикла. Присвоить с
¬ d
, d
¬ r
, t
¬ а
', а
' ¬ а
, а
¬ (t
– qa
), t
¬ b
'
, b
'
¬ b
, b
¬ (t
– qb
) и вернуться к шагу Е2. Если изъять из алгоритма переменные а
, b
, а
' и b
'
и использовать m
и n
в качестве вспомогательных переменных с
и d
, то получим старый алгоритм Е (см. параграф 1.1). В новой версии алгоритма выполняется немного больше вычислений, так как необходимо определить коэффициенты a
и b
. Предположим, что m
= 1769 и n
= 551. Тогда последовательно (после шага Е 2) имеем: а
' a
b
' b
c
d
q
r
1 0 0 1 1769 551 3 116 0 1 1 – 3 551 116 4 87 1 – 4 – 3 13 116 87 1 29 – 4 5 13 – 16 87 29 3 0 Проверяя полученные результаты, убеждаемся в том, что все правильно, так как 5 ´ 1769 - 16 ´ 551 = 8845 - 8816 = 29, т.е. мы получили наибольший общий делитель чисел 1769 и 551. Теперь нужно доказать, что рассматриваемый алгоритм работает правильно при любых т
и п. Для этого попробуем применить метод математической индукции к следующему утверждению Р
(п
): «Алгоритм Е дает правильное решение для заданного n
и всех целых m
». Но провести подобное доказательство не так-то просто, поэтому нужно доказать сначала несколько дополнительных фактов. После некоторого изучения проблемы выясняется, что нужно доказать какой-то факт, связанный с коэффициентами а
, b
, а
' и b
'.
Этот факт заключается в том, что равенства а'т +
b
'п = с
, am
+
bn
=
d
(1.9) верны в каждом случае выполнения шага Е2. Данные равенства можно доказать непосредственно, заметив, что они безусловно справедливы после первого выполнения шага Е2, и что шаг Е4 не меняет это положение вещей (см. упражнение 1.17). Теперь мы готовы индукцией по п
доказать, что алгоритм Е работает правильно. Если т
кратно п
, то очевидно, что алгоритм работает правильно, поскольку его работа заканчивается на шаге ЕЗ в первом же цикле и мы получаем верный результат. Это происходит всегда, когда n
= 1. Поэтому остается провести доказательство для случая, когда п >
1 и т
не является кратным п
. В такой ситуации в первом цикле осуществляется переход к шагу Е4 и выполняются операции присвоения с
¬ п
, d
¬ r
. И так как r
< п
, по индукции можно предположить,
что окончательное значение d
– наибольший общий делитель чисел п
и r
. Из доказательства, приведенного в параграфе 1.2. следует, что пары {т
,п
} и {п
,r
} имеют одинаковые наибольшие общие делители и, в частности, один и тот же наибольший общий делитель. Значит, d
– это наибольший общий делитель чисел m
и n
и согласно (1.9) am
+
bn
=
d
.
Фраза, которая в приведенном выше доказательстве выделена курсивом, является иллюстрацией того общепринятого условного языка, который так часто используется в доказательствах методом индукции. Например, выполняя п. (b), вместо того чтобы сказать «Теперь предположим, что утверждения Р
(1), Р
(2), ..., Р
(п
) справедливы, и на этом основании докажем справедливость утверждения Р
(п +
1)», мы будем говорить просто «Теперь докажем утверждение Р
(п
); по индукции мы можем предположить,
что P
(k
) верно для любого 1 £ k
<
n
» . Если хорошо вдуматься и посмотреть на все вышесказанное с несколько иной точки зрения, то перед нами предстанет общий метод доказательства корректности любого
алгоритма. Идея состоит в том, чтобы взять блок-схему некоторого алгоритма и к каждой стрелке добавить примечание о текущем состоянии дел в тот момент, который соответствует стрелке. На рис. 1.4 эти примечания (мы их будем называть также утверждениями) обозначены через A
l, A
2, ..., А
6.
В утверждении А
1 даются первоначальные предположения о входных данных алгоритма, а в А
4 формулируется положение о том, что мы хотим доказать по поводу выходных значений а
, b
и d
.
Если доказать утверждение
(1.10) для каждого блока, то все примечания к стрелкам будут верны в любом случае выполнения алгоритма.
Теперь мы можем применить индукцию по числу шагов, т. е. по числу стрелок в блок-схеме. При прохождении первой стрелки (той, которая выходит из блока «Начало») утверждение А
1 верно, поскольку мы всегда исходим из предположения, что входные значения удовлетворяют заданным условиям. Таким образом, утверждение, которое соответствует первой стрелке, верно. Если утверждение, которое соответствует n
-й стрелке, верно, то согласно (1.10) утверждение, которое соответствует (n
+ 1)-й стрелке, тоже верно. Исходя из этого общего метода доказательство правильности заданного алгоритма, очевидно, сводится к нахождению правильных утверждений, соответствующих стрелкам блок-схемы. Как только данное начальное препятствие будет преодолено, останется лишь рутинная работа, связанная с доказательством того, что каждое утверждение на входе в блок влечет за собой утверждение на выходе из блока. В действительности после того как вы придумаете самые трудные из этих утверждений, найти все остальные уже не составит труда. Скажем, если даны утверждения А
1, А
4 и А
6, уже понятно, какими должны быть утверждения А
2, А
З и А
5.
В нашем примере самых больших творческих усилий потребует доказательство утверждения А
6; все остальное, в принципе, должно получиться автоматически. Этот подход к доказательству корректности алгоритма имеет и другой, еще более важный аспект: он отражает способ нашего понимания алгоритма.
Нужно проверять работу алгоритма на примере одного-двух наборов входных данных. И это не случайно, так как пробная «прогонка» алгоритма поможет вам мысленно сформулировать утверждения, соответствующие стрелкам на блок-схеме. Уверенность в корректности алгоритма приходит только тогда, когда мысленно сформулированы все утверждения, приведенные на рис. 1.4. Отсюда следуют важные психологические выводы, касающиеся передачи алгоритма от одного лица к другому. Речь идет о том, что, объясняя алгоритм кому-либо другому, всегда следует явно формулировать основные утверждения, которые трудно получить автоматически. Например, в случае алгоритма Е нужно обязательно упомянуть утверждение А
6.
Но бдительный читатель, конечно, заметил явный недостаток
в нашем последнем доказательстве алгоритма Е. Из доказательства нигде не следует, что алгоритм обладает свойством конечности, т.е. рано или поздно его выполнение завершится. Мы доказали только, что если
алгоритм конечен, то он дает правильный результат! (Например, заметим, что алгоритм Е по-прежнему имеет смысл, если его переменные m
, n
, с
, d
и r
принимают значения типа
где параметры и
и v
– целые числа*
. Переменные q
, а
, b
, а
', b
' должны по-прежнему принимать целые значения. Если, например, на вход подать значения Доказательства конечности алгоритмов обычно проводят отдельно. Но в упражнении 1.16 показано, что во многих важных случаях приведенный выше метод можно
обобщить таким образом, чтобы включить доказательство конечности в виде промежуточного результата. Итак, мы уже дважды доказали правильность алгоритма Е. Чтобы быть последовательными до конца, нам следовало бы попытаться доказать, что первый алгоритм в этом разделе, а именно – алгоритм I, также корректен. Ведь, в сущности, мы использовали алгоритм I, чтобы показать корректность любого доказательства по индукции. Но если мы попытаемся доказать,
что алгоритм I работает правильно, то попадем в затруднительное положение: мы не сможем сделать это, не воспользовавшись снова индукцией! Итак, получается замкнутый круг. В последнее время любое
свойство целых чисел принято доказывать с помощью индукции в ту или иную сторону. Ведь если мы обратимся к основным понятиям, то увидим, что целые числа, в сущности, определяются
по индукции. Поэтому можно принять в качестве аксиомы утверждение о том, что любое целое положительное число n
либо равно 1, либо может быть получено, если взять 1 за исходное значение и последовательно прибавлять по единице. Этого достаточно, чтобы доказать правильность алгоритма I. Упражнение 1.8
. Объясните, как можно модифицировать идею доказательства методом математической индукции в случае, если некоторое утверждение Р
(п
) нужно доказать для всех неотрицательных
целых чисел, т.е. для n
= 0, 1, 2, ... , а не для n
= 1, 2, 3, ... . Упражнение 1.9
. Найдите ошибку в следующем доказательстве. «Теорема
. Пусть a
– любое положительное число. Для всех целых положительных чисел п
имеем Доказательство.
Если п =
1, то
следовательно, теорема верна также для n
+ 1.» Упражнение 1.9
. Следующее доказательство по индукции выглядит корректным, но по непонятной причине для п
= 6 левая часть уравнения дает
Доказательство.
Используем индукцию по п.
Для п
= 1 доказательство очевидно: 3/2 – 1/п
= 1/(1 ´ 2). Предполагая, что теорема верна для п
, имеем:
Упражнение 1.10
. Докажите, что числа Фибоначчи удовлетворяют не только соотношению (1.6), но и неравенству Упражнение 1.11
. Простое число
– это целое число, большее единицы, которое делится только на 1 и на само себя. Используя данное определение и метод математической индукции, докажите, что любое целое число, большее единицы, можно записать как произведение одного или нескольких простых чисел. (Для удобства будем считать, что простое число – это «произведение» одного простого числа, т.е. его самого.) Упражнение 1.12
. Докажите по индукции, что если 0 < a
< 1, то Упражнение 1.13
. Докажите по индукции, что если п >
10, то Упражнение 1.14
. Найдите и докажите простую формулу для следующей суммы:
Упражнение 1.15
. Покажите, как можно обобщить алгоритм Е, чтобы, как было указано в тексте, для него допускались входные значения вида Упражнение 1.16
. Обобщите алгоритм Е, введя новую переменную Т
и добавив в начале каждого шага операцию Т
¬ Т+
1. (Таким образом, переменная Т
– это счетчик выполненных шагов.) Предположим, что первоначальное значение Т
равно нулю, поэтому утверждение А
1 на рис. 1.4 примет вид m
> 0, n
> 0, Т =
0. Аналогично к А
2 следует добавить дополнительное условие Т =
1. Покажите, как добавить к утверждениям дополнительные условия таким образом, чтобы из любого утверждения А
1, А
2, ..., А
6 следовало, что Т
< 3n
, и чтобы можно было провести доказательство по индукции. (Следовательно, вычисления должны закончиться максимум через 3n
шагов.) Упражнение 1.17
. Докажите, что если соотношения (1.9) справедливы непосредственно перед выполнением шага Е4, то они верны и после его выполнения. Давайте начнем с быстрого введения в язык «C». Наша цель – продемонстрировать существенные элементы языка на реальных программах, не увязая при этом в деталях, формальных правилах и исключениях. В этой главе мы не пытаемся изложить язык полностью или хотя бы строго (разумеется, приводимые примеры будут корректными). Мы хотим как можно скорее довести вас до такого уровня, на котором вы были бы в состоянии писать полезные программы, и чтобы добиться этого, мы сосредотачиваемся на основном: переменных и константах, арифметике, операторах передачи управления, функциях и элементарных сведениях о вводе и выводе. Мы совершенно намеренно оставляем за пределами этой главы многие элементы языка «C», которые имеют первостепенное значение при написании больших программ, в том числе указатели, структуры, большую часть из богатого набора операторов языка «C», несколько операторов передачи управления и несметное количество деталей. Такой подход имеет, конечно, свои недостатки. Самым существенным является то, что полное описание любого конкретного элемента языка не излагается в одном месте, а пояснения, в силу краткости, могут привести к неправильному истолкованию. Кроме того, из-за невозможности использовать всю мощь языка, примеры оказываются не столь краткими и элегантными, как они могли бы быть. И хотя мы старались свести эти недостатки к минимуму, все же имейте их в виду. Другой недостаток состоит в том, что последующие главы будут неизбежно повторять некоторые части этой главы. Мы надеемся, что такое повторение будет скорее помогать, чем раздражать. Во всяком случае, опытные программисты должны оказаться в состоянии проэкстраполировать материал данной главы на свои собственные программистские нужды. Начинающие же должны в дополнение писать аналогичные маленькие самостоятельные программы. И те, и другие могут использовать эту главу как каркас, на который будут навешиваться более подробные описания, начинающиеся с главы 3. Единственный способ освоить новый язык программирования – писать на нем программы. Первая программа, которая должна быть написана, – одна для всех языков: напечатать слова: «Здравствуй, Мир!». Это – самый существенный барьер; чтобы преодолеть его, вы должны суметь завести где-то текст программы, успешно его скомпилировать, загрузить, прогнать и найти, где оказалась ваша выдача. Если вы научились справляться с этими техническими деталями, все остальное сравнительно просто. Пример 2-1
. Программа печати «Здравствуй, Мир !» на языке «C» имеет вид: main() { printf("Здравствуй, Мир !\n"); } Как пропустить эту программу, зависит от используемой вами системы. Чаще всего первые опыты с «C» осуществляют в одной из двух операционных систем: Unix
или Windows
XP
. 1. В операционной системе Unix
вы должны завести исходную программу в файле, имя которого оканчивается суффиксом «.с» , например, Hello.c , и затем скомпилировать ее по команде cc Hello.c . Если вы не допустили какой-либо небрежности, такой как пропуск символа или неправильное написание, компиляция пройдет без сообщений и будет создан исполняемый файл с именем а.out . Прогон его по команде а.out приведет к выводу слов «Здравствуй, Мир !». – Это самый примитивный способ создания выполняемой программы в Unix
. Замечание
: на самом деле Unix
не всегда поддерживает национальные алфавиты в консольном режиме, в т.ч. «кириллицу». Поэтому можно увидеть вместо фразы на русском языке какие-то символы и значки, не имеющие смысла. 2. В операционной системе Windows
XP
будем использовать оболочку Visual Studio
и среду программирования Visual
C++. Предположим, что вы хотите на диске c:\ в папке Консоль01 создать проект Test01, в рамках которого будет работать наша программа, причем нужно обеспечить внешнее сходство с операционной системой Unix
. В папке c:\Консоль01\ создадим файл Hello.cpp, причем суффикс «.сpp» говорит о том, что мы работаем в среде C++. Далее в основном меню Visual Studio
создадим новый проект в режиме «Консольное приложение» (рис. 1.1.). Этот режим соответствует рассмотренному способу создания программы в операционной системе Unix
: File ® New ® Project ® Win32 ® Console Application . Проект Test01 расположим (Location) расположим в той же папке c:\Консоль01\ . После этого автоматически будет создана вложенная папка Test01 и более вложенная – папка Debug. Далее нужно выйти в режим просмотра файлов (File View) и включить в проект (Add Files to Folder) единственный файл Hello.cpp. После этого структура проекта примет вид, показанный на рис 2.1. Через главное меню нужно выполнить компиляцию и сборку выполняемой программы Test01.exe: Build ® Rebuild All .
Эта программа появится в папке c:\Консоль01\Test01\Debug. Далее нужно войти в эту папку, используя Проводник
, и выполнить программу Test01.exe с помощью команды Test01.exe > a.txt . Результат можно посмотреть помощью Блокнота
Notepad
операционной системы Windows
(рис. 2.2.) или стандартного редактора Visual Studio
в файле a.txt. Замечание
: в других системах соответствующие правила будут иными. Проконсультируйтесь с местным «авторитетом». Упражнение 2-1.
Пропустите эту программу на вашей системе. Попробуйте не включать различные части программы и посмотрите какие сообщения об ошибках вы при этом получите. Теперь некоторые пояснения к самой программе. Любая «C»-программа, каков бы ни был ее размер, состоит из одной или более «функций», указывающих фактические операции компьютера, которые должны быть выполнены. Функции в языке «C» подобны функциям и подпрограммам ФОРТРАНА и процедурам PL/1, ПАСКАЛЯ и т.д. В нашем примере такой функцией является main. Обычно вы можете давать функциям любые имена по вашему усмотрению, но main – это особое имя; выполнение вашей программы начинается сначала с функции main. Это означает, что каждая программа должна в каком-то месте содержать функцию с именем main. Для выполнения определенных действий функция main обычно обращается к другим функциям, часть из которых находится в той же самой программе, а часть – в библиотеках, содержащих ранее написанные функции. Одним способом обмена данными между функциями является передача посредством аргументов. Круглые скобки, следующие за именем функции, заключают в себе список аргументов; здесь main – функция без аргументов, что указывается как ( ). Операторы, составляющие функцию, заключаются в фигурные скобки { }, которые аналогичны DO-END в PL/1 или BEGIN-END в АЛГОЛЕ, ПАСКАЛЕ и т.д. Обращение к функции осуществляется указанием ее имени, за которым следует заключенный в круглые скобки список аргументов. здесь нет никаких операторов CALL, как в ФОРТРАНЕ или PL/1. Круглые скобки должны присутствовать и в том случае, когда функция не имеет аргументов. Строка printf("Здравствуй, Мир !\n"); является обращением к функции, которое вызывает функцию с именем printf и аргуметом ("Здравствуй, Мир !\n". Функция printf является библиотечной функцией, которая выдает выходные данные на терминал (если только не указано какое-то другое место назначения). В данном случае печатается строка символов, являющаяся аргументом функции. Последовательность из любого количества символов, заключенных в удвоенные кавычки "...", называется «символьной строкой» или «строчной константой». Пока мы будем использовать символьные строки только в качестве аргументов для printf и других функций. Последовательность \n в приведенной строке является обозначением на языке «C» для «символа новой строки», который служит указанием для перехода на терминале к левому краю следующей строки. Если вы не включите \n (полезный эксперимент), то обнаружите, что ваша выдача не закончится переходом терминала на новую строку. Использование последовательности \n – единственный способ введения символа новой строки в аргумент функции printf; если вы попробуете что-нибудь вроде printf("Здравствуй, Мир !\n "); то «C»-компилятор будет печатать злорадные диагностические сообщения о недостающих кавычках. Функция printf не обеспечивает автоматического перехода на новую строку, так что многократное обращение к ней можно использовать для поэтапной сборки выходной строки. Наша первая программа, печатающая идентичную выдачу, с точно таким же успехом могла бы быть написана в виде main() { printf("Здравствуй, "); printf("Мир !"); printf("\n"); } Подчеркнем, что \n представляет только один символ. Условные (или «эскайп») последовательности, подобные \n , дают общий и допускающий расширение механизм для представления трудных для печати или невидимых символов. Среди прочих символов в языке «C» предусмотрены следующие: \t – для табуляции, \b – для возврата на одну позицию (символ «забоя»), \" – для двойной кавычки, \\ – для самой обратной косой черты. Упражнение 2-2
. Проведите эксперименты для того, чтобы узнать что произойдет, если в строке, являющейся аргументом функции printf, будет содержаться \x, где x – некоторый символ, не входящий в вышеприведенный список. Пример 2-2
. Следующая программа печатает приведенную ниже таблицу температур по Фаренгейту и их эквивалентов по стоградусной шкале Цельсия, используя для перевода формулу
Шкала по Фаренгейту Стоградусная шкала Цельсия 0 -17,8 20 -6,7 40 4,4 60 15,6 …
…
260 126,7 280 137,8 300 140,9 Теперь сама программа: // Напечатать таблицу Фаренгейт-Цельсий main() { int lower, upper, step; float fahr, celsius; lower = 0; // Нижний предел таблицы upper = 300; // Верхний предел таблицы step = 20; // Размер шага fahr = lower; while (fahr <= upper) { celsius = (5.0/9.0) * (fahr -32.0); printf("%4.0f %6.1f\n", fahr, celsius); fahr = fahr + step; } } Первая строка // Напечатать таблицу Фаренгейт-Цельсий является комментарием, который в данном случае кратко поясняет, что делает программа. Любые символы, начинающиеся с // в пределах строки программы, игнорируются компилятором; можно свободно пользоваться комментариями для облегчения понимания программы. Комментарии могут появляться в любом месте, где возможен пробел или переход на новую строку. В языке «C» все переменные должны быть описаны до их использования, обычно это делается в начале функции до первого выполняемого оператора. Если вы забудете вставить описание, то получите диагностическое сообщение от компилятора. Описание состоит из типа и списка переменных, имеющих этот тип, как в: int lower, upper, step; float fahr, celsius; Тип int означает, что все переменные списка целые; тип float предназначен для чисел с плавающей точкой, т.е. для чисел, которые могут иметь дробную часть. Точность как int, так и float зависит от конкретной машины, на которой вы работаете. На PDP-11, например, тип int соответствует 16-битовому числу со знаком, т.е. числу, лежащему между -32768 и +32767. Число типа float – это 32-битовое число, имеющее около семи значащих цифр и лежащее в диапазоне от 1.0е–38 до 1.0е+38. В главе 3 приводится список размеров для других машин. В языке «C» предусмотрено несколько других основных типов данных, кроме int и float: · char символ (один байт); · short короткое целое; · long длинное целое; · double плавающее с двойной точностью. Размеры этих объектов тоже машинно-независимы; детали приведены в главе 3. Имеются также массивы, структуры и объединения этих основных типов, указатели на них и функции, которые их возвращают; со всеми ними мы встретимся в свое время. Фактически вычисления в программе перевода температур начинаются с операторов присваивания: lower = 0; upper = 300; step = 20; fahr = lower; которые придают переменным их начальные значения. каждый отдельный оператор заканчивается точкой с запятой. Каждая строка таблицы вычисляется одинаковым образом, так что мы используем цикл, повторяющийся один раз на строку. В этом назначение оператора while: while (fahr <= upper) { ... // Тело оператора while } проверяется условие в круглых скобках. Если оно истинно (fahr меньше или равно upper), то выполняется тело цикла – все операторы, заключенные в фигурные скобки { }. Затем вновь проверяется это условие и, если оно истинно, опять выполняется тело цикла. Если же условие не выполняется (fahr превосходит upper ), цикл заканчивается и происходит переход к выполнению оператора, следующего за оператором цикла. Так как в настоящей программе нет никаких последующих операторов, то выполнение программы завершается. Тело оператора while может состоять из одного или более операторов, заключенных в фигурные скобки, как в программе перевода температур, или из одного оператора без скобок, как, например, в while (i < j)
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||