wpierw probowalem liczyc rekurencyjnie sume na podstawie wczesniej obliczonych, ale trwalo to troche za dlugo
Zauwazmy ze:
- http://pl.wikipedia.org/wiki/Twierdzenie_Zeckendorfa liczbe z(x) mozna liczyc w sposob zachlanny
- nastepujaca zaleznosc:
liczba / reprezentacja
1 / 1
2 / 2
3 / 3
4 / 3 +1
5 / 5
6/ 5 + 1
7 / 5 + 2
…
12 / 8 + 3 + 1
jesli S(x) to jest suma z(x) czyli S(10) = z(1) + z(2) + … z(10)
to na przyklad
S(12) = S(8) + …
wiadomo, że rozkład danej liczby ma conajmniej jedną liczbę
stąd należy dodać (12 - 8)
pozostaje nam jeszcze obliczyć S(12-8) - wystarczy że obliczymy to ponieważ “odjęliśmy” po jednej liczbie z każdego rozkładu
Czyli wzór ogólny na sumę dla liczby n znajdującej się pomiędzy dwoma liczbami fibonacciego Fai Fb:
S(n) = S(Fa) + (n - Fa) + S(n - Fa)
zatem prosta funkcja rekurencyjna
miałem problem przy liczeniu S od liczby fibonacciego, więc jest to po prostu
S(F) = S(F-1) + 1 #bo wiadomo ze liczba Fibonacciego ma z(F) = 1
[code=ruby]# znajdujemy liczby fibonaciego taka ze a < x i nie istnieje inna liczba wieksza niz a
class Solver
attr_accessor :fibo
attr_accessor :mapped
def initialize
@fibo = [1,1]
@mapped = {}
last = 1
# generujemy liczby Fibonacciego mniejsze niz 10^17
while last < 10**17
last = fibo[-2] +fibo[-1]
fibo << last
end
end
def s(x)
return @mapped[x] if @mapped.include?(x) # jesli suma jest juz wyliczona => nie liczymy ponownie
return 1 if x==1 # 1 ma liczbę Z = 1
return 1 + s(x-1) if @fibo.include?(x) # poniewaz nie wiemy jakie jest s(liczba_fibonnaciego) stosujemy maly trick
last = 1
@fibo.each do |v|
if v >= x
val = s(last) + x - last + s(x-last)
@mapped[x] = val
return val
end
last = v
end
end
end
s = Solver.new
puts s.s(10**17-1)[/code]