Terima kasih kepada peserta Habr yang baik karena telah diundang untuk menulis posting dan menerima umpan balik tentang mereka.
Hari ini saya ingin menyoroti topik merepresentasikan bilangan menggunakan deret Fibonacci dan, tentu saja, menulis REST API sederhana menggunakan algoritma Mongo DB menggunakan bahasa Ruby , yang akan mengembalikan representasi untuk bilangan N.
Bagian 1: representasi Zeckendorff
Seperti yang dinyatakan dalam artikel Wikipedia:
Teorema Zeckendorff menyatakan bahwa bilangan asli dapat direpresentasikan secara unik sebagai penjumlahan dari satu atau beberapa bilangan Fibonacci yang berbeda sehingga representasi ini tidak mengandung dua bilangan yang berdekatan dari deret Fibonacci.
100 = 89 + 8 + 3.
Menurut saya, memahami apa itu bilangan Fibonacci, tidak akan sulit untuk memahami tentang apa teorema ini.
Tujuan yang ingin dicapai:
kecepatan kerja
kesederhanaan kode maksimum
Sebagai bahasa pemrograman saya akan menggunakan Ruby , kenapa? Karena Ruby adalah
Sahabat programmer.
Pertama, secara teoritis, Anda perlu menemukan pola penulisan algoritme.
, (), , , .
:
N = 51
F = 1 , 1 , 2 , 3 , 5 , 8 , 13, 21, 34.
34, (21) , N, , :-).
, : .
- : .
: N , , <= 0.
:
N = 51
F = 1 , 1 , 2 , 3 , 5 , 8 , 13, 21, 34.
ans = [34]
N = 51 - 34 = 17
F = 1 , 1 , 2 , 3 , 5 , 8 , 13.
ans = [34 , 13]
N = 17 - 13 = 4
F = 1 , 1 , 2 , 3.
ans = [34 , 13 , 3]
N = 4 - 3 = 1
F = 1
ans = [34 , 13 , 3, 1]
:
def le_fib(limit, fib)
theoretical = fib[fib.count - 1] + fib[fib.count - 2]
return fib.last if theoretical > limit
fib << theoretical
le_fib(limit, fib)
end
def main(target,result)
temporary = le_fib(target, [1,1])
result << temporary
return result if target - temporary <= 0
main(target - temporary, result)
end
pp main(gets.to_i,[])
le_fib - , , target. , , .
main - c, , .
, , , , , .
20 1000
( )
Seperti yang Anda lihat, waktu pengoperasian bahkan pada angka hingga 10 ^ 9 sangat positif.
Dan jumlah total kode dalam 17 baris menunjukkan bahwa kedua tugas diselesaikan dengan sukses.
Sebuah artikel tentang minat, Anda selalu perlu memiliki beberapa masalah dengan nomor Fibonache di lengan Anda, jika tidak, pemrogram seperti apa Anda :-)