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

@Ватадот · Регистрация: 11.01.2011

Author24 — интернет-сервис помощи студентам

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

Добавлено через 29 минут
Или мне кажется что такого нет поиска??

silent_1991 · 28.12.2011, 15:46

Ватадот, не представляю, как бинарный (последовательный) поиск может в то же время быть последовательным (бинарным). Это два разных подхода, причём один универсальный, другой специальный.

@Ватадот · 28.12.2011, 15:50 **[ТС]**

Тю блин,я ошибся мне надо Быстрого-последовательного поиска алгоритм

silent_1991 · 28.12.2011, 15:53

Ватадот, тоже не очень понятно... Последовательный - он и есть последовательный, ишет, пока не найдёт. Как его можно вот просто так взять и ускорить?

@Ватадот · 28.12.2011, 16:13 **[ТС]**

Быстрый последовательный поиск он точно есть.Суть заключается в оптимизации циклов,то есть сокращение числа действий в них.

silent_1991 · 28.12.2011, 16:25

Ватадот, как можно оптимизировать один-единственный цикл, в котором последовательно сравниваются элементы некоторой последовательности на предмет совпадения с искомым, с учётом того, что элементы в последовательности расположены произвольно (т.е. мы ничего не знаем заранее об их порядке)? Бинарный поиск и есть оптимизация обычного, но с учётом того, что последовательность упорядочивается (т.е. в неё вносится некоторая закономерность, благодаря которой и становится возможным сократить число итераций).
По логике всё так, но вдруг я чего-то не знаю? Пруф в студию.

valeriikozlov · 28.12.2011, 16:30

Может быть имеется ввиду это:
http://window.edu.ru/window/li... 0&p_page=8
тогда вот пример:

C

#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 · 28.12.2011, 16:34

valeriikozlov, а где "быстрый"?)) Это же обычный последовательный поиск.

valeriikozlov · 28.12.2011, 16:36

Цитата оттуда:

6.1. Последовательный поиск
.....
.....
Оказывается, что данный алгоритм можно ускорить при помощи
вставки ключа поиска в конец массива ключей.
Быстрый последовательный поиск:
....
....
....

silent_1991 · 28.12.2011, 16:45

Мдя... Так-то оно может и так, но на сложность алгоритма-то не влияет...

valeriikozlov · 28.12.2011, 16:46

Сообщение от silent_1991

но на сложность алгоритма-то не влияет...

на сложность не влияет, только на скорость.

silent_1991 · 28.12.2011, 16:49

valeriikozlov, я всё-же привык, что алгоритм называют "быстрым", когда его сложность по отношению к базовому меняется. Ну да ладно, это всё лирика)) Главное, решение найдено.

@Ватадот · 28.12.2011, 17:03 **[ТС]**

silent_1991, суть в том что в последовательном поиске например в цикле while производитьсся два сравнениея

i<=n) и (A[i]<>Key),в быстром-последовательном убираем 1но сравнение,поменяв на A[n+1]:=Key.Надо сказать, что хотя такой фрагмент кода будет работать быстрее, но его теоретическая сложность остается такой же.

Добавлено через 3 минуты
http://altim.narod.ru/Docs/Rus... inding.htm
Цитата отсуда

silent_1991 · 28.12.2011, 17:04

Сообщение от Ватадот

но его теоретическая сложность остается такой же

Вот я об этом и говорил))

silent_1991 5055 / 3115 / 271 Регистрация: 11.11.2009 Сообщений: 7,044
	28.12.2011, 17:04	14
	Сообщение от Ватадот но его теоретическая сложность остается такой же Вот я об этом и говорил)) 0

@Ватадот 3 / 3 / 0 Регистрация: 11.01.2011 Сообщений: 155
		1
	Бинарно-последовательный поиск 28.12.2011, 15:28. Показов 4680. Ответов 13 Метки нет (Все метки) Здраствуйте.Ктонить может написать алгоритм бинарно-последновательного поиска.Плз в инете искал несмог найти... Добавлено через 29 минут Или мне кажется что такого нет поиска?? 0

silent_1991 5055 / 3115 / 271 Регистрация: 11.11.2009 Сообщений: 7,044
	28.12.2011, 15:46	2
	Ватадот, не представляю, как бинарный (последовательный) поиск может в то же время быть последовательным (бинарным). Это два разных подхода, причём один универсальный, другой специальный. 1

@Ватадот 3 / 3 / 0 Регистрация: 11.01.2011 Сообщений: 155
	28.12.2011, 15:50 [ТС]	3
	Тю блин,я ошибся мне надо Быстрого-последовательного поиска алгоритм 0

silent_1991 5055 / 3115 / 271 Регистрация: 11.11.2009 Сообщений: 7,044
	28.12.2011, 15:53	4
	Ватадот, тоже не очень понятно... Последовательный - он и есть последовательный, ишет, пока не найдёт. Как его можно вот просто так взять и ускорить? 0

@Ватадот 3 / 3 / 0 Регистрация: 11.01.2011 Сообщений: 155
	28.12.2011, 16:13 [ТС]	5
	Быстрый последовательный поиск он точно есть.Суть заключается в оптимизации циклов,то есть сокращение числа действий в них. 0

silent_1991 5055 / 3115 / 271 Регистрация: 11.11.2009 Сообщений: 7,044
	28.12.2011, 16:25	6
	Ватадот, как можно оптимизировать один-единственный цикл, в котором последовательно сравниваются элементы некоторой последовательности на предмет совпадения с искомым, с учётом того, что элементы в последовательности расположены произвольно (т.е. мы ничего не знаем заранее об их порядке)? Бинарный поиск и есть оптимизация обычного, но с учётом того, что последовательность упорядочивается (т.е. в неё вносится некоторая закономерность, благодаря которой и становится возможным сократить число итераций). По логике всё так, но вдруг я чего-то не знаю? Пруф в студию. 0

silent_1991 5055 / 3115 / 271 Регистрация: 11.11.2009 Сообщений: 7,044
	28.12.2011, 16:34	8
	valeriikozlov, а где "быстрый"?)) Это же обычный последовательный поиск. 0

valeriikozlov 4728 / 2549 / 757 Регистрация: 18.08.2009 Сообщений: 4,568
	28.12.2011, 16:36	9
	Цитата оттуда: 6.1. Последовательный поиск ..... ..... Оказывается, что данный алгоритм можно ускорить при помощи вставки ключа поиска в конец массива ключей. Быстрый последовательный поиск: .... .... .... 0

silent_1991 5055 / 3115 / 271 Регистрация: 11.11.2009 Сообщений: 7,044
	28.12.2011, 16:45	10
	Мдя... Так-то оно может и так, но на сложность алгоритма-то не влияет... 0

valeriikozlov 4728 / 2549 / 757 Регистрация: 18.08.2009 Сообщений: 4,568
	28.12.2011, 16:46	11
	Сообщение от silent_1991 но на сложность алгоритма-то не влияет... на сложность не влияет, только на скорость. 1

silent_1991 5055 / 3115 / 271 Регистрация: 11.11.2009 Сообщений: 7,044
	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/Rus... inding.htm Цитата отсуда 0