Задача к ЕГЭ по информатике на тему «соседние элементы, проверка условий» №5

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

|--------------------------------|------------------------------------|-------------------------| |Бейси-к-------------------------|Python------------------------------|А-лгори-тми-ческий-язы-к-| |CON ST N ASIN TEGER = 30 |# допуск ается такж е |ал-г | |DIM A (0TON − 1)ASLON G |# испол ьзовать три |нач | | | |---- | |DIM IASLON G |# ц елочисл енны е п еремен ны е i,t,k ц-елN = 30 | | T ASLON G |a = [] | ц-елтабa[0 : N − 1] | | KASLON G |n = 30 | ц-елi,t,k | |FORI = 0T ON − 1 |foriinrange (0,n) : | н ц дляiот0д оN − 1 | | | | ------- --- | | IN P U TA (I) | a.append (int(input ())) | вводa[i] | |N EXT I |... | к-ц- | |... | |... | -EN-D------------------------------------------------------------------кон-----------------------

В качестве ответа Вам необходимо привести фрагмент программы, который должен находиться на месте многоточия. Вы можете записать решение также на другом языке программирования (укажите название и используемую версию языка программирования, например, Cython 0.20). В этом случае Вы должны использовать те же самые исходные данные и переменные, какие были предложены в приведённых фрагментах. Например, для исходного массива из 10 элементов 57583204339835343232 программа должна вывести 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)$

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

$cout < < t;$

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