Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 16, средняя оценка - 4.63
Amell
0 / 0 / 0
Регистрация: 05.09.2011
Сообщений: 13
#1

Перебор значений double - C++

05.09.2011, 02:14. Просмотров 2105. Ответов 30
Метки нет (Все метки)

Привет всем, весь день сижу и думаю над алгоритмом следующего

Нам известна функция которая принимает один параметр типа double и возвращает double.

Реализация функции неизвестна, но известны некоторые особенности:
  1. При вызове функции с параметром 0.0, мы получим число меньше нуля
  2. При вызове функции с параметром 1.0, мы получим число больше нуля
  3. Есть лишь единственное значение Х, между 0.0 и 1.0, при которых функция вернет 0

  • Цель - написать функцию перебора чисел от 0.0 до 1.0 чтобы найти при каком значение Х мы получим 0 из функции о которой писалось выше.


Естественно, double - число довольно здоровое, и хотя мы ограничены определенным диапозоном, у нас всеравно остается куча вариантов для перебора.. [0.000000000000001 ; 0.999999999999999] Простой перебор, увеличение Х на 0.000000000000001 в цикле, займет вечность, хотя и будет самым точным..

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

Можетбыть кто знает какие способы по скоращению времени на перебор в данном случае? Или куда глядеть дальше по этой теме?
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
05.09.2011, 02:14
Я подобрал для вас темы с готовыми решениями и ответами на вопрос Перебор значений double (C++):

Ошибки error C2296: -: недопустимо, левый операнд имеет тип "double (__cdecl *)(double,double,double
Думаю из-за polp #include<iostream> #include<cmath> #include<cstdlib>...

Ошибка: error LNK2001: unresolved external symbol "double __cdecl Akk(double,double,double)"
#include <iostream> #include <cmath> using namespace std; double Akk(double...

перебор значений
Вывести на экран в возрастающем порядке все трехзначные числа, в десятичной...

Перебор значений
Вывести на экран в возрастающем порядке все трехзначные числа, в десятичной...

Перебор значений
Комрады, как мне заставить программу подбирать значение х и у не только парные...

Перебор и сравнение значений
Добрый день. Столкнулся с проблемой перебора. Есть входные данные и массив с...

30
Jupiter
Каратель
Эксперт С++
6568 / 3989 / 400
Регистрация: 26.03.2010
Сообщений: 9,273
Записей в блоге: 1
Завершенные тесты: 2
05.09.2011, 02:31 #2
Метод половинного деления
1
5ANDR0
3 / 3 / 2
Регистрация: 27.07.2011
Сообщений: 13
05.09.2011, 02:38 #3
Метод_половинного_деления
А кто сказал, что функция выдает непрерывно возрастающие значения?
Может перебирать все варианты начиная из нескольких мест сразу(например с начала и с конца),
так вероятность, что попадется быстрее выше.
0
Amell
0 / 0 / 0
Регистрация: 05.09.2011
Сообщений: 13
05.09.2011, 02:51  [ТС] #4
Перебор с двух концов идея не плохая, однако сокращение во времени тут будет зависеть от параметра.

Если параметр при котором функция вернет 0 находится в середине диапозона 0.0.....1 - 0.(9) то мы ничего не сократим.

С другой стороны если оно на начале 0.0....1 или в конце диапозона, тогда сократим.


Однако, не думаю что сокращение по времени будет большим.
0
grizlik78
Эксперт С++
1983 / 1476 / 191
Регистрация: 29.05.2011
Сообщений: 3,048
05.09.2011, 02:52 #5
Цитата Сообщение от 5ANDR0 Посмотреть сообщение
А кто сказал, что функция выдает непрерывно возрастающие значения?
А монотонность (то есть непрерывное возрастание) для половинного деления и не требуется. Главное, чтобы функция меняла знак только один раз, проходя через ноль. Если функция может менять знак сколько угодно раз (очевидно, имея множество разрывов), то задача в общем случае нерешаема.
0
Amell
0 / 0 / 0
Регистрация: 05.09.2011
Сообщений: 13
05.09.2011, 02:57  [ТС] #6
Забыл написать, функция математически непрерывная. Значит меняет знак один раз.

Значит судя по сообщениям, следует попробовать Метод половинного деления, попробую утрецом, отпишусь.
0
grizlik78
Эксперт С++
1983 / 1476 / 191
Регистрация: 29.05.2011
Сообщений: 3,048
05.09.2011, 03:00 #7
Раз она непрерывна и проходит через ноль только один раз, то и знак меняет только один раз. Так что метод половинного деления — это как раз то, что позволит очень быстро приблизиться вплотную к искомому значению.
1
Amell
0 / 0 / 0
Регистрация: 05.09.2011
Сообщений: 13
05.09.2011, 03:02  [ТС] #8
Думаете она сможет относительно быстро перебрать этот диапозон?

В любом случае, пошел читать про этот метод.
0
grizlik78
Эксперт С++
1983 / 1476 / 191
Регистрация: 29.05.2011
Сообщений: 3,048
05.09.2011, 03:05 #9
Не больше, чем за 64 итерации А на самом деле даже меньше.
1
kazak
05.09.2011, 03:28
  #10

Не по теме:

Цитата Сообщение от Amell Посмотреть сообщение
Забыл написать, функция математически непрерывная. Значит меняет знак один раз.
Это утверждение справедливо для монотонных функций.

0
Amell
0 / 0 / 0
Регистрация: 05.09.2011
Сообщений: 13
05.09.2011, 03:33  [ТС] #11
Написал, работает!
Спасибо огромное!

Осталось теперь попроверять точность с несколькими разными уравнениями подходящими под описание, но посложнее чем то что я там понаписал для тестов, есть варианты?
0
grizlik78
Эксперт С++
1983 / 1476 / 191
Регистрация: 29.05.2011
Сообщений: 3,048
05.09.2011, 03:33 #12
Цитата Сообщение от kazak Посмотреть сообщение
Это утверждение справедливо для монотонных функций.
Это, конечно, так, но если условие 3 относится именно к реализации, а не к математической функции, то задача снова становится нерешаемой в общем случае. Если же условие всё-так означает, что сама математическая функция проходит через ноль только один раз, то вместе с непрерывностью это гарантирует единственную смену знака.
0
alkagolik
Заблокирован
05.09.2011, 03:34 #13
это конечно правильно, но ведь
Реализация функции неизвестна
как же тогда проверять значения функции на знак? Подставим x=1/2... а куда подставим?
0
Amell
0 / 0 / 0
Регистрация: 05.09.2011
Сообщений: 13
05.09.2011, 03:35  [ТС] #14
kazak, значит решение данной задачи с помощью этого метода не может гарантировать в итоге решение для всех функций и присутвуют исключения?

Вообще запутался...
0
grizlik78
Эксперт С++
1983 / 1476 / 191
Регистрация: 29.05.2011
Сообщений: 3,048
05.09.2011, 03:40 #15
Цитата Сообщение от Amell Посмотреть сообщение
Реализация функции неизвестна, но известны некоторые особенности:
Это особенности реализации или самой функции?
0
Amell
0 / 0 / 0
Регистрация: 05.09.2011
Сообщений: 13
05.09.2011, 03:45  [ТС] #16
Вобщем есть некая функция:

double d_Function(double X);

Мы не знаем ничего про само тело функции. Нам лишь известно следующее:
  1. d_Function математически непрерывная функция
  2. При d_Function(0.0f), return из функции выйдет < 0
  3. При d_Function(1.0f), return из функции выйдет > 0
  4. Есть лишь одно значение Х, при которых return из функции = 0.0f
0
alkagolik
Заблокирован
05.09.2011, 03:48 #17
дизассемблер, дебаггер и узнать функцию. иначе перебор (и то... как?). Или есть возможность кормить ей переменные? Если есть, то деление пополам лучший вариант (я так думаю)
0
Amell
0 / 0 / 0
Регистрация: 05.09.2011
Сообщений: 13
05.09.2011, 03:49  [ТС] #18
узнать функцию к сожалению невозможно
0
grizlik78
Эксперт С++
1983 / 1476 / 191
Регистрация: 29.05.2011
Сообщений: 3,048
05.09.2011, 03:52 #19
Всё чудесатее и чудесатее (C)
Числа 1.0f и 0.0f имеют тип float. При этом аргумент и результат функций объявлены как double. По-моему кто-то хочет нас запутать

Цитата Сообщение от alkagolik Посмотреть сообщение
дизассемблер, дебаггер и узнать функцию. иначе перебор
Чтобы перебрать все числа double на отрезке (0.0, 1.0) потребуется очень быстрый вычислитель и очень много времени. Ну или очень много удачи
0
Amell
0 / 0 / 0
Регистрация: 05.09.2011
Сообщений: 13
05.09.2011, 03:54  [ТС] #20
Пардонте, там не флоат (без f), привычка так записывать числа с плав точкой просто

Тобишь, метод половинного деления будет работать только елси математически функция монотонная, я правильно понял? Попытаюсь тогда разузнать, монотонна она или нет.
0
05.09.2011, 03:54
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
05.09.2011, 03:54
Привет! Вот еще темы с решениями:

Перебор действительных значений в цикле
Ребят, вот только начал изучать с++ и сразу же возник вопрос. Есть X-начальное...

Перебор возможных значений для трёх чисел
Доброго времени суток. Нужно перебрать все возможные значения трёх чисел. их...

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

Объясните перебор всех значений от 0 до n с помощью битовых операций
for (int i = (1 &lt;&lt; n) - 1; i &gt;= 0; i--) { for (int j = 0; j &lt; n; j++) {...


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

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

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