Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
Лабораторная работа 2
Принципы структурного программирования
1 Общие сведения о структурном программировании
Структурное программирование — методология разработки программного обеспечения, в основе которой лежит представление программы в виде иерархической структуры блоков. Предложена в 70-х годах XX века Э. Дейкстрой, разработана и дополнена Н. Виртом.
В соответствии с данной методологией
Любая программа представляет собой структуру, построенную из трёх типов базовых конструкций:
- последовательное исполнение — однократное выполнение операций в том порядке, в котором они записаны в тексте программы;
- ветвление — однократное выполнение одной из двух или более операций, в зависимости от выполнения некоторого заданного условия;
- цикл — многократное исполнение одной и той же операции до тех пор, пока выполняется некоторое заданное условие (условие продолжения цикла).
В программе базовые конструкции могут быть вложены друг в друга произвольным образом, но никаких других средств управления последовательностью выполнения операций не предусматривается.
Повторяющиеся фрагменты программы (либо не повторяющиеся, но представляющие собой логически целостные вычислительные блоки) могут оформляться в виде т. н. подпрограмм (процедур или функций). В этом случае в тексте основной программы, вместо помещённого в подпрограмму фрагмента, вставляется инструкция вызова подпрограммы. При выполнении такой инструкции выполняется вызванная подпрограмма, после чего исполнение программы продолжается с инструкции, следующей за командой вызова подпрограммы.
Разработка программы ведётся пошагово, методом «сверху вниз».
Сначала пишется текст основной программы, в котором, вместо каждого связного логического фрагмента текста, вставляется вызов подпрограммы, которая будет выполнять этот фрагмент. Вместо настоящих, работающих подпрограмм, в программу вставляются «заглушки», которые ничего не делают. Полученная программа проверяется и отлаживается. После того, как программист убедится, что подпрограммы вызываются в правильной последовательности (то есть общая структура программы верна), подпрограммы-заглушки последовательно заменяются на реально работающие, причём разработка каждой подпрограммы ведётся тем же методом, что и основной программы. Разработка заканчивается тогда, когда не останется ни одной «затычки», которая не была бы удалена. Такая последовательность гарантирует, что на каждом этапе разработки программист одновременно имеет дело с обозримым и понятным ему множеством фрагментов, и может быть уверен, что общая структура всех более высоких уровней программы верна. При сопровождении и внесении изменений в программу выясняется, в какие именно процедуры нужно внести изменения, и они вносятся, не затрагивая части программы, непосредственно не связанные с ними. Это позволяет гарантировать, что при внесении изменений и исправлении ошибок не выйдет из строя какая-то часть программы, находящаяся в данный момент вне зоны внимания программиста.
Теорема о структурном программировании:
Основная статья: Теорема Бома-Якопини
Любую схему алгоритма можно представить в виде композиции вложенных блоков begin и end, условных операторов if, then, else, циклов с предусловием (while) и может быть дополнительных логических переменных (флагов).
Эта теорема была сформулирована итальянскими математиками К. Бомом и Дж. Якопини в 1966 году и говорит нам о том, как можно избежать использования оператора перехода goto.
2 Рекурсия
В программировании рекурсия – вызов функции (процедуры) из неё же самой, непосредственно (простая рекурсия) или через другие функции (сложная или косвенная рекурсия), например, функция A вызывает функцию B, а функция B – функцию A. Количество вложенных вызовов функции или процедуры называется глубиной рекурсии.
Преимущество рекурсивного определения объекта заключается в том, что такое конечное определение теоретически способно описывать бесконечно большое число объектов. С помощью рекурсивной программы же возможно описать бесконечное вычисление, причём без явных повторений частей программы.
Реализация рекурсивных вызовов функций в практически применяемых языках и средах программирования, как правило, опирается на механизм стека вызовов — адрес возврата и локальные переменные функции записываются в стек, благодаря чему каждый следующий рекурсивный вызов этой функции пользуется своим набором локальных переменных и за счёт этого работает корректно. Оборотной стороной этого довольно простого по структуре механизма является то, что на каждый рекурсивный вызов требуется некоторое количество оперативной памяти компьютера, и при чрезмерно большой глубине рекурсии может наступить переполнение стека вызовов. Вследствие этого, обычно рекомендуется избегать рекурсивных программ, которые приводят (или в некоторых условиях могут приводить) к слишком большой глубине рекурсии.
Имеется специальный тип рекурсии, называемый «хвостовой рекурсией». Интерпретаторы и компиляторы функциональных языков программирования, поддерживающие оптимизацию кода (исходного или исполняемого), автоматически преобразуют хвостовую рекурсию к итерации, благодаря чему обеспечивается выполнение алгоритмов с хвостовой рекурсией в ограниченном объёме памяти. Такие рекурсивные вычисления, даже если они формально бесконечны (например, когда с помощью рекурсии организуется работа командного интерпретатора, принимающего команды пользователя), никогда не приводят к исчерпанию памяти. Однако, далеко не всегда стандарты языков программирования чётко определяют, каким именно условиям должна удовлетворять рекурсивная функция, чтобы транслятор гарантированно преобразовал её в итерацию. Одно из редких исключений — язык Scheme (диалект языка Lisp), описание которого содержит все необходимые сведения.
Любую рекурсивную функцию можно заменить циклом и стеком.
3 Стек
Стек (англ. stack — стопка) — структура данных, в которой доступ к элементам организован по принципу LIFO (англ. last in — first out, «последним пришёл — первым вышел»).
Добавление элемента, называемое также проталкиванием (push), возможно только в вершину стека (добавленный элемент становится первым сверху). Удаление элемента, называемое также выталкиванием (pop), тоже возможно только из вершины стека, при этом второй сверху элемент становится верхним.
Стеки широко применяются в вычислительной технике. Например, для отслеживания точек возврата из подпрограмм используется стек вызовов, который является неотъемлемой частью архитектуры большинства современных процессоров. Языки программирования высокого уровня также используют стек вызовов для передачи параметров при вызове процедур.
4 Операторы цикла
В языке С, как и в других языках программирования, операторы цикла служат для многократного выполнения последовательности операторов до тех пор, пока выполняется некоторое условие. Условие может быть установленным заранее (как в операторе for) или меняться при выполнении тела цикла (как в while или do-while).
4.1 Цикл for
Во всех процедурных языках программирования циклы for очень похожи. Однако в С этот цикл особенно гибкий и мощный. Общая форма оператора for следующая:
for (инициализация; условие; приращение) оператор;
Цикл for может иметь большое количество вариаций. В наиболее общем виде принцип его работы следующий. Инициализация — это присваивание начального значения переменной, которая называется параметром цикла. Условие представляет собой условное выражение, определяющее, следует ли выполнять оператор цикла (часто его называют телом цикла) в очередной раз. Оператор приращение осуществляет изменение параметра цикла при каждой итерации. Эти три оператора (они называются также секциями оператора for) обязательно разделяются точкой с запятой. Цикл for выполняется, если выражение условие принимает значение ИСТИНА. Если оно хотя бы один раз примет значение ЛОЖЬ, то программа выходит из цикла и выполняется оператор, следующий за телом цикла for.
В следующем примере в цикле for выводятся на экран числа от 1 до 100:
#include <stdio.h>
int main(void)
{
int x;
for(x=1; x <= 100; x++) printf("%d ", x);
return 0;
}
В этом примере параметр цикла х инициализирован числом 1, а затем при каждой итерации сравнивается с числом 100. Пока переменная х меньше 100, вызывается функция printf() и цикл повторяется. При этом х увеличивается на 1 и опять проверяется условие цикла х <= 100. Процесс повторяется, пока переменная х не станет больше 100. После этого процесс выходит из цикла, а управление передается оператору, следующему за ним. В этом примере параметром цикла является переменная х, при каждой итерации она изменяется и проверяется в секции условия цикла.
4.2 Цикл while
Обшая форма цикла while имеет следующий вид:
while (условие) оператор;
Здесь оператор (тело цикла) может быть пустым оператором, единственным оператором или блоком. Условие (управляющее выражение) может быть любым допустимым в языке выражением. Условие считается истинным, если значение выражения не равно нулю, а оператор выполняется, если условие принимает значение ИСТИНА. Если условие принимает значение ЛОЖЬ, программа выходит из цикла и выполняется следующий за циклом оператор.
В следующем примере ввод с клавиатуры происходит до тех пор, пока пользователь не введет символ А:
char wait_for_char(void)
{
char ch;
ch = '\0'; /* инициализация ch */
while(ch != 'A') ch = getchar();
return ch;
}
Переменная ch является локальной, ее значение при входе в функцию произвольно, поэтому сначала значение ch инициализируется нулем. Условие цикла while истинно, если ch не равно А. Поскольку ch инициализировано нулем, условие истинно и цикл начинает выполняться. Условие проверяется при каждом нажатии клавиши пользователем. При вводе символа А условие становится ложным и выполнение цикла прекращается.
Как и в цикле for, в цикле while условие проверяется перед началом итерации. Это значит, что если условие ложно, тело цикла не будет выполнено. Благодаря этому нет необходимости вводить в программу отдельное условие перед циклом.
4.3 Цикл do-while
В отличие от циклов for и while, которые проверяют свое условие перед итерацией, do-while делает это после нее. Поэтому цикл do-while всегда выполняется как минимум один раз. Общая форма цикла do-while следующая:
do {
оператор;
} while (условие);
Если оператор не является блоком, фигурные скобки не обязательны, но их почти всегда ставят, чтобы оператор достаточно наглядно отделялся от условия. Итерации оператора do-while выполняются, пока условие не примет значение ЛОЖЬ.
В следующем примере в цикле do-while числа считываются с клавиатуры, пока не встретится число, меньшее или равное 100:
do {
scanf("%d", &num);
} while(num > 100);
Цикл do-while часто используется в функциях выбора пунктов меню. Если пользователь вводит допустимое значение, оно возвращается в качестве значения функции. В противном случае цикл требует повторить ввод. Следующий пример демонстрирует усовершенствованную версию программы для выбора пункта меню проверки грамматики:
void menu(void)
{
char ch;
printf("1. Проверка правописания\n");
printf("2. Коррекция ошибок\n");
printf("3. Вывод ошибок\n");
printf(" Введите Ваш выбор: ");
do {
ch = getchar(); /* чтение выбора с клавиатуры */
switch(ch) {
case '1':
check_spelling();
break;
case '2':
correct_errors();
break;
case '3':
display_errors();
break;
}
} while(ch!='1' && ch!='2' && ch!='3');
}
В этом примере применение цикла do-while весьма уместно, потому что итерация, как уже упоминалось, всегда должна выполниться как минимум один раз. Цикл повторяется, пока его условие не станет ложным, т.е. пока пользователь не введет один из допустимых ответов.
5 Условные операторы
В языке С существуют два условных оператора: if и switch. При определенных обстоятельствах оператор ? является альтернативой оператора if.
5.1 Оператор if
Общая форма оператора if следующая:
if (выражение) оператор;
else оператор;
Здесь оператор может быть только одним оператором, блоком операторов или отсутствовать (пустой оператор). Фраза else может вообще отсутствовать.
Если выражение истинно (т.е. принимает любое значение, отличное от нуля), то выполняется оператор или блок операторов, следующий за if. В противном случае выполняется оператор (или блок операторов), следующий за else (если эта фраза присутствует). Необходимо помнить, что выполняется или оператор, связанный с if, или с else, но оба — никогда!
5.2 Вложенные условные операторы if
Оператор if является вложенным, если он вложен, т.е. находится внутри другого оператора if или else. В практике программирования вложенные условные операторы используются довольно часто. Во вложенном условном операторе фраза else всегда ассоциирована с ближайшим if в том же блоке, если этот if не ассоциирован с другой фразой else. Например:
if(i)
{
if(j) statement 1;
if(k) statement 2; /* этот if */
else statement 3; /* ассоциирован с этим else */
}
else statement 4; /* ассоциирован с if(i) */
Последняя фраза else не ассоциирована с if(j) потому, что она находится в другом блоке. Эта фраза else ассоциирована с if(i). Внутренняя фраза else ассоциирована с if(k), потому что этот if — ближайший.
6 Операторы перехода
6.1 Оператор return
Оператор return используется для выхода из функции. Отнесение его к категории операторов перехода обусловлено тем, что он заставляет программу перейти в точку вызова функции. Оператор return может иметь ассоциированное с ним значение, тогда при выполнении данного оператора это значение возвращается в качестве значения функции. В функциях типа void используется оператор return без значения. Общая форма оператора return следующая:
return выражение;
6.2 Оператор break
Оператор break применяется в двух случаях. Во-первых, в операторе switch с его помощью прерывается выполнение последовательности case (см. раздел "Оператор выбора — switch" ранее в этой главе). В этом случае оператор break не передает управление за пределы блока. Во-вторых, оператор break используется для немедленного прекращения выполнения цикла без проверки его условия, в этом случае оператор break передает управление оператору, следующему после оператора цикла.
Когда внутри цикла встречается оператор break, выполнение цикла безусловно (т.е. без проверки каких-либо условий.) прекращается и управление передается оператору, следующему за ним. Например, программа
#include <stdio.h>
int main(void)
{
int t;
for(t=0; t<100; t++) {
printf("%d ", t);
if(t==10) break;
}
return 0;
}
выводит на экран числа от 0 до 10. После этого выполнение цикла прекращается оператором break, условие t < 100 при этом игнорируется.
6.3 Функция exit()
Функция exit() не является оператором языка, однако рассмотрим возможность ее применения. Аналогично прекращению выполнения цикла оператором break, можно прекратить работу программы и с помощью вызова стандартной библиотечной функции exit(). Эта функция вызывает немедленное прекращение работы всей программы и передает управление операционной системе. Общая форма функции exit() следующая:
void exit (int код_возврата);
6.4 Оператор continue
Можно сказать, что оператор continue немного похож на break. Оператор break вызывает прерывание цикла, a continue — прерывание текущей итерации цикла и осуществляет переход к следующей итерации. При этом все операторы до конца тела цикла пропускаются. В цикле for оператор continue вызывает выполнение операторов приращения и проверки условия цикла. В циклах while и do-while оператор continue передает управление операторам проверки условий цикла.
7 Функции
7.1 Структура функций
Функции — это строительные элементы языка С и то место, в котором выполняется вся работа программы. В этой главе изучаются свойства функций, в том числе их аргументы, возвращаемые значения, прототипы, а также рекурсия.
Общий вид функции
В общем виде функция выглядит следующим образом:
возвр-тип имя-функции(список параметров)
{
тело функции
}
возвр-тип определяет тип данного, возвращаемого функцией. Функция может возвращать любой тип данных, за исключением массивов список параметров — это список, элементы которого отделяются друг от друга запятыми. Каждый такой элемент состоит из имени переменной и ее типа данных. При вызове функции параметры принимают значения аргументов. Функция может быть и без параметров, тогда их список будет пустым. Такой пустой список можно указать в явном виде, поместив для этого внутри скобок ключевое слово void.
В объявлениях (декларациях) переменных можно объявить (декларировать) несколько переменных одного и того же типа, используя для этого список одних только имен, элементы которого отделены друг от друга запятыми. А все параметры функций, наоборот, должны объявляться отдельно, причем для каждого из них надо указывать и тип, и имя. То есть в общем виде список объявлений параметров должен выглядеть следующим образом:
f(тип имя_переменной1, тип имя_переменной2,..., тип имя_переменнойN)
Вот, например, два объявления параметров функций, первое из которых правильное, а второе — нет:
f(int i, int k, int j) /* правильное */
f(int i, k, float j) /* неправильное, у переменной k должен быть
собственный спецификатор типа */
7.2 Аргументы функции main(): argv и argc
Иногда при запуске программы бывает полезно передать ей какую-либо информацию. Обычно такая информация передается функции main() с помощью аргументов командной строки. Аргумент командной строки — это информация, которая вводится в командной строке операционной системы вслед за именем программы. Например, чтобы запустить компиляцию программы, необходимо в командной строке после подсказки набрать примерно следующее:
cc имя_программы
имя_программы представляет собой аргумент командной строки, он указывает имя той программы, которую вы собираетесь компилировать.
Чтобы принять аргументы командной строки, используются два специальных встроенных аргумента: argc и argv. Параметр argc содержит количество аргументов в командной строке и является целым числом, причем он всегда не меньше 1, потому что первым аргументом считается имя программы. А параметр argv является указателем на массив указателей на строки. В этом массиве каждый элемент указывает на какой-либо аргумент командной строки. Все аргументы командной строки являются строковыми, поэтому преобразование каких бы то ни было чисел в нужный двоичный формат должно быть предусмотрено в программе при ее разработке.
Вот простой пример использования аргумента командной строки. На экран выводятся слово Привет и ваше имя, которое надо указать в виде аргумента командной строки.
#include <stdio.h>
#include <stdlib.h>
int main(int argc, char *argv[])
{
if(argc!=2) {
printf("Вы забыли ввести свое имя.\n");
exit(1);
}
printf("Привет %s", argv[1]);
return 0;
}
7.3 Прототип функции
В современных, правильно написанных программах на языке С каждую функцию перед использованием необходимо объявлять. Обычно это делается с помощью прототипа функции.
В общем виде прототип функции должен выглядеть таким образом:
тип имя_функции(тип имя_парам1, тип имя_парам2, ..., имя_парамN);
Использование имен параметров не обязательно. Однако они дают возможность компилятору при наличии ошибки указать имена, для которых обнаружено несоответствие типов, так что не поленитесь указать этих имен — это позволит сэкономить время впоследствии.
Следующая программа показывает, насколько ценными являются прототипы функций. В ней выводится сообщение об ошибке, происходящей из-за того, что программа содержит попытку вызова sqr_it() с целым аргументом, в то время как требуется указатель на целое.
/* В этой программе используется прототип функции
чтобы обеспечить тщательную проверку типов. */
void sqr_it(int *i); /* прототип */
int main(void)
{
int x;
x = 10;
sqr_it(x); /* несоответствие типов */
return 0;
}
void sqr_it(int *i)
{
*i = *i * *i;
}
Задание на лабораторную работу
1. Создать консольное приложение, где организовать интерфейс для работы с пользователем по принципу работы командной строки, где приложение предлагает команды, а пользователь их выбирает.
2. Добавить команду, вычисляющую сумму целых чисел заданного интервала.
3. Создать программу, вычисляющую факториал заданного числа.
4. Найти сумму ряда при заданном n:
5. Найти сумму бесконечного ряда:
Суммировать до тех про, пока члены ряда не станут меньше заданного eps>0.
PAGE \* MERGEFORMAT1