Дан массив, содержащий 2016 положительных целых чисел, не превышающих 1000. Необходимо найти и вывести минимальный из тех элементов этого массива, чётность которых совпадает с чётностью произведения всех элементов.
Например, в массиве из шести элементов, равных соответственно 2, 3, 1, 5, 6, 4, произведение всех элементов чётно, значит, ответом будет минимальный чётный элемент, то есть 2.
Напишите на одном из языков программирования программу для решения этой задачи. Исходные данные объявлены так, как показано ниже. Запрещается использовать переменные, не описанные ниже, но разрешается не использовать часть из описанных.
| Бейсик | Python |
|---|---|
CONST N=2016 DIM A(N) AS INTEGER DIM I, M, K AS INTEGER FOR I = 1 TO N INPUT A(I) NEXT I … END
| # допускается также использо- # вание целочисленных # переменных m, k a = [] N = 2016 for i in range(0, N): a.append(int(input())) …
|
| Алгоритмический язык | Паскаль |
алг нач цел N=2016 целтаб a[1:N] цел i, m, k нц для i от 1 до N ввод a[i] кц … кон | const N=2016; var a: array [1..N] of integer; i, m, k: integer; begin for i:=1 to N do readln(a[i]); … end. |
| Си++ | |
#include <iostream> using namespace std; #define N 2016 int main(){ int a[N]; int i, m, k; for (i=0; i < N; i++) cin >> a[i]; … return 0; }
| |
В качестве ответа Вам необходимо привести фрагмент программы, который должен находиться на месте многоточия. Вы можете записать решение также на другом языке программирования (укажите название и используемую версию языка программирования, например Free Pascal 2.4). В этом случае Вы должны использовать те же самые исходные данные и переменные, какие были предложены в условии.
Чтобы получить ответ за один просмотр всех элементов массива, можно найти минимумы среди чётных и нечётных элементов и выбрать из них тот, который соответствует чётности произведения. Само произведение вычислять не нужно, так как при этом возникает опасность переполнения. Достаточно заметить, что произведение всех элементов чётно, если в массиве есть хотя бы один чётный элемент, и для определения чётности произведения не нужна даже дополнительная переменная: наличие или отсутствие в массиве чётных элементов можно определить по значению чётного минимума.
Пример правильной программы на языке Паскаль (способ 1)
m:=1001; k:=1001;
for i:=1 to N do begin
if (a[i] mod 2 = 0) and (a[i] < m)
then m := a[i];
if (a[i] mod 2 = 1) and (a[i] < k)
then k := a[i];
end;
if m < 1001
then writeln(m)
else writeln(k)
Возможно решение, в котором используется всего одна дополнительная переменная. В этом решении все элементы по очереди сравниваются с текущим минимумом, как при обычном поиске минимального элемента. При сравнении элементов одинаковой чётности текущим минимумом становится больший из них, а при сравнении элементов разной чётности текущим минимумом становится чётный.
Пример правильной программы на языке Паскаль (способ 2)
m:=a[1];
for i:=2 to N do begin
if (a[i] mod 2 = m mod 2) and (a[i] < m) or
(a[i] mod 2 = 0) and (m mod 2 = 1)
then m := a[i];
end;
writeln(m)
Возможны и другие решения, в том числе использующие несколько циклов и/или несколько просмотров массива.