Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.62/21: Рейтинг темы: голосов - 21, средняя оценка - 4.62
21 / 13 / 5
Регистрация: 04.11.2012
Сообщений: 89
Записей в блоге: 1
1

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

01.04.2013, 01:57. Просмотров 4147. Ответов 8
Метки нет (Все метки)

Здравствуйте, вот задался целью написать поиск в большом массиве, с помощью метода золотого сечения:
вернуть функция должна номер элемента в массиве, если он там есть, -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
+ Входной массив отсортирован по возрастанию
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
01.04.2013, 01:57
Ответы с готовыми решениями:

Поиск элемента в массиве методом золотого сечения
* Составить блок-схему алгоритма поиска элемента в массиве методом золотого сечения. Массив...

найти методом золотого сечения минимум
просто нужно взять любое линейное уравнение и найти методом золотого сечения минимум. и на с++ всё...

Найти минимум функции методом золотого сечения.
Помогите пожалуйста!... Нужно найти минимум функции у=х*х-sinх методом золотого сечения. в СИ....

Вычисление корня нелинейного уравнения методом Золотого сечения.
Всем вечер добрый, нужен алгоритм поиска корня нелинейного уравнения методом Золотого сечения....

8
193 / 173 / 30
Регистрация: 10.07.2012
Сообщений: 800
01.04.2013, 05:08 2
Цитата Сообщение от hoob Посмотреть сообщение
Входной массив отсортирован по возрастанию
используйте в таких случаях всегда бинпоиск. быстро пишется и работает за логарифм с маленькой константой.
0
21 / 13 / 5
Регистрация: 04.11.2012
Сообщений: 89
Записей в блоге: 1
01.04.2013, 13:55  [ТС] 3
Цитата Сообщение от salam Посмотреть сообщение
используйте в таких случаях всегда бинпоиск. быстро пишется и работает за логарифм с маленькой константой.
Но ведь золотое сечение оптимально, а значит работает шустрее, так почему нет?

Добавлено через 5 часов 6 минут
подниму-ка я тему: актуальна(
0
_
317 / 151 / 27
Регистрация: 08.10.2011
Сообщений: 432
01.04.2013, 15:03 4
Цитата Сообщение от hoob Посмотреть сообщение
Здравствуйте, вот задался целью написать поиск в большом массиве, с помощью метода золотого сечения:
вернуть функция должна номер элемента в массиве, если он там есть, -1, в случае, если элемент попадает в нужный мне диапазон и -2, если он совсем мне не нужен. Но искать элементы он отказывается: все время возвращает либо -1, либо -2
Чем отличаются случаи, выделенные жирным?
0
21 / 13 / 5
Регистрация: 04.11.2012
Сообщений: 89
Записей в блоге: 1
01.04.2013, 15:08  [ТС] 5
Цитата Сообщение от ya_noob Посмотреть сообщение
Чем отличаются случаи, выделенные жирным?
Суть в том, что я должен параллельно записывать в массив новые данные, при этом хочу избежать повторений, поэтому, если элемент попадает в нужный дипазон и не содержится там, то я возвращаю -1 и уже по этому коду возврата решаю, что элемент нужен и мне нужно его добавить в массив, а в случае, если элемент не входит в нужный мне диапазон я возвращаю -2 и не записываю его в массив. Может существует и более простой способ решения этой проблемы, не отрицаю. Буду рад, если подскажите)
0
193 / 173 / 30
Регистрация: 10.07.2012
Сообщений: 800
01.04.2013, 15:59 6
как вам сказать...) просто метод ЗС не имеет никакого отношения к поиску в массиве.
0
_
317 / 151 / 27
Регистрация: 08.10.2011
Сообщений: 432
01.04.2013, 16:12 7
ах вон оно что.
а вы уверены в правильности условия в 29 строке? по мне так оно не полное т.к. цикл завершается когда а и b либо совпадают, либо |а-b|=1, следовательно нужно проверить оба исхода
1
21 / 13 / 5
Регистрация: 04.11.2012
Сообщений: 89
Записей в блоге: 1
01.04.2013, 21:38  [ТС] 8
Цитата Сообщение от salam Посмотреть сообщение
как вам сказать...) просто метод ЗС не имеет никакого отношения к поиску в массиве.
Обоснуйте?)) Кто мешает искать мне минимум функции вида f=y-searchValue ?
0
193 / 173 / 30
Регистрация: 10.07.2012
Сообщений: 800
02.04.2013, 17:40 9
никто по сути... просто это говнокод.
1
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
02.04.2013, 17:40

Заказываю контрольные, курсовые, дипломные и любые другие студенческие работы здесь.

Метод Золотого сечения. Пассивный поиск
Нужно написать программу Описание на картинке. Выручайте! Спасибо заранее кто поможет...

Поиск экстремумов, методы золотого сечения, дихотомии, кв. интерполяции-экстраполяции
Всем привет! Возникли проблемы с реализацией методов, указанных выше. Функция всегда используется...

Метод золотого сечения
Доброго времения суток. Помогите пжлст исправить или добавь формулу(методы Золотого сечения). Там...

Метод золотого сечения
Народ, подскажите пожалуйста как будет выглядеть задача на С++ по методу Золотого сечения, найти...

Метод золотого сечения
Ребята помогите нужно методом золотого сечения найти функцию(смотрел как это решали другие на вашем...

Метод золотого сечения
Пожалуйста , скиньте код Золотого сечения на С++ и объясните строчки именно с алгоритмом , очень...


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

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

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