Матч 322, Образующая последовательность (DerivativeSequence)

Дивизион 2, Уровень 1

В массиве a задана последовательность, состоящая из k элементов. По ней можно найти последовательность, состоящую из разностей соседних элементов. Например, из последовательности {5, 6, 3, 9, -1} можно получить {6-5, 3-6, 9-3, -1-9} = {1, -3, 6, -10}. Формально, последовательностью разностей для {a₁, a₂, …, a_k} будет {b₁, b₂, …, b_k-1}, где b_i = a_i+1 – a_i.

Разностью n - го порядка для последовательности a будет такая последовательность, которая будет получена применением выше описанного правила n раз. Например, для вычисления разности второго порядка для {5, 6, 3, 9, -1} следует произвести преобразования:

{5, 6, 3, 9,-1} -> {1, -3, 6,-10} -> {-3-1, 6-(-3), -10-6} = {-4, 9, -16}

По заданной последовательности a требуется найти ее n - ую разность.

Класс: DerivativeSequence

Метод: vector<int> derSeq(vector<int> a, int n)

Ограничения: a содержит от 1 до 20 элементов, -100 £ a[i] £ 100, 0 £ n £ k -1.

Вход. Массив чисел a и величина искомой разности n.

Выход. n - ая разность последовательности a.

Пример входа

a	n
{5,6,3,9,-1}	1
{5,6,3,9,-1}	2
{5,6,3,9,-1}	4
{4,4,4,4,4,4,4,4}	3

Пример выхода

{1,-3, 6, -10}

{-4, 9, -16}

{-38}

{0, 0, 0, 0, 0}

РЕШЕНИЕ

обработка массива

Задача решается моделированием процесса вычисления разностей. Выполняем n итераций. На каждой итерации вычисляем разности и удаляем последний элемент массива.

ПРОГРАММА

#include <cstdio>

#include <vector>

using namespace std;

class DerivativeSequence

{

public:

vector<int> derSeq(vector<int> a, int n)

{

while(n--)

{

for(int i = 0; i < a.size() - 1; i++) a[i] = a[i+1] - a[i];

a.erase(a.end() - 1);

}

return a;

}

};