🗊Презентация Работа с одномерными и двумерными массивами

Лекция 4

Массив последовательность логически связанных элементов одного типа, которым присвоено одно имя. Размерность массива – это количество индексов у каждого элемента массива. TYPE <имя типа> = ARRAY [индекс] OF <тип эл-тов >; Buffer1: ARRAY [1..10] of Integer; Buffer2: ARRAY [1..10, 1..10] of Integer;

Массивы могут быть Одномерные (вектор) Многомерные (матрицы) Открытые

Размер массива

Массив можно создать несколькими способами: const n = 20; m=10; type months = (jan, feb, mar, apr, may, jun, jul, aug, sep, oct, nov, dec); years = 1900..2100; people = array[years] of longint; arr = array[1..4, 1..3] of integer; сonst cords: arr = ((1,-1,3), (0,0,0), (1,4,0), (4,-1,-1)); var growth: array[months] of real; hum: people; notes: array[1..n] of string; Narod:array [1..m] people; matrix = array [1..n, 1..m] of integer;

Инициализация массива Если значения элементов массива определены до начала работы программы Если исходные данные необходимо внести с клавиатуры в процессе выполнения программы Прямое присвоение в теле программы значений элементам массива

Инициализация массива CONST A: ARRAY [1..10] OF REAL = (0.1, -15.3, 7, 0, -11.89, 4, -78,11.2, 1,0.01); { A[1]=0.1, A[2]=-15.3 … A[10]=0.01} M: ARRAY [1..5, 1..2] OF REAL = ((0.1, -15.3), (7, 0), (-11.89,4), (-78,11.2), (1,0.01)); {M[1,1] = 0.1, M[1,2] = -15.3, M[2, 1] = 7, M[2, 2] = 0, ... M[5,1]=1, M[5, 2]= - 0.01}

Инициализация массива CONST  M = 3; N = 4; VAR     A: ARRAY[ 1.. М, 1.. N] OF REAL; begin … FOR I := 1 ТО М DO FOR J:= 1 TO N DO READ(A[I,J]); … end.

Инициализация массива FillChar( var V; Count: Word; B: Byte ); Для обнуления массива A[1..10] of Real можно записать:    FillChar(A, 40, 0); или FillChar(A, SizeOf(A), 0); FOR      I := 1 ТО М DO         FOR J:=l TO N               DO A[I,J]:=0;

Обращение к элементам массива var ch: array [1..11] of char; i: integer; begin for i := 1 to 11 do read (ch[i]); for i := 1 to 11 do write (ch[i]:3); readln end.

Открытый массив < имя_массива>: array of <тип эл-тов>; mas2: array of integer;

Вычисление индекса массива Пример программы с ошибкой массива Паскаля Program primer _ error ;  Type  vector=array [1..80] of word;  var     n: integer;     a: vector;  begin     n:=45;     a[n*2]:=25;  end .

Заполнение матрицы «по спирали»

Поиска максимального элемента (Max) и его номера (Nmax) в массиве X, состоящем из n элементов

Удаление элемента из массива

Пример: Удалить из массива X(n) отрицательные элементы.

Вставка элемента

Вставка элемента

Определить, есть ли в заданном массиве серии элементов, состоящих из знакочередующихся чисел. Если есть, то вывести на экран количество таких серий.

{ {

Определить является ли данный массив возрастающим PROGRAM z_array; USES crt; Var A: array[1..100] of real; N,i:byte; Flag: boolean; begin clrscr; writeln(' Количество элементов массива'); readln(N); for I := 1 to N do begin write('[', I ,']= '); readln(A[I]); end;

Свойства элементов матрицы если номер строки элемента совпадает с номером столбца (i=j) - элемент лежит на главной диагонали матрицы; если номер строки превышает номер столбца (i>j), то элемент находится ниже главной диагонали; если номер столбца больше номера строки (i<j), то элемент находится выше главной диагонали; элемент лежит на побочной диагонали, если его индексы удовлетворяют равенству i+j–1=n; неравенство i+j–1<n характерно для элемента, находящегося выше побочной диагонали; соответственно, элементу, лежащему ниже побочной диагонали, соответствует выражение i+j–1>n.

Найти сумму элементов матрицы, лежащих выше главной диагонали

Найти седловой элемент(ы) и его координаты, либо сообщить, что таковой нет Program z_array; uses crt;  var A: array [1..100,1..100] of real;      N,  M,  I,  J,  K, L:byte;      Flag1,Flag2:boolean;  begin  write(‘число строк ');   readln(N);   write(‘ число столбцов ');   readln(M);   L:=0;  for I := 1 to N do    for J := 1 to M do    begin     write('[', I,',', J,']= ');     readln(A[I, J]);    end; 

Транспонирование матрицы

Понятие задачи и подзадачи Исходные данные называют параметрами задачи. для решения квадратного уравнения ax2 + bx + c = 0, определяются три параметра - a, b и c. для нахождения среднего арифметического параметры - количество чисел и их значения.

Понятие задачи и подзадачи

Найти самую тяжелую монету из 10 монет. "Самая тяжелая монета" из 1 монеты, "Самая тяжелая монета" из 2 первых монет, "Самая тяжелая монета" из 3 первых монет, ... "Самая тяжелая монета" из 9 первых монет. все они основываются на одной подзадаче: найти самую тяжелую из 2 монет.

Рекуррентное соотношение соотношение, связывающее одни и те же функции, но с различными аргументами. Правильное рекуррентное соотношение -соотношение, у которых количество или значения аргументов у функций в правой части меньше количества или значений аргументов функции в левой части соотношения. Если аргументов несколько, то достаточно уменьшения одного из аргументов.

Метод динамического программирования метод оптимизации, приспособленный к операциям, в которых процесс принятия решения может быть разбит на этапы (шаги): 1. Разбиение задачи на подзадачи меньшего размера. 2.   Построение таблицы решений. 3.   Решение задачи с помощью построенной таблицы

Динамическое программирование (ДП)  - метод решения задач путем составления последовательности из подзадач таким образом, что: первый элемент последовательности (возможно несколько элементов) имеет тривиальное решение последний элемент этой последовательности - это исходная задача каждая задача этой последовательности может быть решена с использованием решения подзадач с меньшими номерами Для T составляется {T1,T2,T3,…,Ti,…,Tn}, причем T=Tn и Ti=F(Ti-1)

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

Определить, сколькими различными способами можно подняться на 10-ю ступеньку лестницы, если за один шаг можно подниматься на следующую ступеньку или через одну. Пусть K(10) -количество способов подъема на 10 ступеньку, K(i) количество способов подъема на i-ю ступеньку. K(i) = K(i - 2) + K(i - 1), при i≥3 K(1) = 1, K(2) = 2.

В заданной числовой последовательности  A[1..N] определить максимальную длину последовательности подряд идущих одинаковых элементов

Для заданной числовой последовательности A[1.. N] найти максимальную длину строго возрастающей подпоследовательности элементов (не обязательно подряд идущих, но обязательно в порядке увеличения индексов) последовательности A.

Составить программу подсчета для натурального числа n количества всех его делителей. Пусть dn(n) и dnx(n,x) - функции для решения исходной и обобщенной задач. dn(n)=dnx(n,n).

В таблице размера m*n, с элементами 0 и 1 найти квадратный блок максимального размера, состоящий из одних единиц. Пусть T[i,j]- функция, значение которой равно размеру максимального квадратного блока из единиц, правый нижний угол которого расположен в позиции (i,j). T[1,j] = a[1,j], T[i,1] = a[i,1]. T[i,j] =0, если A[i,j] = 0, T[i,j] = min(T[i-1,j],T[i,j-1],T[i-1,j-1]) +1, при A[i,j] = 1.

const m=5;n=6; const m=5;n=6; var a:array[1..M,1..N] of integer T:array[1..n,1..N] of integer; J,I,MAX,AMAX,BMAX:INTEGER; begin FOR I:=1 TO M DO FOR J:=1 TO N DO BEGIN T[1,J]:=A[1,J]; T[I,1]:=A[I,1]; END; FOR I:=2 TO M DO FOR J:=2 TO N DO IF A[I,J]=0 THEN T[I,J]:=0 ELSE Begin T[I,J]:= T[i-1,j]; IF T[I,J] > T[i,j-1] THEN T[I,J]:= T[i,j-1] ; IF T[I,J]>T[i-1,j-1] THEN T[I,J]:= T[i-1,j-1] ; T[I,J]:= T[I,J] +1; end; MAX:=1; AMAX:=1; BMAX:=1; FOR I:=2 TO M DO FOR J:=2 TO N DO IF T[I,J]>MAX THEN BEGIN MAX:=T[I,J]; AMAX:=I; BMAX:=J;END; WRITELN(‘RASMER_BLOKA:’,MAX,’KOORDINAT;’, AMAX:5, BMAX:5); readln; end.