При общении двух людей на естественном языке (русский, английский и др.) их речь может быть не совсем «правильна», однако, это не помешает им понимать друг друга.
По-иному обстоит дело у компьютеров и если при написании программы человек отступит от жёстких правил, налагаемых языком программирования, то вычислительное устройство не сможет выполнить инструкции, так как она их просто «не поймёт».
Язык программирования – формальная знаковая система, предназначенная для записи компьютерных программ. Язык программирования определяет набор лексических, синтаксических и семантических правил, задающих внешний вид программы и действия, которые выполнит исполнитель (компьютер) под её управлением.
Под алфавитом понимается всё множество знаков, которые могут быть использованы при описании команд (инструкций):
Из допустимых символов формируются лексемы.
Лексемы – предопределённые константы, идентификаторы, ключевые слова и знаки операций. Идентификаторы – имена, которые даются программным объектам – именованным константам, переменным, типам и функциям. Предопределённые константы определяются директивой препроцессора #define. Введённая константа будет действовать, начиная с момента задания и до конца кода или отмены с помощью директивы препроцессора #undef.
#define имя константы [значение]
//Действие константы
#undef имя константыРазличают следующие типы констант:
123, -34, 67.25, -2.459)'Z')"first")Ключевые слова – это лексемы, которые зарезервированы компилятором для обозначения типов переменных, класса хранения, элементов операторов.
Стандартом C99 определены следующие ключевые слова:
sizeof, typedef, auto, register, extern, static, char, short, int, long, signed, unsigned, float, double, void, struct, enum, union, do, for, while, if, else, switch, case, default, break, continue, goto, return, inline, _Bool, _Complex, _Imaginary, restrict.
Операция – это функция, которая выполняется над операндами и которая возвращает вычисленное значение – результат выполнения операции.
Операнд – это константа, переменная, выражение или вызов определённой в программе функции.
Приведённый пример программы вначале выведет запрос Input symbol и после ввода символа и нажатия кнопки Enter выведет надписи Good и Code symbol, а также через пробел символ и через знак - код символа.
1
2
3
4
5
6
7
8
9
10
11
// Здесь может быть любой текст (комментарий)
#include
#define out std::cout <<
int main() {
std::cout << "Input symbol" << std::endl;
char ch; // Объявление переменной
std::cin >> ch;
std::cout << "Good" << std::endl;
out "Code symbol " << ch << '-' << ch+0 << std::endl;
return 0;
}
В первой строке текста программы – однострочный комментарий. Такой комментарий всегда начинается парой символов // и заканчивается символом конца строки. Обратите внимание и на шестую строчку текста программы char ch; // Объявление переменной, эта строчка также содержит однострочный комментарий.
Комментарии не компилируются и необходимы в программе только с целью пояснения смысла кода для человека.
Во второй строчке кода помещена директива препроцессора #include служащая целью подключения библиотеки iostream, которая содержит необходимые команды для работы со стандартными потоками ввода и вывода. Для лёгкого запоминания названия библиотеки раскроем аббревиатуру (мнемоника): i (input) – ввод, o (output) – вывод, stream – поток.
Стандартным потоком ввода по умолчанию является клавиатура, стандартным потоком вывода является экран (дисплей, монитор). Стандартные потоки ввода и вывода могут быть переопределены извне и внутри программы.
Третья строка содержит директиву препроцессора #define, о которой было уже сказано выше по тексту. Она определяет новую переменную out, после чего препроцессор встретив в тексте программы отдельно стоящую надпись out подменит её текстом std::cout <<.
Четвёртая строка содержит объявление функции int main(). Данное объявление указывает, что данная функция не принимает каких-либо данных (аргументов), так как содержимое скобок пусто, а так же объявление показывает, что данная функция возвращает целое число int.
Тело любой функции – это заключённая в фигурные скобки последовательность описаний, определений и операторов.
Определим два термина: высказывание (понятие) и логическая связка (операция). В свою очередь высказывания будем делить на простые высказывания, в таких высказываниях будут отсутствовать логические связки и сложные (составные) высказывания – высказывания составленные из простых и сложных высказываний и объединённых между собой с помощью логических связей.
Под высказыванием будем понимать такое выражение (высказывание), относительно которого можно с той или иной вероятностью ответить «Да» («Истина») или «Нет» («Ложь»).
Например, «Сегодня хорошая погода» – простое высказывание (в некоторых источниках такая фраза не будет считаться логическим высказыванием, так как понятие «хорошая» не однозначно). Так же будем и такое выражение считать логическим «Сегодня хорошая погода?», да это выражение в вопросительной форме и так же во многих литературных источниках не является логическим, однако на него можно ответить «Да» или «Нет» и в данном изложении будем считать его логическим высказыванием.
А вот выражение: «Сколько тебе лет?» не является логическим высказыванием, так как ответ на него не подразумевает допустимых здесь ответов («Да», «Нет»).
Приведём пример сложного высказывания: «Человек знает язык программирования или английский язык». Если человек знает язык программирования, то данное выражение следует считать истинным, если человек знает английский язык, так же следует считать данное выражение истинным. А что если человек знает язык программирования и английский язык, с точки зрения русского языка возникает неоднозначность, возможно, следует дать положительный, а возможно и отрицательный ответ.
Покажем другой пример, не отрывая его из контекста: «Объект за совершение поступка А или за совершение поступка Б наказывается наказанием 1 или наказанием 2». В рамках данного изложения в первом упоминании «Или» оно имеет смысл, как по отдельности, так и одновременно, то есть если совершено оба поступка, то это не освобождает от наказания. А вот второе «Или» наоборот имеет смысл в том, что выбирается либо одно, либо другое, но не оба одновременно.
Так как в математике не должно быть неоднозначностей в ней введены специальные обозначения и смысл каждого из них однозначен.
Алгебра логики (алгебра высказываний) — раздел математической логики, в котором изучаются логические операции над высказываниями.
Отрицание - унарная операция над суждениями, результатом которой является суждение «противоположное» исходному.
В языках программирования C/C++ используется знак !.
Например, a = !(c > b).
Таблица истинности:
| a | !a |
|---|---|
| 0 | 1 |
| 1 | 0 |
Конъюнкция — логическая операция, по своему применению максимально приближенная к союзу «и» в русском языке. Синонимы: логическое «И», логическое умножение, иногда просто «И».
Таблица истинности:
| a | b | a && b |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
Дизъюнкция — логическая операция, по своему применению максимально приближённая к союзу «или» в смысле «или то, или это, или оба сразу. Синонимы: логическое сложение, логическое «ИЛИ», включающее «ИЛИ»; иногда просто «ИЛИ».
Таблица истинности:
| a | b | a || b |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 1 |
Теория множеств — раздел математики, в котором изучаются общие свойства множеств — совокупностей элементов произвольной природы, обладающих каким-либо общим свойством.
Примеры множеств и их описаний:
{2,3,4,5} - множество целых положительных чисел от 2 до 5 включительно.
{x : x>1 & x<6}
Теория графов — раздел дискретной математики, изучающий свойства графов.
Граф - пара множеств G=(V,E), где V есть подмножество любого счётного множества, а E — подмножество V×V.
V - называют вершинами, узлами или точками
E - называют рёбрами или дугами
Стек (англ. stack — стопка, кипа, навал) — структура данных, представляющая собой список элементов, организованных по принципу LIFO (англ. Last In — First Out, «последним пришёл — первым вышел»).
Над данной структурой необходимо реализовать 3 операции:
Реализация на массиве (в примере с int):
int st[1000]; // До 1000 элементов
int ind = 0; // Стек пуст
st[ind++] = 3; // Положили на вершину стека 3
st[ind++] = 7; // Положили на вершину стека 7
st[ind++] = 2; // Положили на вершину стека 2
int b = st[--ind]; // b = 2, стек теперь содержит 7 и 3
b = st[--ind]; // b = 7, в стеке только один элемент - 3Заметьте, ind равен количеству элементов в стеке, поэтому его проверка на равенство нулю и есть проверка на пустоту.
В массиве по окончанию работы программы st[1] = 7, st[2] = 2, то есть записанные числа не стёрты из памяти, но ind указывает на 1 - первую свободную ячейку для записи. При следующей записи в стек ячейка с номером ind будет переписана новым значением.
Очередь — структура данных, представляющая собой список элементов, организованных по принципу FIFO (англ. First In — First Out, «первым пришёл — первым вышел»).
Над данной структурой необходимо реализовать 3 операции:
Реализация на массиве (в примере с int):
int qu[1000]; // До 1000 элементов
int fr = 0; // Фронт очереди
int ba = 0; // Конец очереди
qu[fr++] = 3; // Положили 3 в очередь
qu[fr++] = 7; // Положили 7 в очередь
qu[fr++] = 2; // Положили 2 в очередь
int b = qu[ba++]; // b = 3, очередь теперь содержит 7 и 2
b = qu[ba++]; // b = 7, в очереди только один элемент - 2Чтобы проверить, пуста ли очередь, достаточно сравнить fr и ba, если они равны, то очередь пуста.
Если заранее известно, что размер очереди не превысит некоторого количества N, то массива размером в N вполне достаточно. Когда fr и br увеличиваются на единицу, необходимо проверить не стали ли они указывать на элемент N и если да, то обнулить.
Пример:
#define N 1000
int qu[N];
qu[fr++] = 9;
if(fr == N)
fr = 0;