- •Тема 11. Основы алгоритмизации и программирования
- •11.1 Алгоритмы. Алгоритмизация. Алгоритмические языки
- •11.1.1. Понятие алгоритма
- •11.1.2. Базовые алгоритмические структуры
- •11.1.3. Итерационные циклы
- •11.1.4. Вложенные циклы
- •11.1.5. Простейшие структуры данных
- •11.2. Примеры разработки алгоритмов
- •11.2.1. Линейные алгоритмы
- •11.2.2. Разветвляющиеся алгоритмы
- •11.2.3. Циклические алгоритмы
- •11.2.4. Алгоритмы со структурами вложенных циклов
- •11.2.5. Вспомогательные алгоритмы
- •11.2.6. Декомпозиция алгоритма
- •11.3. Технология подготовки и решения задач с помощью компьютера
- •11.4. Языки программирования
- •11.4.1. Алгоритмические языки
- •11.4.2. Принципы построения трансляторов
11.1.5. Простейшие структуры данных
Для того чтобы ясно представить как "работает" алгоритм, опишем простейший автомат, который предназначен для выполнения операций, предписанных этим алгоритмом.
В состав такого автомата входят:
память, состоящая из отдельных ячеек;
считывающая/записывающая головка;
процессор, т.е. устройство, способное выполнять операции, в том числе математические, и отдавать головке указания читать данные из ячеек или записывать данные в ячейки памяти автомата.
Головка, получив указание от процессора, может записывать в ячейку или считывать из нее одну константу.
В простейшем случае константой является любое арифметическое число. Например, 12, 0.78, 0, –45.33 и т. д. Константами могут быть такие строки символов, структуры данных и др.
Под простой переменной, или просто переменной будем понимать некоторую ячейку памяти, т.е. отдельное место для хранения одной константы. В отдельной ячейке за время работы алгоритма может побывать множество различных констант (отсюда название – переменная). Такими ячейками (электронными, магнитными, оптическими) снабжен реальный компьютер.
Переменные имеют буквенно-символьное обозначение. Например, 1, n, a, a1, b, H2 – переменные. Одновременно обозначение переменной является индексом ячейки, в которую будут записываться константы. Любая из таких констант называется значением переменной. Например, Z является переменной и адресом ячейки Z одновременно. С алгоритмической точки зрения понятия “переменная” и “адрес ячейки” памяти являются идентичными.
Запись вида Y: = 5.5 следует понимать так: записать константу 5.5 в ячейку с адресом Y (если до этой операции в ячейку была записана константа, то она будет затерта, а на ее место будет помещена константа 5.5). Произносить эту запись следует так: “переменной Y присвоить значение 5.5”.
Запись вида L: = M следует понимать так: прочитать константу, расположенную по адресу M и скопировать эту константу в ячейку с адресом L (при этом константа из ячейки M не удаляется, а остается такой, какой она была до чтения). Произносить эту запись нужно так: "переменной L присвоить значение переменной M (или просто: L присвоить M)".
Другой разновидностью переменных являются так называемые индексированные переменные или массивы. Массив – это некоторая совокупность ячеек, объединенная одним обозначением (массивом может быть одна ячейка). Всякий массив обязательно имеет размерность. Массивы бывают одномерными, двумерными, трехмерными и т.д.
Одномерный массив – это последовательность ячеек, расположенных в одну линию. Ниже приведен пример такого массива.
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
q= |
2.3 |
-6 |
0 |
4.4 |
-3 |
0 |
8.2 |
-4.7 |
Массив имеет имя q. Для того чтобы можно было отличить одну ячейку массива от другой ячейки этого же массива, их нумеруют. Нумерация ячеек обычно начинается с 1. Номер ячейки массива называется его индексом, а константа в ячейке – элементом массива. Теперь становится возможной работа с отдельной ячейкой такого массива. Например, команда q7: = 8.2 означает, что в 7-ю ячейку массива q надлежит записать константу 8.2. Команда r41:= q2 + q5 означает, что нужно сложить константы, записанные во 2-ю и 5-ю ячейки массива q, и результат записать в 41-ю ячейку одномерного массива r. Эту же операцию можно описать другими словами: 41-му элементу массива r присвоить значение суммы 2-го и 5-го элементов массива q.
Двумерный массив по расположению ячеек напоминает математическую матрицу:
|
1 |
2 |
3 |
4 |
5 |
6 |
||||||||||||||||||||||||
1 |
|
|||||||||||||||||||||||||||||
2 |
||||||||||||||||||||||||||||||
3 |
||||||||||||||||||||||||||||||
4 |
Элемент такого массива характеризуется двумя индексами: первый показывает строку, в которой расположена ячейка, второй – ее столбец. Например, команда d2, 5 = 43 означает, что в ячейку, размещенную на пересечении 2-й строки и 5-го столбца двумерного массива d, нужно записать константу 43.
Аналогично устроена структура массивов трех- и большей размерности.