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

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

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

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

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

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

Бейсик

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 Многоразрядные целые числа, задачи длинной арифметики

Тип ответа:

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

Номер: D7E72A

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

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

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

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

j = 10001
for i in range(n):
    if a[i] % 8 != 0:
        if a[i] < j:
            j = a[i]
for i in range(n):
    if a[i] % 8 != 0:
        a[i] = j
    print(a[i])

Проверка и обоснование.
На примере из условия рассматриваем массив: 14, 16, 11, 8, 9, 32.
Получаем: 9, 16, 9, 8, 9, 32.
После обработки первых i элементов j содержит минимум среди подходящих элементов именно этого префикса. Если подходящих элементов в префиксе ещё нет, для минимума или максимума сохраняется начальное вспомогательное значение, а для суммы или количества — ноль. На очередном шаге неподходящий элемент ничего не меняет, а подходящий учитывается по нужному правилу. Поэтому после полного прохода получен требуемый результат.
Время работы пропорционально n: два полных прохода. Дополнительный массив не создаётся; помимо исходных данных используются только целочисленные переменные из условия.
Ответ: Фрагмент программы на Python 3 приведён в решении.

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

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

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

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