Версия для печати темы
Нажмите сюда для просмотра этой темы в обычном формате
Форум «Всё о Паскале» _ Задачи _ Быстрый поиск в массиве
Автор: Белоснежка 20.02.2008 7:02
Помогите с задачей. Искала в поисковиках, в книжках с алгоритмами но ничего не нашла 
Нужно программку которая производит быстрый поиск (при помощи алгоритма быстрого поиска) заданной буквы в массиве из заданного количества элементов
Я уже все что можно перечитала нигде про алгоритм быстрого поиска ничего не нашла.
Ребятки может кто-то знает? Помогите а?
Автор: Ozzя 20.02.2008 12:59
http://algolist.manual.ru/search/index.php
Автор: andriano 20.02.2008 13:03
Думаю, "быстрый поиск" не является общеупотребительным термином.
Поэтому нужно определиться, что именно искать и при каких условиях.
Если, например, нужно найти что-то в отсортированном массиве, целесообразно применить бинарный поиск, а если нужно найти объект в базе сразу по нескольким классифицирующим признакам, то можно посмотреть:
http://www.web-brodilka.ru/lesson.php?part=5&num=24
Автор: Белоснежка 20.02.2008 14:05
Вот я нашла но этот кодя никак не смогла довести до рабочего состояния. Мне нужно чтоб поиск был по буквам а это кажется ищет цифры. Но алгоритм именно то что мне нужен там 2 варианта.
program Poisk3a;
var A:array[1..100] of integer;
N,X,left,right:integer;
begin
read(N); {N<=100}
write('введите упорядоченный по возрастанию массив');
for i:=1 to N do read(A[i]);
read(X);
left:=1; right:=N;
{левая и правая граница фрагмента для поиска}
while left
begin
c:=(left + right) div 2;
{середина с округлением в меньшую сторону}
if X>A[c] then
{если массив упорядочен по убыванию, то if X
left:=c+1
{выбираем правую половину без середины, меняя left}
else right:=c;
{выбираем левую половину с серединой, меняя right}
end;
if X=A[left] then {здесь left = right, но не всегда = c}
write('первое вхождение числа ',X,' в массив A на ',left,' месте')
else write('не нашли');
end.
ПРИМЕР: Поиск в массиве, упорядоченном по возрастанию сумм цифр элементов массива, последнего числа с суммой цифр равной X.
program Poisk3b;
var A:array[1..100] of integer;
N,X,left,right:integer;
{функция считает сумму цифр числа a, здесь a - локальная переменная}
function Sum(a:integer):integer;
var s:integer;
begin
s:=0; a:=abs(a);
while a>0 do
begin
s:=s + a mod 10;
a:=a div 10;
end;
Sum:=s;
end;
begin
read(N); {N<=100}
write('введите массив, упорядоченный по возрастанию сумм цифр');
{например, для N=4 : 122, -432, 88, 593}
for i:=1 to N do read(A[i]);
read(X);
left:=1; right:=N;
{левая и правая граница фрагмента для поиска}
while left
begin
c:=(left+right+1) div 2;
{середина с округлением в большую сторону}
if X>=Sum(A[c]) then left:=c
{выбираем правую половину с серединой, меняя left}
else right:=c-1;
{выбираем левую половину без середины, меняя right}
end;
if X=Sum(A[left]) then {здесь left = right, но не всегда = c}
write('последнее число с суммой цифр=',X,' равно',A[left], ' находится в массиве A на ',left,' месте')
else write('не нашли');
end.
Автор: Белоснежка 20.02.2008 14:09
Может кто сможет переделать?
Автор: spill 20.02.2008 16:20
Буквы почти ни чем не отличаются от цифр (с точки зрения этой задачи). Поэтому если ты везде заменишь тип integer на char, то все должно работать.
Кстати, эту строчку:
(это сортируемый массив) можно заменить на A: String (в нескольких местах). Тогда будет сортироваться строка.
Другой вопрос, если нужно отсортировать записи с ключем типа символ. Это делается по-другому. Ты опиши поподробнее, что именно нужно сделать.
Автор: volvo 20.02.2008 17:01
program Poisk3a;
var
A: string;
midd, left, right:integer;
X: char;
begin
write('Введите упорядоченную строку: '); readln(A);
Write('Что будем искать? '); readln(X);
left:=1; right:=length(A);
while (Right - Left) > 1 do begin
midd := (right + left) div 2;
if X <= A[midd] then right := midd else left := midd
end;
midd := -1;
if X = A[ left ] then midd := left
else
if X = a[ right ] then midd := right;
if midd <> -1 then
write('символ с индексом ', midd ,' является: ', X)
else write('искомый символ не найден');
end.
Автор: spill 20.02.2008 17:08
Прошу прощения, я перепутал...
Автор: Белоснежка 20.02.2008 18:50
Ой большое спасибо!
Я вот что нашла ...Существуют две модификации этого алгоритма для поиска первого и последнего вхождения. Все зависит от того, как выбирается средний элемент: округлением в меньшую или большую сторону. В первом случае средний элемент относится к левой части массива, а во втором - к правой.
Это значит тут гдето надо просто поменять < на >
Случайно не здесь if X <= A[midd] then right := midd else left := midd ?