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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 23, средняя оценка - 4.96
Ватадот
3 / 3 / 0
Регистрация: 11.01.2011
Сообщений: 155
#1

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

28.12.2011, 15:28. Просмотров 3009. Ответов 13
Метки нет (Все метки)

Здраствуйте.Ктонить может написать алгоритм бинарно-последновательного поиска.Плз в инете искал несмог найти...

Добавлено через 29 минут
Или мне кажется что такого нет поиска??
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
silent_1991
Эксперт С++
4956 / 3032 / 149
Регистрация: 11.11.2009
Сообщений: 7,027
Завершенные тесты: 1
28.12.2011, 15:46     Бинарно-последовательный поиск #2
Ватадот, не представляю, как бинарный (последовательный) поиск может в то же время быть последовательным (бинарным). Это два разных подхода, причём один универсальный, другой специальный.
Ватадот
3 / 3 / 0
Регистрация: 11.01.2011
Сообщений: 155
28.12.2011, 15:50  [ТС]     Бинарно-последовательный поиск #3
Тю блин,я ошибся мне надо Быстрого-последовательного поиска алгоритм
silent_1991
Эксперт С++
4956 / 3032 / 149
Регистрация: 11.11.2009
Сообщений: 7,027
Завершенные тесты: 1
28.12.2011, 15:53     Бинарно-последовательный поиск #4
Ватадот, тоже не очень понятно... Последовательный - он и есть последовательный, ишет, пока не найдёт. Как его можно вот просто так взять и ускорить?
Ватадот
3 / 3 / 0
Регистрация: 11.01.2011
Сообщений: 155
28.12.2011, 16:13  [ТС]     Бинарно-последовательный поиск #5
Быстрый последовательный поиск он точно есть.Суть заключается в оптимизации циклов,то есть сокращение числа действий в них.
silent_1991
Эксперт С++
4956 / 3032 / 149
Регистрация: 11.11.2009
Сообщений: 7,027
Завершенные тесты: 1
28.12.2011, 16:25     Бинарно-последовательный поиск #6
Ватадот, как можно оптимизировать один-единственный цикл, в котором последовательно сравниваются элементы некоторой последовательности на предмет совпадения с искомым, с учётом того, что элементы в последовательности расположены произвольно (т.е. мы ничего не знаем заранее об их порядке)? Бинарный поиск и есть оптимизация обычного, но с учётом того, что последовательность упорядочивается (т.е. в неё вносится некоторая закономерность, благодаря которой и становится возможным сократить число итераций).
По логике всё так, но вдруг я чего-то не знаю? Пруф в студию.
valeriikozlov
Эксперт C++
4663 / 2489 / 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
Эксперт С++
4956 / 3032 / 149
Регистрация: 11.11.2009
Сообщений: 7,027
Завершенные тесты: 1
28.12.2011, 16:34     Бинарно-последовательный поиск #8
valeriikozlov, а где "быстрый"?)) Это же обычный последовательный поиск.
valeriikozlov
Эксперт C++
4663 / 2489 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
28.12.2011, 16:36     Бинарно-последовательный поиск #9
Цитата оттуда:
6.1. Последовательный поиск
.....
.....
Оказывается, что данный алгоритм можно ускорить при помощи
вставки ключа поиска в конец массива ключей.
Быстрый последовательный поиск:
....
....
....
silent_1991
Эксперт С++
4956 / 3032 / 149
Регистрация: 11.11.2009
Сообщений: 7,027
Завершенные тесты: 1
28.12.2011, 16:45     Бинарно-последовательный поиск #10
Мдя... Так-то оно может и так, но на сложность алгоритма-то не влияет...
valeriikozlov
Эксперт C++
4663 / 2489 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
28.12.2011, 16:46     Бинарно-последовательный поиск #11
Цитата Сообщение от silent_1991 Посмотреть сообщение
но на сложность алгоритма-то не влияет...
на сложность не влияет, только на скорость.
silent_1991
Эксперт С++
4956 / 3032 / 149
Регистрация: 11.11.2009
Сообщений: 7,027
Завершенные тесты: 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++
C++ Последовательный вызов методов класса
Непрерывное чтение и обработка с com порта (последовательный порт) в Visual C++ C++

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

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

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