Fibonacci say sistemi
Fibonacci ardıcıllığı, bildiyimiz kimi, 0 və 1 ədədləri ilə başlayır və hər bir növbəti ədəd əvvəlki iki ədədin cəmi olaraq yaranır. Məsələn, ardıcıllığın üçüncü ədədi 1 (1=1+0), dördüncü 2 (2=1+1), beşinci isə 3 (3=2+1) olur və bu şəkildə davam edir.
Şəkil 1 - Fibonacci ardıcıllığının ilk ədədləri
Bu ardıcıllıq həm təbiətdə, həm də gündəlik həyatımızda geniş yayılmış və əhəmiyyətlidir. Bəs bilirdinizmi ki, hər bir müsbət tam ədəd Fibonacci ardıcıllığının ədədlərinin cəmi kimi ifadə edilə bilər? Üstəlik, bu ədədləri təkrarlanmadan təqdim etmək mümkündür. Məsələn, 13 ədədi {13}, {5,8} və ya {2,3,8} kimi ifadə edilə bilər. 17 isə {1,3,13} və ya {1,3,5,8} kimi təqdim edilə bilər. Bütün ədədlərin bu xüsusiyyətə malik olduğunu nəzərə alsaq (bunu sübut etmək istəyirsinizsə, cəhd edə bilərsiniz), bu üsul ədədlərin təqdim edilməsi üçün "baza" (say sisteminin əsası) kimi istifadə üçün əlverişlidir. Lakin, bəzi ədədlər bir neçə fərqli üsulla təqdim edilə bilər. Bu vəziyyətdən çıxış yolu nədir? Çox sadə! Sadəcə olaraq, təqdimatda Fibonacci ardıcıllığının iki ardıcıl elementindən istifadə etməmək kifayətdir. Bu məhdudiyyət, Fibonacci ardıcıllığının iki ardıcıl üzvünün cəminin də ardıcıllığın üzvü olması ilə izah olunur.
İndi, bu məlumatlara əsaslanaraq, hər hansı müsbət tam ədədin təqdim edilməsi üçün yaxşı bir üsul təklif edə bilərik. Bunun üçün ikilik ardıcıllıqdan (yalnız sıfırlar və birlər) istifadə edəcəyik. Məsələn, 17 = 1 + 3 + 13 (Fibonacci ardıcıllığının iki ardıcıl ədədindən istifadə edilməməsini unutmayın). Fibonacci ardıcıllığının növbəti ədədi istifadə olunmursa, sıfır, istifadə olunursa, bir yazacağıq. Beləliklə, 17 = 100101 (aparıcı sıfırlar olmamalıdır). Şəkil 2-də bu yazının necə alındığı və sıfırların və birlərin nə demək olduğu ətraflı göstərilmişdir. Bu sxemi daha yaxşı başa düşmək üçün qeyd edək ki, Fibonacci ardıcıllığının iki ardıcıl ədədindən istifadə edilməməsi ikilik ardıcıllığın ardıcıl iki birə malik olmayacağını bildirir. Bu üsuldan istifadə edərək, Fibonacci say sistemindən istifadə etdiyimizi deyəcəyik və onu 17 = 100101 (fib) kimi yazacağıq.
Şəkil 2 - 17 ədədinin Fibonacci say sistemində təqdim edilməsinin izahı
Sizin vəzifəniz verilmiş onluq ədədin Fibonacci say sistemində yazılmasıdır.
Giriş verilənləri
Giriş məlumatlarının ilk sətirində test nümunələrinin sayını göstərən yeganə natural ədəd N verilir (1 ≤ N ≤ 500).
Sonrakı N sətirlərdə 100 000 000-dən çox olmayan bir müsbət tam ədəd verilir. Ədədlər istənilən qaydada verilə bilər.
Çıxış verilənləri
Giriş məlumatlarında verilmiş hər bir N ədəd üçün aşağıdakı formatda bir sətir çıxarmalısınız: "DEC_BASE = FIB_BASE (fib)". DEC_BASE onluq say sistemində verilmiş orijinal ədəd, FIB_BASE isə onun Fibonacci say sistemində təqdim edilməsidir. Çıxış nümunəsi verilmiş çıxış məlumatlarında göstərilmişdir.