Сдам Сам

ПОЛЕЗНОЕ


КАТЕГОРИИ







Оператор безусловного перехода (go to)





Оператор безусловного перехода (go to) означает "перейти к…" и применяется в случаях, когда после выполнения некоторого оператора надо выполнить не следующий по порядку, а какой-либо другой, отмеченный меткой оператор. Метка объявляется в разделе описания меток и может содержать как цифровые, так и буквенные символы. Например:

gо to 999;

gо to EndBlock;

При использовании оператора go to необходимо помнить, что областью действия метки является только тот блок, в котором она описана. Передача управления в другой блок запрещена.

Использование безусловных передач управления в программе считается теоретически избыточным и подвергается серьезной критике, так как способствует созданию малопонятных и трудно модифицируемых программ, которые вызывают большие сложности при отладке и сопровождении. Поэтому рекомендуется минимальное использование оператора go to с соблюдением следующих правил:

• следует применять операторы перехода (если кажется невозможным обойтись без них) для передачи управления только вниз (вперед) по тексту программы; при необходимости передачи управления назад следует использовать операторы цикла;

• расстояние между меткой и оператором перехода на нее не должно превы­шать одной страницы текста (или высоты экрана дисплея).

Оператор вызова процедуры

Оператор вызова процедуры служит для активизации предварительно опреде­ленной пользователем, или стандартной, процедуры.

Например:

ClrScr; {Вызов стандартной процедуры очистки экрана}

InitWotrk(True); {Вызов пользовательской процедуры}

 

Пустой оператор.

Пустой оператор не содержит никаких символов и не выполняет никаких действий. Пустому оператору соответствует отсутствие записи на том месте, где по правилам должен быть какой-нибудь оператор. После него можно ставить символ точки с запятой, например:

А:=В;

R:=2;

;

K:=7.2;

Здесь третий оператор является пустым.

Структурные операторы

Структурные операторы представляют собой конструкции, построенные из операторов по строго определенным правилам. Все структурные операторы можно разделить на три группы: составные, условные, повтора.

Составной оператор

Составной оператор представляет собой группу из произвольного числа операторов, отделенных друг от друга точкой с запятой, и ограниченную операторными скобками begin и end. Синтаксическую диаграмму составного оператора можно представить в виде следующей схемы:

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

2.2. Условные операторы

Условные операторы предназначены для выбора к исполнению одного из воз­действий (операторов) в зависимости от некоторого условия (при этом одно из действий может быть пустым, т.е. отсутствовать). В качестве условий выбора используется значение логического выражения. В Турбо Паскале имеются два условных оператора: if и case.

Оператор условия if.

Оператор условия if является одним из самых популярных средств, изменяющих естественный порядок выполнения операторов программы. Синтаксическая диаграмма оператора условия if выглядит таким образом:

Как видно из диаграммы, он может принимать одну из следующих форм:

if <условие> then <оператор 1>

ЕСЛИ <условие> ТО <оператор1>

else <оператор 2>

ИНАЧЕ<оператор 2>

if <условие> then <оператор>

ЕСЛИ <условие> ТО <оператор>

Условный оператор выполняется следующим образом. Сначала вычисляется выражение, записанное в условии. В результате его вычисления получается значение булевского типа. В первом случае, если значение выражения есть True (истина), выполняется <оператор1>, указанный после слова then (TO). Если результат вычисления выражения в условии есть False (ложь), то выполняется <оператор2>. Во втором — если результат выражения True, выполняется <оператор>, если False — оператор, следующий сразу за оператором if. Операторы if могут быть вложенными. Например:

IF X<0 THEN Y:=X+1 ELSE Y:=2*X

Оператор выбора case

Если один оператор if обеспечивает выбор из двух альтернативно, то оператор выбора case позволяет сделать выбор из произвольного числа имеющихся вариантов. Оператор выбора относится к сложным и имеет следующую форму записи:

 

CASE < выражение > OF

Константа 1: оператор 1;

Константа 2: оператор 2;

….

Константа N: оператор N;

END

Здесь CASE (в случае), OF (из), END (конец) – служебные слова.

Оператор выбора действует следующим образом: если значение выражения равно одной из констант, то выполняется соответствующий ей оператор. Затем управление передается за пределы оператора выбора. Если значение выражения не совпадает ни с одной константой, то управление передается за пределы группы.

При использовании оператора выбора case должны выполняться следующие правила:

1. значение выражения «переключателя», записанного после служебного слова case, должны принадлежать дискретному типу, для целого типа они должны лежать в диапазоне integer.

2. все константы, предшествующие операторам альтернатив, должны иметь тип, совместный с типом выражения.

3. все константы в альтернативах должны быть уникальны в переделах оператора варианта, диапазоны не должны пересекаться и не должны содержать констант, указанных в данной или других альтернативах.

Например: Ввести номер дня недели и вывести соответствующий ему день недели на русском языке.

Program Day_week;

Var

Day: byte;

Begin

Write (‘vvedite nomer:’);

Readln (Day);

Case Day of {вычисление значения селектора и выбор}

1: Writeln (‘понедельник’);

2: Writeln (‘вторник’);

3:Writeln (‘среда’);

4: Writeln (‘четверг’);

5: Writeln (‘пятница’);

6: Writeln (‘суббота’);

Else

Writeln (‘воскресенье’);

end;

End.


2.3. Операторы повтора.

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

Если в программе возникает необходимость неоднократно выполнять некоторые операторы, то используются операторы повтора (цикла). В языке Паскаль различают три вида операторов цикла: while, repeat, for. Они используются для организации циклов различных типов. Выражение, употребляющее повторения, должно иметь булевский тип. Если число повторений оператора (составного оператора) заранее неизвестно, а задано лишь условие его повторения (или окончания), используются операторы while, repeat. Оператор for используется, если число повторений заранее известно.

Оператор while.

Оператор while (пока) часто называют оператором цикла с предварительным условием (с предусловием). Используется в тех случаях, когда заранее неизвестно число повторений цикла.

Форма записи оператора цикла с предусловием имеет вид:

While <логическое выражение> DO

BEGIN

<операторы циклической части программы>

END

Здесь While (пока) и DO (выполнить) – служебные слова.

Оператор цикла действует так: сначала проверяется значение логического выражения. До тех пор пока оно истинно, выполняются операторы циклической части. Как только оно становится ложным – выход из цикла. Если изначально значение логического выражения ложно, то операторы циклической части не выполняются ни разу. Операторы циклической части, заключенные в операторные скобки BEGIN – END представляют собой составной оператор.

Примером может служить программа, производящая суммирование десяти произвольных введенных целых чисел.

Program Summ;

Const

Limit = 10 {ограничение на количество вводимых чисел}

Var

Count, Item, Sum: integer;

Begin

Count:=0; {счетчик чисел }

Sum:=0; { сумма чисел }

while (Count < Limit) do {условие выполнения цикла}

Begin

Count:=Count+1;

While(‘ введите ‘, Count,’- целое число: ‘);

Readln (Item); {ввод очередного числа с клавиатуры }

 


Sum:= Sum + Item;

end;

Writeln (‘ сумма введенных чисел равна’,Sum);

End.

В данном примере в разделе описания констант описана константа Limit=10, задающая ограничения на количество вводимых чисел. В разделе описания переменных описаны переменные Count, Item, Sum целочисленного типа.

В начале выполнения программы обнуляются значения счетчика введенных чисел Count и их суммы.

Оператор повтора.

Оператор цикла с последующим условием.

Цикл с постусловием, как правило, используется в тех случаях, когда заранее неизвестно число повторений цикла. Оператор цикла имеет вид:

REPEAT

<операторы циклической части программы>

UNTIL <логическое выражение>

Здесь REPEAT (повторить) и UNTIL (до тех пор) – служебные слова.

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

Поскольку нижняя граница операторов циклической части четко обозначена словом UNTIL, то нет необходимости заключать операторы циклической части в скобки вида BEGIN – END, хотя наличие операторных скобок не является ошибкой.

В следующем фрагменте показано, как оператор repeat используется для ожи­дания нажатия клавиш Y и N. Нажатие других клавиш будет игнорироваться:

uses Crt;

Var

YN: char; begin

...

Repeat

YN:=ReadKey until

Upcase(YN) in ['Y1,'N'];

End.

Примером действия оператора repeat может служить программа, которая вводит и суммирует любое количество целочисленных значений. Если вве­дено значение 999, то на экран выводится результат суммирования.


Program Summa;

Var

X: integer; Sum: real;

Begin

Sum:=0;

repeat {Повторять}

Write('Значение X= '); {Начало тела цикла}

Readln(X); {Считать очередное значение X

if X < 999 then

Sum:= Sum+X;

until X = 999; {Условие окончания цикла}

Writeln('Сумма введенных чисел— ',Sum);

End.

В данном примере в разделе описания переменных описана переменная X целочисленного типа intege r и Sum вещественного типа real.

В начале выполнения программы обнуляется значение суммы чисел. Затем зарезервированным словом repeat объявляется цикл, после чего следуют операторы цикла, которые выводят на экран запрос 'Значение Х= ', считывают введенное с клавиатуры значение X. Оператор if проверяет его на неравенство числу 999 и, если оно не равно 999, увеличивает значение суммы Sum на значение числа X. В цикле оператор until X = 999 проверяет условие окончания цикла. Если значение выражения X = 999 истинно, то цикл завершится, а управление в программе передано на оператор, находящийся за словом until, т. е. первый оператор за границей цикла repeat. Это вызов процедуры Writeln, которая выведет сообщение ‘Сумма введенных чисел равна' и напечатает значение переменной Sum.

2.3.3. Оператор цикла с параметром. В случаях, когда число повторений может быть заранее известно, для организации циклической обработки информации применяется оператор повтора for. Часто этот оператор повтора называют оператором цикла с параметром, так как число повторений задается переменной, называемой параметром цикла, или управляющей переменной.

Оператор повтора for состоит из заголовка и тела цикла.

Синтаксическая диаграмма данного оператора имеет вид:

 

Т.е., оператор цикла имеет вид:

FOR i:=m1 TO m2 DO

BEGIN

<Операторы циклической части программы>

END

Здесь FOR (для), TO (до), DO (выполнить) – служебные слова; i – параметр цикла; m1, m2 - начальное и конечное значение параметра цикла.

Циклическая часть программы выполняется повторно для каждого значения параметра цикла i от его начального значения m1 до конечного значения m2 включительно. В качестве параметра цикла может быть только переменная, в качестве m1 и m2 могут быть выражения, за исключением действительного типа (REAL).

В качестве примера действия оператора for можно рассмотреть программу, которая выводит на экран таблицу перевода градусов по шкале Цельсия (С) в градусы по шкале Фаренгейта (F) для значений от 15оС до 30оС шагом 1 градус. Для перевода воспользуемся формулой: F = C*1.8 + 32.

Program Temperature;

Var

I: integer; F: real

Begin

writeln (‘ температура ‘);

for i:=15 to 30 do { заголовок цикла программы}

begin {начало тела цикла }

F:=i*1.8+32;

Writeln (‘по Цельсию =’, i, ‘ по Фаренгейту=’, F:5:2)

end; {конец цикла программы}

End.

В блоке описания переменных описаны параметры цикла i типа integer и переменная F – температура по Фаренгейту типа real. Переменная i, помимо функций управляющей переменной, является еще и переменной, хранящей целочисленные значения температуры по шкале Цельсия. В начале выполнения программы на экране появляется надпись ‘температура’, а затем с помощью оператором повтора выводится таблица соотношения температуры в шкалах Цельсия и Фаренгейта. Печать таблицы выполняется оператором

Writeln (‘по Цельсию =’, i, ‘ по Фаренгейту=’, F:5:2),

Выполнение цикла происходит следующим образом: при первом обращении к оператору for вычисляется значение начального (15) и конечного (30) параметров цикла, и управляющей переменной i присваивается начальное значение 15.

Затем циклически выполняется следующее:

1. Проверяется условие i<=30.

2. Если оно выполняется, то рассчитывается выражение i*1.8 + 32, значение которого присваивается переменной F, и на экран выводится сообщение

‘по Цельсию =’, i, ‘ по Фаренгейту=’, F:5:2.

Если условие i <= 30 не выполняется, то оператор цикла тела цикла не выполняется, а управление в программе передается за пределы оператора for, в данном случае оператору end;. Программа завершает работу.

3. Значение параметра цикла i увеличивается на единицу, и управление передается в заголовок цикла for для проверки условия. Далее все повторяется с п.1.

2.4. Вложенные операторы цикла. Если в теле цикла присутствует циклическая структура, то такие циклы называются вложенными. Цикл, содержащий в себе цикл, является внешним, а цикл, содержащийся внутри другого цикла, является внутренним. Внешний и внутренний циклы могут быть трех видов: цикл с предусловием while, цикл с постусловием repeat или циклами с параметрами for.

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

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

Program Tabl_Umn;

Var

i, j: byte;

Begin

For i:=1 to 10 do {внешний цикл}

For j:=1 to 10 do {внутренний цикл}

writeln(i,’*’,j,’=’,i*j); { тело внутреннего цикла}

End.

Здесь в разделе описания переменных описываются переменные i, j целого типа byte, выполняющие функции управляющих переменных циклов for.

Выполнение программы начинается с внешнего цикла. При первом обращении к оператору внешнего цикла for вычисляются значения начального (1) и конечного (10) параметров цикла и управляющей переменной i присваивается начальное значение 1.

Затем циклически выполняется следующее:

1. Проверяется условие i<=10.

2. Если оно выполняется, то выполняется оператор в теле цикла, т.е. выполняется внутренний цикл.

При первом обращении к оператору внутреннего цикла for вычисляются значения начального (1) и конечного (10) параметров цикла и управляющей переменной j присваивается начальное значение 1.

Затем циклически выполняется следующее:

проверяется условие j <=10;

если оно удовлетворяется, то выполняется оператор в теле цикла, т.е. оператор writeln(i,’*’,j,’=’,i*j);, выводящий на экран строку таблицы умножения в соответствии с текущими значениями переменных i и j;

затем значение управляющей внутреннего цикла j увеличивается на одну единицу и оператор внутреннего цикла for проверяет условие j <=10. если условие соблюдается, то выполняется тело внутреннего цикла при неизменном значении управляющей переменной внешнего цикла до тех тор, пока выполняется условие j <=10.

Если условие j <=10 не удовлетворяется, т.е. как только j станет больше 10, оператор тела цикла не выполняется, внутренний цикл завершается и управление в программе передается за пределы оператора for внутреннего цикла, т.е. на оператор for внешнего цикла.

3. Значение параметра цикла i увеличивается на единицу, и проверяется условие i <=10. Если условие i <=10 не соблюдается, т.е. как только i станет больше 10, оператор тела цикла не выполняется, внешний цикл завершается и управление в программе передается за пределы for внешнего цикла, т.е. на оператор end, и программа завершает работу.

 

Примечание.

При записи операторов необходимо помнить, что:

1. точка с запятой не ставиться в разделах описаний после зарезервированных слов unit, uses, label, type, const, var и ставиться после завершения каждого описания;

2. слова begin и end являются операторными скобками, а не операторами, поэтому точка с запятой не ставиться после слова begin и перед end;

3. точка с запятой является разграничителем операторов, ее отсутствие между операторами вызывает ошибку компиляции;

4. в операторах цикла точка с запятой не ставиться после while, repeat, do и перед until;

5. в условных операторах точка с запятой не ставиться после then и перед else.

Контрольные вопросы по теме: «Операторы языка».

1. Что такое оператор? В чем отличие простых и структурных операторов?

2. Оператор присвоения, назначение и порядок выполнения.

3. Оператор безусловного перехода, его назначение и особенности применения.

4. Назначение оператора вызова процедур.

5. Что представляет собой пустой оператор и для чего он используется?

6. Что представляет собой составной оператор? Как ограничиваются операторы, объеденные в составной оператор?

7. Особенности использования вложенных условных операторов.

8. Каковы отличия оператора выбора case от оператора условия if?

9. Какие правила должны соблюдаться при использовании оператора case?

10. Каково назначение операторов повтора?

11. Чем отличаются операторы while и repeat?

12. Как в операторе цикла for описывается изменение значения параметра цикла?

13. Какие ограничения налагаются на использование управляющей переменной в цикле for?

14. О чем необходимо помнить при записи операторов?

15. Что такое вложенные циклы?


Лекция №4.

Тема: «Массивы»

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

<имя типа> = ARRAY [ диапазоны индексов ] OF <тип элемента массива>;

В качестве типа для элементов массива можно использовать любые типы Турбо Паскаля кроме файловых. Диапазоны индексов представляют собой один или несколько диапазонов, перечисленные через запятую. В качестве диапазонов индексов нельзя использовать диапазоны с базовым типом Longint.

Пример: Триспособа описания одного и того же типа массива:

type {1} M1 = array [0..5] of integer;

M2 = array [char] of M1;

M3 = array [-2..2] of M2;

{2} M3 = array [-2..2] of array [char] of array [0..5] of integer;

{3} M3 = array [-2..2,char,0..5] of integer;

var A:M3;

{Обращаться к элементам массива можно следующим образом:}

Begin

read (A[-1,'a',3]);

read (A[1]['x'][0]);

A[1]['c',1]:=100;

end.

Глубина вложенности, т.е. количество индексов, при определении массивов не ограничена. Играет роль только суммарный объем данных в программе. В стандартном режиме работы Турбо Паскаля этот объем ограничен размерами сегмента, т.е. 64 килобайта. Целиком над массивами допускается применение только операции присваивания массивов (подмассивов) одинаковых типов. Остальные операции должны выполняться поэлементно.

Пример: Вычисление значения многочлена степени N, коэффициенты которого находятся в массиве A в точке X по схеме Горнера.

Pn(x) = A[0]*Xn + A[1]*X(n-1) +... + A[n-1]*X + A[n] = (...((A[0]*X + A[1])*X + A[2])*X +... + A[n-1])*X + A[n].

Program Scheme_Gorner;

type Mas = array [0..100] of integer;

var A:Mas; i,j,n:integer; x,p:real;

Begin

write ('степень многочлена = ');

read (n);

writeln ('введите целые коэффициенты: ');

for i:=0 to n do read (A[i]);

write ('значение X = ');

read (x);

p:=0;

for i:=0 to n do p:=p*x+A[i];

writeln ('Pn(X) = ',p);

end.

Алгоритм сортировки

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

Существуют различные методы сортировки. Рассмотрим каждый из методов на примере задачи сортировки по возрастанию массива из N целых чисел.

Сортировка выбором

Идея метода заключается в том, что находится максимальный элемент массива и меняется местами с последним элементом (с номером N). Затем, максимум ищется среди элементов с первого до предпоследнего и ставится на N-1 место, и так далее. Необходимо найти N-1 максимум. Можно искать не максимум, а минимум и ставить его на первое, второе и так далее место. Также применяют модификацию этого метода с одновременным поиском максимума и минимума. В этом случае количество шагов внешнего цикла N div 2.

Вычислительная сложность сортировки выбором - величина порядка N*N, что обычно записывают как O(N*N). Это объясняется тем, что количество сравнений при поиске первого максимума равно N-1. Затем N-2, N-3, и так далее до 1, итого: N*(N-1)/2.

Пример: Сортировка выбором по возрастанию массива A из N целых чисел.

Program Sort_Vybor1;

var A: array [1..100] of integer; N,i,m,k,x: integer;

Begin

write ('количество элементов массива ');

read (N);

for i:=1 to n do read (A[i]);

for k:=n downto 2 do { k - количество элементов для поиска max }

Begin

m:=1; { m - место max }

for i:=2 to k do if A[i]>A[m] then m:=i;

{меняем местами элементы с номером m и номером k}

x:=A[m]; A[m]:=A[k]; A[k]:=x;

end;

for i:=1 to n do write (A[i],' '); {упорядоченный массив}

end.

Сортировка обменом (методом "пузырька")

Идея метода заключается в том, что последовательно сравниваются пары соседних элементов массива. Если они располагаются не в том порядке, то совершаем перестановку, меняя местами пару соседних элементов. После одного такого прохода на последнем месте номер N окажется максимальный элемент ("всплыл" первый "пузырек"). Следующий проход должен рассматривать элементы до предпоследнего и так далее. Всего требуется N-1 проход. Вычислительная сложность сортировки обменом O(N*N).

Пример: Сортировка обменом по возрастанию массива A из N целых чисел. (Базовый вариант)

Program Sort_Obmen1;

var A: array [1..100] of integer; N,i,k,x: integer;

Begin

write ('количество элементов массива ');

read (N);

for i:=1 to n do read (A[i]);

for k:=n-1 downto 1 do {k - количество сравниваемых пар}

for i:=1 to k do

if A[i]>A[i+1] then

{меняем местами соседние элементы}

Begin

x:=A[i]; A[i]:=A[i+1]; A[i+1]:=x;

end;

for i:=1 to n do write (A[i],' '); {упорядоченный массив}

end.

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

Пример: Сортировка обменом с проверкой факта перестановки.

Program Sort_Obmen2;

var A: array [1..100] of integer; N,i,k,x: integer; p: boolean;

Begin

write ('количество элементов массива ');

read (N);

for i:=1 to n do read (A[i]);

k:=n-1; {количество пар при первом проходе}

p:=true; {логическая переменная p истинна, если были перестановки, т.е. нужно продолжать сортировку}

while p do

Begin

p:=false;

{Начало нового прохода. Пока перестановок не было.}

for i:=1 to k do

if A[i]>A[i+1] then

Begin

x:=A[i]; A[i]:=A[i+1]; A[i+1]:=x;

{меняем элементы местами}

p:=true; {и запоминаем факт перестановки}

end;

k:=k-1;

{уменьшаем количество пар для следующего прохода}

end;

for i:=1 to n do write (A[i],' '); {упорядоченный массив}

end.

Следующая модификация алгоритма сортировки обменом получается при запоминании места последней перестановки. Если при очередном проходе последней парой элементов, которые поменялись местами, были A[i] и A[i+1], то элементы массива с i+1 до последнего уже стоят на своих местах. Использование этой информации позволяет нам сделать количество пар для следующего прохода равным i-1.

Пример: Сортировка обменом с запоминанием места последней перестановки.

Program Sort_Obmen3;

var A: array [1..100] of integer; N,i,k,x,m: integer;

Begin

write ('количество элементов массива ');

read (N);

for i:=1 to n do read (A[i]);

k:=n-1; {количество пар при первом проходе}

while k>0 do

Begin

m:=0;

{пока перестановок на этом проходе нет, место равно 0}

for i:=1 to k do

if A[i]>A[i+1] then

Begin

x:=A[i]; A[i]:=A[i+1]; A[i+1]:=x; {меняем элементы местами}

m:=i; {и запоминаем место перестановки}

end;

k:=m-1; {количество пар зависит от места последней перестановки}

end;

for i:=1 to n do write (A[i],' '); {упорядоченный массив}

end.

 

Шейкерная перестановка

Этот алгоритм, по сути, является модификацией сортировки обменом. Отличие состоит только в том, что если в сортировке обменом проходы осуществлялись только в одном направлении, то здесь направление каждый раз меняется. В шейкерной сортировке также можно проверять факт перестановки или запоминать место последней перестановки. В базовом алгоритме количество двойных проходов равно N div 2. Вычислительная сложность шейкерной сортировки O(N*N).

Пример: Шейкерная сортировка по возрастанию массива A из N целых чисел.

Program Shaker;

var A: array [1..100] of integer; N,i,k,x,j,d: integer;

Begin

write ('количество элементов массива ');

read (N);

for i:=1 to n do read (A[i]);

d:=1; i:=0;

for k:=n-1 downto 1 do {k - количество сравниваемых пар }

Begin

i:=i+d;

for j:=1 to k do

Begin

if (A[i]-A[i+d])*d>0 then

{меняем местами соседние элементы}

begin x:=A[i]; A[i]:=A[i+d]; A[i+d]:=x;

end;

i:=i+d;

end;

d:=-d;

{меняем направление движения на противоположное}

end;

for i:=1 to n do write (A[i],' '); {упорядоченный массив}

end.

Сортировка включением

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

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

При использовании линейного поиска вычислительная сложность сортировки включением составляет O(N*N), а при использовании двоичного поиска - O(N*LogN) (имеется в виду логарифм по основанию 2).

Пример: Сортировка по возрастанию массива A из N целых чисел включением с линейным поиском.

Program Sort_Include1;

var A: array [1..100] of integer; N,i,k,x: integer;

Begin

write ('количество элементов массива ');

read (N);

read (A[1]); { for i:=1 to n do read (A[i]);}

{k - количество элементов в упорядоченной части массива}

for k:=1 to n-1 do

Begin

read (x); {x:=A[k+1];}

i:=k;

while (i>0) and (A[i]>x) do

Begin

A[i+1]:=A[i];

i:=i-1;

end;

A[i+1]:=x;

end;

for i:=1 to n do write (A[i],' '); {упорядоченный массив}

end.

 

Сортировка Хоара

Эту сортировку также называют быстрой сортировкой. Метод был разработан в 1962 году профессором Оксфордского университета К. Хоаром. Это прекрасный пример использования рекурсии. Рассмотрим принцип работы алгоритма при упорядочении массива A из N элементов по возрастанию.

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

После этого массив окажется разделенным на две части. В первой находятся элементы меньше либо равные X, а справа - больше либо равные X. Можно заменить исходную задачу о сортировке массива A на две подзадачи о сортировке полученных частей массива.

Вычислительная сложность одного вызова данного рекурсивного алгоритма пропорциональна количеству элементов сортируемого фрагмента массива. В лучшем случае деление на части производится пополам, поэтому вычислительная сложность всего алгоритма быстрой сортировки составляет величину порядка N*LogN (логарифм по основанию 2). Вычислительная сложность в среднем того же порядка.

Пример: Быстрая сортировка по возрастанию массива A из N целых чисел.

Program Quick_Sort;

var A: array [1..100] of integer;

N,i: integer;

{В процедуру передаются левая и правая границы сортируемого фрагмента}

procedure QSort(L,R:integer);

var X,y,i,j:integer;

Begin

X:=A[(L+R) div 2];

i:=L; j:=R;

while i<=j do

Begin

while A[i]<X do i:=i+1;

while A[j]>X do j:=j-1;

if i<=j then

Begin

y:=A[i]; A[i]:=A[j]; A[j]:=y;

i:=i+1; j:=j-1;

end;

end;

if L<j then QSort(L,j);

if i<R then QSort(i,R);

end;

Begin

write ('количество элементов массива ');

read (N);

for i:=1 to n do read (A[i]);

QSort(1,n); {упорядочить элементы с первого до n-го}

for i:=1 to n do write (A[i],' '); {упорядоченный массив}

end.

Контрольные вопросы по теме: «Массивы».

1. Что такое массив?

2. Как определить местоположение элемента в массиве?

3. Каким образом задается описание массива, что в нем указывается?

4. Что называется сортировкой массива?

5. Какие методы сортировки вы знаете, опишите их существенные отличия.

6. В чем состоит сортировка методом «пузырька»?

7. Что такое «Сортировка по методу Хоара»?

 

Лекция № 5.

Тема: «Процедуры и функции»

Турбо Паскаль позволяет выделять фрагменты программы во вспомогательные алгоритмы (ВА). Это позволяет писать хорошо структурированные программы. Языки программирования, в которых предусмотрены ВА, называются процедурно - ориентированными. Структурированные программы обычно проще в понимании и отладке. Под структурным программированием понимают такие методы разработки и записи программы, которые ориентированы на максимальные удобства для восприятия и понимания человеком.

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

Технология нисходящего программирования. Базируется на методе программирования «сверху - вниз» При этом сначала создается главная программа, предполагая наличие некоторых ВА, решающих определенные задачи.

Технология восходящего программирования, Бази







Живите по правилу: МАЛО ЛИ ЧТО НА СВЕТЕ СУЩЕСТВУЕТ? Я неслучайно подчеркиваю, что место в голове ограничено, а информации вокруг много, и что ваше право...

Что вызывает тренды на фондовых и товарных рынках Объяснение теории грузового поезда Первые 17 лет моих рыночных исследований сводились к попыткам вычис­лить, когда этот...

Что способствует осуществлению желаний? Стопроцентная, непоколебимая уверенность в своем...

Что делает отдел по эксплуатации и сопровождению ИС? Отвечает за сохранность данных (расписания копирования, копирование и пр.)...





Не нашли то, что искали? Воспользуйтесь поиском гугл на сайте:


©2015- 2024 zdamsam.ru Размещенные материалы защищены законодательством РФ.