Поперечные профили набережных и береговой полосы: На городских территориях берегоукрепление проектируют с учетом технических и экономических требований, но особое значение придают эстетическим...
Семя – орган полового размножения и расселения растений: наружи у семян имеется плотный покров – кожура...
Топ:
Эволюция кровеносной системы позвоночных животных: Биологическая эволюция – необратимый процесс исторического развития живой природы...
Когда производится ограждение поезда, остановившегося на перегоне: Во всех случаях немедленно должно быть ограждено место препятствия для движения поездов на смежном пути двухпутного...
Интересное:
Отражение на счетах бухгалтерского учета процесса приобретения: Процесс заготовления представляет систему экономических событий, включающих приобретение организацией у поставщиков сырья...
Мероприятия для защиты от морозного пучения грунтов: Инженерная защита от морозного (криогенного) пучения грунтов необходима для легких малоэтажных зданий и других сооружений...
Национальное богатство страны и его составляющие: для оценки элементов национального богатства используются...
Дисциплины:
2020-12-06 | 99 |
5.00
из
|
Заказать работу |
|
|
Решение
1. Выбирается средний элемент массива и сравнивается с заданным числом b.
После чего могут представиться два возможных случая.
Случай 1. Выбранный средний элемент меньше числа b, тогда нет смысла рассматривать левую часть массива (там равного элемента уже точно не будет), а остается искать равный элемент среди второй, правой половины элементов.
Случай 2. Выбранный средний элемент больше или равен заданному числу b и, тогда нет смысла рассматривать правую часть массива, а поиск продолжается среди элементов левой части.
Таким образом, сразу сокращается число испытаний вдвое.
2. С той половиной массива, в которой установлено, что может быть равный элемент, проделывается та же процедура деления.
3. Процесс такого деления продолжается. Наконец наступает такой момент, что в выбранной части массива остается один элемент (т.е. номера элементов слева и справа станут равными), тогда он является искомым, либо (если он не равен заданному числу) такого элемента вообще нет в массиве.
Рассмотрим несколько частных примеров, чтобы уразуметь математику этого вопроса.
1. Пусть задан массив из 10 упорядоченных по неубыванию чисел:
23 34 45 48 56 63 67 72 78 89
1 2 3 4 5 6 7 8 9 10
Надо найти элемент этого массива, равный числу 78.
Пусть p - номер элемента левой границы массива, q - номер элемента правой границы массива, s - номер среднего элемента.
Устанавливаем средний элемент. Им будет элемент под номером (знак "\" - знак целочисленного деления), т. е. 56.
Сравниваем этот элемент с числом 78: 56 < 78.
Значит искомый элемент находится справа от 56.
Рассматриваем правую половину заданного массива, т.е. элементы, находящиеся справа от 56:
|
63 67 72 78 89
6 7 8 9 10
Тогда, p = 6, q = 10.
Выбираем и в нём средний элемент. Им будет элемент под номером
s = (p + q)\2 = (6 + 10)=8, равный 72.
Сравниваем: 72 < 78
Значит, снова искомый элемент будет находится справа от 72, т.е. в следующей части массива:
78 89
9 10
p = 9, q = 10.
Находим среди них средний элемент. Им будет элемент под номером
s = (p + q)\2 = (9 + 10)\2 = 9.
Сравниваем: 78 < 78.
Условие не выполняется. Значит надо брать элементы массива слева от числа 78.
Тогда, p = 9, q = 9. Номера левой и правой границ стали равны, цикл заканчивается, искомым элементом будет элемент под номером 9, равный 78.
В самом деле: 78 = 78.
Еще один пример. Задан массив из 15 элементов:
7 9 11 12 15 18 20 24 34 42 45 67 78 89 98
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
Надо найти элемент массива, равный числу 9.
p = 1, q = 15, s = (p + q)\2 = (1 + 15)\2 = 8.
Средним является элемент под номером 8, равный 24.
Сравниваем: 24 < 9.
Условие не выполняется, значит будем искать элемент в левой части массива, т.е. ищем его среди элементов:
7 9 11 12 15 18 20 24
1 2 3 4 5 6 7 8
p = 1, q = 8, s =(p + q)\2 = (1 + 8)\2 = 4.
Средним элементом будет элемент под номером 4, равный 12.
Сравниваем: 12 < 9.
Условие не выполняется. Снова надо рассматривать левую часть оставшихся элементов, т.е. элементы, расположенные слева от 12 (включая 12):
7 9 11 12
1 2 3 4
p = 1, q = 4, s = (p + q)\2 = (1 + 4)\2 = 2.
Средним элементом будет элемент под номером 2, равный 9.
Сравниваем: 9 < 9.
Условие не выполняется.
Рассматриваем элементы слева от 9 (включая 9):
7 9
1 2
p = 1, q = 2, s = (p + q)\2 = (1 + 2)\2 = 1.
Средним является элемент под номером 1, равный 7.
Сравниваем: 7 < 9.
Условие выполняется, значит надо рассматривать элемент справа от 7, т.е. 9.
9
2
p = 2, q = 2, p = q, цикл заканчивается, искомый элемент под номером 2, равный 9.
Алгоритм
Первоначально в качестве границ - левой и правой берутся значения 1 и n. Пусть p и q обозначают левую и правую границы, тогда p:= 1, а q:= n; далее производится деление и шаг за шагом границы сближаются. Процесс деления должен продолжаться до совпадения границ, когда p = q (т. е. цикл выполняется пока Границы сближаются следующим образом: пусть s - номер среднего элемента, значение s - это целая часть среднего арифметического границ p и q
|
если тогда надо изменить прежнюю нижнюю границу на а верхняя граница (q) остается без изменения (выбирается правая часть массива), иначе, оставить без изменения нижнюю границу (p), а верхнюю заменить на s
Теперь можно записать этот алгоритм в виде последовательности операторов:
p:= 1; q:= n;
while p < q do
Begin
s:= (p + q) div 2;
if a[s] < b then p:= s + 1 else q:= s
end;
Может случиться, что элемента массива, равного заданному числу b в массиве нет. Это обстоятельство надо учесть и добавить следующие операторы
if a[p] = b then writeln('Число ', b, ' входит в масс. и равно ', p, '-му элементу')
else writeln('Такого элемента в массиве нет')
Program Problem 8;
uses WinCrt;
const
n = 20;
type
t = array [1..n] of integer;
var
a : t;
p, q, s, b, i: integer;
begin
writeln('Вводите элементы упорядоченного по неубыванию массива');
for i:= 1 to n do
begin
write(' Введите ', i, '- й элемент '); readln(a[i])
end;
writeln;
write(' Введите число b '); readln(b);
p:= 1; q:= n;
while p < q do
begin
s:= (p + q) div 2;
if a[s] < b then p:= s + 1
else q:= s
end;
if a[p ]= b
then writeln(' Число ', b, ' равно ', p, '- му элементу ')
else writeln('Такого элемента в массиве нет')
end.
Задача 9. Поиск " среднего " элемента массива
Решение
Program Problem9; {Поиск "среднего" элемента массива}
uses WinCrt;
const
n = 20;
type
t = array [1..n] of integer;
var
x: t;
m, i: integer;
{---------------------------------------------------------------------------------------}
Procedure create(n: integer; var x: t);
var
i: integer;
begin
randomize;
writeln('Заданный массив целых чисел');
for i:= 1 to n do
begin
x[i]:= random(201)-100;
write(x[i], ' ')
end;
writeln
end;
{----------------------------------------------------------------------------------------}
Procedure exchange(l, r: integer);
var
p: integer;
begin
p:= x[l]; x[l]:= x[r]; x[r]:= p
end;
{----------------------------------------------------------------------------------------}
|
Procedure middle(k: integer; var x: t; var m: integer);
var
l, r: integer;
begin
l:= 1; r:= k;
repeat
while (x[l] <= x[r]) and (l < r) do r:= r - 1;
exchange(l, r); { Процедура обмена }
while (x[l] <= x[r]) and (l < r) do l:= l + 1;
exchange(l, r)
until l = r;
m:= l
end;
{---------------------------------------------------------------------------------------}
begin
create(n, x);
middl e (n, x, m);
write('Измененный массив со средним элементом ', x[m]);
writeln(' на ', m, '-ом месте');
for i:= 1 to n do write(x[i], ' ');
writeln
end.
Задача 10. Составить программу, которая создает два массива чисел с помощью функции случайных чисел, упорядочивает их с помощью рекурсивной процедуры быстрой сортировки, а затем объединяет их в один упорядоченный массив, также с использованием рекурсивной процедуры.
Решение
Program Problem 10;
uses WinCrt;
const
n = 10; m =15;
type
t = array [1..n] of integer;
u = array [1..m] of integer;
f = array [1..n+m] of integer;
var
a: t; b: u; c: f;
i, p, q: integer;
{----------------------------------------------------------------------------------------}
Procedure fast(q, p: integer; var a: t);
var
s, l, r: integer;
begin
l:= q;
r:= p;
s:= a[l];
repeat
while (a[r] >= s) and (l < r) do r:= r - 1;
a[l]:= a[r];
while (a[l] <= s) and (l < r) do l:= l + 1;
a[r]:= a[l]
until l = r;
a[l]:= s;
if q < l - 1 then fast(q, l - 1, a);
if l + 1 < p then fast(l + 1, p, a)
end;
{----------------------------------------------------------------------------------------}
Procedure fast1(q, p: integer; var b: u);
var
s, l, r: integer;
begin
l:= q;
r:= p;
s:= b[l];
repeat
while (b[r] >= s) and (l < r) do r:= r - 1;
b[l]:= b[r];
while (b[l] <= s) and (l < r) do l:= l + 1;
b[r]:= b[l]
until l = r;
b[l]:= s;
if q < l - 1 then fast1(q, l - 1, b);
if l + 1 < p then fast1(l + 1, p, b)
end;
{----------------------------------------------------------------------------------------}
Procedure new(n, m, q, p, k: integer; var c: f);
label 1, 2;
begin
if k = n + m + 1 then goto 1;
if p = n then begin q:= q + 1; c[k]:= b[q]; goto 2 end;
if q = m then begin p:= p + 1; c[k]:= a[p]; goto 2 end;
if a[p + 1] < b[q + 1]
|
then begin p:= p + 1; c[k]:= a[p]; goto 2 end
else begin q:= q + 1; c[k]:= b[q] end;
2: new(n, m, q, p, k + 1, c);
1: end;
{----------------------------------------------------------------------------------------}
begin
randomize;
for i:= 1 to n do a[i]:= random(201)-100;
for i:= 1 to m do b[i]:= random(201)-100;
fast(1, n, a);
writeln('Заданный упорядоченный 1-й массив');
for i:= 1 to n do write(a[i], ' ');
writeln;
fast1(1, m, b);
writeln(' Заданный упорядоченный 2- й массив ');
for i:= 1 to m do write(b[i], ' ');
writeln;
new(n, m, 0, 0, 1, c);
writeln('Новый упорядоченный объединенный массив');
for i:=1 to n + m do write(c[i], ' ');
writeln
end.
Задача 11. Рекурсивная процедура "быстрой" сортировки элементов массива.
Решение
Procedure fast(q, p: integer; var a: t);
var
s, l, r: integer;
begin
l:= q; r:= p;
s:= a[l];
repeat
while (a[r] >= s) and (l < r) do r:= r - 1;
a[l]:= a[r];
while (a[l] <= s) and (l < r) do l:= l + 1;
a[r]:= a[l]
until l = r;
a[l]:= s;
if q < l - 1 then fast(q, l - 1, a);
if l + 1 < p then fast(l + 1, p, a)
end;
|
|
Биохимия спиртового брожения: Основу технологии получения пива составляет спиртовое брожение, - при котором сахар превращается...
Организация стока поверхностных вод: Наибольшее количество влаги на земном шаре испаряется с поверхности морей и океанов (88‰)...
Архитектура электронного правительства: Единая архитектура – это методологический подход при создании системы управления государства, который строится...
Таксономические единицы (категории) растений: Каждая система классификации состоит из определённых соподчиненных друг другу...
© cyberpedia.su 2017-2024 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!