Книги, научные публикации
Министерство общего и профессионального образования Российской Федерации НОВОСИБИРСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ МЕТОДЫ ПРОГРАММИРОВАНИЯ Методические указания к лабораторным работам для
студентов I курса ФПМиИ (направление 510200 - Прикладная математика и информатика) дневного отделения Новосибирск 2002 Составители: В. П. Хиценко, ст. преп., Т. А. Шапошникова, ст. преп.
Рецензент Т. А. Шапошникова, ст.преп.
Работа подготовлена на кафедре прикладной математики й Новосибирский государственный технический университет, 2002 г.
2 ВВЕДЕНИЕ Цели лабораторных работ: - формирование практических навыков программирования и работы в современных вычислительных системах;
- овладение одним из алгоритмических языков высокого уровня (в данном лабораторном практикуме - языком Си/Си++). Основная концепция, заложенная в лабораторных работах, - это движение от простейших алгоритмов, управляющих структур, типов данных к более сложным алгоритмам, управляющим структурам, типам данных. Методические указания к лабораторным работам являются ориентиром в самостоятельной подготовке студентов по теме работы и содержат требования, рекомендации, контрольные вопросы, задания по теме работы. Выполнение лабораторной работы включает следующие этапы: 1. Допуск к работе. На этом этапе преподаватель проверяет подготовленность студента по теме работы, задавая контрольные вопросы или контрольные упражнения. 2. Проектирование и реализация программы решения задачи (вариант выдает преподаватель после успешного выполнения п. 1). Этот этап включает: - разработку и описание алгоритма поставленной задачи, - написание программы в соответствии с требованиями к лабораторной работе, - трансляцию и отладку программы на тестовых примерах (набор тестов подбирает студент). 3. Защита лабораторной работы. К защите студент должен подготовить отчет по работе, продемонстрировать работу программы на тестовых примерах. Защита состоит в обсуждении алгоритма и программы, ответе на контрольные вопросы, решении контрольных примеров. Отчет по лабораторной работе включает следующие разделы: 1. Условие задачи 2. Анализ задачи 3. Алгоритм решения задачи 4. Текст программы 5. Набор тестов 6. Результаты работы программы Анализ задачи необходим для достижения следующих целей: - установить, что является исходными данными и результатами решения задачи;
- выделить основные отношения между входными и выходными данными (если возможно описать их на языке математики);
- выделить основные подзадачи, которые надо решить, чтобы достичь результата. На основании этого определяется подход к разработке алгоритма решения задачи (т.е. метод ее решения), который позволяет в самом общем виде сформулировать, что должен делать алгоритм, чтобы преобразовать исходные данные в результат. Как правило, в условии задачи нет каких-либо ограничений на размер и тип исходных данных, поэтому необходимо определить класс входных данных, которые должны обрабатываться алгоритмом. Например, входными данными является матрица. В этом случае необходимо задать максимально допустимое число строк и максимально допустимое число столбцов. При этом студент должен не сужать, а максимально расширять класс входных данных, чтобы разработать наиболее универсальную программу. Алгоритм решения задачи - это не программа ее решения, а способ дать человеку (а не машине) представление о структуре алгоритма, о смысле его шагов и их логической взаимосвязи. Поэтому шаги алгоритма должны описываться в терминах тех объектов и отношений между ними, о которых идет речь в условии задачи (это, конечно, не исключает использования математической и другой условной символики). Структура алгоритма станет более ясной, если ее описывать в наглядной и достаточно формализованной (напоминающей конструкции языка программирования) форме. Поэтому требуемой формой описания алгоритма в данном лабораторном практикуме является либо графическое представление алгоритма на языке блок-схем, либо на специальном языке описания алгоритмов, например школьном алгоритмическом языке. Пример. По заданному целому X сформировать матрицу A размера 10x10 следующим образом:
1 x.. 9 x x x2.. x x2 x3.. x K K K K K x9 x 10.. x Описание алгоритма на псевдоязыке: begin {ввод заданного числа X};
{Заполнить 1ю строку матрицы A};
for i :=2 to 10 do begin {заполнить первые девять элементов i-й строки, взяв их из (i-1) строки};
{заполнить последний элемент i-й строки};
end end. Если необходимо, нужно продолжить описание, детализируя отдельные шаги.
ЛАБОРАТОРНАЯ РАБОТА № 1 Тема. Программирование ветвлений. Простые скалярные типы данных. Цель. Сформировать практические навыки программирования простейших задач, в основе решения которых лежат фундаментальные структуры, такие как последовательность и ветвления и скалярные типы данных. Содержание работы 1. Изучить управляющие структуры последовательность и ветвление (операторы присваивания и условные операторы языка Си). 2. Изучить основные характеристики скалярных типов данных. 3. Спроектировать и отладить программу решения поставленной задачи.
Методические указания 1. Понятие ветвления. Разветвляющийся вычислительный процесс предполагает несколько возможных направлений вычисления, но только одно из них должно выполняться при реализации алгоритма. Поэтому разветвление включает проверку одного или нескольких условий, в зависимости от которой и будет выбираться направление (ветвь) вычисления. Таким образом, алгоритм разветвления состоит из проверки условия (условий) и всех возможных ветвей вычисления, при этом желательно, чтобы действия, общие для всех ветвей, описывались один раз (до или после ветвления). 2. Типы данных В (Турбо) Си переменные должны быть описаны, а их тип специфицирован до того, как эти переменные будут использованы. При описании переменных применяется префиксная запись, при которой вначале указывается тип, а затем - имя переменной. Общая форма описания простой переменной: <спецификация типа > <идентификатор>[,<идентификатор>...] Например: float weight;
int exam,а1,р;
char ch;
С типом данных связываются и набор предопределенных значений (область значений), и набор операций, которые можно выполнять над величиной данного типа. Область значений - это интервал от минимального до максимального значения, которое может быть представлено в переменной данного типа. Переменные можно инициализировать в месте их описаний. Пример: int height = 71 ;
float income =26034.12 ;
Простейшими скалярными типами, предопределёнными в (Турбо) Си (их называют базовыми типами), являются:
- целые типы: char, int, long int;
- плавающие типы: float, double, long double. Целые типы имеют две формы - знаковую (signed) и беззнаковую (unsigned). В сокращенной форме signed может быть опущено. Таблица 1 Размер памяти и область значений типов Тип char int Назначение знаковый символьный знаковый целый знаковый длинный целый беззнаковый символьный беззнаковый целый Представление в памяти 1 байт зависит от реализации 4 байта 1 байт зависит от реализации 4 байта 4 байта 8 байтов 10 байтов Область значений от -128 до 127 от -32768 до 32767, если 2 байта long unsigned char unsigned int unsigned long от -2.147.483.648 до 2.147.483.647 от 0 до 255 от 0 до 65535, если 2 байта беззнаковый длинный целый плавающий float одинарной точности плавающий double двойной точности long dou- длинный плавающий ble двойной точности от 0 до 4.294.967.295 стандартный формат IEEE стандартный формат IEEE стандартный формат IEEE 3. Операции Различают следующие группы операций (Турбо) Си: арифметические операции, операции отношения, операции присваивания, логические операции, побитовые операции, операция вычисления размера (sizeof) и операция следования (запятая). Арифметические операции К арифметическим операциям относятся: сложение (+), вычитание (-), деление (/), умножение (*) и остаток (%). Все операции (за исключением остатка) определены для значений целого и плавающего типов. Остаток (остаток от деления) определен только для значений целых типов. Все арифметические операции с плавающей точкой производятся над операндами двойной точности. Операции отношения В языке определены следующие операции отношения: проверка на равенство (= =), проверка на неравенство (!=), меньше (<), меньше или равно (< =), больше (>), больше или равно (> =). Все перечисленные операции вырабатывают результат типа int. Если данное отношение между операндами истинно, то значение этого целого единица, а если ложно, то нуль. Логические операции В языке имеются три логические операции: операция И (&&) - конъюнкция, операция ИЛИ ( | | ) - дизъюнкция и отрицание (!). Логические операции определены для целых и плавающих типов. Результат логической операции типа int. Операция состоит в вычислении значения операнда/операндов и сравнении его/их с нулем. Все значения, отличные от нуля, интерпретируются как истинные иначе - ложь. Результатом логической операции является либо единица (истина), либо нуль (ложь). Вычисление выражений, содержащих логические операции, производится слева направо и прекращается (усекается), как только удается определить результат. Если выражение составлено из логических утверждений (т.е. выражений, вырабатывающих значения типа int), соединенных между собой операцией И (&&), то вычисление выражения прекращается, как только хотя бы в одном логическом утверждении вырабатывается значение нуль. Если выражение составлено из логических утверждений, соединенных между собой операцией ИЛИ ( | | ), то вычисление выражения прекращается, как только хотя бы в одном логическом утверждении вырабатывается ненулевое значение. Примеры выражений, в которых используются логические операции: i > 50 && j == 24 - значение будет истинно (равно единице) только тогда, когда оба утверждения i > 50 и j == 24 истинны ;
value1 < value2 && (value3 > 50 || value4 < 20) - подвыражение (value3 > 50 || value4 < 20) истинно, если истинно хотя бы одно из утверждений value3 > 50 или value4 < 20;
все выражение истинно, когда истинны оба утверждения value1 < value2 и (value3 > 50 || value4 < 20).
Операции присваивания К операциям присваивания относятся =, +=, -=, *= и /=, а также префиксные и постфиксные операции ++ и --. Все операции присваивания присваивают переменной результат вычисления выражения. Если тип левой части присваивания отличается от типа правой части, то тип правой части приводится к типу левой. В одном операторе операция присваивания может встречаться несколько раз. Вычисления производятся справа налево. Например: a = ( b = c ) * d;
Вначале переменной b присваивается значение с, затем выполняется операция умножения на d, и результат присваивается переменной а. Операции +=, -=, *= и /= являются укороченной формой записи операции присваивания. Их применение проиллюстрируем при помощи следующего описания: a += b означает a = a + b;
a -= b означает a = a - b;
a *= b означает a = a * b;
a /= b означает a = a / b;
Префиксные и постфиксные операции ++ и -- используют для увеличения (инкремент) и уменьшения (декремент) на единицу значения переменной. Семантика указанных операций следующая: ++a увеличивает значение переменной а на единицу до использования этой переменной в выражении. а++ увеличивает значение переменной а на единицу после использования этой переменной в выражении. --a уменьшает значение переменной а на единицу до использования этой переменной в выражении. a-- уменьшает значение переменной а на единицу после использования этой переменной в выражении. Операция следования (или последовательного вычисления) выражение1, выражение2 Запятая - это знак операции следования. Вычисляется значение первого выражения, затем второго. Результат операции имеет значение и тип второго выражения. Таблица 2 Приоритет и порядок выполнения операций в языке Си Знак операции Наименование Порядок () [ ]. - > -~!*& + + - - sizeof приведение типа */ % +< > <= >= = = != && ?: = *= /= %= += -= <= >>=, Первичные Унарные Мультипликативные Аддитивные Отношение Отношение Логическое И Логическое ИЛИ Условная Простое и составное присваивание Последовательное вычисление Слева направо Справа налево Слева направо Слева направо Слева направо Слева направо Слева направо Слева направо Справа налево Справа налево Слева направо Операции в таблице приведены в порядке убывания приоритета. Операцию sizeof (размер) можно применить к константе, типу или переменной. В результате будет получено число байтов, занимаемых операндом. Например: printf ( "\nРазмер памяти под целое %d", sizeof( int) );
printf ( "\nРазмер памяти под cимвол %d", sizeof( сhar) );
4. Константы В языке (Турбо) Си имеются четыре типа констант: целые, вещественные (с плавающей точкой), символьные и строковые. Константы целого типа Константы целого типа могут задаваться в десятичной, двоичной, восьмеричной или шестнадцатеричной системе счисления. Десятичные целые константы образуются из цифр. Первой цифрой не должен быть нуль. Восьмеричные константы всегда начинаются с цифры нуль, вслед за которой либо не стоит ни одной цифры, либо стоят несколько цифр от нуля до семерки. Шестнадцатеричные константы всегда начинаются с цифры нуль и символа х или Х, за которыми может стоять одна или более шестнадцатеричных цифр. Шестнадцатеричные цифры - это десятичные цифры от 0 до 9 и латинские буквы: a, b, c, d, e, f, или A, B, C, D, E, F.
Например: задание константы 3478 в десятичном, восьмеричном и шестнадцатеричном виде: int a = 3478, b = 06626, c = 0хD96;
К любой целой константе можно справа приписать символ l или L, и это будет означать, что константа - длинная целая (long integer). Символ u или U, приписанный к константе справа, указывает на то, что константа целая без знака (unsigned long). Считается, что значение любой целой константы всегда неотрицательно. Если константе предшествует знак минус, то он трактуется как операция смены знака, а не как часть константы. Десятичная константа может иметь тип int или long в зависимости от ее значения. Восьмеричные и шестнадцатеричные константы в зависимости от значения тип int или unsigned int или long или unsigned long. Константы вещественного типа Константы с плавающей точкой (называемые вещественными) - это действительное десятичное положительное число, состоящее из цифр, десятичной точки и знаков десятичного порядка е или Е. Формат представления: [< цифры >] [.< цифры >] [< э > [ - ] < цифры >], где < э > - признак экспоненты, задаваемый символом е или Е. Цифры следующие за символом экспоненты - это целочисленное значение порядка действительного числа, возможно со знаком + или -. Ниже приведены варианты записи констант вещественного типа: а)1. 2e1 б).1234 в).1e3 г) 257.1 2E1 д) 1.234 0.0035e-6 е) 10 2e-1 ж) 21. з).00075Е-20 Чтобы записать отрицательное действительное число, надо сформировать константное выражение: знак унарной операции минус за ним константа, например -12.234 или -.00345е-2. Константа с плавающей точкой имеет тип double. Cимвольные константы Cимвольная константа - это любой символ из множества представимых символов, в том числе и любой специальный символ. Cимвольные константы заключаются в апострофы (кавычки). Все символьные константы имеют в (Турбо) Си значение типа int (целое), совпадающее с кодом символа в кодировке ASCII. Одни символьные константы соответствуют символам, которые можно вывести на печать, другие - управляющим символам, задаваемым с помо щью esc - последовательности, третьи - форматирующими символами, также задаваемым с помощью esc - последовательности. Каждая esc - последовательность должна быть заключена в кавычки. Управляющие символы \n Переход на новую строку \t Горизонтальная табуляция \v Вертикальная табуляция \b Возврат на символ \r Возврат в начало строки \f Прогон бумаги до конца страницы \\ Обратная дробная черта (слэш) \' Одинарная кавычка \" Двойная кавычка \ddd Код символа в ASCII от одной до трех восьмеричных цифр \xhhh Код символа в ASCII от одной до трех шестнадцатеричных цифр. Строковые константы Строковые константы состоят из нуля или более символов, заключенных в двойные кавычки. В строковых константах управляющие коды задаются с помощью esc - последовательности. Обратный слэш используется как символ переноса текста на новую строку. Пример написания и использования строковых констант: printf(У Пример использования\n\nФ);
printf(Устроковых\ констант.\n\nФ);
Будет выведен следующий текст: Пример использования строковых констант. 5.Выражение Выражение задает правило вычисления нового значения. Выражение состоит из операций и операндов. Операции определяют действия выполняемые над операндами. Операндом выражения может быть константа, переменная, выражение. Выражение, входящее как операнд в другое выражение может быть первичным выражением, таким как, например, вызов функции или выражением, заключенным в круглые скобки.
Результат вычисления значения выражения зависит от порядка выполнения операций и их приоритета. Для задания правильного порядка вычислений используются скобки, они повышают приоритет операции. Но для операций, обладающих свойством коммутативности, не гарантируют определенный порядок вычисления. При выполнении операции, как правило, происходит преобразование типов ее операндов к общему типу. Преобразования по умолчанию осуществляются следующим образом: 1) все операнды типа float преобразуются к типу double;
2) если один операнд имеет тип long double, то второй операнд преобразуется к типу long double;
3) если один операнд имеет тип double, то второй операнд преобразуется к типу double;
4) если один операнд имеет тип unsigned long, то второй операнд преобразуется к типу unsigned long;
5) если один операнд имеет тип long, то второй операнд преобразуется к типу long;
6) если один операнд имеет тип unsigned int, то второй операнд преобразуется к типу unsigned int;
7) все операнды типа char преобразуются к типу int;
8) все операнды типа unsigned char преобразуются к типу unsigned int;
9) иначе оба операнда имеют тип int. Тип значения выражения имеет тип результата последней выполняемой операции в этом выражении. 6. Основные управляющие структуры Основу языка (Турбо) Си составляют операторы. В (Турбо) Си точка с запятой является признаком конца оператора. Принято группировать все операторы в следующие классы: присваивания, вызов функции, ветвления и цикла. Управляющие структуры или операторы управления служат для управления последовательностью вычислений в программе. 1) Оператор - выражение <выражение>;
Действие заключается в вычислении значения выражения. 2) Оператор присваивания В простейшем случае общий вид оператора: V = E;
Здесь V - имя переменной, а E - выражение. В операторе присваивания используется операция присваивания =. Например:
c = a * b;
Действие такого оператора можно описать следующими словами: " с присваивается значение а, умножение на b ". Значение, присваиваемое переменной с, равняется произведению текущих значений переменных а и b. Тип вычисленного значения выражения перед присваиванием преобразуется к типу переменной по правилам преобразования типов. 3) Составной оператор (или последовательность) Любая последовательность операторов, заключенная в фигурные скобки, является составным оператором (блоком). Концом составного оператора служит сама закрывающаяся скобка. Внутри блока каждый оператор должен ограничиваться (;
). Например: { I+= a;
n++;
} Составной оператор может использоваться везде, где синтаксис языка допускает применение одного оператора. Составной оператор называется блоком, если кроме операторов он содержит спецификации переменных. Структурная схема последовательности:
S S...
Sn где Si - любой оператор. 4)Условные операторы (ветвления) - полный условный оператор : if ( B ) S1;
else S2 ;
Здесь B - выражение, принимающее логическое значение, S1 - оператор, исполняемый, если B истинно, S2 - оператор, исполняемый, если B ложно. Структурная схема полного условного оператора:
истина ложь B S S - сокращенный условный оператор if ( B ) S;
Здесь S - оператор, исполняемый, если B истинно, в противном случае выполняется следующий по порядку оператор. Структурная схема сокращенного условного оператора:
B истина ложь S - оператор переключатель (варианта): switch ( I ) { case L1: S1;
break;
case L2: S2;
break;
... case Ln: Sn;
break;
default: Sn+1;
} Где I - выражение целого типа, L1, L2,...,Ln - константы того же типа, что и I, S1, S2,..., Sn - операторы, из которых выполняется тот, с константой которого совпало значение I. Ветка default (оператор Sn+1) выполняется, если ни одно из вышестоящих выражений не удовлетворено. Структурная схема оператора варианта:
L1 S1 I L2 S2 Ln...
Sn 7. Программа на языке Си Простая программа - это программа с управляющей структурой, обладающей следующими особенностями: 1) имеется только один вход и один выход, 2) через каждый узел программы проходит путь от входа к выходу структуры.
Структурные схемы простых программ при программировании ветвлений: а) f f...
fn б) f в) I f1 f2...
B f fn где fi - функциональный узел, который может иметь а), б), в) структуры. Программа на языке Си состоит из одной или более функций. Одна из этих функций - главная, она имеет имя main. Операционная система передает управление в программу пользователя на функцию с этим именем и тем самым начинается выполнение программы. Функция main вызывает другие функции программы. Кроме функций программа может содержать директивы препроцессору, указания компилятору, объявления и определения. Директивы препроцессора используют для того, чтобы облегчить модификацию программы. Директива - это инструкция препроцессору языка Си. Препроцессор обрабатывает исходную программу перед ее компиляцией. Текст программы на языке Си может быть разделен на несколько исходных файлов. Исходный файл - это текстовый файл, который содержит либо всю программу, либо ее часть. Исходный файл не обязательно должен содержать выполняемые операторы. Удобно размещать определения переменных в одном файле, а в других файлах использовать эти переменные путем их объявления. Каждый исходный файл компилируется отдельно, а затем связывается с другими компоновщиком программ. Отдельные исходные файлы можно объединить в один исходный файл, компилируемый как единое целое, используя директиву препроцессора - include. Директива include Синтаксис: #include < имя пути > Эта директива включает содержимое исходного файла <имя пути> в компилируемый исходный текст, содержащий директиву include. Имя пути - это имя файла. Появление директив #include <файл_1> #include "файл_2"... #include <файл_n> приводит к тому, что препроцессор подставляет на место этих директив тексты файлов файл_1, файл_2,..., файл_n соответственно. Если имя файла заключено в угловые скобки <...>, то поиск файла производится сначала в директориях, указанных в командной строке компиляции, а затем в стандартных директориях. Директива define Синтаксис: #define < идентификатор > < текст > Директива #define заменяет все вхождения < идентификатора > в исходном файле на < текст >. Этот процесс называется макроподстановкой. <Текст> представляет собой набор лексем, таких как ключевые слова, константы, идентификаторы или выражения. С помощью макроса можно задавать именованные константы, что облегчает модификацию программы. Например, директива #define pi 3.1415926 связывает идентификатор pi со значением 3.1415926. Если мы захотим изменить значение константы, например, задать ее с меньшей точностью, достаточно изменить только директиву, а не все операторы, где используется pi. Объявления Объявление переменной задает ей имя и атрибуты. Объявление функции задает ее имя, тип результата и атрибуты формальных параметров. Объявление типа позволяет создать собственный тип данных, либо задавая новое имя некоторому базовому типу, либо составному типу. Определения Определение переменной, кроме задания ее имени и атрибутов, приводит к выделению для нее памяти, а также задает начальное значение переменной ( явно или неявно).
Определение функции специфицирует тело функции, которое представляет собой составной оператор или блок, кроме этого задает ей имя, тип результата, атрибуты формальных параметров. Определение типа совпадает с понятием объявление типа. В простейшем случае синтаксис определения функции: < идентификатор > ( ) < тело функции > Тело функции представляет собой составной оператор или блок. Он содержит операторы, которые определяют действие этой функции, и, если необходимо, объявления и/или определения переменных, используемых в этих операторах. В простейшем случае главная функция имеет следующий вид: main() { [< объявление >]... [< оператор >]... } Комментарии Текст на (Турбо) Си, заключенный в скобки /* и */, компилятором игнорируется. Комментарии служат двум целям: документировать текст программы и облегчить отладку. Если программа работает не так, как надо, то иногда оказывается полезным закомментировать часть кода ( т.е. вынести ее в комментарий ), заново скомпилировать программу и выполнить ее. Если после этого программа начнет работать правильно, то значит, закомментированный код содержит ошибку и должен быть исправлен. 8. Ввод и вывод данных Ввод и вывод осуществляется посредством использования функций ввода/вывода, входящих в состав стандартной библиотеки языка Си. Необходимые нам функции содержатся в файле stdio.h, который должен быть подключен к программе директивой #include < stdio.h>. Для любой программы на языке Си всегда доступны три стандартных файла: stdin - файл ввода, stdout - файл вывода, stderr - файл сообщений об ошибках. По умолча нию они связываются с пользовательским терминалом. Файлы открываются при входе в программу и закрываются при выходе из нее. Для задания значений исходным данным задачи будем использовать оператор (функцию) форматного ввода scanf: scanf (управляющая строка [,список аргументов]);
Функция scanf читает данные из стандартного потока stdin в переменные, адреса которых задаются в списке аргументов. В простом случае управляющая строка состоит из одной или более спецификаций преобразования (формата). Спецификация преобразования в простом случае имеет вид: %C, где C - символ преобразования.
Символы преобразования Входная строка Тип аргумента c d D e f Символ Десятичное целое Десятичное целое Значение с плавающей точкой char int long float Каждой вводимой переменной в строке функции scanf должна соответствовать спецификация. Перед именами переменных необходимо ставить символ &. Этот символ означает "взять адрес". Управляющая строка рассматривается слева направо и, когда встречается первая спецификация формата, значение первого входного поля преобразуется согласно этой спецификации и записывается по адресу первой переменной списка аргументов. Согласно второй спецификации преобразуется значение второго входного поля и помещается по адресу второй переменной и так далее до конца управляющей строки. Пример: scanf (У %d %d %d Ф,&x,&y,&z);
Первое значение из входного потока рассматривается как целое число и преобразуется в соответствии с %d к типу int, затем помещается по адресу переменной x, аналогично преобразуются следующие два значения и помещаются по адресам переменных x и y соответственно. Вводимые значения в потоке ввода разделяются пробелами. Для вывода результатов работы программы будем использовать оператор (функцию) форматного вывода printf: printf (управляющая строка [,список аргументов]);
Управляющая строка может содержать символы, которые нужно вывести, управляющие символы и спецификации формата. Аргумент задается константой, переменной или выражением. Общий вид спецификации преобразования: % [-] [dd] [. pp] C где C - символ или пара символов, определяющих преобразование выводимого значения;
- означает, что выводимое значение должно быть в поле вывода выравнено влево. По умолчанию оно выравнивается вправо;
dd - десятичное целое число, задающее минимальный размер поля, т.е. число позиций, занимаемых выводимым значением. Если размер поля недостаточен для значения, оно тем не менее будет выведено полностью, если размер поля больше, в избыточных позициях по умолчанию будут пробелы;
pp - десятичное целое число, указывающее для плавающих типов, количество цифр после десятичной точки. Пример: printf ("\nВозраст Эрика - %d. Его доход $%.2f",age,income);
Предполагается, что целой переменной age (возраст) и вещественной переменной income (доход) присвоены какие-то значения. Последовательность символов "\n" переводит курсор на новую строку. Последовательность символов "Возраст Эрика -" будет выведена с начала новой строки. Символы %d - это спецификация для целой переменной age в соответствии с которой значение переменной будет преобразовано в десятичное число и выведено после символов "Возраст Эрика -". Следующая литерная строка " Его доход $ ". %2f - это спецификация ( символ преобразования формата ) для вещественного значения, а также указание формата для вывода только двух цифр после десятичной точки. Так выводится значение переменной income. Символ формата Тип выводимого объекта %с char %s строка %d int %o int ( в восьмеричном виде ) %u unsigned int %x int ( в шестнадцатеричном виде ) %ld long ( в десятичном виде ) %lo long ( в восьмеричном виде ) %lu unsigned long %lx long ( в шестнадцатеричном виде ) %f float/double ( c фиксированной точкой) %e %g %lf %le %lg float/double ( в экспоненциальной форме ) float/double ( в виде f или е в зависимости от значения ) long float ( c фиксированной точкой ) long float ( в экспоненциальной форме ) long float ( в виде f или е в зависимости от значения ) Пример простой программы на Си: #include
/*рост*/ printf("\n Введите ваш вес: ");
scanf("%d", &weight);
printf(" \nВведите ваш pocт: ");
scanf("%d", &height);
printf("\n\nВес = %d, рост = %d\n", weight,height);
} Чтобы знать, при каких именно исходных данных выполнялась программа, целесообразно вывести на экран не только результаты, но и введенные значения исходных данных. Контрольные вопросы 1. Понятие типа данных. 2. Базовые типы в Си. 3. Характеристики простых скалярных типов данных. 4. Понятие выражения. Правила вычисления выражения. 5. Структура программы на языке Си. 6. Управляющие структуры следования. 7. Управляющие структуры ветвления. 8. Программирование ветвлений.
ЛАБОРАТОРНАЯ РАБОТА №2 Тема. Программирование итерационных циклов. Простые типы данных. Цель. Сформировать навыки программирования простейших задач, в основе решения которых лежат такие фундаментальные структуры, как циклы и простые типы данных. Содержание работы 1. Изучить циклические управляющие структуры (операторы цикла с предусловием и постусловием). 2. Изучить скалярные типы. 3. Спроектировать и отладить программу решения поставленной задачи. Методические указания 1. Понятие цикла Вычислительный процесс, в котором многократно повторяются вычисления по одним и тем же формулам, называется циклическим (или просто циклом). В основе реализации цикла лежит обобщенное представление (запись) многократно повторяющихся действий. Например, требуется вычислить значение многочлена a5x5 + a4x4 +... a1x + a0. Для сокращения вычислений приведем этот полином к скобочной записи, называемой схемой Горнера: (((( a5 x + a4 )x + a3 )x + a2 )x + a1 )x + a0. Здесь повторяющейся совокупностью действий является умножение на x и сложение с очередным коэффициентом полинома. Чтобы вычислить полином, надо выp=p*x + a4;
полнить следующую последовательность действий: p=a5;
p=p*x + a3;
p=p*x + a2;
p=p*x + a1;
p=p*x + a0. С увеличением порядка полинома длина такой последовательности действий может быть очень большой (или даже заранее неизвестной, если порядок полинома задается переменной величиной). Выходом из этой ситуации является такая запись повторяющихся действий (называемая обобщенной записью, т.е. независимой от номера повторного выполнения), которая позволяет, описав эти действия один раз и организовав их повторение столько раз, сколько необходимо вычислить требуемое значение. В данной задаче обобщенная запись может иметь вид p=p*x + k, где k- коэффициент полинома. Перед выполнением этого действия k должна получить значение очередного коэффициента. Или вид p=p*x + ai, здесь ai также обобщенная запись коэффициента полинома с номером i. Кроме основных действий, называемых телом цикла цикл содержит дополнительные действия, обеспечивающие повторение тела цикла.
Цикл с предусловием подготовка цикла Цикл с постусловием подготовка цикла продолжать цикл?
_ + тело цикла + тело цикла продолжать цикл?
_ выход из цикла выход из цикла Таким образом, в самом общем виде структурная схема цикла содержит три части: действия по подготовке цикла к первому исполнению;
- действия, являющиеся основным содержанием данного вычислительного процесса - тело цикла;
- действия, отслеживающие повторение тела цикла - проверка условия продолжения или условия окончания повторений. Блок-схема алгоритма вычисления значения полинома nЦй степени для заданного значения x:
начало ввод x, k p=k i = _ вывод p in + ввод k p=p*x+k i=i+ конец Для итерационных методов характерны стереотипные вычисления, связанные с переходом от одного приближения к следующему. Это позволяет записывать соответствующие этим методам алгоритмы в виде циклических, причем число повторений этих стереотипных вычислений (итераций) заранее, как правило, неизвестно и зависит от начального приближения и допустимой погрешности. Характерным условием окончания цикла является некоторое отношение, связывающее разность последовательных приближений и допустимую погрешность. 2. Циклические управляющие структуры - оператор цикла с предусловием: while ( В ) S;
где B - выражение, определяющее условие выполнения тела цикла;
S - оператор (тело цикла). Структурная схема оператора цикла с предусловием:
B S ложь истина Таким образом, тело цикла с предусловием может ни разу не выполнится, если выражение B сразу ложно. Выражение B и оператор S должны быть связаны так, чтобы когда-нибудь выражение стало ложным и, цикл завершился. - оператор цикла с постусловием: do S while ( B );
где B - выражение, определяющее условие выполнения цикла;
S - оператор (тело цикла). Структурная схема оператора цикла с постусловием:
S истина B ложь Таким образом, тело оператора цикла с постусловием всегда, хотя бы один раз выполнится. Выражение B и оператор S должны быть связаны так, чтобы когданибудь выражение стало ложным и, цикл завершился. -оператор пошагового цикла: for (e1;
e2;
e3) S;
где e1- выражение, задающее начальные условия выполнения цикла;
e2 - выражение, задающее условие продолжения цикла;
e3 - выражение, изменяющее (модифицирующее) условия, заданные выражением e1;
S - оператор - тело цикла. Выполнение оператора цикла for состоит из следующих действий: e1;
while (e2);
{ S;
e3;
} Таким образом, это цикл с предусловием, включающий в себя наряду с телом цикла и условием продолжения цикла, действия по инициализации и модификации цикла. 3. Схемы итерационного цикла 1. v = v0;
while p(v) { S;
f(v) ;
} Такая схема используется в задачах, в основе решения которых лежат рекуррентные соотношения. При этом если v принимает последовательно значения v0, v1, v2,..., vn, то эти значения имеют следующие свойства:
для всех i > 0, vi v j, для всех i j, p( v i ) = true, для всех i < n, p( v n ) = false, для всех i = n. 2. t = t0;
s = t;
while p(s,t) { t = f(t);
s += t ;
} Такая схема используется в задачах, реализующих какой-либо процесс последовательных приближений, например вычисление суммы ряда, заканчивающееся при условии, по которому можно судить о погрешности вычислений. При этом если t0, t1, t2,..., tn - последовательность членов ряда, то t i = f ( t i 1 ), для всех i > 0, ti t j, для всех i j, S i = S i 1 + t i, для всех i > 0, p(S i, t i ) = true, для всех i < n, p(S n, t n ) = false, для всех i = n. Реализуя приближенные вычисления, необходимо помнить, что в памяти ЭВМ действительные числа представляются приближенно и поэтому сравнение действительных значений необходимо производить, задавая уровень точности. Например, необходимо проверить, лежат ли три точки на одной прямой. Для этого в уравнение прямой, проходящей через две точки, необходимо подставить координаты третьей точки. Все точки лежат на одной прямой тогда и только тогда, когда в результате получается нуль. Из-за неточности машинной арифметики для действительных чисел нуль почти никогда не будет получен. Поэтому условие приходится считать выполненным, если полученный при подстановке результат по модулю меньше некоторого предусмотренного разработчиком малого числа, например 10-5, называемого точностью вычислений. Контрольные вопросы 1. Понятие цикла. 2. Циклические структуры типа while, do, for - их синтаксис и семантика. 3. Понятие итерационного цикла. 4. Программирование итерационных вычислений. 5. Структура программы на языке Си. 6. Простые типы и циклы.
v i = f ( v i 1 ), ЛАБОРАТОРНАЯ РАБОТА № Тема. Регулярные типы (массивы). Основные алгоритмы обработки массивов.
Цель. Знать свойства регулярных типов, способы их описания и уметь решать задачи, связанные с обработкой массивов. Содержание работы 1. Изучить правила задания массивов, их свойства и операции, допустимые над этим типом. 2. Изучить оператор цикла с заданным числом повторений. 3. Спроектировать и отладить программу решения поставленной задачи. Методические указания 1. Понятие сложного типа Массив - это пример сложного (структурированного) типа. Сложные типы характеризуются тем, что любое значение такого типа состоит из множества компонентов (элементов) каким-то образом связанных между собой в единое целое, т.е. имеет сложную структуру. Сложный тип строится по следующим правилам: а) элемент сложной структуры может иметь как простую, так и сложную структуры. Таким образом, значения сложных типов в общем случае имеют иерархическую структуру, на самом нижнем уровне которой элементы только простого типа (при этом уровень вложенности может ограничиваться или нет);
б) внутри сложной структуры тип всех элементов может быть - одинаков - однородная структура, - различен - неоднородная структура;
в) количество элементов в структуре может быть: - фиксировано в течение времени существования структуры (структуры фиксированного размера или статические), - переменным, т.е. динамически меняться путем включения или исключения элементов в процессе работы со структурой (структуры переменного размера или динамические);
г) обращение (доступ) к элементам структуры может быть: - непосредственное (прямое) - вычисляемое (по индексу или месту в структуре) или не вычисляемое (по имени элемента);
- последовательное - характерное для структур переменного размера. Вид обращения определяется способом объединения компонент в единую структуру;
д) значение структуры может храниться либо в оперативной (внутренняя структура), либо во внешней памяти. 2. Массив Регулярный тип (массив) - это сложный тип с однородной структурой фиксированного размера и прямым вычисляемым доступом к элементам. Размер структуры фиксируется при описании массива.
Задание регулярного типа (массива) имеет вид: <спецификация типа> <идентификатор> [<константное выражение>] Здесь квадратные скобки являются терминальными символами. Константное выражение определяет число компонентов в массиве, поэтому его значение целого типа. Элементы массива занимают непрерывную область памяти, т.е. последовательно располагаются друг за другом. Элементы в массиве нумеруются, начиная с нуля. Тип компонентов задается спецификацией типа. Тип компонентов может быть любой (кроме файлового). Если тип компонентов: - простой, то определяемая структура будет одномерной (линейной);
- сложный, то определяемая структура будет многомерной (нелинейной). Многомерный массив это массив, элементы которого типа массив. Задание многомерного массива: <спецификация типа> <идентификатор> [
float mas [5] [25];
char line [80];
float x[10][10], y[n1][n2][n3];
Переменная vector это линейный (одномерный) массив с 10 элементами: vector [0], vector [1],..., vector [9]. Тип каждого компонента целый.
Переменная mas это двумерный массив из 5 строк и 25 столбцов (т.е. со 125 компонентами): mas[0][0], mas[0][1], mas[0][2],..., mas[0][24], mas[1][0],mas[1][1],..., mas[1][24], mas[2][0],..., mas[2][24],..., mas[4][0],..., mas[4][24], тип компонентa float. Если указать только один индекс, например mas[0] - это означает одномерный подмассив, т.е. строку матрицы с номером 0. Переменная line одномерный массив с 80 компонентами: line [0], line [1], Е,line [79], элементы типа char. Тип компонентов переменных x и y - float;
x - двумерный массив с 10 строками и 10 столбцами - квадратная матрица размером 10 10;
y - трехмерный массив размером n1n2n3. Здесь n1,n2,n3 Цименованные константы, значения которых могут быть определены директивой define или с помощью модификатора const. На элементы массива y можно ссылаться: y[0], y[1], y[2],Е, y[n1-1], где y[i] означает двумерный подмассив с номером i размером n2n3 ;
элементы более нижнего уровня обозначаются y[0][0], y[0][1],..., y[0][n21], y[1][0],..., y[n1-1][n2-1], где y[i][j] означает одномерный подмассив массива y размером n3;
элементы самого нижнего уровня обозначаются y[0][0][0], y[0][0][1],..., y[0][0][n3-1], y[0][1][0],...,y[0][1][n3-1],..., y[n1-1][0][0],..., y[n1-1][n21][n3-1]. Обратиться к элементу массива можно еще одним способом - используя для этого указатель. Указатель - это переменная, значением которой является адрес другой переменной, т.е. номер единицы памяти, которая выделена для переменной. Указатель может ссылаться только на объекты заданного типа. Имя массива является константой-указателем на первый элемент массива. Для многомерного массива, определенного, например как тип А [n1][n2][n3], имя массива - константа-указатель, поставленная в соответствие элементам типа тип [n2][n3]. Для вышеприведенных примеров, имени массива vector соответствует адрес первого элемента этого массива (т.е. элемента vector[0]), имя line - константа-указатель на элемент line[0]. Имя массива mas - указатель, поставленный в соответствие элементам типа float mas[25], выражение *(mas+i) - указатель на элемент mas[i];
имя x - указатель, поставленный в соответствие элементам типа float x[10], выражение *(x+i) - указатель на элемент x[i];
имя y - указатель, поставленный в соответствие элементам типа float y[n2][n3], выражение *(y+i) - указатель, поставленный в соответствие элементам типа float[n3]. Увеличивая на единицу значение указателя, получаем адрес следующего элемента (числовое значение адреса при этом увеличивается на размер памяти элемента массива). Имя vector указывает на первый элемент массива, а выра жение vector+i, на i-ый элемент после первого (т.е. vector+i - это адрес i Цтого элемента массива vector). Выражение *(vector+i) - это значение i-того элемента массива vector. Таким образом, записи vector[i] и *(vector+i) эквивалентны. Унарная операция * есть операция косвенной адресации. Ее результатом является значение, на которое указывает операнд - указатель. Если выражение *(mas+i) это указатель на элемент mas[i] типа float mas[25], то выражение *(mas+i)+j это указатель на элемент mas[i][j]. Выражение *(*(mas+i)+j) это значение элемента с адресом *(mas+i)+j, т.е. элемента mas[i][j]. Для трехмерного массива y выражение *(y+i) - указатель на элемент y[i], выражение *(y+i)+j - указатель на элемент y[i][j], а выражение *(*(y+i)+j)+k - указатель на элемент y[i][j][k], выражение *(*(*(y+i)+j)+k) это значение элемента y[i][j][k]. Если определить переменную указатель, то доступ к элементам массива можно осуществлять через эту переменную. Объявление переменной указателя на значение специфицированного типа: <спецификация типа> * <идентификатор>;
Пример: int *pv;
float *py;
Переменная pv - это указатель на значение типа int (т.е. значение pv это адрес области памяти, в которой может храниться число типа int), а py - указатель на значение типа float. Для вышеописанных массивов в результате присваивания pv=vector, pv будет указывать на первый элемент массива, иначе говоря, значение pv - это адрес элемента vector[0];
*pv - это операция косвенной адресации, ее результатом является значение первого элемента массива, что эквивалентно vector[0];
*(pv+i) - это операция косвенной адресации, результатом которой будет значение iЦтого элемента массива, что эквивалентно vector[i], если pv указывает на первый элемент массива (если нет, то на i-ый после pv, а pv-i на i-ый перед pv).
pv+2: pv+1: pv:
vector:
vector[0] vector[9] Переменную py можно использовать для ссылки на любой из массивов с элементами типа float. Если присвоить py=&mas[0][0], то py равно указателю на mas[0][0], выражение py+i*25+j это адрес элемента y[i][j]. Если присвоить py=&x[i][j], то py указывает на x[i][j] элемент массива x, если присвоить py=&y[0][0][0], то py - это адрес y[0][0][0], а выражение py+i*n2*n3+j*n3+k это указатель на элемент y[i][j][k]. В общем случае для двумерного массива А из m строк и n столбцов указатель на элемент A[i][j] вычисляется по формуле x+i*n+j, где x указатель на пер вый элемент массива А, т.е. на элемент А[0][0]. (Примечание: числовое значение адреса A[i][j] при этом вычисляется по формуле: (x+i*n+j)*sizeof (лтип элемента)). Над элементами массива можно выполнять все операции, допустимые для типа элемента. 3. Применение массивов при решении задач Необходимость в использовании массивов при решении задач возникает всякий раз, когда приходится иметь дело с большим, но конечным числом однотипных данных. В таком случае все данные можно объединить в каком-то порядке следования в единую структуру, которой дается одно имя. Это позволяет в компактном и единообразном виде записать действия над отдельными данными как над элементами массива (используя обобщенное обозначение элемента массива). Особенностью алгоритмов обработки массивов является то, что все или большинство (или какое-то число) элементов обрабатываются одинаково (по одному алгоритму). Поэтому, решая задачу, приходится в том или ином порядке просматривать (перебирать) элементы массивов. Чтобы осуществить перебор надо определить правило изменения индекса элементов (для многомерных массивов - индексов). В случае многомерных массивов (если индексы не должны изменяться одновременно) изменение одного индекса должно быть вложено в правило изменения другого. Пример: для матрицы float a [10][5] перебор элементов можно организовать по строкам, столбцам или диагоналям. Если перебор идет по строкам, то первый индекс (индекс строки) изменяется 0 i 9, второй индекс (индекс столбца) изменяется 0 j 4 для каждого значения i. Схема обработки всех элементов матрицы может быть представлена следующим образом: i := v0;
while (i vn ) {S1;
j := t0;
while( j tm ) { S2;
j := j+1 ;
} S3;
i := i+1;
} Здесь i принимает последовательно значения v0, v0+1, v0+2,..., vn. Ее можно использовать в операторах S1, S2, S3 как один из индексов (номер строки или столбца) элемента матрицы. Переменная j принимает последовательно значения t0, t0+1, t0+2,..., tm и ее можно использовать в операторе S2 как второй индекс (номер столбца или строки). 4. Рекомендации Если, обрабатывая массив, приходится перебирать все его элементы или известное количество, то удобно воспользоваться оператором цикла с заданным числом повторений (со счетчиком): for (v=a;
vb;
v++) S;
(1) где v - параметр цикла - переменная целого типа;
a - начальное значение параметра цикла;
b - конечное значение параметра цикла (a и b задаются выражениями, при этом a b);
S - оператор (тело цикла) или for (v =a;
vb;
v-- ) S;
(2) здесь a b. Выполнение действий в цикле происходит следующим образом: в цикле (1): v = a;
while (v b) {S;
v++;
} в цикле (2): v= a;
while( v b) {S;
v--;
} Шаг изменения параметра цикла v может быть (по модулю) и больше единицы. В таких циклах, как правило, параметр цикла v используется в качестве индекса элемента массива. Так как размер массива фиксируется при его описании, задавайте его, используя именованные константы, тогда вы получите более общее описание. В этом случае фактический размер массива может быть меньше или равен объявленному: # define n 20 # define m 10 main ( ) { int p,k,i,j,x[n][m];
printf (У\n введи размер матрицыФ);
scanf(У%d%dФ, &p,&k);
Тогда ввод значений элементов массива x можно описать:
- по строкам for (i=0;
i i++ ) for (j=0; j j++) scanf (У%fФ, &x[i][j]); Во входной строке значения элементов матрицы должны следовать друг за другом через пробел и перечисляться по строкам. После ввода элементов строки удобно с целью разделения строк нажимать ENTER; - по столбцам for (i=0; i i++ ) for (j=0; j j++) scanf( У%fФ, &x[j][i]); Во входной строке значения элементов матрицы должны следовать друг за другом через пробел и перечисляться по столбцам. После ввода столбца нажимайте ENTER для разделения столбцов. Контрольные вопросы 1. Понятие сложного типа данных. 2. Понятие типа массив, задание этого типа и операции над типом. 3. Задание многомерного массива. 4. Обращение к элементам массива. 5. Обращение к элементам массива через указатели. 6. Использование массива при решении задач.