Схемы перебора элементов массива.
· Направление перебора
· Количество одновременно рассматриваемых элемента
· Характер изменения индекса элементов (арифметическая прогрессия, геометрическая, нелинейная)
1. По одному, от начала к концу
Const n = 100;
Var a:array [1..n] of real;
For i:=1 to n do
Обработка (a[i]);
2. По одному, от конца к началу
3. По одному, от концов к середине
I:=1; j:=n;
While i<=j do
If на предыдущем шаге обработан a[i]
Then begin
Обработать a[j];
J:=j-1
End
Else begin
Обработать a[i]; i:=i+1;
End;
!*использовать флаги*!
4. По одному, от середины к концу
M:=(n+1) div z;
i:=m;
j:=m+1;
while (i>=1) and (j<=n) do
if на предыдущем шаге обработали a[i]
then begin
обработать a[j];
j:=j+1
else begin
обработать a[i];
i:=i-1;
b:=true;
end;
5. По одному, с концу, чётные
6. Обработка соседей
For i:=1 to n-1 do
Обработать a[i], a[i+1]
For i:=2 to n do
Обработать a[i-1]. a[i]
ОБЩИЙ ВИД:
For i:=1 to n-k+1 do
Обработать a[i],a[1],…,a[i+k-1]
For i:=k to n do
Обработать a [i-k+1], … , a[i-1], a[i];
Классы задач на массивах. Правила решения задач соответствующих классов.
Существует 4 класса задач:
1 . Однотипная обработка всех или указанных элементов массива
Требуется:
· Определить схему перебора элементов массива
· Определить действия которые нужно выполнить для каждого элемента, и они встраиваются внутрь схемы
2 .Задачи в результате выполнения которых меняется последовательность элементов массива или их структура.
Требуется:
· Определить границы изменения
· Встраиваются в конкретную схему
3 . Обработка нескольких массивов одновременно или несколько подмассивов одного и того же массива.
Требуется:
· Определить схему обработки для каждого массива
· Для каждого массива определяется свой индекс
· Отслеживается чтобы индекс не вышел за границы вычисления
Синхронная обработка – одним и тем же индексом можно управлять всеми массивами
Асинхронная – по значению 1-го индекса нельзя вычислить значение другого.
4 . Поисковые задачи
· Рассматриваются все элементы массива и определяется первый который будет совпадать с указанным значением.
Схемы решении поисковых задач: -
Линейный поиск:
Const n =10 ;
Type vector: array [ 1..n] of integer;
…
Function line_search ( a: vector; x: integer ): integer;
Var q: boolean; i: integer;
Begin
Q: = false;
I:= 1;
While ( I <= n ) and (not q ) do
If a [i] = x then q:= true
Else i:= i+1;
If q then line_search := i
Else line_search := -1;
End;
Поиск с барьером
Барьер – дополнительный фиктивный элемент который располагается в начале или в конце массива
Const n=10;
Type vector: array [ 1..n + 1] of integer;
…
Function line_search ( a: vector; x: integer): integer;
Var I : integer;
Begin
A [ n+1] := x;
I:= 1;
While a[i] <> x do i:= i+1;
If I < n+1 then line_search:= I
Else line_search := -1 ;
End;
Двоичный поиск ( методом деления пополам)
Const n =10 ;
Type vector: array [ 1..n] of integer;
…
Function binary_search ( a: vector; x: integer ): integer;
Var I, r ,m : integer; Q: Boolean;
Begin
I:= 1;
R:= n;
Q:= false;
While ( i< r ) and ( not q ) do
Begin
M:= ( l + r ) div 2;
If a [m] = x then q:= true
Else if a[m] < x then L:= m
Else r:= m;
End;
If q then binary_search :=m
Else binary_search := -1;
End;
Понятие списка. Реализация операций со списками.
Список- динамическая структура данных которая позволяет организовать связанную последовательность динамических переменных.
Динамические структуры данных используют тогда когда данные меняют свои размеры во время выполнения программы.
Линейный список – последовательность узлов Х 1, Х2 , …Хn ,…, где n- больше или равно 0 , структурные св-ва которых ограничиваются линейным порядком расположения узлов.
Самым простым способом организации списков – это массив. ( type list = array [1..n] of базовый тип)
Основные операции над списками :
· Построение списка
· Включение элемента в список
· Исключение элемента из списка
· Копирование элемента
· Разбиение списка на 2 и более
· Объединение списка
· Нахождение элемента с заданными значениями.
· Печать списка.
При использовании массивов операции исключения элементов приводит к необходимости сдвига инфор-ции оставшейся части массива при добавлении аналогично . При включении нового элемента может оказаться что все элементы массива уже заполнены и включать новый элемент не куда. Поэтому создание списков осуществляется с использованием связного распределения
Списки
type Spisok=record
inf:real;
next:TSpisok;
end;
TSpisok=^Spisok;
Списки.Обход(нерекурс.вар.):
procedure Browse(head:TSpisok);
begin while head<>nil do begin
write(head^.inf);head:=head^.next;
Списки.Обход (рекурс.вар.):
procedure browse(head:TSpisok);
begin if head<>nil then begin
write(head^.inf);browse(head^.next);
Списки.Подсчёта кол-ва элем-ов:
function ength(head:TSpisok):integer;
begin if head<>nil then length:=1+length(head^.next)
else length:=0; end;
Списки.Поиск по значению:
function Find(x:real;head:TSpisok): TSpisok; begin if head<>nil then begin while (head<>nil) and (head^.inf<>x)do head:=head^.next; Find:=head;end
else Find:=nil;end;
function find(x:real; head:TSpisok): TSpisok; begin if head<>nil
then if head^.inf<>x then find:=find(x;head^.next) else find:=head; else find:=nil;end;
Списки.Вставка в список:
procedure Insert(p:TSpisok;x:real;var head:TSpisok); var q:TSpisok; begin
new(q); g^.inf:=x; if head<>nil then begin q^.next:=p^.next; p^.next:=q;
end else begin g^.next:=nil;head:=q;
Списки.Вставка в начало:
procedure Insert1(var head:TSpisok; x:real); var q:TSpisok; begin new(q);
q^.inf:=x; if head<>nil then begin
q^.next:=head; head:=q; end else begin g^.next:=nil; head:=q; end;
Списки.Вставка в конец:
procedure Insert2(var head:TSpisok; x:real); var p,q:TSpisok; begin
new(q); q^.inf:=x; if head<>nil
then begin q^.next:=nil; p:=head;
while p^.next<>nil do p:=P^.next;
p^.next:=q end else begin
g^.next:=nil; head:=q; end; end;
Списки.Удаление из списка:
procedure delete(var head:TSpisok; var p,q:TSpisok); begin if head<>nil
then begin q^.next:=p^.next;
dispose(p); end; end;
Списки.Удаление из начала:
procedure delete1(var head:TSpisok);
var q:TSpisok; begin if head<>nil
then begin q:=head; head:=head^.next; despose(q); end;
Списки.Удаление из конца:
procedure delete2(var head:TSpisok);
var p,q:TSpisok; begin if head<>nil
then begin q:=head; while q^.next<>nil do begin p:=q;
q:=q^.next; end; p^.next:=nil;
dispose(q); end; end;
Списки.Удал. из любого места:
procedure Delete(var head:TSpisok; q:TSpisok); var p:TSpisok; begin
if q=head then head:=q^.next
else begin p:=head;while p^.next<>q do p:=p^.next; p^.next:=q^.next;
end; dispose(q); end;
Списки.Уничтожение списка:
procedure Destroy(head:TSpisok);
var d:TSpisok; begin while head<>nil do begin d:=head^.next;
dispose(head); head:=d; end;
head:=nil; end;
procedure destroy(head:TSpisok);
var d:TSoisok; begin if head<>nil do
begin d:=head^.next; dispose(head);
destroy(d); head:=nil; end; end;
Стек - такой последовательный список с переменной длиной, включение и исключение элементов из которого выполняются только с одной стороны списка, называемого вершиной стека. Применяются и другие названия стека - магазин и очередь, функционирующая по принципу LIFO (Last - In - First- Out - "последним пришел - первым исключается").
Основные операции над стеком - включение нового элемента (английское название push - заталкивать) и исключение элемента из стека (англ. pop - выскакивать).
Полезными могут быть также вспомогательные операции:
· определение текущего числа элементов в стеке;
· очистка стека;
· неразрушающее чтение элемента из вершины стека, которое может быть реализовано, как комбинация основных операций:
x:=pop(stack); push(stack,x).Для наглядности рассмотрим небольшой пример, демонстрирующий принцип включения элементов в стек и исключения элементов из стека. На рис. 4.1 (а,б,с) изображены состояния стека:
· а). пустого;
· б-г). после последовательного включения в него элементов с именами 'A', 'B', 'C';
· д, е). после последовательного удаления из стека элементов 'C' и 'B';
· ж). после включения в стек элемента 'D'.
Рис 4.1. Включение и исключение элементов из стека.