|
|
Программа термин, в переводе означающий предписание
Часть 1 Теоретические вопросы
Понятие алгоритма и программы. Способы записи алгоритмов.
Алгоритм - это система точных и понятных предписаний о содержании и последовательности выполнения конечного числа действий, необходимых для решения любой задачи данного типа.
Программа — термин, в переводе означающий «предписание», то есть заданную последовательность действий. Данное понятие непосредственно связано с понятием алгоритм.
Словесная форма записи алгоритмов обычно используется для алгоритмов, ориентированных на исполнителя-человека. Команды такого алгоритма выполняются в естественной последовательности, если не оговорено противного.
Графическая запись с помощью блок-схем осуществляется рисованием последовательности геометрических фигур, каждая из которых подразумевает выполнение определенного действия алгоритма.
Алфавит языка СИ.
Прописные и строчные буквы латинского алфавита, а также знак подчеркивания (код ASCII 95);
Арабские цифры от 0 до 9;
Специальные символы:
+(плюс) –(минус) *(звездочка) /(дробная черта) =(равно) >(больше) <(меньше) ;(точка с запятой) &(амперсант) [ ](квадратные скобки) { }(фигурные скобки) ()(круглые скобки) _(знак подчеркивания) .(точка) ,(запятая) :(двоеточие) #("решетка") %(процент) (поразрядное отрицание) ?(знак вопроса) !(восклицательный знак) \(обратный слеш).
+- пробельные (разделительные) символы: пробел, символы табуляции, перевода строки, возврата каретки.
Общая характеристика языков программирования и их классификация
Языками программирования называют формальные языки, которые были специально разработаны для общения человека с компьютером. Любой язык программирования, так же как человеческий язык (русский, английский и т.д.) включает в себя:
алфавит — набор основных символов,фиксированный для данного языка, которые допустимы для составления текста программы на этом языке;
синтаксис — систематизированные правила, определяющие, какие конструкции языкадопустимы в ходе программирования;
семантика – систематизированные правила однозначного толкования отдельных конструкций языка, которые позволяют воспроизводить процесс обработки данных
Классификация языков программирования по категориям определяется методами, используемыми в процессе написании программ. Языки высокого уровня применяются в машинно-независимых системах программирования. Такие системы программирования, по сравнению с машинно-ориентированными системами являются более простыми в использовании.
Понятие о системе программирования. Трансляция программ
Системы программирования - это комплекс инструментальных программных средств, предназначенный для работы с программами на одном из языков программирования. Системы программирования предоставляют сервисные возможности программистам для разработки их собственных компьютерных программ.
Транслятор — программа или техническое средство, выполняющее трансляцию программы.
Трансляция программы - преобразование программы, представленной на одном языке программирования, в программу на другом языке и в определенном смысле равносильную первой.
Существует несколько видов трансляторов.
Диалоговый транслятор — транслятор, обеспечивающий использование языка программирования в режиме разделения времени.
Синтаксически-ориентированный (синтаксически-управляемый) транслятор — транслятор, получающий на вход описание синтаксиса и семантики языка, текст на описанном языке и выполняющий трансляцию в соответствии с заданным описанием.
Однопроходной транслятор — транслятор, преобразующий исходный код при его однократном последовательном чтении (за один проход).
Многопроходной транслятор — транслятор, преобразующий исходный код после его нескольких чтений (за несколько проходов).
Оптимизирующий транслятор — транслятор, выполняющий оптимизацию создаваемого кода.
Тестовый транслятор — транслятор, получающий на вход исходный код и выдающий на выходе изменённый исходный код. Запускается перед основным транслятором для добавления в исходный код отладочных процедур. Например, транслятор с языка ассемблера может выполнять замену макрокоманд на код.
Обратный транслятор — транслятор, выполняющий преобразование машинного кода в текст на каком-либо языке программирования.
Основные конструкции языка программирования. Язык программирования СИ. Структура программы.
Основные конструкции в СИ:
Комментарии (// - однострочный комментарий, /**/ - многострочный комментарий).
Переменные и типы данных. Чтобы объявить переменную в C, нужно сначала указать её тип, а потом написать имя. Отдельного служебного слова для создания переменной в C нет. В C есть разделение на короткие (short), обычные и длинные (long) переменные — на 2, 4 и 8 байт соответственно. Это нужно для экономии памяти, чтобы выделять ровно то количество байт, которое нужно для работы программы.
Директивы. Чтобы программа получила некоторые дополнительные возможности, которых нет в коде по умолчанию, используют директивы. Они обычно пишутся в начале программы и начинаются с символа решётки
Формат программы. В каждой программе на C должна быть функция main (), внутри которой размещается основной код. Большинство компиляторов требуют, чтобы мы указали тип этой функции — обычно можно использовать int (целочисленный) или void (пустой). Все остальные функции добавляются по желанию, но main () должна быть всегда.
Ввод и вывод. Для вывода используется команда printf (), а для ввода scanf ().
Присваивание и сравнение. СИ использует классический подход:
один символ «равно» — присваивание
два символа «равно» — сравнение
Остальные операторы сравнения и логические операторы такие же, как и в других языках. Каждое сравнение берётся в скобки.
Условный оператор if. Тоже всё стандартно (потому что C во многом этот стандарт и создал). Если блок с else не нужен, его можно не писать — короткий if тоже работает.
Оператор множественного выбора Switch. Чтобы не плодить множество операторов if, когда нужно выбрать одно из нескольких значений, используют оператор switch. Если не ставить команду break, то оператор будет продолжать выполнять остальные проверки, даже если найдёт совпадение по условию.
Си — компилируемый статически типизированный язык программирования общего назначения, разработанный в 1969—1973 годах сотрудником Bell Labs Деннисом Ритчи как развитие языка Би. Первоначально был разработан для реализации операционной системы UNIX, но впоследствии был перенесён на множество других платформ.
Структура программы.
Программа на языке Си состоит из набора директив препроцессора, определений функций и глобальных объектов. Директивы препроцессора управляют преобразованием текста до его компиляции. Глобальные объекты определяют используемые данные или состояние программы. А функции определяют поведение или действия программы.
Понятие величины. Оператор присваивания. Объявление переменных.
Оператор присваивания.
Общий вид оператора присваивания следующий:
имя_переменной = выражение;
где выражение может быть как простой одиночной константой, так и сложной комбинацией переменных, операторов и констант.
Объявление переменных.
Чтобы объявить переменную в C, нужно сначала указать её тип, а потом написать имя. Отдельного служебного слова для создания переменной в C нет. В C есть разделение на короткие (short), обычные и длинные (long) переменные — на 2, 4 и 8 байт соответственно. Это нужно для экономии памяти, чтобы выделять ровно то количество байт, которое нужно для работы программы.
Линейные программы. Ввод и вывод данных в языке СИ.
Линейной называется программа, все операторы которой выполняются последовательно, в том порядке, в котором они записаны.
Ввод и вывод информации осуществляется через функции стандартной библиотеки. Прототипы рассматриваемых функций находятся в файле stdio.h. Эта библиотека содержит функции
printf() — для вывода информации
scanf() — для ввода информации.
Форматы нужны для того, чтобы указывать вид, в котором информация будет выведена на экран. Отличительной чертой формата является наличие символа процент ‘%’ перед ним:
%d — целое число типа int со знаком в десятичной системе счисления;
%f — вещественный формат (числа с плавающей точкой типа float);
%lf — вещественный формат двойной точности (числа с плавающей точкой типа double);
И тд.
Организация ввода и вывода данных в программах на языке CИ
Ввод и вывод информации осуществляется через функции стандартной библиотеки. Прототипы рассматриваемых функций находятся в файле stdio.h. Эта библиотека содержит функции
printf() — для вывода информации
scanf() — для ввода информации.
Форматы нужны для того, чтобы указывать вид, в котором информация будет выведена на экран. Отличительной чертой формата является наличие символа процент ‘%’ перед ним:
%d — целое число типа int со знаком в десятичной системе счисления;
%f — вещественный формат (числа с плавающей точкой типа float);
%lf — вещественный формат двойной точности (числа с плавающей точкой типа double);
И тд.
Арифметические и логические операции в СИ. Приоритет операций
Арифметические операции: *, /, +, -, %.
Логические операции: &&, ||, !.
Приоритет операций: 1) *, 2) /, 3) +, 4) -, 5) %, 6) !, 7) &&, 8) ||
Типы данных CИ. Объявление и инициализация.
Типы данных СИ.
Переменная имеет определенный тип. И этот тип определяет, какие значения может иметь переменная и сколько байт в памяти она будет занимать. int: представляет целое число. char: представляет один символ. float: представляет вещественное число ординарной точности с плавающей точкой. double: представляет вещественное число двойной точности с плавающей точкой.
Во время объявления переменных можно сообщить им значение путем помещения знака равенства и константы после имени переменной. Этот процесс называется инициализацией и в общем случае имеет вид:
тип имя_переменной — константа;
Разветвляющиеся алгоритмы и программы. Реализация в языке СИ. Примеры.
Ветвление обеспечивает выполнение одной или более инструкций алгоритма, при условии истинности некоторого логического выражения.
Синтаксис ветвления.
Пример.
Оператор множественного выбора (варианта). Реализация в языке СИ. Пример.
Оператор множественного выбора или конструкция Switch предназначена для того, чтобы избегать в программе множественного повторения оператора if-else-is.
Хотя конструкция if-else-if может выполнять многочисленные проверки, она не очень элегантна. Код очень труден для восприятия и в нем может запутаться даже автор через некоторое время. С этой целью С имеет оператор принятия решений switch, выполняющий действия, основываясь на сравнении значения со списком констант символов или целых чисел.
Оператор switch имеет следующий вид:
switch (выражение) {
case константа1:
последовательность операторов
break;
case константа2:
последовательность операторов
break;
case константа3:
последовательность операторов break;
...
default:
последовательность операторов
}
Пример.
Циклические алгоритмы и программы. Реализация в языке СИ.
Циклический алгоритм – алгоритм, в котором некоторая часть операций (тело цикла — последовательность команд) выполняется многократно.
В языке Си следующие виды циклов:
while — цикл с предусловием;
do…while — цикл с постусловием;
for — параметрический цикл (цикл с заданным числом повторений).
При построении цикла while, в него необходимо включить конструкции, изменяющие величину проверяемого выражения так, чтобы в конце концов оно стало ложным (равным нулю). Иначе выполнение цикла будет осуществляться бесконечно (бесконечный цикл).
Цикл do...while — это цикл с постусловием, где истинность выражения, проверяющего Условие проверяется после выполнения Блока Операций, заключенного в фигурные скобки. Тело цикла выполняется до тех пор, пока выражение, проверяющее Условие, не станет ложным, то есть тело цикла с постусловием выполнится хотя бы один раз.
Для организации цикла for необходимо осуществить три операции:
Инициализация - присваивание параметру цикла начального значения;
Условие - проверка условия повторения цикла, чаще всего - сравнение величины параметра с некоторым граничным значением;
Модификация - изменение значения параметра для следующего прохождения тела цикла.
Эти три операции записываются в скобках и разделяются точкой с запятой. Как правило, параметром цикла является целочисленная переменная.
Инициализация параметра осуществляется только один раз — когда цикл for начинает выполняться.
Проверка Условия повторения цикла осуществляется перед каждым возможным выполнением тела цикла. Когда выражение, проверяющее Условие становится ложным (равным нулю), цикл завершается. Модификация параметра осуществляется в конце каждого выполнения тела цикла. Параметр может как увеличиваться, так и уменьшаться.
Назовите отличия циклов с условиями и цикла с параметром. Пример.
Цикл с условием, к примеру while, имеет, как и все циклы тело и заголовок цикла. Количество итераций в данном цикле заранее неизвестно, он будет выполняться до тех пор, пока условие в нем выполняется.
В другую очередь чикл с параметром for будет выполнять столько итераций, сколько было прописано в заголовке цикла.
Примеры.
Чем отличается цикл «До» от цикла «Пока»?
В цикле «До» начала выполняется тело цикла, затем проверяется условие. Если оно ложно, то выполняется тело цикла. Если условие истинно, то цикл считается выполненным. В свою очередь в цикле «Пока» сначала проверяется условие и если оно истинно, то выполняется тело цикла.
Понятие подпрограммы. Процедуры и функции.
Подпрограмма – это отдельная функционально независимая часть программы. Любая подпрограмма обладает той же структурой, которой обладает и вся программа.
Процедуры в си
В Си можно вводить собственные процедуры. Программа разбивается на подпрограммы. Использование собственных процедур делает наглядным код программы. Кроме того, процедуры можно вызвать в различных местах программы.
Функции в си
Функции – это подпрограммы, которые возвращают определённый результат. При этом функции могут выполнять набор различных действий.
Чтобы задать собственную функцию, необходимо указать тип возвращаемого результата, название функции, список параметров, тело функции и ключевое слово return за которым следует значение возвращаемого результата.
Используя функции можно задать собственную математическую функцию. Задав ее один раз, мы можем вызвать ее в любом месте программы просто по имени и аргументу.
Реализация процедур и функций в СИ.
Чтобы задать собственную процедуру в си необходимо указать
void имя процедуры( тип параметра 1 параметр1, тип параметра2 параметр2 …. )
{
//набор команд выполняемых процедурой
}
Чтобы задать собственную функцию, необходимо указать тип возвращаемого результата, название функции, список параметров, тело функции и ключевое слово return за которым следует значение возвращаемого результата.
Тип функции Название функции (параметры)
{
Исполняемые операторы
return возвращаемое значение;
}
Массивы. Ввод и вывод элементов одномерного массива.
Массив – это линейно упорядоченная совокупность однотипных элементов. Массив определяется типом элементов (int, double, ...) и длиной. Доступ к элементам осуществляется по индексу – порядковому номеру элемента массива. Логически первый элемент массива имеет индекс ноль.
Ввод и вывод массива, то есть заполнение массива пользователем программы и выдачу содержимого массива пользователю. Функция scanf предназначается для ввода данных с клавиатуры. Функция printf предназначена для вывода пользователю содержимого массива.
Для заполнения и вывода массива требуется цикл, который будет проходить весь массив и осуществлять ввод или вывод содержимого массива.
Массивы. Ввод и вывод элементов двумерного массива.
Массив – это линейно упорядоченная совокупность однотипных элементов. Массив определяется типом элементов (int, double, ...) и длиной. Доступ к элементам осуществляется по индексу – порядковому номеру элемента массива. Логически первый элемент массива имеет индекс ноль.
Для ввода или вывода содержимого двумерного массива одного цикла будет недостаточно, потому что в двумерном массиве помимо строк существуют еще и столбцы и для вывода или ввода содержимого массива понадобится уже два цикла (строки и столбцы).
Дайте понятие квадратной матрицы, диагоналей квадратной матрицы.
Квадратная матрица — это матрица, у которой число строк совпадает с числом столбцов, и это число называется порядком матрицы.
Диагонали в квадратной матрице – это набор элементов матрицы от верхнего левого или правого угла соответственно к нижнему правому или левому углу.
Типовые алгоритмы обработки одномерных массивов. Примеры.
Перечислим основные типовые алгоритмы, используемые для работы с одномерными массивами: ввод-вывод массива, вычисление значений элементов массива, поиск суммы и (или) произведения элементов массива, поиск максимального (минимального) элемента массива, упорядочивание элементов массива, добавление (вставка) новых элементов в массив, удаление данных из массива с его сжатием и т.д.
Типовые алгоритмы обработки двумерных массивов. Примеры.
Все, что было сказано об основных действиях с одномерными массивами, справедливо и для матриц.
1. Нахождение суммы элементов массива. Элементы двумерного массива складываются аналогично одномерным, только меняются уже два индекса, в то время как в одномерном массиве - один.
2. Нахождение произведения элементов массива. Элементы двумерного массива умножаются аналогично одномерным, только меняются уже два индекса, в то время как в одномерном массиве - один.
3. Нахождение минимального (наименьшего) и максимального (наибольшего) элемента массива. Аналогично одномерному массиву, для определения максимума/минимума в двумерном массиве первый элемент массива (а он стоит в первой строке и в первом столбце) обозначим за максимальный/минимальный, затем пересмотрим все остальные элементы массива и если встретим элемент, больший того, который считался максимальным/минимальным до этого момента, то обозначим его за максимальный/минимальный.
Сортировка элементов одномерного массива.
Один из самых простых методов сортировки, в том числе одномерных массивов, это метод пузырька.
При сортировке по возрастанию элементы с меньшим значение постепенно "всплывают" в начало массива. В тоже время элементы с большим значением опускаются в низ.
Суть алгоритма заключается в последовательном сравнении парных элементов массива и заменой их местами, если истинно условие что один больше или меньше другого, в зависимости от направления сортировки.
Поясните порядок использования вложенных циклов при вводе элементов двумерного массива.
При использовании двумерных массивов для работы с его элементами необходимо одновременно перебирать два индекса. Это делается с помощью двух вложенных циклов, удобнее всего использовать счетный цикл for. Обычно внешний цикл перебирает номера строк, а внутренний – номера столбцов. Вложенные циклы используются и при вводе значений массива (с клавиатуры или с помощью генератора случайных чисел).
Поиск элементов в двумерном массиве по заданным критериям. Пример.
 |
|
|
Скачать 0.71 Mb.