По каналу связи передаётся последовательность положительных целых чисел. Все числа не превышают 1000, их количество известно, но может быть очень велико. Затем передаётся контрольное значение — наибольшее число R, удовлетворяющее следующим условиям:
1) R — произведение двух различных переданных элементов последовательности («различные» означает, что не рассматриваются квадраты переданных чисел, произведения различных, но равных по величине элементов допускаются);
2) R не делится на 10.
В результате помех при передаче как сами числа, так и контрольное значение могут быть искажены.
Напишите программу которая будет проверять правильность контрольного значения. Программа должна напечатать отчёт по следующей форме:
Получено чисел: …
Принятое контрольное значение: …
Вычисленное контрольное значение: …
Контроль пройден (или Контроль не пройден)
Если удовлетворяющее условию контрольное значение определить невозможно, вычисленное контрольное значение не выводится, но выводится фраза «Контроль не пройден».
Перед текстом программы кратко опишите алгоритм решения и укажите язык программирования и его версию.
Вам предлагаются два задания, связанные с этой задачей: задание А и задание Б. Вы можете решать оба задания А и Б или одно из них по своему выбору.
Итоговая оценка выставляется как максимальная из оценок за задания А и Б. Если решение одного из заданий не представлено, то считается, что оценка за это задание составляет 0 баллов.
Задание Б является усложненным вариантом задания А, оно содержит дополнительные требования к программе. Перед программой укажите версию языка программирования.
А. Напишите на любом языке программирования программу для решения поставленной задачи, в которой входные данные будут запоминаться в массиве, после чего будут проверены все возможные пары элементов.
Обязательно укажите, что программа является решением задания А.
Максимальная оценка за выполнение задания А – 2 балла.
Б. Напишите программу для решения поставленной задачи, которая будет эффективна как по времени, так и по памяти (или хотя бы по одной из этих характеристик).
Программа считается эффективной по времени, если время работы программы пропорционально количеству элементов последовательности N, т. е. при увеличении N в k раз время работы программы должно увеличиваться не более чем в k раз. Обязательно укажите, что программа является решением задания Б.
Входные данные
В первой строке указывается количество чисел N. В каждой из последующих
N строк записано одно натуральное число, не превышающее 1000.
В последней строке записано контрольное значение.
Пример входных данных:
5
60
7
8
15
20
105
Выходные данные
Программа должна напечатать отчёт по образцу, приведённому в условии.
Пример выходных данных для приведённого выше примера входных данных:
Получено чисел: 5
Принятое контрольное значение: 105
Вычисленное контрольное значение: 105
Контроль пройден
Произведение двух чисел делится на 10, если один из сомножителей делится на 10 (второй может быть любым), либо если ни один из сомножителей не делится на 10, но один из сомножителей делится на 2, а другой — на 5.
Чтобы получить произведение, не делящееся на 10, нужно взять два сомножителя так, чтобы эти условия не выполнялись. Чтобы добиться этого, можно разбить все элементы входной последовательности на 4 непересекающихся класса чисел:
- кратные 10 (класс 10);
- кратные 2, но не кратные 5 (класс 2);
- кратные 5, но не кратные 2 (класс 5);
- не кратные ни 2, ни 5 (класс 0).
Числа, кратные 10, можно сразу отбросить: они не могут участвовать в итоговом произведении. Произведение двух чисел не будет делиться на 10, если оба числа принадлежат одному классу, либо если числа принадлежат
разным классам, но не классам 2 и 5. При этом для получения максимального значения следует брать максимально возможное число из каждого класса. Пусть a2 — максимальное число в классе 2, b2 — второе по величине число в классе 2, аналогичным образом обозначим два наибольших числа в классах 5 и 0. Тогда контрольным значением будет наибольшее из следующих произведений: a2*b2, a5*b5, a0*b0, a0*a2, a0*a5.
Программа читает все входные данные один раз, не запоминая все данные в массиве, для каждого входного числа определяет его класс, отбрасывает числа класса 10 и хранит два наибольших числа для каждого из остальных классов. После ввода всей последовательности программа вычисляет 5 перечисленных выше произведений, выбирает из них наибольшее и сравнивает его с введённым контрольным значением.
Пример правильной и эффективной программы на языке Паскаль
program c4;
var
N: integer; {количество чисел на входе}
x: integer; {исходные данные}
a2, b2: integer; {макс. числа, кратные 2, но не кратные 5}
a5, b5: integer; {макс. числа, кратные 5, но не кратные 2}
a0, b0: integer; {максимальные числа, не кратные 5 и 2}
R: integer; {введенное контрольное значение}
m: integer; {вычисленное контрольное значение}
i: integer;
begin
readln(N);
a2:=0; b2:=0;
a5:=0; b5:=0;
a0:=0; b0:=0;
for i:=1 to N do begin
readln(x);
if x mod 10 = 0 then {ничего не делать}
else if x mod 2 = 0 then begin
if x>a2 then begin b2:=a2; a2:=x end
else if x>b2 then b2:=x
end
else if x mod 5 = 0 then begin
if x>a5 then begin b5:=a5; a5:=x end
else if x>b5 then b5:=x
end
else begin
if x>a0 then begin b0:=a0; a0:=x end
else if x>b0 then b0:=x
end
end;
readln(R);
m := a0*a2;
if a0*a5>m then m:=a0*a5;
if a0*b0>m then m:=a0*b0;
if a2*b2>m then m:=a2*b2;
if a5*b5>m then m:=a5*b5;
writeln('Получено чисел: ', N);
writeln('Принятое контрольное значение: ', R);
if m>0 then writeln('Вычисленное контрольное значение: ', m);
if (R>0) and (R=m)
then writeln('Контроль пройден')
else writeln('Контроль не пройден')
end.
Пример правильной и эффективной программы на языке Си
#include <stdio.h>
void main ()
{
int N; /*количество чисел на входе*/
int x; /*исходные данные*/
int a2=0, b2=0; /*макс. числа, кратные 2, но не кратные 5*/
int a5=0, b5=0; /*макс. числа, кратные 5, но не кратные 2*/
int a0=0, b0=0; /*максимальные числа, не кратные 5 и 2*/
int R; /*введенное контрольное значение*/
int m; /*вычисленное контрольное значение*/
int i;
cin >> N;
for (i=1; i<=N; ++i) {
cin >> x;
if (x % 10 == 0) continue; /*ничего не делать*/
if (x % 2 == 0) {
if (x>a2) {b2=a2; a2=x;}
else if (x>b2) b2=x;
}
else if (x % 5 == 0) {
if (x>a5) {b5=a5; a5=x;}
else if (x>b5) b5=x;
}
else {
if (x>a0) {b0=a0; a0=x;}
else if (x>b0) b0=x;
}
}
cin >> R;
m = a0*a2;
if (a0*a5>m) m=a0*a5;
if (a0*b0>m) m=a0*b0;
if (a2*b2>m) m=a2*b2;
if (a5*b5>m) m=a5*b5;
printf("Получено чисел: %d\n", N);
printf("Принятое контрольное значение: %d\n", R);
if (m>0) printf("Вычисленное контрольное значение: %d\n", m);
if (R>0 && R==m) cout << "Контроль пройден\n";
else cout << "Контроль не пройден\n";
}
Пример правильной и эффективной программы на языке Бейсик
DIM N AS INTEGER 'количество чисел на входе
DIM x AS INTEGER 'исходные данные
DIM a2, b2 AS INTEGER 'макс. числа, кратные 2, но не кратные 5
DIM a5, b5 AS INTEGER 'макс. числа, кратные 5, но не кратные 2
DIM a0, b0 AS INTEGER 'максимальные числа, не кратные 5 и 2
DIM R AS INTEGER 'введенное контрольное значение
DIM m AS INTEGER 'вычисленное контрольное значение
DIM i AS INTEGER
INPUT N
FOR i = 1 TO N
INPUT x
IF x MOD 10 = 0 THEN 'ничего не делать
ELSEIF x MOD 2 = 0 THEN
IF x > a2 THEN
b2 = a2: a2 = x
ELSEIF x > b2 THEN b2 = x
END IF
ELSEIF x MOD 5 = 0 THEN
IF x > a5 THEN
b5 = a5: a5 = x
ELSEIF x > b5 THEN b5 = x
END IF
ELSE
IF x > a0 THEN
b0 = a0: a0 = x
ELSEIF x > b0 THEN b0 = x
END IF
END IF
NEXT i
INPUT R
m = a0 * a2
IF a0 * a5 > m THEN m = a0 * a5
IF a0 * b0 > m THEN m = a0 * b0
IF a2 * b2 > m THEN m = a2 * b2
IF a5 * b5 > m THEN m = a5 * b5
PRINT "Получено чисел: "; N
PRINT "Принятое контрольное значение: "; R
IF m > 0 THEN PRINT "Вычисленное контрольное значение: "; m
IF (R > 0) AND (R = m) THEN
PRINT "Контроль пройден"
ELSE
PRINT "Контроль не пройден"
END IF
Пример правильной и эффективной программы на Алгоритмическом языке
алг
нач
цел N | количество чисел на входе
цел x | исходные данные
цел a2=0, b2=0 | макс. числа, кратные 2, но не кратные 5
цел a5=0, b5=0 | макс. числа, кратные 5, но не кратные 2
цел a0=0, b0=0 | максимальные числа, не кратные 5 и 2
цел R | введенное контрольное значение
цел m | вычисленное контрольное значение
ввод N
нц N раз
ввод x
выбор
при mod(x, 10) = 0: | ничего не делать
при mod(x, 2) = 0:
выбор
при x>a2: b2:=a2; a2:=x
при x>b2: b2:=x
все
при mod(x, 5) = 0:
выбор
при x>a5: b5:=a5; a5:=x
при x>b5: b5:=x
все
иначе
выбор
при x>a0: b0:=a0; a0:=x
при x>b0: b0:=x
все
все
кц
ввод R
m := a0*a2
если a0*a5>m то m:=a0*a5 все
если a0*b0>m то m:=a0*b0 все
если a2*b2>m то m:=a2*b2 все
если a5*b5>m то m:=a5*b5 все
вывод "Получено чисел: ", N
вывод нс, "Принятое контрольное значение: ", R
если m>0
то вывод нс, "Вычисленное контрольное значение: ", m
все
если R>0 и R=m
то вывод нс, "Контроль пройден"
иначе вывод нс, "Контроль не пройден"
все
кон
Пример решения задачи А на языке Паскаль.
vara: array[1..10000] of integer; {исходные данные}
N: integer; {количество элементов последовательности}
R: integer; {принимаемое контрольное значение}
max: integer; {вычисляемое контрольное значение}
i, j: integer;
begin
readln(N);
max := 0;
for i := 1 to N do read(a[i]);
for i := 1 to N-1 do
for j := i+1 to N do
if (a[i]*a[j] > max) and (a[i]*a[j] mod 10 <> 0) then max := a[i] * a[j];
readln(R);
writeln('Получено чисел: ', N);
writeln('Принятое контрольное значение: ', R);
if max>0 then writeln('Вычисленное контрольное значение: ', max);
if (R>0) and (R=max) then writeln('Контроль пройден')
else writeln('Контроль не пройден');
end.