Улучшенная модель с массивом

 

Задача №220.  Опупенные числа (Симферополь, IIэтап, 2015)

Вася Пупкин на уроке информатики недавно познакомился с числами Фибоначчи:

1, 1, 2, 3, 5, 8, 13, 21, 34, …

где каждое последующее число равно сумме двух предыдущих. С тех пор Васе не дают покоя лавры Леонардо Пизанского, известного под прозвищем «Фибоначчи». И Вася решил создать числовой ряд имени Пупкина «опупенные числа».

1,1,1,3,5,9,17,31,57,105,193,…

где каждое последующее число равно сумме ТРЁХ предыдущих.

Помогите Васе написать программу, определяющую такое число, по его номеру в последовательности.

Входные данные

Единственная строка содержит число N – номер члена числового ряда (1 <= N <= 10000).

Выходные данные

Одно число – значение PN члена числового ряда с номером N.

Примеры

№	Ввод	Вывод
1	3	1
2	13	653
3	43	56804250945

Решение

Это типичная задача на длинную арифметику. Нам она интересна лишь в контексте применения данной модели работы с длинными числами

#include <cstdio>

#define SIZE 1000

#define BASE 1000000

int N, f[SIZE], tmp[SIZE];

int f1[SIZE]={1,1,}, f2[SIZE]={1,1,}, f3[SIZE]={1,1,};

//суммирование длинных c=a+b

void SumLong(int *a, int *b, int *c){

for (int i = 0; i < SIZE; i++) c[i] = 0;

int len = (a[0] > b[0] ? a[0] : b[0]);

for (int i=1; i<=len; i++) {

     c[i+1] = (a[i] + b[i] + c[i]) / BASE;

     c[i] = (a[i] + b[i] + c[i]) % BASE;

}

c[0] = len;

if (c[len+1]) c[0]++;

}

//присваивание для длинных чисел to = int

void CopyLong(int * from, int *to){

for (int i = 0; i < SIZE; i++) to[i] = from[i];

}

//вывод длинного числа

void WriteLong(int *a){

printf("%d", a[a[0]]);

for (int i = a[0]-1; i; i--)

     printf("%06d", a[i]);

}

 

int main() {

scanf("%d", &N);

if (N < 4) {

     printf("1");

     return 0;

}

for (int i = 4; i <= N; i++) {

     SumLong(f3, f2, tmp);

     SumLong(tmp, f1, f);

     CopyLong(f2, f3);

     CopyLong(f1, f2);

     CopyLong(f, f1);

}

WriteLong(f);

}

Класс длинной арифметики через вектор

Базовое описание класса сверхдлинных знаковых целых

В этой части книги рассмотрим поэтапно создание класса hugeдля выполнения операций длинной арифметики. Наш класс будет выполнять стандартные арифметические операции над знаковыми целыми числами большой длины.

Реализуем его на базе STL-контейнера vector– массива переменной длины. В минимальном варианте нам потребуется описать величину base – максимальное значение ячейки массива, содержащего элементы huge. Само описание вектора valueв protected– оно должно быть доступно только функциям-членам класса и дружественным функциям. Также в protectedпоместим величину digits– максимальное количество цифр «длинного» числа, содержащихся в одной ячейке массива. Чтобы уменьшить количество операций, а значит, ускорить вычисления, возьмем наибольшее возможное для intзначение digit = 9и base =1 e9.

С модификатором доступа publicобъявим конструкторы класса, операторы присваивания и потокового ввода-вывода.

class huge

{

protected:

vector<int> value;

static const int base = 1e9;

static const int digits = 9;

public:

huge();  

huge(const string& );

huge(long long);

 

huge& operator =(const huge&);

huge& operator +=(const huge&);

huge& operator *=(const huge&);

 

friend huge operator +(const huge&, const huge&);

friend huge operator *(const huge&, const huge&);

 

friend istream& operator >>(istream&, huge&);

friend ostream& operator <<(ostream&, const huge&);

};

Для реализации класса нам потребуются библиотеки ввода-вывода

#include <iostream> //операцииввода-вывода + работа со строками

#include <iomanip> //флаги для форматированного вывода

#include <vector> //описаниеvector-ов

#include <sstream> //строковые потоки для преобразования чисел

#include <cstdlib> //функция atoi

 

using namespace std; //стандартное пространство имён

Конструкторы класса

Для создания объектов класса huge нам потребуется три конструктора: конструктор по умолчанию, конструктор по длинному целому и конструктор по строке.

//конструктор по умолчанию

huge::huge() {

value.push_back(0);

}

//конструктор по строке

huge::huge(const string& str){

for (int i = str.length(); i > 0; i -= digits)

   if (i < digits)

       value.push_back(atoi(str.substr(0, i).c_str()));

   else

       value.push_back(atoi(str.substr(i-digits,                                              digits).c_str()));

}

//конструктор по длинному целому

huge::huge(long long x) {

ostringstream ost;

ost << x;

string str = ost.str();

for (int i = str.length() ; i > 0 ; i -= digits)

   if (i < digits)

       value.push_back(atoi(str.substr(0, i).c_str()));

   else

     value.push_back(atoi(str.substr(i-digits,                                           digits).c_str()));

}

Сложение длинных чисел

//оператор добавления длинного целого

huge& huge::operator +=(const huge& b){

for (int carry = 0, i = 0;

       i <max(this->value.size(), b.value.size()) || temp; i++){

 

   if (i == value.size()) //создаём новые разряды

value.push_back(0);  // изаполняем их нулями

 

value[i] += carry + (i <b.value.size() ? b.value[i] : 0 );

carry = value[i] >= base; // находим значение переноса

if (carry) value[i] -= base;

}

return *this;

}

//универсальный оператор сложения

huge operator +(const huge& x, const huge& y){

huge z = x;

z += y;

return z;

}

Длинное умножение

Поскольку элементы нашего вектора имеют тип int, произведение двух таких элементов может вызвать переполнение. Поэтому будем результат поразрядного умножения сохранять в longlong. Для преобразования произведения двух целых к типу longlongиспользуем в качестве одного из множителей литерал 1 LL(единица в представлении longlong).

// универсальныйоператорумножения

hugeoperator * (consthuge&a, const huge& b){

huge c;

c.value.resize(a.value.size() + b.value.size());

 

for (int i = 0; i<a.value.size(); i++)

for (int j = 0, carry = 0; j < b.value.size() || carry; ++j){

       long long cur = c.value[i+j] + a.value[i] * 1LL *

                     (j<b.value.size() ? b.value[j] : 0) + carry;

       c.value[i+j] = int(cur % huge::base);

         carry = int (cur / huge::base);        

   }  

 

while (c.value.size() > 1 && !c.value.back())

   c.value.pop_back();

 

return c;

}

 

huge& huge::operator *= (const huge& x){

huge y = *this;

*this = y + x;

return *this;

}