Fibonaççi sistemi

Kiçik Con ədədi sistemləri öyrənir. Sabit əsaslı ədədi sistemləri öyrəndikdən sonra Conu daha qeyri-adi halları maraqlandırdı. Onların arasında o, Fibonacci sistemi ilə rastlaşdı. Bu sistemdə bütün natural ədədlər yalnız iki rəqəmdən: sıfır və birdən istifadə edərək yalnız bir şəkildə təsvir olunur. Lakin adi ikilik (binary) sistemdən fərqli olaraq, Fibonacci sistemində ardıcıl iki 1 yanaşı mövqedə yerləşə bilməz.

Sübut etmək olar ki, əgər bir ədəd Fibonacci sistemində verilibsə, onun qiyməti aşağıdakı kimidir:

N = a_n F_n + a_n-1 F_n-1 + ...+ a_1 F_1,

burada F_k adi Fibonacci ardıcıllığıdır və belə tərif olunur: F_0 = F_1 = 1, F_i = F_i-1 + F_i-2.

Məsələn, ilk bir neçə natural ədəd Fibonacci sistemində belə təsvir olunur:

1 = 1_F

2 = 10_F

3 = 100_F

4 = 101_F

5 = 1000_F

6 = 1001_F

7 = 1010_F

Con Fibonacci sistemində ardıcıl natural ədədlərin təsvirlərindən (sonsuz uzunluqlu hesab edin) ibarət çox uzun bir sətir yazıb. Məsələn, bu sətirin ilk rəqəmləri belədir: 110100101100010011010...

Conu maraqlandırır ki, N-ci prefiksdə 1 rəqəminə neçə dəfə rast gəlinir. Xatırladırıq ki, sətirin N-ci prefiksi onun ilk N simvolundan ibarət sətrə deyilir.

Conun sətirinin N-ci prefiksində neçə 1 olduğunu təyin edən proqram yazın.