49522 (Языки и технология программирования), страница 5

program Poisk2a;

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

N,X,i:integer;

begin

read(N); {N<=100}

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

read(X);

A[N+1]:=X; {установка барьера дополнительным элементом}

i:=1; {i:=0;}

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

{repeat i:=i+1; until A[i]=X;}

if i<=N then write('первое вхождение числа ',X,' в массив A на ',i,' месте')

else write('не нашли');

end.

program Poisk2b;

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

N,X,i,y:integer;

begin

read(N); {N<=100}

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

read(X);

y:=A[N]; {сохранение последнего элемента}

A[N]:=X; {установка барьера на последнее место массива}

i:=1; {i:=0;}

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

{repeat i:=i+1; until A[i]=X;}

if (i

write('первое вхождение числа ',X,' в массив A на ',i,' месте')

else write('не нашли');

A[N]:=y; {восстановление последнего элемента массива}

end.

ДВОИЧНЫЙ (БИНАРНЫЙ) ПОИСК

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

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

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

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

ПРИМЕР: Поиск в упорядоченном по возрастанию массиве первого вхождения числа X.

program Poisk3a;

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

N,X,left,right:integer;

begin

read(N); {N<=100}

write('введите упорядоченный по возрастанию массив');

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

read(X);

left:=1; right:=N;

{левая и правая граница фрагмента для поиска}

while left

begin

c:=(left + right) div 2;

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

if X>A[c] then

{если массив упорядочен по убыванию, то if X

left:=c+1

{выбираем правую половину без середины, меняя left}

else right:=c;

{выбираем левую половину с серединой, меняя right}

end;

if X=A[left] then {здесь left = right, но не всегда = c}

write('первое вхождение числа ',X,' в массив A на ',left,' месте')

else write('не нашли');

end.

ПРИМЕР: Поиск в массиве, упорядоченном по возрастанию сумм цифр элементов массива, последнего числа с суммой цифр равной X.

program Poisk3b;

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

N,X,left,right:integer;

{функция считает сумму цифр числа a, здесь a - локальная переменная}

function Sum(a:integer):integer;

var s:integer;

begin

s:=0; a:=abs(a);

while a>0 do

begin

s:=s + a mod 10;

a:=a div 10;

end;

Sum:=s;

end;

begin

read(N); {N<=100}

write('введите массив, упорядоченный по возрастанию сумм цифр');

{например, для N=4 : 122, -432, 88, 593}

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

read(X);

left:=1; right:=N;

{левая и правая граница фрагмента для поиска}

while left

begin

c:=(left+right+1) div 2;

{середина с округлением в большую сторону}

if X>=Sum(A[c]) then left:=c

{выбираем правую половину с серединой, меняя left}

else right:=c-1;

{выбираем левую половину без середины, меняя right}

end;

if X=Sum(A[left]) then {здесь left = right, но не всегда = c}

write('последнее число с суммой цифр=',X,' равно',A[left], ' находится в массиве A на ',left,' месте')

else write('не нашли');

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.

ПРИМЕР: Та же задача с одновременным выбором max и min.

program Sort_Vybor2;

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

N,i,m,k,x,p : integer;

begin

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

read(N);

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

for k:=1 to n div 2 do { k - номер пары max и min }

begin

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

p:=k; { p - место min }

{max и min ищутся среди элементов с k до n-k+1}

for i:=k+1 to n-k+1 do

if A[i]>A[m] then m:=i

else if A[i]

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

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

if m=k then m:=p;

{если max стоял на месте k, то сейчас он на месте p}

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

x:=A[m]; A[m]:=A[n-k+1]; A[n-k+1]:=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.

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

program Sort_Include2;

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

N,i,k,x,c,left,right : 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];}

left:=1; right:=k;

{левая и правая граница фрагмента для поиска}

while left

{двоичный поиск последнего вхождения}

begin

c:=(left+right+1) div 2;

{середина с округлением в большую сторону}

if x>=A[c] then left:=c

{берем правую половину с серединой}

else right:=c-1; {берем левую половину без середины}

end;

if x>=A[left] then left:=left+1;

{сдвигаем на 1 вправо часть массива, освобождая место

для включения x}

for i:=k downto left do A[i+1]:=A[i];

A[left]:=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]

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

if i

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.

СОРТИРОВКА С ИСПОЛЬЗОВАНИЕМ ВЕКТОРА ИНДЕКСОВ

В отличии от всех ранее изложенных методов сортировки, этот не является самостоятельным алгоритмом, а представляет собой идею, которую можно применять к любому из них. Идея заключается в том, что вводится дополнительный массив B, который принято называть вектором индексов. Числа в нем говорят о том, в каком порядке нужно смотреть на элементы из A, например:

Массив A : 4 7 3 5 Массив B : 3 1 4 2 { A[3] A[1] A[4] A[2] }

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

МОДУЛЬ CRT (основные возможности)

Модуль Crt относится к стандартным модулям Турбо Паскаля и находится в файле turbo.tpl (Turbo Pascal Library). Для подключения модуля достаточно написать uses Crt. Модуль Crt содержит средства управления экраном в текстовом режиме и клавиатурой.

На экране используются два активных цвета: цвет текста и цвет фона. Их можно установить с помощью процедур TextColor и TextBackground, которые имеют по одному параметру: целому числу, задающему номер цвета. Для цвета текста используются числа от 0 до 15, а для цвета фона - от 0 до 7. Обе эти процедуры оказывают влияние только на последующий вывод.

Координаты на экране задаются следующим образом. Левый верхний угол имеет координаты (1,1), а правый нижний (80,25). Можно вводить относительные координаты, объявляя окно с помощью процедуры Window(x1,y1,x2,y2), где x1,y1 - абсолютные координаты левого верхнего, а x2,y2 - правого нижнего угла окна. После этого все процедуры и функции кроме Window используют относительные координаты. Вернуться к работе со всем экраном можно, написав Window(1,1,80,25). С помощью процедуры GotoXY(x,y) можно установить курсор в заданную позицию окна, а с помощью пары функций WhereX и WhereY без параметров можно узнать текущие координаты курсора. Процедура ClrScr не имеет параметров и закрашивает текущее окно цветом фона.

Модуль Crt позволяет осуществлять контроль клавиатуры. Известно, что информация о нажатых клавишах поступает сначала в буфер клавиатуры и только затем считывается компьютером. Также известно, что клавиши и комбинации клавиш делятся на обычные, и управляющие. В результате нажатия обычной клавиши в буфер клавиатуры поступает ее код, который может быть от 1 до 255, а при нажатии управляющей клавиши в буфер клавиатуры поступает два кода, первый из которых 0. Функция KeyPressed не имеет параметров и возвращает истиный результат если буфер не пуст. При этом содержимое буфера не изменяется. Функция ReadKey также не имеет параметров и забирает из буфера клавиатуры очередное число, возвращая в программу символ (тип char), код которого соответствует этому числу. В случае, когда буфер пуст, функция ReadKey ожидает нажатия на клавиатуре.

ЛИТЕРАТУРА

1. Абрамов А.Г., Трифонов Н.П., Трифонова Г.Н. Введение в язык Паскаль. М., Наука, 1988.

2. Абрамов С.А., Гнездилова Г.Г., Капустина Е.Н., Селюн М.И. Задачи по программированию. М., Наука, 1988.

3. Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. М., Мир, 1979.

4. Вирт Н. Алгоритмы и структуры данных. М., Мир, 1989.

5. Епанешников А., Епанешников В. Программирование в среде Turbo Pascal 7.0. М., Диалог-Мифи, 1993.

6. Зуев Е.А. Система программирования Turbo Pascal. М., Радио и связь, 1992.

7. Зуев Е.А. Программирование на языке Турбо-Паскаль 6.0,7.0. М. Радио и связь. Веста. 1993.

8. Йодан Э. Структурное программирование и конструирование программ. М.: Мир, 1979.

9. Кенин А.М., Печенкина Н.С. Работа на IBM PC. М., АО "Книга и бизнес", 1992.

10. Кнут Д. Искусство программирования на ЭВМ. М.: МИР, т.1, 1976; т.2, 1977; т.3, 1978.

11. Липский В. Комбинаторика для программистов. М., Мир, 1988.

12. Майерс Г. Искусство тестирование программ. М.: Финансы и статистика, 1982. Гласс Р., Нуазо Р. Сопровождение программного обеспечения, М.: Мир, 1983.

13. Пильщиков В.Н. Сборник упражнений по языку Паскаль. М., Наука, 1989.

14. Поляков Д.Б., Круглов И.Ю. Программирование в среде Турбо Паскаль (версия 5.5). Изд-во МАИ, 1992.

15. Рейнгольд Э., Нивергельт Ю., Део Н. Комбинаторные алгоритмы. М., Мир, 1980.

16. Фаронов В.В. Турбо Паскаль 7.0. Начальный курс. М., Нолидж, 1997.

17. Фаронов В.В. Турбо Паскаль 7.0. Практика программирования. М., Нолидж, 1997.

18. Шень А. Программирование: Теоремы и задачи. М., МЦНМО, 1995.

56