4CCF69 — Самостоятельное написание алгоритма: ответ и решение

Дайте развернутый ответ.

Дан целочисленный массив из 30 элементов. Элементы массива могут принимать целые значения от 0 до 10 000 включительно. Опишите на одном из языков программирования алгоритм, который находит сумму элементов массива, не меньших 99 и при этом не кратных 4, а затем заменяет каждый такой элемент на число, равное найденной сумме. Гарантируется, что хотя бы один такой элемент в массиве есть. В качестве результата необходимо вывести изменённый массив, каждый элемент выводится с новой строчки.

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

101

128

105

программа должна вывести следующий массив:

206

128

206

Исходные данные объявлены так, как показано ниже на примерах для некоторых языков программирования. Запрещается использовать переменные, не описанные ниже, но разрешается не использовать некоторые из описанных переменных.

Бейсик	Python
CONST N AS INTEGER = 30 DIM A (1 TO N) AS LONG DIM I AS LONG, J AS LONG, K AS LONG FOR I = 1 TO N INPUT A(I) NEXT I ... END	# допускается также # использовать две # целочисленные переменные j и k a = [] n = 30 for i in range(0, n): a.append(int(input())) ...
Алгоритмический язык	Паскаль
алг нач цел N = 30 целтаб a[1:N] цел i, j, k нц для i от 1 до N ввод a[i] кц ... кон	const N = 30; var a: array [1..N] of longint; i, j, k: longint; begin for i := 1 to N do readln(a[i]); ... end.
C++
#include <iostream> using namespace std; const int N = 30; int main() { long a[N]; long i, j, k; for (i = 0; i < N; i++) cin >> a[i]; ... return 0; }

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

СВОЙСТВА ЗАДАНИЯ

КЭС:

3.2 Оценка сложности вычислений. Время работы и объём используемой памяти, их зависимость от размера исходных данных. Оценка асимптотической сложности алгоритмов. Алгоритмы полиномиальной сложности. Переборные алгоритмы. Примеры различных алгоритмов решения одной задачи, которые имеют различную сложность

3.3 Определение возможных результатов работы простейших алгоритмов управления исполнителями и вычислительных алгоритмов. Определение исходных данных, при которых алгоритм может дать требуемый результат

3.4 Алгоритмы обработки натуральных чисел, записанных в позиционных системах счисления: разбиение записи числа на отдельные цифры, нахождение суммы и произведения цифр, нахождение максимальной (минимальной) цифры. Представление числа в виде набора простых сомножителей. Алгоритм быстрого возведения в степень. Поиск простых чисел в заданном диапазоне с помощью алгоритма «решето Эратосфена»

3.5 Многоразрядные целые числа, задачи длинной арифметики

Тип ответа:

Развернутый ответ

Номер: 4CCF69

Статус задания: НЕ РЕШЕНО Изменить статус

Решение задания EGEINF4CCF69

Ответ: Фрагмент программы на Python 3 приведён в решении

Решение.
Используем Python 3. В условии уже даны ввод массива a и n = 30. Вставляем приведённый ниже фрагмент вместо многоточия. Повторно вводить массив не требуется. Используем только разрешённые переменные a, n, i, j и, при необходимости, k. Индексы Python — от 0 до n − 1.
Условие отбора: a[i] >= 99 и a[i] % 4 != 0. Все перечисленные проверки должны выполняться одновременно. Оператор % вычисляет остаток; нулевой остаток означает делимость. Для отрицательных чисел проверка равенства остатка нулю также корректна.
В переменной j накапливаем сумму подходящих элементов.
Сначала j = 0. К j прибавляем значение каждого подходящего элемента, включая повторяющиеся значения на разных позициях. Неподходящие элементы в сумму не входят.
Первый проход только читает массив. Изменять его до завершения поиска нельзя: искомое значение должно относиться ко всему исходному массиву.
Во втором проходе проверяем то же условие и заменяем подходящий a[i] значением j. Затем печатаем каждый элемент, в том числе неподходящий, с новой строки. Порядок элементов сохраняется.
Во втором проходе текущая позиция проверяется до своего изменения и посещается ровно один раз. Уже изменённые позиции не влияют на отбор последующих: проверка использует только текущий a[i], а j больше не меняется.
Фрагмент программы:

j = 0
for i in range(n):
    if a[i] >= 99 and a[i] % 4 != 0:
        j += a[i]
for i in range(n):
    if a[i] >= 99 and a[i] % 4 != 0:
        a[i] = j
    print(a[i])

Проверка и обоснование.
На примере из условия рассматриваем массив: 101, 128, 6, 105, 4, 18.
Получаем: 206, 128, 6, 206, 4, 18.
После обработки первых i элементов j содержит сумму среди подходящих элементов именно этого префикса. Если подходящих элементов в префиксе ещё нет, для минимума или максимума сохраняется начальное вспомогательное значение, а для суммы или количества — ноль. На очередном шаге неподходящий элемент ничего не меняет, а подходящий учитывается по нужному правилу. Поэтому после полного прохода получен требуемый результат.
Время работы пропорционально n: два полных прохода. Дополнительный массив не создаётся; помимо исходных данных используются только целочисленные переменные из условия.
Ответ: Фрагмент программы на Python 3 приведён в решении.

Задание EGEINF4CCF69: Самостоятельное написание алгоритма

Решение задания EGEINF4CCF69

Помочь улучшить сайт

Комментарии к решению