Алгоритмы и структуры данных. Программирование в Cи (стр. 3 из 7)
- односторонний выбор - выполняет действие только на одном из путей разветвления и соединяет оба пути в один, т.е. if (Условное выражение) Инструкция;
- двусторонний выбор – выполняет действия на каждом пути разветвления и также соединяет оба пути, т.е. if (Условное выражение) Инструкция1; else Инструкция2;
Далее автор рассматривает еще один вид условного оператора, выражаемого вопросительным знаком. Он имеет следующий вид:
Условное выражение ? Выражение1: Выражение2
Выражение с условием не может стоять в одиночестве, как в предыдущем ветвлении, а стоит внутри выражения.
Третья условная структура – многократный выбор switch..case. Автор показывает, что в этой структуре имеются больше чем 2 пути выбора, которые также соединяются. Для каждого условия обязательно существует своя инструкция. Для всех оставшихся случаев выполняется какое-то действие. Структура switch .. case имеет такой вид:
switch (Выражение)
{
case W1: Инструкция 1;
...;
case Wn: Инструкция n;
default: Инструкция (по умолчанию);
}
2.3 Циклические операторы
В этом параграфе профессор объясняет, что структуры повторения используются, если последовательность команд должна повторяться неоднократно для решения задачи. Программирование структуры повторения ведет к так называемому "программному циклу".
В случае со структурой while условие стоит в начале программного цикла, поэтому цикл может не выполниться ни разу. Общий вид команды таков:
while (Условные выражения) Инструкции;
Следующая циклическая структура – повторение for представляет самую универсальную форму повторения. Команда имеет следующий вид:
for (Выражение 1; Выражение 2; Выражение 3)Команда;
где Выражение 1 – начальное значение выражения, Выражение 2 – условное выражение, которое должно выполниться для выполнения команд, Выражение 3 – изменяет счетную величину для продолжения повторения.
Затем автор рассматривает структуру, обратную структуре while. Последовательность команд запускается в любом случае, по меньшей мере, однажды. Поэтому эту структуру называют также непредотвратимым повторением.
Do
Инструкция;
while (Условное выражение);
Таким образом, в данной главе автором были разобраны различные типы трех структурных единиц любого языка программирования – линейной, разветвляющейся и циклической.
В этой главе автор рассказывает об одном из главных структурных элементов программы – функциях. Во всех высокоуровневых языках программирования происходит разделение программ на части с помощью подпрограмм-функций.
3.1 Понятие
Функции реализуют идеологию структурного программирования и исполняют все необходимые задания для решения общей задачи. Для самых важных и часто используемых заданий имеются стандартные функции, занесенные в программные библиотеки C. Для решения других задач необходимо написать собственные функции. Все C-программы состоят из набора небольших функций. Для определения функции в языке C необходимо указать тип и имя, а также список параметров в круглых скобках.
В языке C любая функция определяется глобально, т.е. не зависит от других функций. В общем виде эту структуру можно представить так:
Тип имя функции (список параметров)
{
Соглашения
Инструкции
return (значение функции)
}
Для каждого из параметров функции представляется его тип. Эти формальные параметры имеют собственное имя, которое используется в пределах работы функции и собственный тип. Например, функция:
int quad (int x)
{
return (x * x);
}
содержит параметр с именем x типа Integer(целый).
При вызове функции формальные параметры заменяются актуальными параметрами, в качестве которых могут выступать определенные значения, константы или переменные величины. Например: y = quad (25); При этом тип актуального параметра должен обязательно соответствовать типу формального параметра.
3.2 Готовность и срок службы имен
Особенно автор обращает внимание на имена переменных, констант, функций в программе. В программе существуют две позиции на значение имен:
1. Готовность (Доступность). Этим свойством определяются места программы, в которых можно получить доступ к тем или иным объектам (переменным величинам или функциям). Здесь существует 4 основных программных области – программа, модуль, функция, блок. Объекты, которые определяются в самой программе или модуле являются глобальными объектами, а если определяются в пределах блока или функции, то являются локальными объектами.
2. Срок службы (Жизненный цикл). Здесь говорится о длительности упорядочивания ячеек памяти. Различают полное время распространения (статическая продолжительность) и время выполнения блока, в котором определялся объект.
Эти правила дают ряд преимуществ при написании программ:
· Переменная получает определенное значение в пределах функции.
· Локальные переменные не применяются для всей программы, поэтому можно использовать одинаковые имена переменных в различных функциях.
· Глобальные переменные определяются один раз и используются всеми функциями программы.
· Если имена глобальных и локальных переменных совпадают, то в данной функции используются значения локальных переменных. Таким образом, необходимо избегать написания одинаковых имен переменных.
3.3 Рекурсия и итерация
В этом параграфе автор рассказывает о очень важном методе решения задач – рекурсивных алгоритмах. Алгоритм называется рекурсивным, если вызов функции происходит в пределах самой функции, т.е. функция ссылается сама на себя. При этом основная мысль состоит в том, чтобы уменьшать рекурсивным образом данную проблему до тех пор, пока не будет получен простейший случай. При этом значительно уменьшается алгоритм решения задачи.
Чтобы достигнуть рекурсивности, локальные переменные величины и параметры должны сохраняться не в статической памяти, а в так называемой динамической памяти, которая реализуется программно.
Также из большого количества шагов состоит итерационный алгоритм. Он содержит промежуточные шаги, которые образуют основу для промежуточных результатов в следующем повторении (итерации). Итерации используются в основном при обработке больших массивов данных. Различают 2 основных вида итераций:
- Алгоритмы с заранее известным количеством шагов повторения.
- Алгоритмы с заранее неизвестным количеством шагов повторения.
Программист должен всегда заботиться о том, чтобы все процессы, которые протекают в определенной программе, после конечного числа шагов завершались. К сожалению, зачастую этого не происходит и программа «зацикливается».
Поэтому, если написана какая-то условная или циклическая структура, необходимо следить, чтобы после конечного числа прохождений условие не было больше выполнено. Конечность повторения можно подытожить следующим образом: число шагов зависит от переменных величин программы и оно больше 0, если условие выполняется хотя бы один раз, а значение счетчика определяется в зависимости от действий.
3.4 Функции ввода-вывода
В этом параграфе автор рассказывает о наиболее важных стандартных функциях, которые позволяют вводить информацию с клавиатуры и выводить ее на экран.
Ввод и вывод данных в C происходит через файловый интерфейс. При этом с устройствами, как, например, принтер или консоль обращаются как с файлами. В стандартной C-библиотеке для нескольких устройств существуют стандартные файлы:
· stdin (стандартный ввод данных, клавиатура)
· stdout (стандартный вывод, монитор)
· stderr (ошибки вывода, монитор)
С функциями ввода-вывода связан файл заголовка stdio.h стандартной библиотеки заголовков. В нем определены для применения функций необходимые функциональные прототипы, такие как типы и константы (макрокоманды), которые стоят в связи с реализацией и приложением функций. Кроме всего прочего определяется константа EOF, которая служит для внутренней идентификации конца файлов.
Также существует специальная функция вывода информации – printf, которая имеет вид:
int printf(контрольная строка, аргумент1, аргумент2, ... ). Функция printf копирует символы из формата стандартного вывода либо до конца строки, либо до символа %. Чтобы определить тип формата вывода, функция ищет следующие за % символы. Самый часто используемым является формат %d, который выводит целые числа в десятичной системе счисления.
Стандартной функцией ввода данных в C является функция scanf, которая имеет следующий вид: scanf (контрольная строка, аргумент1, аргумент2,...). Она переводит соответственно в управляющую строку "контрольную строку" данного типа и формата. Она задает формат и назначает конвертированные значения через определенный адрес соответствующим переменным величинам arg1, arg2....
4.1 Числа и числовые системы
В этой параграфе автор рассказывает об основах представления чисел в компьютере.
Значение числа Z = an an-1 ... a0 a-1 ... a-m в позиционной системе счисления по основанию B имеет вид:
где 0 <= a <B.
Например, в десятичной системе счисления число 1972 выглядит так:
1972 = 1 * 103 + 9 * 102 + 7 * 101 + 2 * 100
Формой представления чисел в компьютере является двоичная. Недостатком этой системы является запутанная, монотонная последовательность цифр при изображении длинных двоичных чисел. Поэтому в информатике также используют часто восьмеричную и шестнадцатеричную системы счисления. Именно о них рассказывает автор в этой главе.
Достаточно часто возникает необходимость преобразования чисел из одной системы в другую, в частности, в наиболее понятную человеку десятичную систему счисления. Правило преобразования из любой системы счисления в десятичную выглядит так: