Алгоритмы. Поиск десятичного числа при известных границах поиска (мин/макс), Algorithms. Find the decimal number under certain boundaries of a search (min/max)
Дано: 1. Десятичное число для поиска. 2. Нижняя (искать от…) и верхняя (искать до…) границы поиска в виде десятичных чисел Границы входят в область, то есть заданное число может быть границей.
Задача: Найти заданные числа как можно быстрее.
Кроме бисекции/дихотомии/метода половинного деления (и то нужно докручивать) больше ничего на ум больше не приходит…
Option Base 1
Option Explicit
Option Private Module
'====================================================================================================
Sub Test()
Dim aFind(4) As Double, d#, t!, tt!, a&, c&, n&
Const cyc& = 100000, LB# = -6.789, UB# = 11.123
tt = Timer
aFind(1) = -6.456123789: aFind(2) = -1.123789456: aFind(3) = 3.123456789: aFind(4) = 9.987321654
Debug.Print "Find Value", "Steps", "Time", "Cycles"
Debug.Print String$(50, "_")
For a = 1 To UBound(aFind)
t = Timer
For c = 1 To cyc
n = PRDX_BiSection(aFind(a), LB, UB)
Next c
Debug.Print aFind(a), Format$(n, "#,##0"), Format$(Timer - t, "0.00 sec"), Format$(cyc, "#,##0")
Next a
Debug.Print String$(50, "_")
Debug.Print "Total Time: " & Format$(Timer - tt, "0.00 sec")
End Sub
'====================================================================================================
Function PRDX_BiSection(iFind#, ByVal LB#, ByVal UB#) As Long
Dim n&, f#
Do
n = n + 1: f = (LB + UB) / 2
Select Case True
Case f < iFind: LB = f
Case f > iFind: UB = f
Case Else: Exit Do
End Select
Loop
PRDX_BiSection = n
End Function
'====================================================================================================
'====================================================================================================
Во всех делах очень полезно периодически ставить знак вопроса к тому, что вы с давних пор считали не требующим доказательств (Бертран Рассел) ►Благодарности сюда◄
написал: Дано: 1. Десятичное число для поиска. 2. Нижняя (искать от…) и верхняя (искать до…) границы поиска в виде десятичных чисел Границы входят в область, то есть заданное число может быть границей.
Задача: Найти заданные числа как можно быстрее.
число уже найдено, см.п.1 (оно задано)
Программисты - это люди, решающие проблемы, о существовании которых Вы не подозревали, методами, которых Вы не понимаете!
Во всех делах очень полезно периодически ставить знак вопроса к тому, что вы с давних пор считали не требующим доказательств (Бертран Рассел) ►Благодарности сюда◄
Ігор Гончаренко написал: ничем не поспособствовал пониманию задачи(((
Мне не понятна задача, первое что пришло на ум уже здесь озвучено:
Цитата
Ігор Гончаренко написал: число уже найдено, см.п.1 (оно задано)
Количество итераций - одна, возвращаем искомое число, если оно находится в диапазоне поиска
Но, скорее всего, задача в другом. Может быть нужно найти аргумент функции, зная ее значение Метод Ньютона не подойдет или Метод хорд? Он должен быстрее сходится, чем метод половинного деления
Хотелось бы более подробно получить описание задачи.
Во всех делах очень полезно периодически ставить знак вопроса к тому, что вы с давних пор считали не требующим доказательств (Бертран Рассел) ►Благодарности сюда◄
Алексей. Задача непонятна и даже указанное применение, eё не поясняет. Любой поиск имеет услоаие по которому принимается решение, что нашли. Поис, как правило осуществляется по известному множеству. В противном случае это скорее подбор. Короче пиши в первом посте. Я почищу тему.
Погадаем. Скорее всего, автор имел ввиду что-то другое. Например, логично предположить, что номер этого числа между двумя заданными. Тогда вопрос должен звучать примерно так: Найти позицию числа С в заданном упорядоченном по возрастанию массиве чисел от А до В. Если все числа в массиве М строго возрастают на 0.000000001, то номер числа =А+С (+/- нижняя граница массива) без всякого поиска. Если числа в массиве последовательные не со строгим шагом, то в поиске можно использовать не деление пополам для очередного индекса, а примерный расчёт в зависимости от А, В и С. Например, если нижняя граница массива =LB, верхняя граница =UB, первое число в массиве M(LB)=А, последнее M(UB)=В, число для поиска =С, то текущий индекс k вычисляется как k=(C-A)/(B-A)*(UB-LB) + LB. Затем элемент массива M(k) сравнивается с С и в зависимости от > или < определяются новые границы LB и UB. И так по циклу.
БМВ: Поис, как правило осуществляется по известному множеству. В противном случае это скорее подбор
Возможно, тут больше про подбор (для примера с подбором высоты строки — точно), но, по-моему, сути это не меняет. Я ищу способ более быстрого поиска/подбора при постоянном приближении к результату. Чистить — не нужно, страна должна знать своих героев У нас полно тем с перепалками (в том числе, с твоим участием), так что пусть будет всё.
tolikt, ссылка не открывается) что с подбором высоты строки?
Во всех делах очень полезно периодически ставить знак вопроса к тому, что вы с давних пор считали не требующим доказательств (Бертран Рассел) ►Благодарности сюда◄
Офф... Не получилось вставить картинку напрямую в сообщение. Как это сделать, так и не понял: либо вставляется значок картинки, либо огромный текст с кучей случайных букв. Ссылка тоже, как видно, не прошла. Во вложении картинка.
tolikt, видел, хорошая) Поясню ещё: есть некий триггер, при котором мы понимаем, что число найдено. Для аналога подбора параметра - результат функции, основанной на подбираемом параметре, равный требуемому с заданной точностью. Для высоты строки - значение, при котором она начинает считаться скрытой/видимой (тут тоже без заданной точности не обойтись). Пример из шапки, где "известное" число является лишь триггером, чтобы понять, что поиск окончен - только для упрощения задачи.
Может, так понятнее будет После праздников сделаю другой вариант, основанный на меняющемся шаге приращения.
Во всех делах очень полезно периодически ставить знак вопроса к тому, что вы с давних пор считали не требующим доказательств (Бертран Рассел) ►Благодарности сюда◄
Jack Famous написал: что с подбором высоты строки?
0 и подбирать не надо, поясню почему установи высоту например 0,6,проверь, что скрыта строка, увеличь масштаб, проверь что строка скрыта, удивись, верни масштаб, проверь, удивись ....
БМВ, не пробовал менять масштаб. Считаем равным 100 и продолжаем искать высоту с точностью хотя бы до 10 знаков)
Во всех делах очень полезно периодически ставить знак вопроса к тому, что вы с давних пор считали не требующим доказательств (Бертран Рассел) ►Благодарности сюда◄
Ну так и напиши, что нужно найти число с известной погрешностью, при котором выполнится условие, которое не позволяет вычислить это число решением уравнения. Нет тут заданного числа , есть только погрешность.
БМВ, в таком случае, можно расширить до "найти число с минимальной погрешностью за установленное время". Только я всё это упростил, потому что это не должно повлиять на алгоритм, а только раздуть код и увести его от сути.
Во всех делах очень полезно периодически ставить знак вопроса к тому, что вы с давних пор считали не требующим доказательств (Бертран Рассел) ►Благодарности сюда◄