Схемы перебора элементов массива.

· Направление перебора

· Количество одновременно рассматриваемых элемента

· Характер изменения индекса элементов (арифметическая прогрессия, геометрическая, нелинейная)

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. Включение и исключение элементов из стека.