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

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

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 19, средняя оценка - 4.95
hoob
19 / 11 / 1
Регистрация: 04.11.2012
Сообщений: 89
Записей в блоге: 1
#1

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

01.04.2013, 01:57. Просмотров 2487. Ответов 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
+ Входной массив отсортирован по возрастанию
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
01.04.2013, 01:57     Поиск методом золотого сечения
Посмотрите здесь:

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

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

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

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

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

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

Метод золотого сечения. - C++
Народ, подскажите пожалуйста как будет выглядеть задача на С++ по методу Золотого сечения, при условии: F0(x)= -(x*x*x)+9(x*x)-24x-2 ...

После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
salam
160 / 141 / 12
Регистрация: 10.07.2012
Сообщений: 720
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
_
201 / 145 / 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
160 / 141 / 12
Регистрация: 10.07.2012
Сообщений: 720
01.04.2013, 15:59     Поиск методом золотого сечения #6
как вам сказать...) просто метод ЗС не имеет никакого отношения к поиску в массиве.
ya_noob
_
201 / 145 / 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++
Помогите пожалуйста прокомментировать данную программу, а то не до конца пойму все действия. #include &lt;iostream&gt; #define eps 1e-3 ...

Метод золотого сечения считается неправильно - C++
#include &quot;stdafx.h&quot; #include &quot;stdio.h&quot; #include &quot;conio.h&quot; #include &quot;math.h&quot; #include &lt;iostream&gt; float Afunc(float x1) { ...

Метод хорд, касательных, золотого сечения - C++
Написать программу которая решает какой из методов дает более точный результат для уравнения (уравнение свое), Хорд/касательных/золотого...


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

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

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