21 / 13 / 5
Регистрация: 04.11.2012
Сообщений: 89
Записей в блоге: 1

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

01.04.2013, 01:57. Показов 6236. Ответов 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
IT_Exp
Эксперт
34794 / 4073 / 2104
Регистрация: 17.06.2006
Сообщений: 32,602
Блог
01.04.2013, 01:57
Ответы с готовыми решениями:

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

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

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

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

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

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

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

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

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

Метод золотого сечения
Народ, подскажите пожалуйста как будет выглядеть задача на С++ по методу Золотого сечения, найти максимум функции: F(x)= -cbrt(x^2)...


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

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

Новые блоги и статьи
Модель заражения группы наркоманов
alhaos 17.04.2026
Условия задачи сформулированы тут Суть: - Группа наркоманов из 10 человек. - Только один инфицирован ВИЧ. - Колются одной иглой. - Колются раз в день. - Колются последовательно через. . .
Мысли в слух. Про "навсегда".
kumehtar 16.04.2026
Подумалось тут, что наверное очень глупо использовать во всяких своих установках понятие "навсегда". Это очень сильное понятие, и я только начинаю понимать край его смысла, не смотря на то что давно. . .
My Business CRM
MaGz GoLd 16.04.2026
Всем привет, недавно возникла потребность создать CRM, для личных нужд. Собственно программа предоставляет из себя базу данных клиентов, в которой можно фиксировать звонки, стадии сделки, а также. . .
Знаешь почему 90% людей редко бывают счастливыми?
kumehtar 14.04.2026
Потому что они ждут. Ждут выходных, ждут отпуска, ждут удачного момента. . . а удачный момент так и не приходит.
Фиксация колонок в отчете СКД
Maks 14.04.2026
Фиксация колонок в СКД отчета типа Таблица. Задача: зафиксировать три левых колонки в отчете. Процедура ПриКомпоновкеРезультата(ДокументРезультат, ДанныеРасшифровки, СтандартнаяОбработка) / / . . .
Настройки VS Code
Loafer 13.04.2026
{ "cmake. configureOnOpen": false, "diffEditor. ignoreTrimWhitespace": true, "editor. guides. bracketPairs": "active", "extensions. ignoreRecommendations": true, . . .
Оптимизация кода на разграничение прав доступа к элементам формы
Maks 13.04.2026
Алгоритм из решения ниже реализован на нетиповом документе, разработанного в конфигурации КА2. Задачи, как таковой, поставлено не было, проделанное ниже исключительно моя инициатива. Было так:. . .
Контроль заполнения и очистка дат в зависимости от значения перечислений
Maks 12.04.2026
Алгоритм из решения ниже реализован на примере нетипового документа "ПланированиеПерсонала", разработанного в конфигурации КА2. Задача: реализовать контроль корректности заполнения дат назначения. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru