🗊Презентация Массивы. Основы алгоритмизации и программирования

МАССИВЫ

В математике и информатике массив называется одномерным, если для получения доступа к его элементам достаточно одной индексной перемен ной. В математике и информатике массив называется одномерным, если для получения доступа к его элементам достаточно одной индексной перемен ной.

Пример объявления несколько переменных типа массив: VAR mas_1: ARRAY[1..10] OF Real; mas_2: ARRAY[5 .. 16] OF Integer; sst: ARRAY[20..40] OF Char;

Пример: VAR Y:ARRAY[1..5] of integer; Объявлен массив, имя которого Y, содержащий 5 элементов целого типа. Каждому элементу массива соответствует отдельная ячейка памяти, обращение к которой возможно также как и к обычной ячейке, имеющей имя какой-либо переменной, т.е по имени.

Пример объявления массивов содержащих элементы различных типов, и индексы различных простых типов: VAR mas: array [1..15] of real; {описан массив из 15 вещественных чисел} www: array [(mon,tue,wed)] of integer; {описан массив из трёх целых чисел, индексы элементов массива имеют перечислимый тип и принимают значение названий дней недели mon, tue, wed} ast: array ['A'..'Z'] of boolean; {описан массив элементов логического типа, тип индексов - ограниченый символьный} art: array [(black,white)] of 11..20; {описан массив целых чисел с индексами black, white. Каждый элемент массива может принимать значения от 11 до 20} svz: array [byte] of integer; {описан массив из 256 целых чисел с индексами стандартного типа byte (от 0 до 256)}

Извлечения и присвоения в массивах В отличие от стандартных переменных массивы не могут обрабатываться целиком. Но Вы можете получить доступ к каждому элементу-ячейке массива. Это выполняется путём указания значения индекса в квадратных скобках. Так например, с помощью оператора mas[2]:=34; элементу массива с индексом 2 присваивается значение 34. Оператор Writeln(mas[2]); вызовет вывод на экран пользователя значение хранящегося в элементе-ячейке № 2 массива mas. Наряду с конкретным значением (конcтантой) в качестве индекса может быть использована переменная, например, при обработке массива поэлементно в рамках цикла "FOR ... TO ... DO". С помощью фрагмента программы FOR i:=1 TO 25 DO mas[i]:=0; всем элементом массива присваивается значение "0".

П Р И М Е Р 1: Дана последовательность реальных чисел s1 ... s10. Организовать массив для хранения этих чисел. Определить сумму этих элементов. PROGRAMM ex_1; VAR m: ARRAY[1..10] of real; {декларация массива} i: integer; {параметр цикла FOR} s: real; {сумма элементов} BEGIN FOR i:=1 TO 10 DO {заполнение массива} Begin Write('Введите элемент последовательности № ',i); Readln(m[i]); End; s:=0; {обнуление счётчика суммы} FOR i:=1 TO 10 DO s:=s+m[i]; {вычисление суммы} Write('Сумма элементов последовательности равна ',s); Readln; { пауза } END.

Пример 2: программа, которая сначала вводит 10 реальных чисел, организовывает их хранение в массиве, определяет количество положительных элементов и выдаёт сообщение на экран. PROGRAMM ex_2; VAR m: ARRAY[1..10] of real; {декларация массива} i: integer; {параметр цикла FOR} n: integer; {счётчик положительных эл-ов} BEGIN Writeln('Введите 10 элементов последовательности через пробел’); FOR i:=1 TO 10 DO {заполнение массива} Read(m[i]); n:=0; {обнуление счётчика п. эл-ов} FOR i:=1 TO 10 DO if m[i]>=0 then n:=n+1; {вычисление количества п. эл-ов} Write('Последовательность содержит ',n,' положительных эл-ов'); Readln; { пауза } END.

Пример 3:

Пример 3

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

ПОИСК МАКСИМАЛЬНОГО И МИНИМАЛЬНОГО ЭЛЕМЕНТОВ В МАССИВЕ.

Поиск элемента в неупорядоченном массиве VAR m: ARRAY[1..30] of real; {декларация массива} i: integer; {параметр цикла FOR} p: real; {значение искомого элемента} t: integer; {индекс (номер) иском. элемента} BEGIN FOR i:=1 TO 30 DO {заполнение массива} Begin Write('Введите элемент последовательности № ',i); Readln(m[i]); End; Write('Введите контрольное число '); Readln(p); t:=0; {допустим, что в массиве нет такого элемента} FOR i:=1 TO 30 DO if m[i]=p then {проверка нашего утверждения} begin t:=i; write('Эл. №',i,' равен искомому'); end; if t=0 then write('В массиве нет такого элемента'); Readln; { пауза } END.

Задания для самостоятельного выполнения Напишите программу, которая вводит с клавиатуры 20 реальных чисел, и организовывает их хранение в массиве. После этого определяет сумму элементов, значение которых больше среднего арифметического элементов массива. Напишите программу, которая вводит с клавиатуры 15 реальных чисел, организовывает их хранение в массиве и определяет разность между максимальным и минимальным элементом массива. Напишите программу, которая вводит с клавиатуры 15 реальных чисел, организовывает их хранение в массиве и определяет индексы (номера) элементов массива, значение которых равно значению первого элемента массива. Если такого элемента нет, вывести соответствующее сообщение на экран. Напишите программу, которая вводит с клавиатуры 10 целых чисел, организовывает их хранение в массиве и определяет количество чётных и количество нечётных элементов в массиве. Напишите программу, которая вводит с клавиатуры 30 реальных чисел и определяет среднее арифметическое первых десяти элементов, вторых десяти и последних десяти. После этого определяется максимальное и минимальное среднее арифметическое и выводится сообщение.

Задания для самостоятельного выполнения Сгенерировать 2 одномерных массива по 23 элемента в каждом. Вывести их на экран. Подсчитать, где больше сумма. Вывести суммы и соответствующее сообщение . Сгенерировать одномерный массив из 30 элементов в диапазоне от 1 до 20. Вывести его на экран. Определить сумму элементов больших 12, произведение элементов меньших 12 и вывести соответствующие результаты на экран. В группе 15 учащихся. Составить два массива, в 1-ом массиве -фамилии учащихся, во втором массиве- оценки по ОИВТ. Вывести значения массивов в следующем виде: ФИО, бал успеваемости. Дан одномерный массив, состоящий из 10 элементов. Получить новый массив, в котором будут сначала положительные, а затем отрицательные значения первого массива

Алгоритм сортировки выбором по возрастанию Очевидно, что первое место в массиве должен занять минимальный элемент массива, второе - наименьший из всех остальных, третий - наименьший из оставшихся и т.д. Для этого необходимо выполнить следующую последовательность действий: Определить минимальный элемент массива; Поменять его местами с первым элементом; Определить минимальный элемент среди оставшихся; Поменять его местами со вторым элементом и т.д.; Эта последовательность действий должна выполняться до тех пор, пока не будет определён последний минимальный элемент.

СОРТИРОВКА МАССИВА ПО ВОЗРАСТАНИЮ МЕТОДОМ ПРЯМОГО ВЫБОРА

СОРТИРОВКА МАССИВА ПО ВОЗРАСТАНИЮ МЕТОДОМ ПРЯМОГО ВЫБОРА

СОРТИРОВКА МАССИВА ПО ВОЗРАСТАНИЮ МЕТОДОМ ПРЯМОГО ВЫБОРА

Сортировка методом пузырька Алгоритм так называемой "пузырьковой" сортировки более оригинален и в большинстве случаев более эффективен. При использовании этого алгоритма весь массив просматривается несколько раз подряд. При каждом таком просмотре сравниваются последовательно только соседние элементы массива: сначала первый со вторым, потом второй с третьим, и в конце предпоследний с последним. Если при сравнении окажется, что предыдущий элемент больше следующего, они меняются местами. Так в результате одного последовательного просмотра элементы, значение которых больше, "всплывают" образно говоря на поверхность, т.е. ближе к концу массива. Если провести такой последовательный просмотр массива несколько раз, то "тяжёлые" элементы окончательно "всплывут" и массив окажется отсортированным. Такой просмотр необходимо выполнять до полной сортировки, т.е. пока при просмотре элементы не будут меняться местами. Для этого удобно организовать логическую переменную ind, и присваивать ей значение ложь в случае, если замена происходила хотя бы один раз. Если значением этой переменной останется истина, то просмотры необходимо прекратить.

Сортировка массива целых чисел по возрастанию методом «пузырька» CONST SIZE=5; {размер массива} Var M:array[1..SIZE] of integer; i:integer; buf: integer; {буфер, используемый при обмене элементов} {массива} ind:boolean; Begin writeln(‘ Введите в одной строке ’,SIZE,’ целых чисел’); for i:=1 to SIZE do read(m[i]); writeln(‘ Сортировка’);

Сортировка массива целых чисел по возрастанию методом «пузырька» REPEAT ind:=true; {предположим, что массив уже отсортирован} FOR i:=1 TO SIZE-1 DO {цикл для организации просмотра} if m[i]>m[i+1] then {сравнение двух соседних элементов} begin buf:=m[i]; {меняем соседние элементы местами} m[i]:=m[i+1]; m[i+1]:=buf; ind:=false; {как оказалось, массив неотсортирован} end; UNTIL ind; {выполняем просмотры пока ind=false} {вывод отсортированного массива} writeln(‘ Массив отсортирован’); for i:=1 to SIZE do write(m[i]:4); readln; End.

Задания для самостоятельного выполнения 1. Организуйте массив, содержащий 20 различных целых чисел. После этого элементы массива упорядочиваются по убыванию и содержимое отсортированного массива выводится на экран. 2. Организуйте массив, содержащий 20 различных целых чисел. После этого 10 первых элементов массива упорядочиваются по возрастанию, а 10 последних элементов по убыванию. Содержимое отсортированного таким образом массива выводится на экран. 3. Организуйте массив, содержащий 15 различных целых чисел. После этого отдельно первых 5 элементов, вторых 5 элементов и последних 5 элементов сортируются по возрастанию. Содержимое отсортированного таким образом массива выводится на экран. 4. Создайте массив, содержащий 10 различных целых чисел. Содержимое массива сортируется по возрастанию, и после этого определяются минимальный и максимальный элементы массива.

Поиск элемента в упорядоченном массиве Рассмотрим наиболее часто встречающуюся задачу поиска необходимого элемента в отсортированном массиве, и алгоритм её решения. Дан отсортированный по возрастанию массив вещественных чисел A состоящий из n элементов. Определить, содержит ли данный массив число B, и если содержит, то определить номер (индекс) данного элемента в массиве. Предположим, что в массиве A имеется элемент, равный B, т.е. существует такой индекс p, что A[p]=B. По результату любого сравнения A[s]<B (1<s<n) мы сразу определяем, лежит ли p в диапазоне от 1 до s, или же в диапазоне от s+1 до n: второе будет иметь место, если неравенство A[s]<B справедливо, а первое - если не справедливо. Это свойство данного сравнения используется в алгоритме деления пополам.

Алгоритм деления пополам Первоначально номера крайних элементов массива 1 и n берут в качестве границ поиска элемента; далее, до тех пор, пока границы не совпадут, шаг за шагом сдвигают эти границы следующим образом: сравнить B с A[s], где s - целая часть среднего арифметического границ; если A[s]<B, то заменить прежнюю нижнюю границу на s+1, оставив верхнюю границу без изменения, иначе оставить без изменения нижнюю границу, а верхнюю границу заменить на s. Поиск закончится когда границы совпадут.

Алгоритм деления пополам Var a:array[1..10] of integer; b: integer; {образец для поиска} p,q,s: integer; {номера верхнего, нижнего и среднего элементов массива} i: integer; f:boolean; {признак совпадения с образцом} Begin writeln(‘ Введите в одной строке 10 целых чисел’); for i:=1 to 10 do read(a[i]); writeln(‘ Введите образец для поиска (целое число)’); Readln(b); p:=1; q:=10; f:=false;

Алгоритм деления пополам Repeat s:=(p+q) div 2; if a[s]=b then f:=true else {в какой части, в верхней или нижней, может находиться искомый элемент?} if b>a[s] then p:=s+1 else q:=s; Until (p>q) or f; If f then writeln(‘совпадение с элементом номер ‘, s) else writeln(‘образец не найден’); Readln; End.

Задания для самостоятельного выполнения Напишите программу, которая организует хранение в массиве 15 различных введённых с клавиатуры целых чисел. Содержимое массива сортируется по возрастанию. После этого, с клавиатуры запрашивается контрольное число, наличие которого в массиве необходимо проверить. Номер элемента массива, в положительном случае, выводится на экран монитора. Напишите программу, которая организует хранение в массиве 10 различных целых чисел. Содержимое массива сортируется по возрастанию. После этого, с клавиатуры вводится контрольное число. Наличие которого в массиве необходимо проверить. В положительном случае замените элемент массива, равный контрольному числу, нулём. Содержимое массива выводится на монитор.

Задания для самостоятельного выполнения Напишите программу, которая организует хранение в массиве 15 различных введённых с клавиатуры целых чисел. Содержимое массива сортируется по убыванию. После этого, с клавиатуры запрашивается контрольное число, наличие которого в массиве необходимо проверить. На экран монитора выводится содержимое массива до "контрольного числа" включительно. Дан массив из 10 целых чисел. Отсортируйте его и найдите в нём контрольное число. Все элементы до контрольного числа замените на противоположные.

Двумерные массивы Двумерный массив в Паскале трактуется как одномерный массив, тип элементов которого также является массивом (массив массивов). Положение элементов в двумерных массивах Паскаля описывается двумя индексами. Их можно представить в виде прямоугольной таблицы или матрицы. Рассмотрим двумерный массив Паскаля размерностью 3*3, то есть в ней будет три строки, а в каждой строке по три элемента:

Рассмотрим двумерный массив А Объявите данный массив.

Пример 1:Дана матрица действительных чисел размером 3x5. Вычислить сумму элементов матрицы. PROGRAM EX_1; CONST n=3; {Количество строк} m=5; {Количество столбцов} TYPE mas=array[1..n,1..m] of real; VAR b: mas; {Массив} i: integer; {Индекс строки} j: integer; {Индекс столбца} s: real; {Сумма} BEGIN {Ввод значений матрицы ---------------------} Writeln('Введите значения элементов матрицы:'); for i:=1 to n do for j:=1 to m do read(b[i,j]); {Вычисление суммы ----------------} s:=0; for i:=1 to n do for j:=1 to m do s:=s+b[i,j]; writeln('Сумма = ',s); END.

Задания для самостоятельного выполнения. Сгенерировать матрицу целых чисел в диапазоне от -5 до 5 размером 5x3. Заменить все отрицательные элементы матрицы на нули. Вывести содержимое матрицы до обработки и после обработки. Дана матрица целых чисел размером 4x4. Увеличить все чётные элементы на 16, а нечётные элементы увеличить втрое. Вывести на экран содержимое обработанной матрицы. Дана матрица целых чисел размером 3Х4. Поменять местами 1 и 4 столбик. Вывести на экран содержимое обработанной матрицы.

Составить программу, которая в двумерном массиве случайных чисел находит в каждой строке наибольший элемент и записывает его в одномерный массив. m – количество строк в двумерном массиве и длина одномерного массива; n – количество столбцов; A[1..m,1..n] - двумерный массив; B[1..m] – одномерный массив max – вспомогательная переменная для нахождения наибольшего элемента в каждой строке.

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

Квадратная матрица Квадратная матрица- это двумерный массив, в котором количество строк равно количеству столбцов. Обращение к элементу происходит также как и в обычном двумерном массиве A[i,j].

Основные свойства квадратной матрицы 1. Квадратные матрицы имеют главную и побочную диагонали. Например, для матрицы А на главной диагонали лежат элементы 1,4,9, на побочной - 45,4,12. Если i = j - элементы расположены на главной диагонали; i > j - элементы расположены ниже главной диагонали; i < j - элементы расположены выше главной диагонали; i > j - элементы расположены на главной диагонали и ниже; i< j - элементы расположены на главной диагонали и выше; i+j = n+1 - элементы расположены на побочной диагонали; i+j < n+1 - элементы расположены над побочной диагональю; i+j > n+1 - элементы расположены под побочной диагональю

Основные свойства квадратной матрицы 2. Квадратная матрица, у которой все элементы, исключая элементы главной диагонали, равны нулю, называется диагональной матрицей

Написать программу, позволяющую получить матрицу следующего вида:

Написать программу, позволяющую получить матрицу следующего вида:

Написать программу, позволяющую получить матрицу следующего вида:

Написать программу, позволяющую получить матрицу следующего вида:

Написать программу, позволяющую получить матрицу следующего вида:

На основе изученных блоков сформировать и распечатать матрицы следующего вида:

Задания для самостоятельной работы