Понятие алгоритма. Способы описания алгоритмов. Основные алгоритмические конструкции: линейный алгоритм, ветвление, цикл.

Алгоритм – описание последовательности действий, строгое исполнение которых приводит к решению поставленной задачи за конечное число шагов.

Свойства алгоритмов:

1. Дискретность (алгоритм должен состоять из конкретных действий, следующих в определенном порядке);

2. Детерминированность (любое действие должно быть строго и недвусмысленно определено в каждом случае);

3. Конечность (каждое действие и алгоритм в целом должны иметь возможность завершения);

4. Массовость (один и тот же алгоритм можно использовать с разными исходными данными);

5. Результативность (отсутствие ошибок, алгоритм должен приводить к правильному результату для всех допустимых входных значениях).

Виды алгоритмов:

1. Линейный алгоритм (описание действий, которые выполняются однократно в заданном порядке);

2. Циклический алгоритм (описание действий, которые должны повторятся указанное число раз или пока не выполнено задание);

3. Разветвляющий алгоритм (алгоритм, в котором в зависимости от условия выполняется либо одна, либо другая последовательность действий)

4. Вспомогательный алгоритм (алгоритм, который можно использовать в других алгоритмах, указав только его имя).

Для более наглядного представления алгоритма широко используется графическая форма - блок-схема, которая составляется из стандартных графических объектов.

Вид стандартного графического объекта	Назначение
	Начало алгоритма
	Конец алгоритма
	Выполняемое действие записывается внутри прямоугольника
	Условие выполнения действий записывается внутри ромба
	Счетчик кол-во повторов
	Последовательность выполнения действий.

16. Понятие типа данных. Типы данных в Си/С++. Пользовательские типы данных.

Типом данных в программировании называют совокупность двух множеств: множество значений и множество операций, которые можно применять к ним. Например, к типу данных целых неотрицательных чисел, состоящего из конечного множества натуральных чисел, можно применить операции сложения (+), умножения (*), целочисленного деления (/), нахождения остатка (%) и вычитания (−).

Основные типы данных

Основные типы данных часто называют арифметическими, поскольку их можно использовать в арифметических операциях. Для описания основных типов определены следующие ключевые слова:

Целый тип (int).

Размер типа int не определяется стандартом, а зависит от компьютера и компилятора.
2)Символьный тип (char).Для хранения кодов символов или маленьких целых чисел
Под величину символьного типа отводится количество байт, достаточное для размещения десятичного кода любого символа из набора символов для данного компьютера, что и обусловило название типа. Как правило, это 1 байт. Тип char, как и другие целые типы, может быть со знаком или без знака. В величинах со знаком можно хранить значения в диапазоне от -128 до 127. При использовании спецификатора unsigned значения могут находиться в пределах от 0 до 255. Этого достаточно для хранения любого символа из 256-символьного набора ASCII. Величины типа char применяются также для хранения целых чисел, не превышающих границы указанных диапазонов.

3)Логический тип (bool).Логические значения
Величины логического типа могут принимать только значения true и false, являющиеся зарезервированными словами. Внутренняя форма представления значения false – 0 (нуль). Любое другое значение интерпретируется как true. При преобразовании к целому типу true имеет значение 1.

4)Вещественный тип (float, double и long double).Вещественные числа одинарной точности,/Вещественные числа двойной точности /Длинные вещественные числа

Стандарт C++ определяет три типа данных для хранения вещественных значений: float, double и long double.
Вещественные типы данных хранятся в памяти компьютера иначе, чем целочисленные.

5)Тип void
Кроме перечисленных, к основным типам языка относится тип void, но множество значений этого типа пусто. Он используется для определения функций, которые не возвращают значения (такие функции в языке Паскаль называют процедурами, но в языке Си процедур нет), для указания пустого списка аргументов функции, как базовый тип для указателей и в операции приведения.

Пользовательские типы

При определении конструкции class, struct, union или enum она используется в остальной части кода, как если бы это был базовый тип. Он имеет известный размер в памяти, и в его отношении действуют определенные правила проверки во время компиляции и во время выполнения в течение срока использования программы. Основные различия между базовыми встроенными типами и пользовательскими типами указаны ниже:

· Компилятор не имеет встроенных сведений о пользовательском типе. Компилятор "изучает" тип при первом появлении его определения в процессе компиляции.

· Пользователь определяет, какие операции можно выполнять с типом и как его можно преобразовать в другие типы, задавая (через перегрузку) соответствующие операторы, либо в виде членов класса, либо в виде функций, не являющихся членами.

· Они не обязательно должны быть статически типизированы (правило, согласно которому тип объекта не изменяется). Через механизмы наследования и полиморфизма переменная, объявленная как пользовательский тип класса (называется экземпляром объекта класса), во время выполнения может иметь тип, отличный от типа во время компиляции.

17. Структуры данных «массив». Логическое и физическое представление массива. Примеры реализации статических и динамических массивов в Си/С++.

Массив — упорядоченный набор данных, для хранения данных одного типа, идентифицируемых с помощью одного или нескольких индексов. В простейшем случае массив имеет постоянную длину и хранит единицы данных одного и того же типа.

Количество используемых индексов массива может быть различным. Массивы с одним индексом называют одномерными, с двумя — двумерными и т. д. Одномерный массив нестрого соответствует вектору в математике, двумерный — матрице. Чаще всего применяются массивы с одним или двумя индексами, реже — с тремя, ещё большее количество индексов встречается крайне редко.

Поддержка индексных массивов есть в большинстве высокоуровневых языков программирования. Максимально допустимая размерность массива, типы и диапазоны значений индексов, ограничения на типы элементов определяются языком программирования и/или конкретным транслятором.

В языках программирования, допускающих объявления программистом собственных типов, как правило, существует возможность создания типа «массив». В определении такого типа может указываться размер, тип элемента, диапазон значений и типы индексов. В дальнейшем возможно определение переменных созданного типа. Все такие переменные-массивы имеют одну структуру. Некоторые языки поддерживают для переменных-массивов операции присваивания.

Динамические массивы.

Динамическим называется массив, размер которого может меняться во время исполнения программы. Язык программирования, поддерживающий динамические массивы, должен предоставлять возможность для изменения размера массива. Динамические массивы делают работу с данными более гибкой, так как не требуют предварительного определения хранимых объёмов данных, а позволяют регулировать размер массива в соответствии с реальными потребностями. Обычные (не динамические) массивы называют ещё фиксированными.

Реализация

Одним из способов реализации статических массивов с одним типом элементов является следующий:

1. Под массив выделяется непрерывный блок памяти объёмом S*m₁*m₂*m₃…m_n, где S — размер одного элемента, а m₁…m_n — размеры диапазонов индексов (то есть количество значений, которые может принимать соответствующий индекс).

2. При обращении к элементу массива A[i₁, i₂, i₃, …, i_n] адрес соответствующего элемента вычисляется как B+S*((…(i_1p*m₁+i_2p)*m₂+…+i_(n-1)p)*m_n-1+i_np), где B — база (адрес начала блока памяти массива), i_kp — значение k-го индекса, приведённое к целому с нулевым начальным смещением.

Таким образом, адрес элемента с заданным набором индексов вычисляется так, что время доступа ко всем элементам массива одинаково.

Первый элемент массива, в зависимости от языка программирования, может иметь различный индекс. Различают три основных разновидности массивов: с отсчетом от нуля (zero-based), с отсчетом от единицы (one-based) и с отсчетом от специфического значения заданного программистом (n-based). Отсчет индекса элемента массивов с нуля более характерен для низкоуровневых языков программирования, однако этот метод был использован в языках более высокого уровня языком программирования Си.

Логически вектор представляет собой структуру данных с фиксированным числом пронумерованных элементов одного и того же типа.

Физически элементы вектора размещаются в ячейках памяти, расположенных подряд. Необходимое число байтов памяти для хранения одного элемента вектора называется слотом.

18. Структуры данных "запись", "таблица". Формальные правила построения записей. Примеры реализации записей.

Записи – структура данных, состоящая из фиксированного числа компонент, называемых полями, каждая из которых может иметь свой тип. Записи позволяют в удобной форме представлять ведомости, таблицы, картотеки, каталоги и лр. данные.

Таблицы – набор записей, с каждой из которых связано имя, называемое ключом. Поиск нужной записи в таблице производится по ее ключу. Основные операции с таблицами: найти запись, включить новую запись и исключить запись из таблицы.