Вопрос 5: Определение алгоритма. Свойства алгоритма.

Алгоритм- фундоментальное понятие информатики. Он определяет способы или правила преобразования информации. Алгоритм- предписание, однозначно заданный процесс преобразования информации виде последовательности элементарных дискретных шагов, приводящих за конечное число их применения к результату.

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

Свойства алгоритма:

1) Дискретность:

Алгоритм состоит из дискретных шагов, выполнених которых переводит исходные данные в результат.

2) Определенность.

Каждый шаг алгоритма четко определен и всегда известно. Что делать дальше.

3) Конечность.

Необходимый результат должен быть получен за некоторое конечное число шагов.

4) Массовость.

Любой алгоритм разрабатывается для решения целого класса однотипных задач, отличающихся лишь исходными данными.

Вопрос 6: Массивы. Одномерные массивы.

Массив – это тип данных объединяющий фиксированное число элементов одного типа, называемого базовым типом. Каждый элемент массива имеет свой индекс, который используется для доступа к этому элементу. По этому можно выделить любой элемент массива и обращаться с ним как с переменной базового типа. Описывают массивы следующим образом:

Имя переменной массива : array[мин. Знач. Индекса...макс. Знач. Индекса]ofбаз. Тип;

Отдельные элементы массив записываются в виде:

Имя переменной массива [индекс], где индекс это константа, переменная или выражение целого типа, значение которого лежит в диапазоне от минимального значения индекса до максимального значения индекса. Одномерный массив – это массив, базовым типом которого является скалярный тип. Количество элементов одномерного массива (вектора), называется длинной или размером массива. Массиву можно присвоить значения другого массива, этого же типа. Это единственная допустимая операция над массивом, как единым целым. Арифметические действия, ввод и вывод выполняются над отдельными элементами массива.

Пример: Найти max элемент в массиве.

Const n=100;

Var a:array [1..n] of integer;

Max,x,I,imax:integer;

Begin

For i:=1 to n do a[i]:=random(n);

Max:=a[1]; imax:=1;

For i:=1 to n do

If a[i]>max then begin

Max:=a[i]; imax:I;

End;

Writeln(max,imax);

End.

Сортировка массивов и поиск элементов массивов.

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

Сортировка выбора элементов массива в порядке их возрастания выполняется следующим образом.

1. Установить номер наименьшего элемента массива.

2. Поменять местами первый и наименьший элемент массива.

3. Выполнить пункты 1 и 2 над оставшимися элементами массива.

4. Повторять пока остаток массива не сократится до одного элемента.

На каждом шаге алгоритма наименьший элемент из области поиска перемещается в уже отсортированную часть массива. За счет этого упорядоченная часть массива растет, а не упорядоченная сокращается на один элемент. Следовательно, для сортировки массива из nэлементов требуетсяn-1 шаг.

Const n=100

Var a:array [1..n] of integer;

Tmp,min,I,j,jmin:integer;

Begin

For i:= 1 to n do a[i]:=random(n)-50;

For i:= 1 to n-1 do

Min:=a[i]; jmin:=I;

For j:=I to n do

If a[j]<min then begin

Min:=a[j]; jmin:=j;

End;

Tmp:= a[jmin]; a [jmin]:= a[i]; a[i]= tmp;

End;

For i:= 1 to n do write(a[i],’’);

End.

Время выполнения одного шага прямо пропорционально размеру неупорядоченной части массива. Размер неупорядоченной части равен nв начале работыb2 в конце. Общее время сортировки выборомT=k*n+k(n-1)+…+k*3+k*2. Гдеk– некоторый коэффициент пропорциональности не зависящий отnи характеризующийся скоростью конкретной ЭВМ.

T=k*(n+2)*(n-1)/2≈c*n², гдеc– константа не зависящая отn. Полученная показывает как меняется продолжительность сортировки с изменением размера массива. Т.е. о временной сложности сортировки выбором говорят, что она квадратична, т.е. время сортировки пропорционально квадрату числа сортирующихся элементов.

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

В отличие от сортировки выбором количество шагов обменной сортировки зависит от первоначального значения массива. По этому оценим временную сложность алгоритма в худшем случае (массив отсортирован в обратном порядке), в лучшем случае (массив отсортирован), временная сложность алгоритма равна сложности одного шага. При обратном порядке чисел потребуется n-1 шаг, по крайней мере, один элемент будет выставлен на свое место. СледовательноT=(n-1)*t(n), гдеt(n) – временная сложность одного шага, зависящая отn,t(n)=k*n, следовательноT≈k*n², т.е. сложность обменной сортировки также квадратична.

Const n=100

Var a:array [1..n] of integer;

Tmp,min,I,j,jmin:integer;

Flag:boolean;

Begin

For i:= 1 to n do a[i]:=random(n)-50;

Flag:= true; I:=1;

While(i<n) and flag do begin

Flag:=false;

For j:=1 to n-1 do

If a[j] >a[j-1] then begin

Tmp:= a[j]; a[j]:=a[j+1]; a[j+1]:=tmp;

Flag:=true;

End;

I:=i+1;

End;

For I:=1 to n do

Write(a[i],’’);

End.

Кроме сортировки часто возникает задача поиска заданного элемента в массиве, при этом необходимо определить имеется ли такой элемент в массиве и если есть то какой его индекс.

Пример: Определить в массиве наличие заданного числа и вывести его индекс.

Const n=100;

Var a:array[1..n] of integer;

B,i:integer;

Flag:Boolean;

Begin read(b);

For i:=1 to n do a[i]:=random(n)-50;

Flag:=false; i:=0;

While(i<n) and not(flag) do begin

I:=i+1;

If a[i]=b then flag:=true;

End;

If flag then writeln(i) else writeln(‘net’);

End.

Многомерные массивы.

Если элементы массива сами являются массивами, получается структура называемая двумерным массивом (матрицей). Описывается матрица также, как и вектор, но в квадратных скобках указывается два диапазона изменения индекса, через запятую. Обращаются к элементам двумерного массива, указывая два индекса. Если указывать один, это будет понятно, как имя одномерного массива, входящего в матрицу. Считается, что первый индекс, обозначает номер строки, второй – номер столбца.

Подобным образом описываются трех, четырех, и т.д. массивы.