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

Поиск методом золотого сечения - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 19, средняя оценка - 4.95
hoob
19 / 11 / 1
Регистрация: 04.11.2012
Сообщений: 89
Записей в блоге: 1
01.04.2013, 01:57     Поиск методом золотого сечения #1
Здравствуйте, вот задался целью написать поиск в большом массиве, с помощью метода золотого сечения:
вернуть функция должна номер элемента в массиве, если он там есть, -1, в случае, если элемент попадает в нужный мне диапазон и -2, если он совсем мне не нужен. Но искать элементы он отказывается: все время возвращает либо -1, либо -2


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
26
27
28
29
30
31
32
33
34
35
36
37
int MainWindow::searchId(vector<node> *nodeVector, unsigned int searchValue){
    if( (searchValue>nodeVector->at(0).id) && (searchValue<nodeVector->at(nodeVector->size()-1).id) ){
        unsigned int x1,x2,y1,y2,a,b;
        double alpha,beta;
        a=0;
        b=nodeVector->size()-1;
        alpha=(sqrt(5)-1)/2;
        beta=(3-sqrt(5))/2;
        x1=alpha*a+beta*b;
        x2=beta*a+alpha*b;
        y1=nodeVector->at(x1).id-searchValue;
        y2=nodeVector->at(x2).id-searchValue;
        while( ((a-b)>2) && ((a-b)>-2)){
            if(y1<y2){
                b=x2;
                x2=x1;
                y2=y1;
                x1=alpha*a+beta*b;
                y1=nodeVector->at(x1).id-searchValue;
            }
            else{
                a=x1;
                x1=x2;
                y1=y2;
                x2=beta*a+alpha*b;
                y2=nodeVector->at(x2).id-searchValue;
            }
        }
        if(nodeVector->at((a+b)/2).id==searchValue)
            return (a+b)/2;
        else
            return -1;
    }
    else
        return -2;
 
}

по идее, ищется же минимум функции y-searchValue
+ Входной массив отсортирован по возрастанию
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
salam
157 / 138 / 11
Регистрация: 10.07.2012
Сообщений: 709
01.04.2013, 05:08     Поиск методом золотого сечения #2
Цитата Сообщение от hoob Посмотреть сообщение
Входной массив отсортирован по возрастанию
используйте в таких случаях всегда бинпоиск. быстро пишется и работает за логарифм с маленькой константой.
hoob
19 / 11 / 1
Регистрация: 04.11.2012
Сообщений: 89
Записей в блоге: 1
01.04.2013, 13:55  [ТС]     Поиск методом золотого сечения #3
Цитата Сообщение от salam Посмотреть сообщение
используйте в таких случаях всегда бинпоиск. быстро пишется и работает за логарифм с маленькой константой.
Но ведь золотое сечение оптимально, а значит работает шустрее, так почему нет?

Добавлено через 5 часов 6 минут
подниму-ка я тему: актуальна(
ya_noob
_
200 / 144 / 9
Регистрация: 08.10.2011
Сообщений: 432
01.04.2013, 15:03     Поиск методом золотого сечения #4
Цитата Сообщение от hoob Посмотреть сообщение
Здравствуйте, вот задался целью написать поиск в большом массиве, с помощью метода золотого сечения:
вернуть функция должна номер элемента в массиве, если он там есть, -1, в случае, если элемент попадает в нужный мне диапазон и -2, если он совсем мне не нужен. Но искать элементы он отказывается: все время возвращает либо -1, либо -2
Чем отличаются случаи, выделенные жирным?
hoob
19 / 11 / 1
Регистрация: 04.11.2012
Сообщений: 89
Записей в блоге: 1
01.04.2013, 15:08  [ТС]     Поиск методом золотого сечения #5
Цитата Сообщение от ya_noob Посмотреть сообщение
Чем отличаются случаи, выделенные жирным?
Суть в том, что я должен параллельно записывать в массив новые данные, при этом хочу избежать повторений, поэтому, если элемент попадает в нужный дипазон и не содержится там, то я возвращаю -1 и уже по этому коду возврата решаю, что элемент нужен и мне нужно его добавить в массив, а в случае, если элемент не входит в нужный мне диапазон я возвращаю -2 и не записываю его в массив. Может существует и более простой способ решения этой проблемы, не отрицаю. Буду рад, если подскажите)
salam
157 / 138 / 11
Регистрация: 10.07.2012
Сообщений: 709
01.04.2013, 15:59     Поиск методом золотого сечения #6
как вам сказать...) просто метод ЗС не имеет никакого отношения к поиску в массиве.
ya_noob
_
200 / 144 / 9
Регистрация: 08.10.2011
Сообщений: 432
01.04.2013, 16:12     Поиск методом золотого сечения #7
ах вон оно что.
а вы уверены в правильности условия в 29 строке? по мне так оно не полное т.к. цикл завершается когда а и b либо совпадают, либо |а-b|=1, следовательно нужно проверить оба исхода
hoob
19 / 11 / 1
Регистрация: 04.11.2012
Сообщений: 89
Записей в блоге: 1
01.04.2013, 21:38  [ТС]     Поиск методом золотого сечения #8
Цитата Сообщение от salam Посмотреть сообщение
как вам сказать...) просто метод ЗС не имеет никакого отношения к поиску в массиве.
Обоснуйте?)) Кто мешает искать мне минимум функции вида f=y-searchValue ?
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
02.04.2013, 17:40     Поиск методом золотого сечения
Еще ссылки по теме:

найти методом золотого сечения минимум C++
Метод Золотого сечения. Пассивный поиск C++
Поиск элемента в массиве методом золотого сечения C++

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

Или воспользуйтесь поиском по форуму:
salam
157 / 138 / 11
Регистрация: 10.07.2012
Сообщений: 709
02.04.2013, 17:40     Поиск методом золотого сечения #9
никто по сути... просто это говнокод.
Yandex
Объявления
02.04.2013, 17:40     Поиск методом золотого сечения
Ответ Создать тему
Опции темы

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