История создания датчика движения: Первый прибор для обнаружения движения был изобретен немецким физиком Генрихом Герцем...
Папиллярные узоры пальцев рук - маркер спортивных способностей: дерматоглифические признаки формируются на 3-5 месяце беременности, не изменяются в течение жизни...
Топ:
Эволюция кровеносной системы позвоночных животных: Биологическая эволюция – необратимый процесс исторического развития живой природы...
Основы обеспечения единства измерений: Обеспечение единства измерений - деятельность метрологических служб, направленная на достижение...
Характеристика АТП и сварочно-жестяницкого участка: Транспорт в настоящее время является одной из важнейших отраслей народного...
Интересное:
Инженерная защита территорий, зданий и сооружений от опасных геологических процессов: Изучение оползневых явлений, оценка устойчивости склонов и проектирование противооползневых сооружений — актуальнейшие задачи, стоящие перед отечественными...
Аура как энергетическое поле: многослойную ауру человека можно представить себе подобным...
Влияние предпринимательской среды на эффективное функционирование предприятия: Предпринимательская среда – это совокупность внешних и внутренних факторов, оказывающих влияние на функционирование фирмы...
Дисциплины:
2020-12-06 | 93 |
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;
|
|
Архитектура электронного правительства: Единая архитектура – это методологический подход при создании системы управления государства, который строится...
Особенности сооружения опор в сложных условиях: Сооружение ВЛ в районах с суровыми климатическими и тяжелыми геологическими условиями...
Механическое удерживание земляных масс: Механическое удерживание земляных масс на склоне обеспечивают контрфорсными сооружениями различных конструкций...
Общие условия выбора системы дренажа: Система дренажа выбирается в зависимости от характера защищаемого...
© cyberpedia.su 2017-2024 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!