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

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

Дан целочисленный массив из 20 элементов. Элементы массива могут принимать целые значения от $-$ 10 000 до 10 000 включительно. Опишите
на естественном языке или на одном из языков программирования алгоритм, позволяющий найти и вывести максимальный элемент массива, который НЕ делится на 3 (наличие хотя бы одного такого элемента гарантируется).

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

Бейсик	Python
CONST N AS INTEGER = 20 DIM A (1 TO N) AS INTEGER DIM I AS INTEGER, J AS INTEGER, K AS INTEGER FOR I = 1 TO N INPUT A(I) NEXT I ... END	# допускается также # использовать две # целочисленные переменные j и k a = [] n = 20 for i in range(0, n): a.append(int(input())) ...
Алгоритмический язык	Паскаль
алг нач цел N = 20 целтаб a[1:N] цел i, j, k нц для i от 1 до N ввод a[i] кц ... кон	const N = 20; var a: array [1..N] of integer; i, j, k: integer; begin for i := 1 to N do readln(a[i]); ... end.
Си	Естественный язык
#include <stdio.h> #define N 20 int main() { int a[N]; int i, j, k; for (i = 0; i<N; i++) scanf("%d", &a[i]); ... return 0; }	Объявляем массив A из 20 элементов. Объявляем целочисленные переменные I, J, K. В цикле от 1 до 20 вводим элементы массива A с 1-го по 20-й. …

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

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

КЭС:

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

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

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

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

Тип ответа:

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

Номер: 3EF705

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

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

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

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

j = -10001
for i in range(n):
    if a[i] % 3 != 0:
        if a[i] > j:
            j = a[i]
print(j)

Проверка и обоснование.
На отдельном проверочном примере рассматриваем массив: -9948, 4, 5930, 10000, -3401, 9399, 0, 5, 10000, 2, 7887, -2, 1, 5, 1, 5154, 10000, 4239, -3, -9999.
Получаем: 10000.
После обработки первых i элементов j содержит максимум среди подходящих элементов именно этого префикса. Если подходящих элементов в префиксе ещё нет, для минимума или максимума сохраняется начальное вспомогательное значение, а для суммы или количества — ноль. На очередном шаге неподходящий элемент ничего не меняет, а подходящий учитывается по нужному правилу. Поэтому после полного прохода получен требуемый результат.
Время работы пропорционально n: один полный проход. Дополнительный массив не создаётся; помимо исходных данных используются только целочисленные переменные из условия.
Ответ: Фрагмент программы на Python 3 приведён в решении.

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

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

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

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