Математика ЕГЭ
Русский язык ЕГЭ
Математика 5-7
Математика ОГЭ
Информатика
Физика
Обществознание
Кликните, чтобы открыть меню

(Старый формат ЕГЭ) 25. Программирование - массивы

1. Вспоминай формулы по каждой теме
2. Решай новые задачи каждый день
3. Вдумчиво разбирай решения
Задание 1 #11838

Дан целочисленный массив из \(N = 40\) элементов. Элементы массива могут принимать целые значения от -10000 до 10000 включительно. Опишите на естественном языке или на одном из языков программирования алгоритм, позволяющий найти и вывести количество пар элементов массива, чья сумма положительна. Под парой подразумевается два подряд идущих элемента массива. Исходные данные объявлены так, как показано ниже на примерах для некоторых языков программирования. Запрещается использовать переменные, не описанные ниже, но разрешается не использовать некоторые из описанных переменных. Индексация элементов в массиве начинается с нуля.

\[\begin{array}{|l|l|l|} \hline \text{Бейсик} & Python & \text{Алгоритмический язык} \\ \hline CONST \; N \; AS \; INTEGER \; = \; 40 & \text{\# \; допускается также} &\underline{\text{алг}} \\ DIM \; A \; (0 \; TO \; N-1) \; AS \; LONG \; &\text{\# \; использовать три} &\underline{\text{нач}} \\ DIM \; I \; AS \; LONG& \text{\# целочисленные переменные i,t,k} & \quad \underline{\text{цел}} \; N = 40 \\ \quad \quad \; \; T \; AS \; LONG& a \; = [] &\quad \underline{\text{целтаб}} \; a[0:N-1] \\ \quad \quad \; \; K \; AS \; LONG& n \; = \; 40&\quad \underline{\text{цел}} \; i, \; t, \; k \\ FOR \; I \; = \; 0 \; TO \; N-1 &for \; i \; in \; range(0, \; n):&\quad \underline{\text{нц для}} \; i \; \underline{\text{от}} \; 0 \; \underline{\text{до}} \; N-1 \\ \quad \quad \; \; INPUT \; A(I)& \quad a.append \; (int(input()))&\quad \quad \underline{\text{ввод}} \; a[i] \\ NEXT \; I& ...&\quad \underline{\text{кц }} \\ ... & &... \\ END & & \underline{\text{кон}} \\ \hline \end{array}\]

\[\begin{array}{|l|l|} \hline \ \text{Паскаль} & C++ \\ \hline const &\#include \; <iostream> \\ \quad N = 40 & using \; namespace \; std; \\ var & const \; int \; N = 40; \\ \quad a: \; array \; [0..N-1] \; of \; longint; & int \; main() \{ \\ \quad i, \; t, \; k: \; longint; &long \; a[N]; \\ begin & long \; i, \; t, \; k; \\ \quad for \; i \; := 0 \; to \; N-1 \; do &for \; (i = 0; \; i < N; \; i++) \; cin >> a[i]; \\ \quad \quad readln (a[i]); & ... \\ ... &return \; 0; \\ end. & \} \\ \hline \end{array}\]

В качестве ответа Вам необходимо привести фрагмент программы, который должен находиться на месте многоточия. Вы можете записать решение также на другом языке программирования (укажите название и используемую версию языка программирования, например, Cython 0.20). В этом случае Вы должны использовать те же самые исходные данные и переменные, какие были предложены в приведённых фрагментах.

Например, для исходного массива из 10 элементов

5

-3

-8

13

-9

7

82

-34

4

5

программа должна вывести

6

(Под условие подходят следующие пары: 5 и -3 (сумма равна 2), -8 и 13 (сумма равна 5), 13 и -9 (сумма равна 4), 7 и 82 (сумма равна 89), 82 и -34 (сумма равна 48), 4 и 5 (сумма равна 9)).

Переменная \(t\) будет отвечать за количество пар элементов массива, чья сумма больше нуля, поэтому изначально \(t = 0\). За пару мы будем считать элементы \(a[i]\) и \(a[i+1]\) (не \(a[i]\) и \(a[i-1]\)!). В цикле от 0 до \(N-1\) мы будем проверять, положительна ли пара. Цикл до \(N-1\), так как индексация элементов массива начинается с нуля, значит, элемента \(a[N]\) нет, и у элемента \(a[N-1]\) нет второй пары (так как \(a[N-1 + 1] = a[N]\)). Если пара оказалась положительна, мы увеличим \(t\) на 1. Вне цикла мы выведем \(t\) — количество пар элементов массива, чья сумма больше нуля.

Пример на \(C++\):

\(t = 0;\)

\(for \; (i = 0; \; i < N-1; \; i++) \; \{\)

\(\quad if \; ((a[i] + a[i+1]) > 0) \; t++; \)

\(\}\)

\(cout \; << \; t;\)

Ответ: см. решение

Задание 2 #11839

Дан целочисленный массив из \(N = 30\) элементов. Элементы массива могут принимать целые значения от -10000 до 10000 включительно. Опишите на естественном языке или на одном из языков программирования алгоритм, позволяющий найти и вывести количество пар элементов массива, произведение которых положительно и дает остаток 2 при делении на 7. Под парой подразумевается два подряд идущих элемента массива. Исходные данные объявлены так, как показано ниже на примерах для некоторых языков программирования. Запрещается использовать переменные, не описанные ниже, но разрешается не использовать некоторые из описанных переменных. Индексация элементов в массиве начинается с нуля.

\[\begin{array}{|l|l|l|} \hline \text{Бейсик} & Python & \text{Алгоритмический язык} \\ \hline CONST \; N \; AS \; INTEGER \; = \; 30 & \text{\# \; допускается также} &\underline{\text{алг}} \\ DIM \; A \; (0 \; TO \; N-1) \; AS \; LONG \; &\text{\# \; использовать три} &\underline{\text{нач}} \\ DIM \; I \; AS \; LONG& \text{\# целочисленные переменные i,t,k} & \quad \underline{\text{цел}} \; N = 30 \\ \quad \quad \; \; T \; AS \; LONG& a \; = [] &\quad \underline{\text{целтаб}} \; a[0:N-1] \\ \quad \quad \; \; K \; AS \; LONG& n \; = \; 30&\quad \underline{\text{цел}} \; i, \; t, \; k \\ FOR \; I \; = \; 0 \; TO \; N-1 &for \; i \; in \; range(0, \; n):&\quad \underline{\text{нц для}} \; i \; \underline{\text{от}} \; 0 \; \underline{\text{до}} \; N-1 \\ \quad \quad \; \; INPUT \; A(I)& \quad a.append \; (int(input()))&\quad \quad \underline{\text{ввод}} \; a[i] \\ NEXT \; I& ...&\quad \underline{\text{кц }} \\ ... & &... \\ END & & \underline{\text{кон}} \\ \hline \end{array}\]

\[\begin{array}{|l|l|} \hline \text{Паскаль} & C++ \\ \hline const &\#include \; <iostream> \\ \quad N = 30 & using \; namespace \; std; \\ var & const \; int \; N = 30;\\ \quad a: \; array \; [0..N-1] \; of \; longint; & int \; main() \{ \\ \quad i, \; t, \; k: \; longint; & long \; a[N]; \\ begin & long \; i, \; t, \; k; \\ \quad for \; i \; := 0 \; to \; N-1 \; do &for \; (i = 0; \; i < N; \; i++) \; cin >> a[i]; \\ \quad \quad readln (a[i]); & ... \\ ... & return \; 0; \\ end. & \} \\ \hline \end{array}\]

В качестве ответа Вам необходимо привести фрагмент программы, который должен находиться на месте многоточия. Вы можете записать решение также на другом языке программирования (укажите название и используемую версию языка программирования, например, Cython 0.20). В этом случае Вы должны использовать те же самые исходные данные и переменные, какие были предложены в приведённых фрагментах.

Например, для исходного массива из 6 элементов

-3

9

1

16

-2

5

11

-6

6

5

программа должна вывести

3

(Под условие подходят пары 9 и 1, 1 и 16, 6 и 5).

Мы будем рассматривать пары \(a[i]\) и \(a[i+1]\).

В \(k\) будем хранить количество пар элементов массива, произведение которых положительно и дает остаток 2 при делении на 7. Так как изначально таких пар нет, обнулим переменную в первой строке программы.

В цикле от 0 до \(N-1\) (если мы укажем цикл до \(N\), то программа будет пытаться проверить пару \(a[N-1]\) и \(a[N]\), но элемента \(a[N]\) не существует) будем для удобства записывать произведене \(a[i]\) * \(a[i+1]\) в переменную \(t\), которую перед циклом приравняем к нулю.

Также будем проверять, что \(t > 0\) (положительность произведения) и \(t \% 7 == 2\) (остаток от деления на 7 равен 2). Если условие выполняется, будем увеличивать \(k\) на один. Вне цикла выведем на экран \(k\) в соответствии с условием.

Пример программы на \(C++\):

\(t = 0, \; k = 0; \)

\(for \; (i = 0; \; i < N-1; i++)\) {

\(t = a[i] * a[i+1];\)

\(if \; ((t > 0) \; \&\& \; (t \% 7 == 0)) \; k++;\)

}

\(cout << k;\)

Ответ: см. решение

Задание 3 #11840

Дан целочисленный массив из \(N = 70\) элементов. Элементы массива могут принимать целые значения от -10000 до 10000 включительно. Опишите на естественном языке или на одном из языков программирования алгоритм, позволяющий найти количество пар элементов массива, у которых разность по модулю больше 14 и первый элемент при делении на второй дает число, большее по модулю единицы. Под парой подразумевается два подряд идущих элемента массива. Исходные данные объявлены так, как показано ниже на примерах для некоторых языков программирования. Запрещается использовать переменные, не описанные ниже, но разрешается не использовать некоторые из описанных переменных. Индексация элементов в массиве начинается с нуля.

\[\begin{array}{|l|l|l|} \hline \text{Бейсик} & Python & \text{Алгоритмический язык} \\ \hline CONST \; N \; AS \; INTEGER \; = \; 70 & \text{\# \; допускается также} &\underline{\text{алг}} \\ DIM \; A \; (0 \; TO \; N-1) \; AS \; LONG \; &\text{\# \; использовать четыре} &\underline{\text{нач}} \\ DIM \; I \; AS \; LONG& \text{\# целочисленные переменные i,t,k,m} & \quad \underline{\text{цел}} \; N = 70 \\ \quad \quad \; \; T \; AS \; LONG& a \; = [] &\quad \underline{\text{целтаб}} \; a[0:N-1] \\ \quad \quad \; \; K \; AS \; LONG& n \; = \; 70&\quad \underline{\text{цел}} \; i, \; t, \; k, \; m \\ \quad \quad \; \; M \; AS \; LONG & & \\ FOR \; I \; = \; 0 \; TO \; N-1 &for \; i \; in \; range(0, \; n):&\quad \underline{\text{нц для}} \; i \; \underline{\text{от}} \; 0 \; \underline{\text{до}} \; N-1 \\ \quad \quad \; \; INPUT \; A(I)& \quad a.append \; (int(input()))&\quad \quad \underline{\text{ввод}} \; a[i] \\ NEXT \; I& ...&\quad \underline{\text{кц }} \\ ... & &... \\ END & & \underline{\text{кон}} \\ \hline \end{array}\]

\[\begin{array}{|l|l|} \hline \ \text{Паскаль} & C++ \\ \hline const &\#include \; <iostream> \\ \quad N = 70 & using \; namespace \; std; \\ var & const \; int \; N = 70;\\ \quad a: \; array \; [0..N-1] \; of \; longint; & int \; main() \{ \\ \quad i, \; t, \; k, \; m: \; longint; &long \; a[N]; \\ begin & long \; i, \; t, \; k, \; m;\\ \quad for \; i \; := 0 \; to \; N-1 \; do &for \; (i = 0; \; i < N; \; i++) \; cin >> a[i]; \\ \quad \quad readln (a[i]); & ... \\ ... &return \; 0; \\ end. & \} \\ \hline \end{array}\]

В качестве ответа Вам необходимо привести фрагмент программы, который должен находиться на месте многоточия. Вы можете записать решение также на другом языке программирования (укажите название и используемую версию языка программирования, например, Cython 0.20). В этом случае Вы должны использовать те же самые исходные данные и переменные, какие были предложены в приведённых фрагментах.

Например, для исходного массива из 10 элементов

57

95

-42

-849

8003

674

-305

667

665

2

программа должна вывести

4

(Условию удовлетворяют следующие пары: 95 и -42, 8003 и 674, 674 и -305, 665 и 2).

Для удобства за пару будем считать элементы \(a[i]\) и \(a[i+1]\) (не \(a[i]\) и \(a[i-1]\)!).

\(t\) будет отвечать за количество пар, подходящих по условие, поэтому изначально она равна нулю.

В цикле от 0 до \(N-1\) (если мы укажем цикл до \(N\), то программа будет пытаться проверить пару \(a[N-1]\) и \(a[N]\), но элемента \(a[N]\) не существует в силу индексации с нуля) мы будем проверять, что \(|a[i] \; - \; a[i+1]| > 14\) и что \(|a[i] \; / \; a[i+1]| > 1\). Если оба условия выполняются, то мы увеличим \(t\) на 1. Вне цикла выведем \(t\).

Так как нам нужно узнать разность и результат деления первого элемента на второй по модулю, а другие библиотеки подключать нельзя, будем делать так: если разность получилась отрицательной, мы меняем знак на обратный, если положительной — оставляем. Аналогично и с делением.

Пример на \(C++\):

\(k = 0, \; m = 0;\)

\(for \; (i = 0; \; i < N-1; \; i++) \{\)

\(\quad k \; = \; a[i] - a[i+1];\)

\(\quad m \; = \; a[i] \; / \; a[i+1];\)

\(\quad if \; (k < 0) \; k = -k; \)

\(\quad if \; (m < 0) \; m = -m; \)

\(\quad if \; ((k > 14) \; \&\& \; (m > 1)) \; t++;\)

\(\}\)

\(cout << t; \)

Ответ: см. решение

Задание 4 #11841

Дан целочисленный массив из 60 элементов. Элементы массива могут принимать целые значения от 0 до 10000 включительно. Опишите на естественном языке или на одном из языков программирования алгоритм, который выполняет следующее: ищет такие тройки элементов (три подряд идущих элемента, \(a[0], a[1], a[2];\) \(a[3], a[4], a[5]; ...; a[56], a[57], a[59]\)), в которых каждое число четно, и cчитает их количество. В качестве результата выведите получившееся число. Исходные данные объявлены так, как показано ниже на примерах для некоторых языков программирования. Запрещается использовать переменные, не описанные ниже, но разрешается не использовать некоторые из описанных переменных. Индексация элементов в массиве начинается с нуля.

\[\begin{array}{|l|l|l|} \hline \text{Бейсик} & Python & \text{Алгоритмический язык} \\ \hline CONST \; N \; AS \; INTEGER \; = \; 50 & \text{\# \; допускается также} &\underline{\text{алг}} \\ DIM \; A \; (0 \; TO \; N-1) \; AS \; LONG \; &\text{\# \; использовать три} &\underline{\text{нач}} \\ DIM \; I \; AS \; LONG& \text{\# целочисленные переменные i,t,k} & \quad \underline{\text{цел}} \; N = 50 \\ \quad \quad \; \; T \; AS \; LONG& a \; = [] &\quad \underline{\text{целтаб}} \; a[0:N-1] \\ \quad \quad \; \; K \; AS \; LONG& n \; = \; 50&\quad \underline{\text{цел}} \; i, \; t, \; k \\ FOR \; I \; = \; 0 \; TO \; N-1 &for \; i \; in \; range(0, \; n):&\quad \underline{\text{нц для}} \; i \; \underline{\text{от}} \; 0 \; \underline{\text{до}} \; N-1 \\ \quad \quad \; \; INPUT \; A(I)& \quad a.append \; (int(input()))&\quad \quad \underline{\text{ввод}} \; a[i] \\ NEXT \; I& ...&\quad \underline{\text{кц }} \\ ... & &... \\ END & & \underline{\text{кон}} \\ \hline \end{array}\]

\[\begin{array}{|l|l|} \hline \ \text{Паскаль} & C++ \\ \hline const &\#include \; <iostream> \\ \quad N = 50 & using \; namespace \; std; \\ var & const \; int \; N = 50;\\ \quad a: \; array \; [0..N-1] \; of \; longint; & int \; main() \{ \\ \quad i, \; t, \; k: \; longint; &long \; a[N]; \\ begin & long \; i, \; t, \; k; \\ \quad for \; i \; := 1 \; to \; N \; do &for \; (i = 0; \; i < N; \; i++) \; cin >> a[i]; \\ \quad \quad readln (a[i]); & ... \\ ... &return \; 0; \\ end. & \} \\ \hline \end{array}\]

В качестве ответа Вам необходимо привести фрагмент программы, который должен находиться на месте многоточия. Вы можете записать решение также на другом языке программирования (укажите название и используемую версию языка программирования, например, Cython 0.20). В этом случае Вы должны использовать те же самые исходные данные и переменные, какие были предложены в приведённых фрагментах.

Под тройками будем подразумевать \(a[i], a[i+1], a[i+2]\). Следующая тройка — это \(a[i+3], \; a[i+4], \; a[i+5]\). Именно поэтому шаг в цикле \(for\) будет равен 3 (чтобы после элемента \(a[i]\) рассматривать \(a[i+3]\), а не \(a[i+1]\)). В \(t\) будем хранить текущее количество троек, в которых каждый элемент четен, поэтому \(t\) изначально равна 0.

В цикле от 0 до \(N-2\) (до \(N-2\), так как для элемента \(a[N-2]\) уже нет тройки \(a[N-2], a[N-2 + 1 = N-1]\) и \(a[N-2 + 2 = N]\)) будем проверять четность \(a[i], \; a[i+1]\) и \(a[i+2]\). Если эти элементы одновременно четны, мы увеличим \(t\) на 1. К концу цикла в \(t\) будет храниться итоговое количество нужных нам троек.

Пример программы на С++:

\(t = 0; \)

\(for \; (i = 0; \; i < N-2; i+=3) \{ \)

\( \quad if \; ((a[i] \; \% \; 2 == 0) \; \&\& \; (a[i+1] \; \% 2 \; == 0) \; \&\& \; (a[i+2]; \% 2\; == 0) \; t++;\)

\( \}\)

\(cout << t; \)

Ответ: см. решение

Задание 5 #11842

Дан целочисленный массив из 30 элементов. Элементы массива могут принимать целые значения от -10000 до 10000 включительно. Опишите на естественном языке или на одном из языков программирования алгоритм, позволяющий найти количество элементов массива, чья сумма цифр кратна 5. В качестве результата выведите измененный массив, каждый элемент выводится с новой строки. Исходные данные объявлены так, как показано ниже на примерах для некоторых языков программирования. Запрещается использовать переменные, не описанные ниже, но разрешается не использовать некоторые из описанных переменных. Индексация элементов в массиве начинается с нуля.

\[\begin{array}{|l|l|l|} \hline \text{Бейсик} & Python & \text{Алгоритмический язык} \\ \hline CONST \; N \; AS \; INTEGER \; = \; 30 & \text{\# \; допускается также} &\underline{\text{алг}} \\ DIM \; A \; (0 \; TO \; N-1) \; AS \; LONG \; &\text{\# \; использовать три} &\underline{\text{нач}} \\ DIM \; I \; AS \; LONG& \text{\# целочисленные переменные i,t,k} & \quad \underline{\text{цел}} \; N = 30 \\ \quad \quad \; \; T \; AS \; LONG& a \; = [] &\quad \underline{\text{целтаб}} \; a[0:N-1] \\ \quad \quad \; \; K \; AS \; LONG& n \; = \; 30&\quad \underline{\text{цел}} \; i, \; t, \; k \\ FOR \; I \; = \; 0 \; TO \; N-1 & for \; i \; in \; range(0, \; n):&\quad \underline{\text{нц для}} \; i \; \underline{\text{от}} \; 0 \; \underline{\text{до}} \; N-1 \\ \quad \quad \; \; INPUT \; A(I)& \quad a.append \; (int(input()))&\quad \quad \underline{\text{ввод}} \; a[i] \\ NEXT \; I& ...&\quad \underline{\text{кц }} \\ ... & &... \\ END & & \underline{\text{кон}} \\ \hline \end{array}\]

\[\begin{array}{|l|l|} \hline \ \text{Паскаль} & C++ \\ \hline const &\#include \; <iostream> \\ \quad N = 30 & using \; namespace \; std; \\ var & const \; int \; N = 30;\\ \quad a: \; array \; [0..N-1] \; of \; longint; & int \; main() \{ \\ \quad i, \; t, \; k: \; longint; &long \; a[N]; \\ begin & long \; i, \; t, \; k; \\ \quad for \; i \; := 0 \; to \; N-1 \; do &for \; (i = 0; \; i < N; \; i++) \; cin >> a[i]; \\ \quad \quad readln (a[i]); & ... \\ ... &return \; 0; \\ end. & \} \\ \hline \end{array}\]

В качестве ответа Вам необходимо привести фрагмент программы, который должен находиться на месте многоточия. Вы можете записать решение также на другом языке программирования (укажите название и используемую версию языка программирования, например, Cython 0.20). В этом случае Вы должны использовать те же самые исходные данные и переменные, какие были предложены в приведённых фрагментах.

Например, для исходного массива из 10 элементов

34

53363

-535

64

3

6

3536

-5

35

2434

программа должна вывести

3

(Под условие подходят 53363 (сумма цифр = 20), 64 (сумма цифр = 10), -5 (сумма цифр = 5)).

В цикле \(for\) от 0 до \(N\) мы будем перебирать элементы массива. В переменной \(k\) мы будем хранить количество элементов, чья сумма цифр кратна 5. Так как изначально таких элементов нет, приравняем \(k\) к нулю в начале.

Опишем алгоритм нахождения суммы цифр числа. Пусть у нас есть число 354. Его последнюю цифру 4 можно найти как остаток от деления на 10 числа 354. Попробуем так же найти и предпоследнюю цифру. Если мы целочисленно разделим 354 на 10, то получим 35, и цифра 5 тогда будет последней. Ее мы уже умеем находить как остаток от деления на 10 всего числа, в данном случае этим числом является 35. Аналогично мы найдем и первую цифру исходного числа, разделив вначале 35 на 10, а потом взяв остаток от деления на 10.

Так как нам заранее неизвестно количество цифр в числе, мы будем использовать цикл \(while\) (внутри цикла \(for\)). Пока рассматриваемое нами число больше или равно 1 (это условие выполнения), мы будем выполнять то, что написано в теле цикла. Как только число станет меньше 1, мы выйдем из цикла (если число стало меньше 1, то мы рассмотрели все его цифры и дальше просто целочисленно делим на 10 и будем получать 0).

Сумму цифр числа будем записывать в переменную \(t\). Приравняем ее изначально вне цикла \(while\) (но внутри цикла \(for\), чтобы \(t\) была равна нулю для каждого следующего элемента) к нулю и будем прибавлять к ней цифру, которую нашли как остаток от деления на 10. После этого будем целочисленно делить на 10, чтобы ’убрать" последнюю цифру числа. После того, как мы выйдем из цикла, в \(t\) будет храниться сумма цифр исходного числа. Если она оказалась кратна 5 (остаток от деления на 5 равен 0), то мы прибавим к \(k\) единицу, что будет значить, что подходящих нам элементов стало на один больше. Вне обоих циклов выведем \(k\) в соответствии с условием.

Пример программы на \(C++\):

\(k = 0;\)

\(for \; (i = 0; \; i < N; \; i++) \{\)

\(\quad t = 0; \)

\(\quad while \; (a[i] >= 1) \{ \)

\(\quad \quad t \; += a[i] \% 10;\)

\(\quad \quad a[i] \; /= 10; \)

\(\quad \}\)

\(\quad if \; (t \% 5 == 0) \; k++; \)

\(\}\)

\(cout << k;\)

Ответ: см. решение

Задание 6 #11843

Дан целочисленный массив из 30 элементов. Элементы массива могут принимать целые значения от 0 до 10000 включительно. Опишите на естественном языке или на одном из языков программирования алгоритм, позволяющий найти количество пар элементов массива, чья сумма в восьмиричной системе счисления оканчивается на 6, и заменить каждый элемент таких пар на их количество. Под парой подразумевается два подряд идущих элемента массива, элементы в парах не повторяются. В качестве ответа программа должна вывести изменённый массив (по одному элементу в строке). Исходные данные объявлены так, как показано ниже на примерах для некоторых языков программирования. Запрещается использовать переменные, не описанные ниже, но разрешается не использовать некоторые из описанных переменных. Индексация элементов в массиве начинается с нуля.

\[\begin{array}{|l|l|l|} \hline \text{Бейсик} & Python & \text{Алгоритмический язык} \\ \hline CONST \; N \; AS \; INTEGER \; = \; 30 & \text{\# \; допускается также} &\underline{\text{алг}} \\ DIM \; A \; (0 \; TO \; N-1) \; AS \; LONG \; &\text{\# \; использовать три} &\underline{\text{нач}} \\ DIM \; I \; AS \; LONG& \text{\# целочисленные переменные i,t,k} & \quad \underline{\text{цел}} \; N = 30 \\ \quad \quad \; \; T \; AS \; LONG& a \; = [] &\quad \underline{\text{целтаб}} \; a[0:N-1] \\ \quad \quad \; \; K \; AS \; LONG& n \; = \; 30&\quad \underline{\text{цел}} \; i, \; t, \; k \\ FOR \; I \; = \; 0 \; TO \; N-1 &for \; i \; in \; range(0, \; n):&\quad \underline{\text{нц для}} \; i \; \underline{\text{от}} \; 0 \; \underline{\text{до}} \; N-1 \\ \quad \quad \; \; INPUT \; A(I)& \quad a.append \; (int(input()))&\quad \quad \underline{\text{ввод}} \; a[i] \\ NEXT \; I& ...&\quad \underline{\text{кц }} \\ ... & &... \\ END & & \underline{\text{кон}} \\ \hline \end{array}\]

\[\begin{array}{|l|l|} \hline \ \text{Паскаль} & C++ \\ \hline const &\#include \; <iostream> \\ \quad N = 30 & using \; namespace \; std; \\ var & const \; int \; N = 30;\\ \quad a: \; array \; [0..N-1] \; of \; longint; & int \; main() \{ \\ \quad i, \; t, \; k: \; longint; &long \; a[N]; \\ begin & long \; i, \; t, \; k; \\ \quad for \; i \; := 0 \; to \; N-1 \; do &for \; (i = 0; \; i < N; \; i++) \; cin >> a[i]; \\ \quad \quad readln (a[i]); & ... \\ ... &return \; 0; \\ end. & \} \\ \hline \end{array}\]

В качестве ответа Вам необходимо привести фрагмент программы, который должен находиться на месте многоточия. Вы можете записать решение также на другом языке программирования (укажите название и используемую версию языка программирования, например, Cython 0.20). В этом случае Вы должны использовать те же самые исходные данные и переменные, какие были предложены в приведённых фрагментах.

Например, для исходного массива из 10 элементов

57

583

20

43

3

983

534

32

3

2

программа должна вывести

2

(Под условие подходят следующие пары: 43 и 3, 534 и 32).

Для удобства за пару будем считать элементы \(a[i]\) и \(a[i+1]\) (не \(a[i]\) и \(a[i-1]\)!), следующей парой будут \(a[i+2]\) и \(a[i+3]\). Шаг цикла будет равен 2, потому что от элемента \(a[i]\) нам надо перейти не к \(a[i+1]\), а к \(a[i+2]\).

В цикле \(for\) от 0 до \(N-1\) (до \(N-1\), а не до \(N\), так иначе программа будет пытаться проверить пару \(a[N-1]\) и \(a[N]\), но элемента \(a[N]\) не существует в силу индексации с нуля) мы будем перебирать элементы массива. В переменной \(t\), которую изначально приравняем к нулю, будем хранить количество пар, чья сумма в восьмиричной системе счисления оканчивается на 6.

Опишем алгоритм для нахождения последней цифры числа в восьмиричной системе счисления. Вспомним, что для перевода числа в восьмиричную систему счисления нужно делить число на 8 до тех пор, пока оно не станет меньше 8, и запоминать остатки, получившиеся при делении. После этого надо выписать подряд в строку все остатки, начиная с последнего. Полученное число и будет являться восьмиричным разложением числа. Таким образом, чтобы узнать последнюю цифру числа в восьмиричной системе счисления, надо узнать остаток от деления исходного числа на 8 (ведь если мы выписываем остатки, начиная с последнего, то последней цифрой числа будет первый остаток от деления на 8).

Задача сводится к тому, что нам надо найти остаток от деления на 8 суммы двух элементов. Если он равен 6, мы увеличиваем счетчик \(t\) на 1.

Пример на \(C++\):

\(t = 0; \)

\(for \; (i = 0; \; i < N-1; i+=2) \)

\(\quad if \; ((a[i] \; + \; a[i+1]) \; \% \; 8 == 6) \; \; t++;\)

\(cout << t;\)

Ответ: см. решение

Задание 7 #11844

Дан целочисленный массив из 30 элементов. Элементы массива могут принимать целые значения от -10000 до 10000 включительно. Опишите на естественном языке или на одном из языков программирования алгоритм, позволяющий найти наибольшее количество одинаковых элементов, расположенных подряд. Исходные данные объявлены так, как показано ниже на примерах для некоторых языков программирования. Запрещается использовать переменные, не описанные ниже, но разрешается не использовать некоторые из описанных переменных. В качестве ответа Вам необходимо привести фрагмент программы, который должен находиться на месте многоточия. Вы можете записать решение также на другом языке программирования (укажите название и используемую версию языка программирования, например, Cython 0.20). В этом случае Вы должны использовать те же самые исходные данные и переменные, какие были предложены в приведённых фрагментах. Индексация элементов в массиве начинается с нуля.

\[\begin{array}{|l|l|l|} \hline \text{Бейсик} & Python & \text{Алгоритмический язык} \\ \hline CONST \; N \; AS \; INTEGER \; = \; 30 & \text{\# \; допускается также} &\underline{\text{алг}} \\ DIM \; A \; (0 \; TO \; N-1) \; AS \; LONG \; &\text{\# \; использовать три} &\underline{\text{нач}} \\ DIM \; I \; AS \; LONG& \text{\# целочисленные переменные i,t,k} & \quad \underline{\text{цел}} \; N = 30 \\ \quad \quad \; \; T \; AS \; LONG& a \; = [] &\quad \underline{\text{целтаб}} \; a[0:N-1] \\ \quad \quad \; \; K \; AS \; LONG& n \; = \; 30&\quad \underline{\text{цел}} \; i, \; t, \; k \\ FOR \; I \; = \; 0 \; TO \; N-1 &for \; i \; in \; range(0, \; n):&\quad \underline{\text{нц для}} \; i \; \underline{\text{от}} \; 0 \; \underline{\text{до}} \; N-1 \\ \quad \quad \; \; INPUT \; A(I)& \quad a.append \; (int(input()))&\quad \quad \underline{\text{ввод}} \; a[i] \\ NEXT \; I& ...&\quad \underline{\text{кц }} \\ ... & &... \\ END & & \underline{\text{кон}} \\ \hline \end{array}\]

\[\begin{array}{|l|l|} \hline \ \text{Паскаль} & C++ \\ \hline const &\#include \; <iostream> \\ \quad N = 30 & using \; namespace \; std; \\ var & const \; int \; N = 30;\\ \quad a: \; array \; [0..N-1] \; of \; longint; & int \; main() \{ \\ \quad i, \; t, \; k: \; longint; &long \; a[N]; \\ begin & long \; i, \; t, \; k; \\ \quad for \; i \; := 1 \; to \; N \; do &for \; (i = 0; \; i < N; \; i++) \; cin >> a[i]; \\ \quad \quad readln (a[i]); & ... \\ ... &return \; 0; \\ end. & \} \\ \hline \end{array}\]

Например, для исходного массива из 13 элементов

23453

-335

335

5

0

0

0

-6

2

677

677

4

4

программа должна вывести

3

В переменной \(k\) мы будем хранить наибольшее количество идущих подряд элементов массива. Так как наименьшая длина такой последовательности равна 1 (сам элемент), изначально приравняем \(k\) к единице.

Опишем кратко идею решения задачи: для каждого элемента массива мы будем подсчитывать, сколько до него идет подряд одинаковых чисел. После этого мы будем сравнивать получившееся количество с наибольшим количеством следующих друг за другом одинаковых элементов массива (с \(k\)) и обновим \(k\), если это понадобится.

В \(t\) мы будем хранить длину последовательности одинаковых чисел для элемента, который мы рассматриваем (сколько одинаковых чисел расположено до этого элемента, считая текущий элемент). Изначально приравняем \(t\) к единице (ведь последовательность одинаковых чисел будет состоять как минимум из текущего элемента).

Например, у нас есть такой массив: 1 1 1 0 0 0 0 4

Перед нулевым элементом массива нет никаких чисел, поэтому до него идет подряд 0 одинаковых чисел, \(t = 1\). \(k = t\), значит, \(k\) не меняем. Перед первым элементом \(a[1]\) = 1 расположен равный ему \(a[0]\) = 1, тогда теперь у нас есть два одинаковых элемента, \(t = 2\). \(k < t\), тогда теперь \(k = t = 2.\) Перед вторым элементом расположен тоже элемент, равный ему, но мы уже знаем, что для предыдущего элемента \(t = 2\). Значит, увеличим \(t\) на единицу (добавив к последовательности одинаковых чисел второй элемент). \(k < t\), тогда \(k = t = 3\). Так как следующий элемент уже не равен предыдущему, начнем рассматривать новую последовательность чисел. Приравняем \(t\) к 1 (теперь последовательность одинаковых чисел состоит из одного элемента, который мы сейчас рассматриваем). Следующий элемент \(a[4]\) равен \(a[3]\), значит, увеличим значение \(t\) на 1. \(k > t\), \(k\) оставляем таким же. \(a[5] = a[4]\), значит, увеличим \(t\) еще на один. \(k = t\), оставляем таким же. Наконец, \(a[6] = a[5]\), увеличим \(t\), ведь теперь последовательность одинаковых чисел равна четырем. Так как \(k > t\), \(k = t\). Следующий элемент \(a[7]\) не равен \(a[6]\), для него \(t = 1\).

Обобщим наш алгоритм: для нулевого элемента \(t = 1\). Для каждого следующего элемента мы проверяем, равен ли он предыдущему. Если да, мы увеличиваем \(t\) на 1, так как последовательность одинаковых элементов стала больше на один элемент и сравним \(t\) с максимумом \(k\) (если \(t > k\), \(t = k\)). Если нет, мы только сравним \(t\) с максимумом \(k\). После этого приравняем \(t\) снова к 1, потому что теперь рассматриваем новую последовательность одинаковых чисел. Вне цикла выведем \(k\), в котором окажется длина максимальной последовательности одинаковых чисел.

Пример на \(C++\) (с комментариями):

\(t = 1, \; k = 1; \)

\(for \; (i = 1; \; i < N; \; i++) \{\) //начнем с первого элемента массива, потому что для нулевого \(t = 1\).

\(\quad if \; (a[i] == a[i-1]) \; t++;\)

\(\quad else \; t = 1; \) //если текущий элемент не равен предыдущему, \(t\) = 1.

\(\quad if \; (k < t)\; k = t;\) //обновляем максимум, если необходимо.

\(\}\)

\(cout << k; \)

Ответ: см. решение