А.В. Романенко, А.И. Попов ОСНОВЫ ПРОГРАММИРОВАНИЯ ДЛЯ АВТОМАТИЗИРОВАННОГО ПРОЕКТИРОВАНИЯ И РЕШЕНИЯ ТВОРЧЕСКИХ ЗАДАЧ • ИЗДАТЕЛЬСТВО ТГТУ • (075) ББК Í973-018я73 Р69 Р е ц е н з е н т ы: Доцент МГТУ им. Баумана В.А. Мартынюк Директор института информационных технологий и коммуникаций Астраханского государственного технического университета О.М. Проталинский Профессор, доктор физико-математических наук С.М. Дзюба Р69 Романенко, А.В. Основы программирования для автоматизированного проектирования и решения творческих задач : учеб. пособие / А.В. Романенко, А.И. Попов. – Тамбов : Изд-во Тамб. гос. техн. ун-та, 2007. – 96 с. – 150 экз. – (9 -0595-3). Рассмотрены теоретические вопросы программирования на одном из широко распространенных языков – языке С. Приведены приемы и алгоритмы для обработки данных различных типов. Даны задания для самостоятельной подготовки и рассмотрены примеры решения задач повышенной сложности. Предназначено для подготовки студентов по дисциплинам, связанным с программированием, может быть использовано профессорско-преподавательским составом и инженерно-педагогическими работниками. (075) ББК Í973-018я73  ГОУ ВПО "Тамбовский государственный (9 -0595-3) технический университет" (ТГТУ), 2007 Министерство образования и науки Российской Федерации ГОУ ВПО "Тамбовский государственный технический университет" А.В. РОМАНЕНКО, А.И. ПОПОВ ОСНОВЫ ПРОГРАММИРОВАНИЯ ДЛЯ АВТОМАТИЗИРОВАННОГО ПРОЕКТИРОВАНИЯ И РЕШЕНИЯ ТВОРЧЕСКИХ ЗАДАЧ Допущено Учебно-методическим объединением вузов по университетскому политехническому образованию в качестве учебного пособия для студентов высших учебных заведений, обучающихся по направлению 230100 "Информатика и вычислительная техника", специальности 230104 "Автоматизированные системы проектирвоания" Тамбов Издательство ТГТУ Учебное издание РОМАНЕНКО Александр Васильевич ПОПОВ Андрей Иванович ОСНОВЫ ПРОГРАММИРОВАНИЯ ДЛЯ АВТОМАТИЗИРОВАННОГО ПРОЕКТИРОВАНИЯ И РЕШЕНИЯ ТВОРЧЕСКИХ ЗАДАЧ Учебное пособие Редактор З.Г. Ч е р н о в а Инженер по компьютерному макетированию М.Н. Р ы ж к о в а Формат 60 × 84/16. 5,58 усл. печ. л. экз. Заказ № 343 Издательско-полиграфический центр Тамбовского государственного технического университета 392000, Тамбов, Советская, 106, к. 14 ВВЕДЕНИЕ Современные техника и многие технологии немыслимы без использования вычислительной техники. Специализированные ЭВМ и компьютеры общего назначения находят широкое применение практически во всех направлениях человеческой деятельности. Одним из таких направлений является разработка новых технических устройств и систем, в процессе создания которых широко применяется человеко-машинный комплекс, называемый системой автоматизированного проектирования (САПР). Однако, сами САПР являются сложными системами обработки информации, для создания и эксплуатации которых необходимо присутствие грамотных специалистов в этой области. В настоящее время для создания программных комплексов различной сложности часто используется язык программирования С. Язык С задумывался как язык программирования "среднего" уровня вследствие наличия некоторых особенностей, целью которых было предоставление программисту удобного инструментального языка, заменяющего язык ассемблера и обеспечивающего легкий доступ к аппаратным средствам ЭВМ. Он был разработан в первой половине 70-х годов XX века сотрудниками фирмы Bell Laboratories Д. Ритчи и Б. Керниганом. Популяризации языка С способствовало написание на этом языке текстов операционной системы Unix. В результате ОС Unix получила максимальную переносимость на разные типы ЭВМ, что способствовало приобретению ею огромной популярности, а язык С стал ее базовым языком программирования. Распространению языка долгое время препятствовало отсутствие полного и однозначного его описания. Вследствие этого в 1983 году в Американском Национальном Институте Стандартов (ANSI) был образован комитет по стандартизации языка С и в 1989 году стандарт на язык программирования С был утвержден и началось беспрепятственное распространение языка С в программистской среде. Данное учебное пособие предназначено для выработки у студентов навыков программирования задач различной сложности с помощью одного из широко распространенных языков программирования – языка С. Компоненты языка С в пособии выделены жирным шрифтом, а фрагменты, на которые следует обратить внимание – курсивом. Во второй части пособия приведены практические задания, которые будут полезны для самостоятельного закрепления изучаемого материала. Часть I ОСНОВЫ ЯЗЫКА С Любой язык программирования образуют три составляющие части: алфавит, синтаксис и семантика. Алфавит – фиксированный для данного языка набор основных символов, из которых должен состоять любой текст на этом языке. Никакие другие символы для записи текстов не допускаются. Синтаксис – система правил, определяющих допустимые конструкции из букв алфавита. С помощью этих конструкций представляются отдельные компоненты алгоритма и алгоритм в целом, записанные на данном языке программирования. Семантика – это система правил истолкования отдельных языковых конструкций, позволяющих однозначно воспроизвести процесс обработки данных по заданной программе. Выделяют основные понятия языков программирования. Операторы. Понятие оператора является ключевым для любого языка программирования. Оператор представляет собой законченную фразу языка, содержащую полностью оформленный этап обработки информации. Операторы разделяют на две группы: основные (не содержащие других операторов) и производные (составные). В алгоритмических языках операторы обычно отделяют друг от друга точкой с запятой. Идентификаторы. В процессе обработки информации, алгоритму необходимо различать программные объекты. Для обозначения имен переменных, их свойств и атрибутов используются идентификаторы. Идентификатор представляет собой сочетание букв и цифр, которое начинается с буквы и не превышает заданной для языка программирования длины. В любом языке программирования существуют стандартные идентификаторы, произвольное использование которых запрещено. Переменные. Переменные представляют собой объекты, способные принимать различные значения. Они обладают следующими свойствами: в один момент времени переменная хранит не более одного значения; переменная имеет постоянный тип; переменная хранит текущее значение до записи в нее нового значения; в начале выполнения программы значение переменных считается неопределенными. 1 АЛФАВИТ И ИДЕНТИФИКАТОРЫ ЯЗЫКА С Алфавит языка С включает следующие символы: • латинские буквы строчные и прописные; • цифры от 0 до 9; • специальные знаки: " { } , | [ ] ( ) + – / % \ ; ' : ? < = > _ ! & # ~ ^ *. Из символов алфавита формируются лексемы языка: идентификаторы, ключевые слова, константы, знаки операций, разделители. В качестве идентификаторов в языке С допускаются любые сочетания символов, начинающиеся с буквы. Длина идентификатора не должна превышать тридцать два символа. Буквы верхнего и нижнего регистров считаются различными. Запрещено использование идентификаторов, совпадающих с ключевыми словами. Ключевыми словами считаются идентификаторы, имеющие специальное значение для компиляторов языка С, их использование ограничено предопределенным смыслом. 1 Ключевые слова языка С auto const double float short struct unsigned break continue else long signed switch void case default enum register sizeof typedef volatile char extern return static union while Помимо этого некоторые компиляторы языка С считают ключевыми слова cdecl, far, huge, near, interrupt. Текст, заключенный между знаками /*…*/ или стоящий в строке после знаков //, считается комментарием. 2 ТИПЫ ДАННЫХ В ЯЗЫКЕ С Типы данных служат для описания переменных. Имени переменной соответствует адрес участка памяти, выделенного для хранения значения переменной, а длина этого участка определяется выбранным типом данных. Тип переменной помимо этого определяет множество допустимых значений, которые может хранить переменная, а также набор операций, для которых переменная может служить операндом. Множество допустимых значений обычно совпадает с множеством допустимых констант того же типа. Существуют символьные, целочисленные и вещественные переменные. Причем, символьные переменные в языке С могут рассматриваться как целочисленные. Переменные типизируются на основе определений и описаний. Определение, в отличие от описания, не только вводит программный объект, но и дает указание компилятору выделить участок памяти для его размещения в памяти ЭВМ. Для определений и описаний переменных используются следующие ключевые слова: char, short, int, long, float, double. Помимо этого как отдельно, так и с другими ключевыми словами могут использоваться слова signed и unsigned. Они обозначают знаковый или беззнаковый вид хранения целого числа. 2 Простые типы данных языка С Тип Размер, бит Диапазон значений char -128...127 unsigned char 0...255 enum -32768...32767 short -32768...32767 unsigned short 0...65535 int -32768...32767 unsigned int 0...65535 long -2147483648...2147483647 unsigned long 0...4294967295 float 3.4e-38...3.4e+38 double 1.7е-308...1.7е+308 long double Особенностью типа int является то, что его длина в байтах соответствует ширине шины данных компьютера, для которого разработан используемый компилятор. Типы данных float, double и long double считаются неупорядоченными. Для описания типа возвращаемого функцией значения может быть использовано ключевое слово void, обозначающее отсутствие результата. В этом случае функция ничего не возвращает. 3 КОНСТАНТЫ В ЯЗЫКЕ С Константа представляет собой языковую конструкцию, обозначающую изображение фиксированного числового, строкового или символьного значения. Они разделены на пять групп: целые, вещественные, перечислимые, символьные, строковые. Перечислимые константы обычно относятся к целочисленному типу данных. Целая константа может быть десятичной, восьмеричной или шестнадцатеричной. Десятичная константа представляет собой набор десятичных цифр, начинающийся с цифры, отличной от нуля, если это не ноль. Отрицательные константы представляют собой константы без знака, к которым применена операция изменения знака. Восьмеричные константы всегда начинаются с нуля. В их записи недопустимо использование цифр 8 и 9. Шестнадцатеричная константа начинается с сочетания '0х'. В ее состав могут входить цифры от 0 до 9 и буквы латинского алфавита от A до F (обозначающие числа от 10 до 15). По умолчанию целочисленные константы относятся к типу int. Можно явным образом повлиять на выбор типа данных для константы. Для этого служат суффиксы L, U и UL. Суффикс L – соответствует типу long, U – типу unsigned int, UL определяет тип unsigned long. Вещественная константа имеет другую форму представления, использующую арифметику с плавающей точкой. Константа с плавающей точкой может иметь семь частей: знак, целая часть, десятичная точка, дробная часть, признак экспоненты е или Е, показатель десятичной степени, суффикс L или F. При отсутствии суффиксов вещественная константа относится к типу double. Суффикс F относит константу к типу float, а суффикс L – к типу long double. Перечислимые константы вводятся с помощью служебного слова enum. По существу это обычные целочисленные константы, которым приписаны уникальные идентификаторы, не совпадающие с другими программными объектами и служебными словами. Каждой такой константе присваивается целочисленное значение. Первому идентификатору в списке присваивается значение нуля, а значение каждого следующего увеличивается на единицу. П р и м е р 1 enum {zero, one, two, three}; Это правило действует и в том случае, когда идентификаторам явно присвоены значения (enum{ten = 10, three = 3, four, five}). Имена констант должны быть уникальными, однако к значениям констант это не относится, одно значение могут иметь несколько констант. Значения перечислимых констант могут быть заданы выражениями (enum {two = 2, four = two * 2}). Для перечислимых констант может быть введено имя соответствующего типа. П р и м е р 2 enum tip {two = 2, tree = 3}; Строка представляет собой последовательность символов, заключенных в кавычки. Размещая строку в памяти, компилятор автоматически добавляет в ее конец нулевой код ('\0'). Символьные константы представляют собой один или два символа, заключенные в апострофы. Односимвольные константы относятся к стандартному типу char. Запись кодов и символов ', \, ?, " должна начинаться с символа '\'. Последовательности, начинающиеся с символа '\', называются Esc-последовательностями. 3 Esc-последовательности Null Bell(звонок) Возврат на шаг Перевод страницы Перевод строки Возврат каретки Табуляция горизонтальная \000 \xhh Табуляция вертикальная Обратный слэш Апостроф Двойная кавычка Знак вопроса Восмиричный код Шестнадцатиричный код 4 ЗНАКИ ОПЕРАЦИЙ Знаки операций обеспечивают формирование и последующее вычисление выражений. Один и тот же знак операции может употребляться в различных выражениях и по-разному восприниматься компилятором в зависимости от ситуации. Все знаки операций по количеству операндов делят на унарные, бинарные и трехразрядные. Бинарные операции бывают следующих видов: аддитивные, мультипликативные, сдвигов, поразрядные, операции отношений, логические, присваивания, адресной арифметики, операция "запятая". Унарные операции (операции с одним операндом): -/+ получение адреса операнда; обращение по адресу (операндом должен быть адрес); унарные операции изменения знака операнда ('+' – сделать операнд положительным); поразрядное инвертирование внутреннего кода скалярного операнда; логическое отрицание значения операнда (применяется к операндам скалярных типов), результат – 0 (если операнд отличен от нуля) и 1 (если операнд равен нулю); в качестве логических значений в языке С используются целые числа: 0 – ложь, ≠0 – истина; увеличение скалярного операнда на 1 (инкремент); пре- фиксная операция – увеличение значения операнда до его использования, постфиксная операция – увеличение операнда после его использования; операнд не может быть константой; -уменьшение скалярного операнда на 1 (декремент); правила оформления аналогичны инкременту; Sizeof вычисление размера в байтах для объекта того типа, кото(операнд) рый имеет операнд; (тип) операнд операция явного преобразования типа операнда. Бинарные операции: Аддитивные операции: арифметическое сложение операндов; арифметическое вычитание операндов. Мультипликативные операции: умножение операндов; деление операндов; для целочисленных операндов возвра/ щается только целая часть от результата деления; получение остатка от деления целочисленных операндов. Операции сдвига: сдвиг влево битового представления значения левого цело<< численного операнда на количество разрядов, равное значению правого целочисленного операнда; сдвиг вправо (аналогично). Поразрядные операции: поразрядная конъюнкция битовых представлений значений целочисленных операндов; поразрядная дизъюнкция битовых представлений значений целочисленных операндов; поразрядное "исключающее или" битовых представлений значений целочисленных операндов. Операции отношения: <, >, <=, >=, == (равно), != (не равно). Логические бинарные операции: конъюнкция арифметических операндов или отношений; дизъюнкция арифметических операндов или отношений. Операции присваивания: =, *=, /=, %=, +=, -=, <<=, >>=,&=, |=, ^=. Операции адресной арифметики: играет роль операции адресной арифметики при прямом выборе компонента структурного объекта; косвенный выбор компонента структурного объекта; играет роль операции адресной арифметики при индексировании элементов массива; играет роль операции адресной арифметики при вызове функций. В некоторых случаях в качестве знака операции может выступать запятая: несколько выражений, разделенных запятыми, будут вычисляться последовательно слева направо. Условная (трехразрядная) операция: операнд1 ? операнд2 : операнд3 – если значение операнда1 истинно, то результат – операнд2, иначе – операнд3. Для того, чтобы получить возможность однозначно вычислять результат при объединении в сложную операцию множества простых операций, введено понятие приоритета выполнения операций. Приоритет операции объясняет порядок ее выполнения в составе некоего выражения. 4 Приоритеты выполнения операций Уровень приоритета Операции Порядок выполнения [ ] . -> ( ) & * + – ++ -- sizeof() (тип) * / % (мультипликативные) + – (аддитивные) << >> < <= > >= == != ? : (условная операция) операция присваивания 5 РАЗДЕЛИТЕЛИ В ЯЗЫКЕ С В составе языка программирования С присутствуют знаки пунктуации, использование которых позволяет изменять смысл выражения. [ ] – ограничивают индексы массивов и индексированных элементов; ( ) – группируют выражения, используются в оформлении операторов, используются при оформлении функций, преобразовании типов, при оформлении макроопределений; { } – обозначают границы составного оператора или блока; , – разделяет элементы списков; ; – завершает все операторы, все определения и все описания; : – отделяет метку от помечаемого оператора; = – отделяет переменную от списка инициализации; # – обозначает директивы препроцессора. 6 ОПЕРАТОРЫ ЯЗЫКА С Оператор представляет собой законченную фразу языка, содержащую полностью оформленный этап обработки информации. Любое выражение, заканчивающееся ';' воспринимается компилятором как оператор. В языке С представлены следующие виды операторов: простые – в состав которых не входят другие операторы (оператор присваивания, пустой оператор и операторы изменения порядка выполнения программы), а также сложные – составной оператор, оператор ветвления, переключатель, циклы. Оператор присваивания предназначен для оформления процесса обработки информации. Он имеет формат имя переменной  константа ,  переменная , выражение  вызов функции . Переменная, расположенная слева от знака операции присваивания и являющаяся приемником результата, должна иметь тот же тип данных, что и значение результата. Пустой оператор используется в некоторых случаях для оформления других операторов. Он представляет собой точку с запятой, перед которой не указаны никакие действия: При компиляции такая конструкция заменяется особым кодом, который требует пропустить выполнение текущего действия. Составной оператор представляет собой группу операторов, заключенных в фигурные скобки: операторы Указанная в скобках последовательность действий воспринимается как одно действие. Это бывает необходимо сделать при записи составных операторов. Условный оператор управляет потоком обработки данных путем изменения последовательности передачи управления. В языке С условный оператор записывается следующим образом: if (условие) оператор1; else оператор2; Условие задается константой, переменной или выражением скалярного типа или указателем. Если результат проверки условия не равен нулю, то условие считается истинным и выполняется Оператор1. В противном случае выражение считается ложным и выполняется Оператор2. Если операторов несколько, – нужно использовать составной оператор для их объединения. В качестве операторов нельзя использовать описания и определения переменных. Схема работы условного оператора представлена на рис. 1. Нет Условие Оператор 1 Оператор 2 Рис. 1 Порядок работы условного оператора Допускается сокращенная форма условного оператора: if (условие) оператор1; В этом случае ветвь, помеченная на рис. 1 надписью "нет" считается пустой и при ложном результате проверки условия не производится никаких действий, а управление передается следующему оператору. При использовании вложенных друг в друга условных операторов, следует следить за отношением ветви else. Переключатель используется для организации множественного ветвления. В языке С оператор-переключатель записывается следующим образом: switch (переключающее_выражение) case константное_выражение1: оператор1; case константное_выражение2: оператор2; default: оператор; Управление передается к тому из помеченных с помощью ключевого слова case операторов, для которого значение константного выражения совпадает со значением переключающего выражения. Переключающее выражение должно быть целочисленным или его значение должно быть приведено к целочисленному типу. Значение константного выражения приводится к типу переключающего выражения. Все константные выражения должны быть различны, но принадлежать к одному типу. Любой из операторов в фигурных скобках может быть помечен несколькими метками. Рис. 2 Порядок работы переключателя Порядок работы переключателя в языке С проиллюстрирован на рис. 2. После проверки значения переключательного выражения (селектора) осуществляется поиск помеченного ключевым словом case варианта с совпадающим значением константы. Первым будет выполнен оператор, помеченный данной меткой. Далее будут выполнены в порядке следования все остальные операторы, находящиеся в переключателе после найденного. Указанный порядок работы оператора-переключателя не всегда удобен: гораздо чаще требуется выполнить только тот оператор, который помечен меткой, совпадающей в данный момент со значением селектора. Выполнение всех остальных операторов в данном случае не требуется. Этот режим работы переключателя представлен на рис. 3.