большая тёрка

Большая Тёрка / Мысли / Личная лента Nks /

Nks

13 января 2009 в 19:41

Фибоначчи и его система счисления :-D

10:44 05.01.2009
Фибоначчи и его система счисления :-D
Оригинал сообщения
Комментарии:

Написал в свое время программку для чисел Фибоначчи =] Делать было нечего, дело было вечером, а задание нашел интересное =] В итоге из-под рук вышло сие творение:

code:



#include 

using namespace std;

typedef long long i64;/*64 бита*/

i64 fib[100], mas[100], fibc[100], N;

i64 recurs(i64 n, i64 N) {/**/


    if (N == 0 || N == 1)


        return N;

    if (N < fib[n-1])


        return recurs(n-1,N);


    else {


        N -= fib[n-1];


        return mas[n-1]+N+recurs(n-2,N);


    }


}

i64 rec(i64 r, i64 n, i64 N) {


    if (r <= 0)


        return 0;

    if (N < fib[n+1])


        return  rec(r-1, n-1, N);

    return 1+rec(r-2, n-2, N-fib[n+1]);


}

i64 main () {


    ifstream in(«input.txt»);


    ofstream out(«output.txt»);


    i64 Q = 0;

    fib[1]  = 1;


    mas[1]  = 1;


    fibc[1] = 1;


    for (i64 i = 2; i < 100; i++) {


        fib[i] = fib[i-1] + fib[i-2];


        mas[i] = fib[i] + fibc[i-2];


        fibc[i] = mas[i] + fibc[i-1];


    }


    in >> N;

    i64 n;


    for (n = 1; n * fib[n] <= N; n++)


        N -= n*fib[n], Q += mas[n];

    i64 tmp = N % n;


    N /= n;


    out << Q + recurs(n,N) + rec(tmp,n,N+fib[n+1]);

    return 0;


}

Программулина берет число Фибоначчи (точнее его порядковый номер), ищет его целочисленное значение и потом преобразует его в систему счисления Фибоначчи =]

Число на вход находится в файлике input.txt, а на выход — в файлике output.txt

По ходу движения мы рекурсивной функцией мы преобразуем число в двоичный код системы счисления Фибоначчи (исходя из правила, что 2 еденицы подряд идти не могут).

Собственно код уже описан выше — кому нужно — тот возмет =]

Я сейчас нахожусь дома
Мой настрой отличный
LIci WP - WordPress crossposting plugin
read more at Накукрыскин



Прошу комментировать в моем stand-alone блоге по адресу live.progger.ru. Заранее благодарю =]

rss2lj

Нет комментариев