Быстрый поиск в массиве, алгоритм быстрого поиска |
1. Заголовок темы должен быть информативным. В противном случае тема удаляется ...
2. Все тексты программ должны помещаться в теги [code=pas] ... [/code], либо быть опубликованы на нашем PasteBin в режиме вечного хранения.
3. Прежде чем задавать вопрос, см. "FAQ", если там не нашли ответа, воспользуйтесь ПОИСКОМ, возможно такую задачу уже решали!
4. Не предлагайте свои решения на других языках, кроме Паскаля (исключение - только с согласия модератора).
5. НЕ используйте форум для личного общения, все что не относится к обсуждению темы - на PM!
6. Одна тема - один вопрос (задача)
7. Проверяйте программы перед тем, как разместить их на форуме!!!
8. Спрашивайте и отвечайте четко и по существу!!!
Быстрый поиск в массиве, алгоритм быстрого поиска |
Белоснежка |
Сообщение
#1
|
Гость |
Помогите с задачей. Искала в поисковиках, в книжках с алгоритмами но ничего не нашла
Нужно программку которая производит быстрый поиск (при помощи алгоритма быстрого поиска) заданной буквы в массиве из заданного количества элементов Я уже все что можно перечитала нигде про алгоритм быстрого поиска ничего не нашла. Ребятки может кто-то знает? Помогите а? |
Ozzя |
Сообщение
#2
|
Гуру Группа: Пользователи Сообщений: 1 220 Пол: Мужской Репутация: 16 |
|
andriano |
Сообщение
#3
|
Гуру Группа: Пользователи Сообщений: 1 168 Пол: Мужской Реальное имя: Сергей Андрианов Репутация: 28 |
Думаю, "быстрый поиск" не является общеупотребительным термином.
Поэтому нужно определиться, что именно искать и при каких условиях. Если, например, нужно найти что-то в отсортированном массиве, целесообразно применить бинарный поиск, а если нужно найти объект в базе сразу по нескольким классифицирующим признакам, то можно посмотреть: http://www.web-brodilka.ru/lesson.php?part=5&num=24 |
Белоснежка |
Сообщение
#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
|
Гость |
Может кто сможет переделать?
|
spill |
Сообщение
#6
|
Пионер Группа: Пользователи Сообщений: 58 Пол: Мужской Реальное имя: Андрей Репутация: 2 |
Буквы почти ни чем не отличаются от цифр (с точки зрения этой задачи). Поэтому если ты везде заменишь тип integer на char, то все должно работать.
Кстати, эту строчку: Код var A:array[1..100] of integer; (это сортируемый массив) можно заменить на A: String (в нескольких местах). Тогда будет сортироваться строка. Другой вопрос, если нужно отсортировать записи с ключем типа символ. Это делается по-другому. Ты опиши поподробнее, что именно нужно сделать. |
volvo |
Сообщение
#7
|
Гость |
Цитата (это сортируемый массив) можно заменить на A: String (в нескольких местах). Тогда будет сортироваться строка. Насколько я вижу, тут вообще нет речи о сортировке, следовательно никакая строка сортироваться не будет. К строке будет применяться алгоритм бинарного поиска - это да... Только надо бы подправить программу, иначе она не то что работать - она и компилироваться не будет...program Poisk3a; |
spill |
Сообщение
#8
|
Пионер Группа: Пользователи Сообщений: 58 Пол: Мужской Реальное имя: Андрей Репутация: 2 |
Прошу прощения, я перепутал...
|
Белоснежка |
Сообщение
#9
|
Гость |
Ой большое спасибо!
Я вот что нашла ...Существуют две модификации этого алгоритма для поиска первого и последнего вхождения. Все зависит от того, как выбирается средний элемент: округлением в меньшую или большую сторону. В первом случае средний элемент относится к левой части массива, а во втором - к правой. Это значит тут гдето надо просто поменять < на > Случайно не здесь if X <= A[midd] then right := midd else left := midd ? |
volvo |
Сообщение
#10
|
Гость |
Цитата Случайно не здесь if X <= A[midd] then right := midd else left := midd ? Угу, здесь... Только не поменять знак, а убрать "=" (сделать "строго меньше"), тогда будет находиться последнее вхождение. |
Текстовая версия | 23.12.2024 19:53 |