C++
незнайка ищет наибольшую подпоследовательность данной последовательности целых чисел, сумма элементов которой делится на 3.
он попросил вас написать программу, которая:
• читает с клавиатуры последовательность целых чисел;
• вычисляет длину самой длинной подпоследовательности, сумма элементов которой делится на 3;
• выводит результат на экран;

ввод
первая строка ввода состоит из одного целого числа n (1  n  1). в каждой из следующих n строк находится один элемент последовательности 0  ai  2 (i = 1..n).

вывод
выведите на экран длину наибольшей найденной подпоследовательности.

пример
вход выход
7
10
6
7
12
4
7
22 5

Ответы

Redob 11.01.2024 20:11

Хорошо, давайте напишем программу на C++, которая будет находить наибольшую подпоследовательность данной последовательности целых чисел, сумма элементов которой делится на 3.

```cpp
#include
#include

using namespace std;

int main() {
int n;
cin >> n; // вводим количество элементов в последовательности

vector sequence(n); // создаем вектор для хранения последовательности

// считываем последовательность с клавиатуры
for(int i = 0; i < n; i++) {
cin >> sequence[i];
}

// создаем массив для хранения суммы элементов подпоследовательностей,
// где индекс массива - это остаток от деления суммы на 3
// инициализируем его нулями
vector sums(3, 0);

int maxLength = 0; // переменная для хранения длины самой длинной подпоследовательности

// проходим по последовательности
for(int i = 0; i < n; i++) {
// добавляем текущий элемент к суммам в нужную ячейку
sums[sequence[i] % 3] += sequence[i];

// проверяем, существует ли подпоследовательность с максимальной суммой, оканчивающаяся на текущем элементе
if(sums[sequence[i] % 3] % 3 == 0) {
maxLength = max(maxLength, i + 1);
}

// проверяем, существует ли подпоследовательность с максимальной суммой, не оканчивающаяся на текущем элементе
for(int j = 0; j < 3; j++) {
if((sums[sequence[i] % 3] - sums[j]) % 3 == 0) {
maxLength = max(maxLength, i - j);
}
}
}

cout << maxLength << endl; // выводим результат

return 0;
}
```

Давайте разберем эту программу пошагово:

1. Первым делом, мы вводим количество элементов в последовательности (`n`).
2. Затем мы создаем вектор `sequence`, в котором будем хранить введенную последовательность.
3. Далее, мы считываем последовательность с клавиатуры и сохраняем ее в вектор `sequence`.
4. Создаем вектор `sums` размером 3, в котором будем хранить сумму элементов подпоследовательностей, где индекс вектора соответствует остатку от деления суммы на 3. Инициализируем его нулями.
5. Затем мы создаем переменную `maxLength`, в которой будем хранить длину самой длинной подпоследовательности.
6. После этого, мы проходим по последовательности с помощью цикла `for`.
7. Внутри цикла мы добавляем текущий элемент к суммам в нужную ячейку, используя остаток от деления элемента на 3.
8. Затем мы проверяем, существует ли текущая подпоследовательность с максимальной суммой, оканчивающаяся на текущем элементе. Это делается с помощью проверки остатка от деления суммы на 3.
9. Если сумма делится на 3, то мы обновляем переменную `maxLength` с помощью функции `max`, чтобы сохранить длину самой длинной подпоследовательности.
10. Затем мы проверяем, существует ли подпоследовательность, не оканчивающаяся на текущем элементе, но имеющая максимальную сумму. Для этого мы проходим по всем возможным значениям вектора `sums` и вычитаем их из текущей суммы.
11. Если новая сумма делится на 3, то мы обновляем переменную `maxLength`.
12. После окончания цикла, мы выводим результат, который хранится в переменной `maxLength`.

Надеюсь, данное пошаговое объяснение поможет вам лучше понять, как работает программа. Если у вас возникнут вопросы или нужна дополнительная информация, не стесняйтесь задавать!

ПОКАЗАТЬ ОТВЕТЫ

Другие вопросы по теме Информатика