IPB
ЛогинПароль:

> Прочтите прежде чем задавать вопрос!

1. Заголовок темы должен быть информативным. В противном случае тема удаляется ...
2. Все тексты программ должны помещаться в теги [code=pas] ... [/code], либо быть опубликованы на нашем PasteBin в режиме вечного хранения.
3. Прежде чем задавать вопрос, см. "FAQ", если там не нашли ответа, воспользуйтесь ПОИСКОМ, возможно такую задачу уже решали!
4. Не предлагайте свои решения на других языках, кроме Паскаля (исключение - только с согласия модератора).
5. НЕ используйте форум для личного общения, все что не относится к обсуждению темы - на PM!
6. Одна тема - один вопрос (задача)
7. Проверяйте программы перед тем, как разместить их на форуме!!!
8. Спрашивайте и отвечайте четко и по существу!!!

 
 Ответить  Открыть новую тему 
> Быстрый поиск в массиве, алгоритм быстрого поиска
сообщение
Сообщение #1


Гость






Помогите с задачей. Искала в поисковиках, в книжках с алгоритмами но ничего не нашла sad.gif
Нужно программку которая производит быстрый поиск (при помощи алгоритма быстрого поиска) заданной буквы в массиве из заданного количества элементов
Я уже все что можно перечитала нигде про алгоритм быстрого поиска ничего не нашла.
Ребятки может кто-то знает? Помогите а?

 К началу страницы 
+ Ответить 
сообщение
Сообщение #2


Гуру
*****

Группа: Пользователи
Сообщений: 1 220
Пол: Мужской

Репутация: -  16  +


http://algolist.manual.ru/search/index.php
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #3


Гуру
*****

Группа: Пользователи
Сообщений: 1 168
Пол: Мужской
Реальное имя: Сергей Андрианов

Репутация: -  28  +


Думаю, "быстрый поиск" не является общеупотребительным термином.
Поэтому нужно определиться, что именно искать и при каких условиях.
Если, например, нужно найти что-то в отсортированном массиве, целесообразно применить бинарный поиск, а если нужно найти объект в базе сразу по нескольким классифицирующим признакам, то можно посмотреть:
http://www.web-brodilka.ru/lesson.php?part=5&num=24
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #4


Гость






Вот я нашла но этот кодя никак не смогла довести до рабочего состояния. Мне нужно чтоб поиск был по буквам а это кажется ищет цифры. Но алгоритм именно то что мне нужен там 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.
 К началу страницы 
+ Ответить 
сообщение
Сообщение #5


Гость






Может кто сможет переделать?
 К началу страницы 
+ Ответить 
сообщение
Сообщение #6


Пионер
**

Группа: Пользователи
Сообщений: 58
Пол: Мужской
Реальное имя: Андрей

Репутация: -  2  +


Буквы почти ни чем не отличаются от цифр (с точки зрения этой задачи). Поэтому если ты везде заменишь тип integer на char, то все должно работать.
Кстати, эту строчку:
Код
var A:array[1..100] of integer;

(это сортируемый массив) можно заменить на A: String (в нескольких местах). Тогда будет сортироваться строка.
Другой вопрос, если нужно отсортировать записи с ключем типа символ. Это делается по-другому. Ты опиши поподробнее, что именно нужно сделать.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #7


Гость






Цитата
(это сортируемый массив) можно заменить на A: String (в нескольких местах). Тогда будет сортироваться строка.
Насколько я вижу, тут вообще нет речи о сортировке, следовательно никакая строка сортироваться не будет. К строке будет применяться алгоритм бинарного поиска - это да... Только надо бы подправить программу, иначе она не то что работать - она и компилироваться не будет...

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.
 К началу страницы 
+ Ответить 
сообщение
Сообщение #8


Пионер
**

Группа: Пользователи
Сообщений: 58
Пол: Мужской
Реальное имя: Андрей

Репутация: -  2  +


Прошу прощения, я перепутал...
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #9


Гость






Ой большое спасибо!
Я вот что нашла ...Существуют две модификации этого алгоритма для поиска первого и последнего вхождения. Все зависит от того, как выбирается средний элемент: округлением в меньшую или большую сторону. В первом случае средний элемент относится к левой части массива, а во втором - к правой.
Это значит тут гдето надо просто поменять < на >
Случайно не здесь if X <= A[midd] then right := midd else left := midd ?
 К началу страницы 
+ Ответить 
сообщение
Сообщение #10


Гость






Цитата
Случайно не здесь if X <= A[midd] then right := midd else left := midd ?
Угу, здесь... Только не поменять знак, а убрать "=" (сделать "строго меньше"), тогда будет находиться последнее вхождение.
 К началу страницы 
+ Ответить 

 Ответить  Открыть новую тему 
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0

 





- Текстовая версия 23.12.2024 19:53
500Gb HDD, 6Gb RAM, 2 Cores, 7 EUR в месяц — такие хостинги правда бывают
Связь с администрацией: bu_gen в домене octagram.name