VPF::[C++] Рекурсия. Число Фибоначчи - Форум программистов

dk88

Дата 9.9.2011, 14:30 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 3
Регистрация: 9.9.2011

Репутация: нет
Всего: нет

Код

Чему равно количество повторений наиболее часто встречающейся цифры в 2011-м члене ряда Фибоначчи.
заранее спасибки smile

volatile

Дата 10.9.2011, 13:01 (ссылка)

(голосов:1)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 2107
Регистрация: 7.1.2011

Репутация: 8
Всего: 85

Чаще всего встречается: '1' = 57 раз.

http://liveworkspace.org/code/f972d0b1ac9d...3bcfb46a34d93a2
smile

dk88

Дата 16.9.2011, 00:32 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 3
Регистрация: 9.9.2011

Репутация: нет
Всего: нет

А можно код на С++? smile

volatile

Дата 16.9.2011, 01:03 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 2107
Регистрация: 7.1.2011

Репутация: 8
Всего: 85

Цитата(dk88 @ 16.9.2011, 00:32

)

А можно код на С++?

Ссылка выше.

dk88

Дата 16.9.2011, 01:20 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 3
Регистрация: 9.9.2011

Репутация: нет
Всего: нет

Не могу открыть:(блокирует...можно сюда код?пожалуйста smile

volatile

Дата 16.9.2011, 09:04 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 2107
Регистрация: 7.1.2011

Репутация: 8
Всего: 85

Код


#include <iostream>
#include <memory.h>

template <size_t N>
class bignum
{
public:
   bignum ( size_t v = 0 ) { assign ( v ); }

   const bignum & operator = ( size_t v ) { assign ( v ); return * this; }

   void assign ( size_t v )
   {
      memset ( body, 0, N );
      char buf [ 32 ];
      size_t len = sprintf ( buf, "%u", v );
      for ( size_t i = 0; i < len; ++ i )
      {
         body [ i ] = buf [ len - i - 1 ] - '0';
      }
   }

   const bignum & operator += ( const bignum & that )
   {
      char cary = 0;
      for ( size_t i = 0; i < N; ++ i )
      {
         char t = body [ i ] + that.body [ i ] + cary;
         if ( cary = t >= 10 )
            t -= 10;
         body [ i ] = t;
      }
      return * this;
   }

   void print_statistic () const
   {
      int dig [ 10 ] = { 0 };
      bool f_started = 0;
      for ( size_t i = 0; i < N; ++ i )
      {
         size_t r = N - i - 1;
         if ( f_started || body [ r ] || r == 0 )
         {
            f_started = 1;
            dig [ body [ r ] ] ++;
         }
      }
      int imax = 0;
      int total = 0;
      for ( int i = 0; i < 10; ++ i )
      {
         std::cout << "'" << i << "' = " << dig [ i ] << " digits" << std::endl;
         total += dig [ i ];
         if ( dig [ i ] > dig [ imax ] )
            imax = i;
      }
      std::cout << "total: " << total << " digits" << std::endl;
      std::cout << "max is: '" << imax << "' = " << dig [ imax ] << " digits" << std::endl;
   }

   friend std::ostream & operator << ( std::ostream & out, const bignum & num )
   {
      bool f_started = 0;
      for ( size_t i = 0; i < N; ++ i )
      {
         size_t r = N - i - 1;
         if ( f_started || num.body [ r ] || r == 0 )
         {
            f_started = 1;
            out << char (num.body [ r ] + '0');
         }
      }
      return out;
   }

private:
   char body [ N ];
};


// Вычисление числа фибоначчи, правда без рекурсии, так эффективнее
template <size_t N>
void fib ( bignum <N> & result, int num )
{
   bignum <N> a [ 2 ] = { 0, 1 };
   int i = -! num;
   for (; i < num - 1; ++ i )
   {
      a [ i & 1 ] += a [ ( i + 1 ) & 1 ];
   }
   result = a [ ( i + 1 ) & 1 ];
}

void go ( int num )
{
   bignum <500> a;
   fib ( a, num );
   std::cout << "fib(" << num << ")= " << a << std::endl;
   a.print_statistic ();
}

int main ()
{
   go ( 2011 );
}

Это сообщение отредактировал(а) volatile - 16.9.2011, 09:19

1 Пользователей читают эту тему (1 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| Центр помощи \| Следующая тема »