Как правильно реализовать алгоритм?

Question

[Michael]

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

public TaskResult FindValue()
        {
            double X = 1;
            double n = 0.1;
            double findValue = CalcValue(X);
            if (findValue > n)
            {
                while (findValue >= n)
                {
                    X += 1;
                    findValue = CalcValue(X);
                }
            }
        }

Проблема в том что при больших значениях X код выполняется долго. Я думал увеличивать Х не на 1 а на 10 например, что должно ускорить процесс нахождения нужного значения. Но данное решение мне тоже не очень нравится, пытался найти что то похожее в интернете нашел алгоритм Метод Хорд, реализовал его, но значения и близко не такие получаются какими должны быть. Скажите как можно ускорить процесс нахождения, может есть алгоритмы для решения подобных задач.

Upd Есть ограничение, если X > 1500 то останавливаем цикл

Comments

[cicatrix]

Алгоритм чего?
что делается в CalcValue? Если уж чего и оптимизировать, так там

[Michael]

cicatrix, Алгоритм поиска значения X в диапазоне от 1 до 1500. В CalcValue функция которая зависит от Х, там все оптимизировано. Мне интересно есть ли какой то способ при нахождении Х идти не по 1 а по более быстрому алгоритму.

[cicatrix]

Michael, Это зависит от того, что в CalcValue. Если есть корреляция между X и получаемым значением, то можно. Если нет корреляции, то есть пальцем в потолок - то нельзя.
Сейчас это угадайка без подсказок. Если по значению, возвращаемому CalcValue можно судить о том, насколько ты далеко или близко от желаемого результата, то поиск можно оптимизировать. А может быть и вообще обойтись без него.
В твоём же случае, ты просто перебираешь числа, не зная критерия. Ну давай я загадаю число от 1 до 10 тыс., а ты угадай, при этом я могу ответить только да, угадал или нет, не угадал. Как это оптимизировать можно?

[soloveid]

Есть программа суть которой найти значение удовлетворяющее условию.

Ну это похоже на поиск нуля функции. Если CalcValue это непрерывная функция, то можно использовать
метод градиентного спуска.

Answer 1

[Sergey В.]

Делал подобный проект.
1. Сначала нужно определить границы начального значения. В вашем случае это 1...1500
2. Далее - определяем разрядность максимального значения. В вашем случае это тысяча: 1000
3. Шагаем в цикле с шагом +1000 Это значения 1, 1000, 2000 (последнее на самом деле 1500). Вычисляем CalcValue. Допустим определили, что нужное значение находится во второй тысяче.
4. Шагаем в цикле во второй тысяче с шагом +100 это значения 1000, 1100, 1200, 1300 ... 2000 Вычисляем CalcValue. Допустим определили, что нужное значение находится в третьей сотне.
5. Шагаем в цикле в третьей сотне с шагом +10 это значения 1300, 1310, 1320, .... 1400 Вычисляем CalcValue.
И так далее, идём до единиц.
В этом алгоритме вычисление CalcValue будет производиться минимальное количество раз.

Comments

[soloveid]

Допустим определили, что нужное значение находится во второй тысяче.

Не совсем понятно как понять по трём значениям, какой участок нужен.
Минимум, среднее?

[Sergey В.]

soloveid,
Например:
При Х = 1, (findValue > n) = true
При Х = 1000, (findValue > n) = true
При Х = 2000, (findValue > n) = false
Значит искомое значение в диапазоне 1000...2000
Обратите внимание, что этот алгоритм можно применять при линейной зависимости, т.е. вычисленное значение не "прыгает".

[freeExec]

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

При Х = 2000, (findValue > n) = false

Второе, ответ уже найден! зачем там все эти диапазоны

[Michael]

BasiC2k, интересно, по описанию как раз то что я искал. Завтра попробую реализовать, спасибо.

[soloveid]

BasiC2k,

При Х = 1, (findValue > n) = true
При Х = 1000, (findValue > n) = true
При Х = 2000, (findValue > n) = false

Это не будет работать, так как наврядли ты попадёшь в 2000 и выполнится условие.

[Michael]

Все получилось, спасибо BasiC2k,
Сделал так

public double FindValue()
        {
            double step_100 == 100;
            double step_10 == 10;
            double step == 1;
            double X = 1;
            double n = 0.1;

            double stepX;

            double findValue = CalcValue(X);
            if (findValue > n)
            {
                       var (stepStart100, stepEnd100) = CalcX(X, 1500, step_100, n);
                        var (stepStart, stepEnd) = CalcX(stepStart100, stepEnd100, step_10, n);
                        (stepX, X) = CalcX(stepStart, stepEnd, step, n);
            }
            return X;
        }

        private (double, double) CalcX(double stepStart, double stepEnd, double step, double n)
        {
            bool stopCalc = false;
            double prevX = stepStart;
            while (stopCalc != true && stepStart <= stepEnd)
            {
                double findValue = CalcValue(stepStart);

                if (findValue >= n)
                {
                    prevX = stepStart;
                    stepStart += step;
                }
                else
                    stopCalc = true;
            }

            return (prevX, stepStart);
        }