Киберфак – бесплатно скачать презентации PowerPoint, лекции, рефераты, шпоры, курсовые cyberfac logo
cyberfac.ru
На главную | Регистрация | Вход
  Статьи  
Главная » Статьи » Информатика » Алгоритмизация и программирование

Линейный поиск

Полезная статья? Пожалуйста, поставьте "+"
Алгоритмизация и программирование - Содержание

Пусть имеется некоторый набор данных и требуется определить, где в этом наборе находится заданный элемент ( и есть ли он в наборе ). Такая задача называется задачей поиска. Большинство задач поиска сводится к поиску в таблице ( массиве ) элемента с заданным значением.

Пример
Написать программу поиска элемента x в массиве из n элементов. Значение элемента x вводится с клавиатуры.

Решение
Пусть имеются следующие описания:
Const   n = 10;     { размерность массива }
Var   a:  array ( 1...n ) Of   Integer;
{ массив из n элементов целого типа }
x: Integer; { искомый элемент целого типа }
В данном случае известно только значение разыскиваемого элемента, никакой дополнительной информации о нем или о массиве, в котором его надо искать, нет. Проверка одного элемента не дает никакой информации об остальных. Поэтому для решения задачи разумно применить очевидный метод - последовательный просмотр массива и сравнение значения очередного рассматриваемого элемента с данным. Если значение очередного элемента совпадает с x, то запомним его номер в переменной к.
For  i: =1  To  n  Do  If  a[i] = x  Then k: = i;
Этот способ решения поставленной задачи, безусловно, приводит к цели, но обладает рядом существенных недостатков:
•    если значение x  встречается в массиве несколько раз, то найдено будет последнее из них;
•    после того, как нужное значение уже найдено, массив просматривается до конца, то есть всегда выполняется n сравнений.

Разумно прекратить просмотр сразу после обнаружения заданного элемента. Так как в этом случае число повторений не известно, необходимо использовать цикл с предусловием. В результате:
- либо будет найден искомый элемент, то есть найдется такой индекс i, что   а [ i ] = x;
- либо будет просмотрен весь массив, и искомый элемент не обнаружится.
Таким образом, поскольку нужно продолжать поиск до обнаружения искомого элемента или до конца массива, условие окончания цикла может выглядеть так:
While ( i <= n ) And ( a[ i ] x )  Do  Inc ( i );

Примечание: Необходимо обратить внимание на порядок простых условий в составном условии цикла. Здесь предполагается, что второе условие не проверяется, если результат логического выражения ясен после проверки первого условия. В противном случае возникнет отказ из-за выхода индекса за границы массива.

Программа линейного поиска:

program n6;
const n=5;
var a:array[1..n] of integer;
{ массив из n элементов целого типа }
x:integer; { искомый элемент целого типа }
i,k:integer;
begin
writeln('Введите исходный массив:');
for i:=1 to n do read(a[i]);
writeln('Введите x');
readln(x);
for i:=1 to n do if a[i]=x then k:=i;
while (i<=n) and (a[i]x) do inc(i);
writeln('a[',k,']=',x,'=x');
end.

Категория: Алгоритмизация и программирование | Добавил: Ni-Cd (10 Декабря 2011)
Просмотров: 978 | Рейтинг: 0.0/0
Всего комментариев: 0
Добавлять комментарии могут только зарегистрированные пользователи.
[ Регистрация | Вход ]
  Полезные материалы  

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

Навигация
Высокоуровневые методы информатики и программирования [28]
Информатика и программирование [34]
Информационные системы в экономике [36]
Языки программирования и методы трансляции [15]
Алгоритмизация и программирование [61]
 

Поиск
 

Онлайн
Онлайн всего: 5
Гостей: 5
Пользователей: 0
 

Статистика


Рейтинг@Mail.ru

 


2007 - 2018 © Ni-Cd. All Rights Reserved