Это может быть похоже на ответ пользователя 635541. Я не до конца понимаю его подход.
Используя матричное представление для чисел Фибоначчи, рассмотренное в других ответах, мы получаем способ перейти от F_n и F_m к F_{n+m} и F_{n-m} в постоянном времени, используя только плюс, умножение, минус и деление ( на самом деле нет! см. обновление ). У нас также есть ноль (единичная матрица), поэтому это математическая группа!
Обычно при выполнении бинарного поиска нам также нужен оператор деления для получения средних значений. Или хотя бы деление на 2. Однако если мы хотим перейти от F_{2n} к F_n, это требует квадратного корня. К счастью, оказывается, что плюс и минус - это все, что нам нужно для логарифмического времени «почти» двоичного поиска!
Википедия пишет о подходе, по иронии судьбы называемом Fibonacci_search , но статья написана не очень четко, поэтому я не знаю, является ли это точно таким же подходом, как мой. Очень важно понимать, что числа Фибоначчи, используемые для поиска Фибоначчи, не имеют ничего общего с числами, которые мы ищем. Это немного сбивает с толку. Чтобы продемонстрировать этот подход, сначала приведем реализацию стандартного «бинарного поиска», использующего только плюсы и минусы:
def search0(test):
# Standard binary search invariants:
# i <= lo then test(i)
# i >= hi then not test(i)
# Extra invariants:
# hi - lo = b
# a, b = F_{k-1}, F_k
a, b = 0, 1
lo, hi = 0, 1
while test(hi):
a, b = b, a + b
hi = b
while b != 1:
mi = lo + a
if test(mi):
lo = mi
a, b = 2*a - b, b - a
else:
hi = mi
a, b = b - a, a
return lo
>>> search0(lambda n: n**2 <= 25)
5
>>> search0(lambda n: 2**n <= 256)
8
Здесь test - некоторая логическая функция; a и b являются последовательными числами Фибоначчи f_k и f_{k-1}, так что разница между верхней границей hi и нижней границей lo всегда равна f_k. Нам нужны и a, и b, чтобы мы могли эффективно увеличивать и уменьшать неявную переменную k.
Хорошо, так как мы можем использовать это для решения проблемы? Я нашел полезным создать оболочку вокруг нашего представления Фибоначчи, которая скрывает детали матрицы. На практике (есть ли такая вещь для искателя Фибоначчи?) вы бы хотели вставить все вручную . Это избавит вас от избыточности в матрицах и сделает некоторую оптимизацию вокруг инверсии матриц.
import numpy as np
class Fib:
def __init__(self, k, M):
""" `k` is the 'name' of the fib, e.g. k=6 for F_6=8.
We need this to report our result in the very end.
`M` is the matrix representation, that is
[[F_{k+1}, F_k], [F_k, F_{k-1}]] """
self.k = k
self.M = M
def __add__(self, other):
return Fib(self.k + other.k, self.M.dot(other.M))
def __sub__(self, other):
return self + (-other)
def __neg__(self):
return Fib(-self.k, np.round(np.linalg.inv(self.M)).astype(int))
def __eq__(self, other):
return self.k == other.k
def value(self):
return self.M[0,1]
Однако код работает, поэтому мы можем проверить его следующим образом. Обратите внимание, насколько мало отличается функция поиска от того, когда наши объекты были целыми числами, а не Фибоначчи.
def search(test):
Z = Fib(0, np.array([[1,0],[0,1]])) # Our 0 element
A = Fib(1, np.array([[1,1],[1,0]])) # Our 1 element
a, b = Z, A
lo, hi = Z, A
while test(hi.value()):
a, b = b, a + b
hi = b
while b != A:
mi = lo + a
if test(mi.value()):
lo = mi
a, b = a+a-b, b-a
else:
hi = mi
a, b = b-a, a
return lo.k
>>> search(lambda n: n <= 144)
12
>>> search(lambda n: n <= 0)
0
Остается открытым вопрос - существует ли эффективный алгоритм поиска моноидов. Это тот, который не нуждается в минус / аддитив обратный. Думаю, нет: без минуса вам понадобится дополнительная память о Никите Рыбаке.
Обновление
Я только что понял, что нам вообще не нужно деление. Определитель матрицы F_n равен всего (-1)^n, поэтому мы можем делать все без деления. Ниже я удалил весь матричный код, но сохранил класс Fib только потому, что в противном случае все стало очень грязно.
class Fib2:
def __init__(self, k, fp, f):
""" `fp` and `f` are F_{k-1} and F_{k} """
self.k, self.fp, self.f = k, fp, f
def __add__(self, other):
fnp, fn, fmp, fm = self.fp, self.f, other.fp, other.f
return Fib2(self.k + other.k, fn*fm+fnp*fmp, (fn+fnp)*fm+fn*fmp)
def __sub__(self, other):
return self + (-other)
def __neg__(self):
fp, f = self.f + self.fp, -self.f
return Fib2(-self.k, (-1)**self.k*fp, (-1)**self.k*f)
def __eq__(self, other):
return self.k == other.k
def value(self):
return self.f
def search2(test):
Z = Fib2(0, 1, 0)
A = Fib2(1, 0, 1)
...
>>> search2(lambda n: n <= 280571172992510140037611932413038677189525)
200
>>> search2(lambda n: n <= 4224696333392304878706725602341482782579852840250681098010280137314308584370130707224123599639141511088446087538909603607640194711643596029271983312598737326253555802606991585915229492453904998722256795316982874482472992263901833716778060607011615497886719879858311468870876264597369086722884023654422295243347964480139515349562972087652656069529806499841977448720155612802665404554171717881930324025204312082516817125)
2000
>>> search2(lambda n: n <= 2531162323732361242240155003520607291766356485802485278951929841991312781760541315230153423463758831637443488219211037689033673531462742885329724071555187618026931630449193158922771331642302030331971098689235780843478258502779200293635651897483309686042860996364443514558772156043691404155819572984971754278513112487985892718229593329483578531419148805380281624260900362993556916638613939977074685016188258584312329139526393558096840812970422952418558991855772306882442574855589237165219912238201311184749075137322987656049866305366913734924425822681338966507463855180236283582409861199212323835947891143765414913345008456022009455704210891637791911265475167769704477334859109822590053774932978465651023851447920601310106288957894301592502061560528131203072778677491443420921822590709910448617329156135355464620891788459566081572824889514296350670950824208245170667601726417091127999999941149913010424532046881958285409468463211897582215075436515584016297874572183907949257286261608612401379639484713101138120404671732190451327881433201025184027541696124114463488665359385870910331476156665889459832092710304159637019707297988417848767011085425271875588008671422491434005115288334343837778792282383576736341414410248994081564830202363820504190074504566612515965134665683289356188727549463732830075811851574961558669278847363279870595320099844676879457196432535973357128305390290471349480258751812890314779723508104229525161740643984423978659638233074463100366500571977234508464710078102581304823235436518145074482824812996511614161933313389889630935320139507075992100561077534028207257574257706278201308302642634678112591091843082665721697117838726431766741158743554298864560993255547608496686850185804659790217122426535133253371422250684486113457341827911625517128815447325958547912113242367201990672230681308819195941016156001961954700241576553750737681552256845421159386858399433450045903975167084252876848848085910156941603293424067793097271128806817514906531652407763118308162377033463203514657531210413149191213595455280387631030665594589183601575340027172997222489081631144728873621805528648768511368948639522975539046995395707688938978847084621586473529546678958226255042389998718141303055036060772003887773038422366913820397748550793178167220193346017430024134496141145991896227741842515718997898627269918236920453493946658273870473264523119133765447653295022886429174942653014656521909469613184983671431465934965489425515981067546087342348350724207583544436107294087637975025147846254526938442435644928231027868701394819091132912397475713787593612758364812687556725146456646878912169274219209708166678668152184941578590201953144030519381922273252666652671717526318606676754556170379350956342095455612780202199922615392785572481747913435560866995432578680971243966868110016581395696310922519803685837460795358384618017215468122880442252343684547233668502313239328352671318130604247460452134121833305284398726438573787798499612760939462427922917659263046333084007208056631996856315539698234022953452211505675629153637867252695056925345220084020071611220575700841268302638995272842160994219632684575364180160991884885091858259996299627148614456696661412745040519981575543804847463997422326563897043803732970397488471644906183310144691243649149542394691524972023935190633672827306116525712882959108434211652465621144702015336657459532134026915214509960877430595844287585350290234547564574848753110281101545931547225811763441710217452979668178025286460158324658852904105792472468108996135476637212057508192176910900422826969523438985332067597093454021924077101784215936539638808624420121459718286059401823614213214326004270471752802725625810953787713898846144256909835116371235019527013180204030167601567064268573820697948868982630904164685161783088076506964317303709708574052747204405282785965604677674192569851918643651835755242670293612851920696732320545562286110332140065912751551110134916256237884844001366366654055079721985816714803952429301558096968202261698837096090377863017797020488044826628817462866854321356787305635653577619877987998113667928954840972022833505708587561902023411398915823487627297968947621416912816367516125096563705174220460639857683971213093125)
20000
Это все работает как шарм. Единственное, что меня беспокоит, так это то, что сложность битов доминирует в вычислениях, поэтому мы могли бы просто выполнить последовательный поиск. Или, на самом деле, просто глядя на количество цифр, вы, вероятно, можете сказать, на что вы смотрели. Хотя это не так весело.