ВУЗ:
Составители:
Рубрика:
33
Begin Writeln('Ввод размерности массива');
Read(n);
For i:=1 to n do begin read(X[ i ]);
Min:=X[1]; k:=1;
For i:=2 to n do
If min>=X[ i ] then begin min:=X[ i ]; k:=i; end;
Write('Последний минимальный элемент = ',
min:6,'его номер = ',k:6);
End.
Следует отметить, что если нам
необходимо найти первый минимальный
элемент, то следует программу изменить в
строке min>=X[ i ] на обратное, то есть
min<=X[ i ].
Линейный поиск
Пусть задана последовательность X[ i ] и
переменная P, которая называется поисковой
переменной. Известно, что все X[ i ] – разные.
Требуется определить номер элемента, значение
которого ра
вно P.
Рисунок 19. Блок-схема поиска
первого минимального элемента
Так как сравнение вещественных величин на равенство не имеет
смысла (последнее можно сравнивать лишь с допустимой точностью),
будем считать, что массив X и переменная P – целые (они могут быть и
символьными).
Если провести аналогию между поиском нужного элемента в
последовательности и поиском тр
ебуемой книги на полке, то становится
очевидным, что в неупорядоченной последовательности нет иного
способа, кроме последовательного просмотра элементов (книг) и
сравнения их с поисковой переменной P (требование на книгу). Когда
обнаружен искомый элемент (книга), запоминаем его номер (место книги
на полке). Такой метод называется линейным поиском. Условия
окончания поиска следующие:
1. Элемент найден, то есть X[ i ]=P
2. Весь массив п
росмотрен, и совпадения не обнаружено.
НАЧАЛО
Ввод n,
Массив X
m:= X( 1 );
k:= 1;
m:= X( i );
k:= i;
КОНЕЦ
Печать k,
m
i:=1, n
m ≤ X( i )
нет
да
34
Обозначим k – номер элемента, значение
которого равно P. Будем считать k=0, если
элемент не найден. Основой алгоритма будет
цикл
while, так как неизвестно, сколько
элементов нужно перебрать, пока не найден
искомый элемент. Если найден элемент массива,
для которого условие X[ i ]=P выполняется, то
будем полагать k=1, i=n+1, чтобы произошел
выход из цикла. Блок-схема алгоритма
представлена на Рисунке 20. В фрагменте
программы отражен непосредственно линейный
поиск, так как ввод элемент
ов массива
выполняется также.
Программа 12. Линейный поиск, оформленный в
виде процедуры
Const n=20;
Type mass=array[1 . . n] of integer;
Procedure LPoisk(X:mass; n, p:integer;
var k:integer);
Var i:integer;
Begin i:=1; k:=0;
While i≤n do
If X[ i ]=p then begin k:=i; i:=n+1 end
Else i:=i+1
End;
Рисунок 20. Блок-схема алгоритма
линейного поиска.
Можно ускорить поиск, если отказаться от проверки условия
выхода за пределы массива, гарантировав, что совпадение обязательно
произойдет. Для этого достаточно в конец массива поместить
дополнительный элемент со значением P, то есть X[ i +1]=P. Назовем
такой вспомогательный элемент “барьером”, так как он охраняет нас от
выхода за п
ределы массива. В таком случае, необходимо анализировать
полученное значение k. Если k=n+1, то совпадения не было, если не
считать совпадения с барьером.
В случае линейного поиска среднее число сравнений, необходимое
для выявления присутствия элемента, совпадающего с P, равно n/2. В
случае отсутствия элемента в массиве понадобятся все n сравнений, чтобы
убедиться в эт
ом.
НАЧАЛО
Ввод n, P
Массив X
i:= 1;
k:= 0;
k:= i;
i:= n;
КОНЕЦ
Печать k
X( i )=P
i > n
i:= i + 1;
да
нет
нет
да
Begin Writeln('Ввод размерности массива'); Обозначим k номер элемента, значение
НАЧАЛО НАЧАЛО
Read(n); которого равно P. Будем считать k=0, если
Ввод n, Ввод n, P элемент не найден. Основой алгоритма будет
For i:=1 to n do begin read(X[ i ]); Массив X цикл while, так как неизвестно, сколько
Массив X
Min:=X[1]; k:=1; элементов нужно перебрать, пока не найден
i:= 1; искомый элемент. Если найден элемент массива,
m:= X( 1 ); For i:=2 to n do
k:= 0; для которого условие X[ i ]=P выполняется, то
k:= 1;
If min>=X[ i ] then begin min:=X[ i ]; k:=i; end; будем полагать k=1, i=n+1, чтобы произошел
выход из цикла. Блок-схема алгоритма
Write('Последний минимальный элемент = ', да
i:=1, n min:6,'его номер = ',k:6); i>n представлена на Рисунке 20. В фрагменте
программы отражен непосредственно линейный
End. нет
да поиск, так как ввод элементов массива
m ≤ X( i ) Следует отметить, что если нам нет выполняется также.
необходимо найти первый минимальный X( i )=P
нет Программа 12. Линейный поиск, оформленный в
элемент, то следует программу изменить в да
m:= X( i ); виде процедуры
строке min>=X[ i ] на обратное, то есть
k:= i; k:= i; Const n=20;
min<=X[ i ].
i:= n; Type mass=array[1 . . n] of integer;
Линейный поиск
Procedure LPoisk(X:mass; n, p:integer;
Печать k, Пусть задана последовательность X[ i ] и var k:integer);
i:= i + 1;
m переменная P, которая называется поисковой
Var i:integer;
переменной. Известно, что все X[ i ] разные.
Требуется определить номер элемента, значение Begin i:=1; k:=0;
КОНЕЦ
которого равно P. Печать k While i≤n do
If X[ i ]=p then begin k:=i; i:=n+1 end
Рисунок 19. Блок-схема поиска
первого минимального элемента КОНЕЦ Else i:=i+1
End;
Так как сравнение вещественных величин на равенство не имеет Рисунок 20. Блок-схема алгоритма
смысла (последнее можно сравнивать лишь с допустимой точностью), линейного поиска.
будем считать, что массив X и переменная P целые (они могут быть и
символьными). Можно ускорить поиск, если отказаться от проверки условия
Если провести аналогию между поиском нужного элемента в выхода за пределы массива, гарантировав, что совпадение обязательно
последовательности и поиском требуемой книги на полке, то становится произойдет. Для этого достаточно в конец массива поместить
очевидным, что в неупорядоченной последовательности нет иного дополнительный элемент со значением P, то есть X[ i +1]=P. Назовем
способа, кроме последовательного просмотра элементов (книг) и такой вспомогательный элемент барьером, так как он охраняет нас от
сравнения их с поисковой переменной P (требование на книгу). Когда выхода за пределы массива. В таком случае, необходимо анализировать
обнаружен искомый элемент (книга), запоминаем его номер (место книги полученное значение k. Если k=n+1, то совпадения не было, если не
на полке). Такой метод называется линейным поиском. Условия считать совпадения с барьером.
окончания поиска следующие: В случае линейного поиска среднее число сравнений, необходимое
1. Элемент найден, то есть X[ i ]=P для выявления присутствия элемента, совпадающего с P, равно n/2. В
случае отсутствия элемента в массиве понадобятся все n сравнений, чтобы
2. Весь массив просмотрен, и совпадения не обнаружено. убедиться в этом.
33 34
Страницы
- « первая
- ‹ предыдущая
- …
- 15
- 16
- 17
- 18
- 19
- …
- следующая ›
- последняя »
