Язык программирования Pascal. Регулярные типы данных. Васильев В.В - 10 стр.

UptoLike

ВУЗ: 

ВГУ | Воронеж

Составители: 

Рубрика: 

10
Type mas1=array[1..100] of integer;
Var i,j,n,g1,g2:integer; b,m:integer; a:mas1;
Begin
{Генерация одномерного массива и вывод массива}
. . . {Сортировка вставками}
for i:=2 to n do
begin
b:=a[i];
for j:=1 to i do
if b<a[j] then break;
for m:=i-1 downto j do a[m+1]:=a[m];
a[j]:=b
end;
{Вывод элементов отсортированного массива}
writeln; writeln('Упорядоченный по неубыванию вектор:');
for i:=1 to n do
begin
write(a[i]:7,' ');
if i mod 10 = 0 then writeln
end;
readkey;
End.{Sort_insert}
Методы сортировки сравниваются обычно по двум показателям - количе-
ству присваиваний и количеству сравнений . Рассмотренные нами методы сор -
тировки по числу присваиваний и по числу сравнений имеют квадратичную
зависимость от длины массива n . Исключение составляет сортировка выбо-
ром, имеющая число присваиваний примерно n*ln(n). Считается, что в сред-
нем методы вставки и выбора приблизительно эквивалентны и несколько луч -
ше, чем метод обмена.
В задаче 5 мы используем алгоритм двоичного поиска (бинарного
поиска , поиска делением пополам).
В фольклоре есть шуточный совет о том, как поймать в Африке льва по
методу двоичного поиска. Нужно разделить Африку пополам. Потом ту поло-
вину, в которой будет находиться лев, снова разделить пополам и т. д. Пло-
щадь Африки равна приблизительно 30 млн. км
2
. Примерно после 45 делений
лев окажется на площадке, не превышающей 1 м
2
, где его предлагается пой -
мать . Найдите “банановую корку” в цепочке рассуждений!
Алгоритм двоичного поиска допустимо использовать только в упорядо-
ченных массивах . Поскольку, сравнивая элемент с очередным средним элемен-
том массива, мы можем ответить на вопрос , в какой половине находится иско-
мый элемент.
Задача 5. Пусть элементы массива X упорядочены по возрастанию . При-
свойте переменной k номер элемента массива Х , равного числу у, или ноль,
если такого элемента нет.

Страницы