1 Массивы

2 Опр. Массивом называется совокупность однотипных данных, связанных общим именем. Основные характеристики массива: 1. Имя массива 2. Тип компонентов массива 3. Размерность – количество измерений массива (одномерный, двумерный, трехмерный) 4. Порядок нумерации компонентов в массиве (с 1 до последнего) 5. Количество компонентов – размер массива

3 Основные классы задач, которые связаны с последовательной обработкой элементов массива: 1. Задачи ввода и вывода 2. Вычисления суммы, произведения, количества, среднего арифметического и т.п. 3. Поиск данных в массиве по заданному признаку, поиск максимального и минимального элементов 4. Изменение порядка и значений – удаление, вставка, перемещение элементов

4 Обобщенная схема работы с массивом: 1. Заполнение массива 2. Обработка массива 3. Вывод результата 3.1. вывод одиночного значения (например, сумма, произведение, количество элементов и т.п.) 3.2. вывод массива

5 Одномерный массив

6 1. Определение массива Введем обозначения: А – имя массива а[i] – элемент массива i – номер (индекс) элемента массива N – количество элементов в массиве

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

8 Вывод массива Последовательную обработку массивов позволяет обеспечить цикл с параметром, который осуществляет прямой доступ к каждому элементу массива.

9 2. Вычисления суммы, произведения, количества элементов массива Перед выполнением цикла необходимо задать начальное значение искомой величины. В цикле обработки массива искомая величина будет изменяться по определенному правилу.

10 3. Поиск элементов удовлетворяющих заданному условию Если элемент удовлетворяет условию поиска, то производится его обработка. Виды обработки: 1. Вывод элемента 2. Изменение его значения 3. Изменение некоторой другой величины (сумма, произведение, количество)

11 Шаблон блок-схемы

12 Результат – вывод элемента Найти все положительные элементы в массиве

13 Результат – изменение элементов массива Все положительные элементы в массиве умножить на 2

14 Результат – вычисляемая величина Найти сумму положительных элементов в массиве

15 4. Поиск минимального элемента Для поиска минимального элемента необходимо назначить некоторый эталон – переменную, которой заранее присваивается значение, например первого элемента. Поиск проводится путем последовательного сравнения всех элементов с эталоном min. Параллельно можно запоминать номер минимального элемента min_N.

16 Шаблон блок-схемы a[i] < min - первый минимальный элемент a[i] min – последний минимальный элемент

17 5. Поиск максимального элемента Для поиска максимального элемента необходимо назначить некоторый эталон – переменную, которой заранее присваивается значение, например первого элемента. Поиск проводится путем последовательного сравнения всех элементов с эталоном max. Параллельно можно запоминать номер максимального элемента max_N.

18 Шаблон блок-схемы a[i] > max - первый максимальный элемент a[i] max – последний максимальный элемент

19 6. Нахождение первого элемента в массиве, удовлетворяющего заданному условию. Возможные ситуации: 1. Нужный элемент есть в массиве 2. Нужного элемента нет в массиве Введем обозначения: х – искомый элемент nom – номер искомого элемента

20 1 вариант решения Обработка массива ведется с помощью цикла с параметром. Просмотр массива начнем с конца, в этом случае последний найденный элемент, удовлетворяющий условию, окажется в начале массива.

21 Шаблон блок-схемы Начальное значение nom возьмем равным N+1, на случай если нужных элементов нет. Минус данного варианта: проверить нужно все элементы не зависимо от места расположения нужного.

22 2 вариант решения Обработка массива ведется с помощью цикла с предусловием. Просмотр массива начнем с начала, если найдем подходящий, то поиск прекратим.

23 Шаблон блок-схемы Возможны два случая: Подходящий элемент есть в массиве, тогда i равно номеру элемента. Подходящего элемента нет в массиве, тогда i равно N+1 и по этому значению работа цикла прекращается.

24 1 вариант - с помощью цикла с параметром: Просмотр массива начнем с начала, в этом случае последний найденный элемент, удовлетворяющий условию, окажется в конце массива. 2 вариант - с помощью цикла с предусловием: Просмотр массива начнем с конца, если найдем подходящий, то поиск прекратим. 7. Нахождение последнего элемента в массиве, удовлетворяющего заданному условию.

25 1) Запоминаем в Х элемент стоящий на позиции i. 2) На его место ставим элемент с позиции j. 3) На место элемента с позиции j ставим Х. 8. Перестановка элементов в массиве X:=a[i]; A[i]:=A[j]; A[j]:=X;

26 Идея: Выделяется наименьший (или наибольший) элемент массива и перемещается в начало массива. Далее опять выделяется наименьший (или наибольший) из оставшихся и перемещается на второе место. И т.д. пока не будут отобраны все элементы. Если ищем наименьший – то сортируем по возрастанию, наибольший – по убыванию. 9. Сортировка массива – простой выбор

27 Сортировка по возрастанию

28 Необходимо удалить элемент с заданным номером nom. Тогда удаление осуществляется за счет последовательного сдвига всех элементов, начиная с позиции nom+1 на одну ячейку вправо. При выводе результата выводим только N-1 первых элементов, т.к. последнем месте осталось старое значение. 10. Удаление одного элемента в массиве

29 Удаление одного элемента

30 Необходимо удалить элементы удовлетворяющие некоторому условию. Введем переменную k – количество удалений, данная переменная будет динамически изменять размерность массива. Для работы будем использовать цикл с предусловием. 10. Удаление нескольких элементов в массиве