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

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

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

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

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

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

Добавлено через 29 минут
Или мне кажется что такого нет поиска??
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
28.12.2011, 15:28
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Бинарно-последовательный поиск (C++):

Индексно-последовательный поиск - C++
вообщем задание такое: "Организовать индексно-последовательный поиск в файле, содержащем список студентов ВУЗа, упорядоченный по фамилии....

Массивы и последовательный поиск - C++
Помогите пожалуйста. Дан массив X.Определить, есть ли в массиве число Z, с использованием метода последовательного поиска.

Поиск. Последовательный поиск - C++
Через 2 дня сдавать лабу =-O , а я до сих пор ни могу с ней справиться :umnik: ... Препад, чесное слово " дебил " :-| , дал задания, а...

Последовательный и быстрый последовательный поиски - C++
Разработать программу для реализации алгоритма последовательного поиска. Написала программу для быстрого последовательного поиска, не...

Метод поиска - последовательный с барьером - C++
Нужно найти в каждой строке матрицы координаты элемента, равного k( если таковые имеются). Метод поиска - последовательный с барьером. C++ ...

Последовательный вызов методов класса - C++
Здравствуйте. Есть два метода, как их запихнуть в класс, чтобы оба работали, сначала один, затем другой? пробовал много способов, и через...

13
silent_1991
Эксперт С++
4985 / 3042 / 149
Регистрация: 11.11.2009
Сообщений: 7,027
Завершенные тесты: 1
28.12.2011, 15:46 #2
Ватадот, не представляю, как бинарный (последовательный) поиск может в то же время быть последовательным (бинарным). Это два разных подхода, причём один универсальный, другой специальный.
1
Ватадот
3 / 3 / 0
Регистрация: 11.01.2011
Сообщений: 155
28.12.2011, 15:50  [ТС] #3
Тю блин,я ошибся мне надо Быстрого-последовательного поиска алгоритм
0
silent_1991
Эксперт С++
4985 / 3042 / 149
Регистрация: 11.11.2009
Сообщений: 7,027
Завершенные тесты: 1
28.12.2011, 15:53 #4
Ватадот, тоже не очень понятно... Последовательный - он и есть последовательный, ишет, пока не найдёт. Как его можно вот просто так взять и ускорить?
0
Ватадот
3 / 3 / 0
Регистрация: 11.01.2011
Сообщений: 155
28.12.2011, 16:13  [ТС] #5
Быстрый последовательный поиск он точно есть.Суть заключается в оптимизации циклов,то есть сокращение числа действий в них.
0
silent_1991
Эксперт С++
4985 / 3042 / 149
Регистрация: 11.11.2009
Сообщений: 7,027
Завершенные тесты: 1
28.12.2011, 16:25 #6
Ватадот, как можно оптимизировать один-единственный цикл, в котором последовательно сравниваются элементы некоторой последовательности на предмет совпадения с искомым, с учётом того, что элементы в последовательности расположены произвольно (т.е. мы ничего не знаем заранее об их порядке)? Бинарный поиск и есть оптимизация обычного, но с учётом того, что последовательность упорядочивается (т.е. в неё вносится некоторая закономерность, благодаря которой и становится возможным сократить число итераций).
По логике всё так, но вдруг я чего-то не знаю? Пруф в студию.
0
valeriikozlov
Эксперт С++
4670 / 2496 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
28.12.2011, 16:30 #7
Может быть имеется ввиду это:
http://window.edu.ru/window/library/pdf2txt?p_id=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;
}
0
silent_1991
Эксперт С++
4985 / 3042 / 149
Регистрация: 11.11.2009
Сообщений: 7,027
Завершенные тесты: 1
28.12.2011, 16:34 #8
valeriikozlov, а где "быстрый"?)) Это же обычный последовательный поиск.
0
valeriikozlov
Эксперт С++
4670 / 2496 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
28.12.2011, 16:36 #9
Цитата оттуда:
6.1. Последовательный поиск
.....
.....
Оказывается, что данный алгоритм можно ускорить при помощи
вставки ключа поиска в конец массива ключей.
Быстрый последовательный поиск:
....
....
....
0
silent_1991
Эксперт С++
4985 / 3042 / 149
Регистрация: 11.11.2009
Сообщений: 7,027
Завершенные тесты: 1
28.12.2011, 16:45 #10
Мдя... Так-то оно может и так, но на сложность алгоритма-то не влияет...
0
valeriikozlov
Эксперт С++
4670 / 2496 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
28.12.2011, 16:46 #11
Цитата Сообщение от silent_1991 Посмотреть сообщение
но на сложность алгоритма-то не влияет...
на сложность не влияет, только на скорость.
1
silent_1991
Эксперт С++
4985 / 3042 / 149
Регистрация: 11.11.2009
Сообщений: 7,027
Завершенные тесты: 1
28.12.2011, 16:49 #12
valeriikozlov, я всё-же привык, что алгоритм называют "быстрым", когда его сложность по отношению к базовому меняется. Ну да ладно, это всё лирика)) Главное, решение найдено.
0
Ватадот
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/Manuals/Lab/Chapter3/Finding.htm
Цитата отсуда
0
silent_1991
Эксперт С++
4985 / 3042 / 149
Регистрация: 11.11.2009
Сообщений: 7,027
Завершенные тесты: 1
28.12.2011, 17:04 #14
Цитата Сообщение от Ватадот Посмотреть сообщение
но его теоретическая сложность остается такой же
Вот я об этом и говорил))
0
28.12.2011, 17:04
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
28.12.2011, 17:04
Привет! Вот еще темы с ответами:

Последовательный ввод двух строк - C++
мне нужно ввести две строки одна за другой,но у меня сразу предлагается ввод двух строк string name,for_number; vector&lt;int&gt; number;...

Последовательный вывод элементов массива на экран с задержкой - C++
Допустим, имеется какой-то простой массив на 10 элементов. Объясните, пожалуйста, как эти элементы выводить на экран не все сразу, а с...

Последовательный сдвиг текста при нажатии клавиши - C++
Добрый день. Прошу помощи в решении лабы. Задание: Составить программу, последовательно сдвигающую текст на экране ПЭВМ вверх на одну...

Непрерывное чтение и обработка с com порта (последовательный порт) в Visual C++ - C++
Здравствуйте, я задумал одну идею с GPS приемником, но для того чтобы реализовать это мне необходимо читать и обработать данные с com порта...


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

Или воспользуйтесь поиском по форуму:
14
Ответ Создать тему
Опции темы

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