Форум программистов, компьютерный форум CyberForum.ru

Бинарно-последовательный поиск - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 23, средняя оценка - 4.96
Ватадот
 Аватар для Ватадот
3 / 3 / 0
Регистрация: 11.01.2011
Сообщений: 155
28.12.2011, 15:28     Бинарно-последовательный поиск #1
Здраствуйте.Ктонить может написать алгоритм бинарно-последновательного поиска.Плз в инете искал несмог найти...

Добавлено через 29 минут
Или мне кажется что такого нет поиска??
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
silent_1991
Эксперт C++
4938 / 3014 / 149
Регистрация: 11.11.2009
Сообщений: 7,024
Завершенные тесты: 1
28.12.2011, 15:46     Бинарно-последовательный поиск #2
Ватадот, не представляю, как бинарный (последовательный) поиск может в то же время быть последовательным (бинарным). Это два разных подхода, причём один универсальный, другой специальный.
Ватадот
 Аватар для Ватадот
3 / 3 / 0
Регистрация: 11.01.2011
Сообщений: 155
28.12.2011, 15:50  [ТС]     Бинарно-последовательный поиск #3
Тю блин,я ошибся мне надо Быстрого-последовательного поиска алгоритм
silent_1991
Эксперт C++
4938 / 3014 / 149
Регистрация: 11.11.2009
Сообщений: 7,024
Завершенные тесты: 1
28.12.2011, 15:53     Бинарно-последовательный поиск #4
Ватадот, тоже не очень понятно... Последовательный - он и есть последовательный, ишет, пока не найдёт. Как его можно вот просто так взять и ускорить?
Ватадот
 Аватар для Ватадот
3 / 3 / 0
Регистрация: 11.01.2011
Сообщений: 155
28.12.2011, 16:13  [ТС]     Бинарно-последовательный поиск #5
Быстрый последовательный поиск он точно есть.Суть заключается в оптимизации циклов,то есть сокращение числа действий в них.
silent_1991
Эксперт C++
4938 / 3014 / 149
Регистрация: 11.11.2009
Сообщений: 7,024
Завершенные тесты: 1
28.12.2011, 16:25     Бинарно-последовательный поиск #6
Ватадот, как можно оптимизировать один-единственный цикл, в котором последовательно сравниваются элементы некоторой последовательности на предмет совпадения с искомым, с учётом того, что элементы в последовательности расположены произвольно (т.е. мы ничего не знаем заранее об их порядке)? Бинарный поиск и есть оптимизация обычного, но с учётом того, что последовательность упорядочивается (т.е. в неё вносится некоторая закономерность, благодаря которой и становится возможным сократить число итераций).
По логике всё так, но вдруг я чего-то не знаю? Пруф в студию.
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
28.12.2011, 16:30     Бинарно-последовательный поиск #7
Может быть имеется ввиду это:
http://window.edu.ru/window/library/...33770&p_page=8
тогда вот пример:
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <stdio.h>
 
int main() {
    int n, mas[100], i, k;
    printf("n= ");
    scanf("%d", &n);
    for(i=0; i<n; i++)
    {
        printf("[%d]= ", i);
        scanf("%d", &mas[i]);
    }
    printf("k= ");
    scanf("%d", &k);
    mas[n]=k;
    i=0; 
    while(mas[i]!=k)
    {
        i++;
    }
    if(i==n)
        printf("No\n");
    else
        printf("pos = %d\n", i);
        return 0;
}
silent_1991
Эксперт C++
4938 / 3014 / 149
Регистрация: 11.11.2009
Сообщений: 7,024
Завершенные тесты: 1
28.12.2011, 16:34     Бинарно-последовательный поиск #8
valeriikozlov, а где "быстрый"?)) Это же обычный последовательный поиск.
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
28.12.2011, 16:36     Бинарно-последовательный поиск #9
Цитата оттуда:
6.1. Последовательный поиск
.....
.....
Оказывается, что данный алгоритм можно ускорить при помощи
вставки ключа поиска в конец массива ключей.
Быстрый последовательный поиск:
....
....
....
silent_1991
Эксперт C++
4938 / 3014 / 149
Регистрация: 11.11.2009
Сообщений: 7,024
Завершенные тесты: 1
28.12.2011, 16:45     Бинарно-последовательный поиск #10
Мдя... Так-то оно может и так, но на сложность алгоритма-то не влияет...
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
28.12.2011, 16:46     Бинарно-последовательный поиск #11
Цитата Сообщение от silent_1991 Посмотреть сообщение
но на сложность алгоритма-то не влияет...
на сложность не влияет, только на скорость.
silent_1991
Эксперт C++
4938 / 3014 / 149
Регистрация: 11.11.2009
Сообщений: 7,024
Завершенные тесты: 1
28.12.2011, 16:49     Бинарно-последовательный поиск #12
valeriikozlov, я всё-же привык, что алгоритм называют "быстрым", когда его сложность по отношению к базовому меняется. Ну да ладно, это всё лирика)) Главное, решение найдено.
Ватадот
 Аватар для Ватадот
3 / 3 / 0
Регистрация: 11.01.2011
Сообщений: 155
28.12.2011, 17:03  [ТС]     Бинарно-последовательный поиск #13
silent_1991, суть в том что в последовательном поиске например в цикле while производитьсся два сравнениеяi<=n) и (A[i]<>Key),в быстром-последовательном убираем 1но сравнение,поменяв на A[n+1]:=Key.Надо сказать, что хотя такой фрагмент кода будет работать быстрее, но его теоретическая сложность остается такой же.

Добавлено через 3 минуты
http://altim.narod.ru/Docs/Russian/M...r3/Finding.htm
Цитата отсуда
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
28.12.2011, 17:04     Бинарно-последовательный поиск
Еще ссылки по теме:

Последовательный вывод элементов массива на экран с задержкой C++
Массивы и последовательный поиск C++
C++ Последовательный вызов методов класса

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
silent_1991
Эксперт C++
4938 / 3014 / 149
Регистрация: 11.11.2009
Сообщений: 7,024
Завершенные тесты: 1
28.12.2011, 17:04     Бинарно-последовательный поиск #14
Цитата Сообщение от Ватадот Посмотреть сообщение
но его теоретическая сложность остается такой же
Вот я об этом и говорил))
Yandex
Объявления
28.12.2011, 17:04     Бинарно-последовательный поиск
Ответ Создать тему
Опции темы

Текущее время: 06:37. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru