По каналу связи передаётся последовательность положительных целых чисел, все числа не превышают 1000. Количество чисел известно, но может быть очень велико. Затем передаётся контрольное значение последовательности — наибольшее число R, удовлетворяющее следующим условиям:
1) R — произведение двух различных переданных элементов последовательности («различные» означает, что не рассматриваются квадраты переданных чисел, произведения различных элементов последовательности, равных по величине, допускаются);
2) R делится на 14.
Если такого числа R нет, то контрольное значение полагается равным 0. В результате помех при передаче как сами числа, так и контрольное значение могут быть искажены.
Напишите программу (укажите используемую версию языка программирования, например, Borland Pascal 7.0), которая будет проверять правильность контрольного значения. Программа должна напечатать отчёт по следующей форме:
Вычисленное контрольное значение: ...
Контроль пройден (или — Контроль не пройден)
Перед текстом программы кратко опишите используемый Вами алгоритм решения.
На вход программе в первой строке подаётся количество чисел N. В каждой из последующих N строк записано одно натуральное число, не превышающее 1000. В последней строке записано контрольное значение.
Вам предлагаются два задания, связанные с этой задачей: задание А и задание Б. Вы можете решать оба задания А и Б или одно из них по своему выбору.
Итоговая оценка выставляется как максимальная из оценок за задания А и Б. Если решение одного из заданий не представлено, то считается, что оценка за это задание составляет 0 баллов.
Задание Б является усложненным вариантом задания А, оно содержит дополнительные требования к программе. Перед программой укажите версию языка программирования.
А. Напишите на любом языке программирования программу для решения поставленной задачи, в которой входные данные будут запоминаться в массиве, после чего будут проверены все возможные пары элементов.
Обязательно укажите, что программа является решением задания А.
Максимальная оценка за выполнение задания А – 2 балла.
Б. Напишите программу для решения поставленной задачи, которая будет эффективна как по времени, так и по памяти (или хотя бы по одной из этих характеристик).
Программа считается эффективной по времени, если время работы программы пропорционально количеству элементов последовательности N, т. е. при увеличении N в k раз время работы программы должно увеличиваться не более чем в k раз. Обязательно укажите, что программа является решением задания Б.
Пример входных данных:
6
77
14
7
9
499
100
7700
Пример выходных данных для приведённого выше примера входных данных:
Вычисленное контрольное значение: 7700
Контроль пройден
Произведение двух чисел делится на 14, если:
- один из сомножителей делится на 14 (второй может быть любым) либо
- ни один из сомножителей не делится на 14. причём один из сомножителей делится на 2, а другой - на 7.
Поэтому программа, вычисляющая кодовое число, может работать так.
Программа читает все входные данные один раз, не запоминая все данные в массиве. Программа для прочитанного фрагмента входной последовательности хранит значения четырех величин:
М2 - самое большое чётное число, не кратное 7;
М7 - самое большое число, кратное 7. но не кратное 2;
М14 - самое большое число, кратное 14;
МАХ - самое большое число среди всех элементов последовательности, отличное от M14 (если число М14 встретилось более одного раза и оно же является максимальным, то МАХ = M14).
После того как все данные прочитаны, искомое кодовое слово вычисляется как максимум из произведений M14*МАХ и М2*М7.
Ниже приведён пример программы на языке Паскаль, которая реализует описанный алгоритм.
Кроме того, приведён пример программы на языке Бейсик, которая правильно решает задачу, но использует алгоритм, немного отличающийся от описанного выше. Возможны и другие правильные алгоритмы. Допускаются решения, записанные на других языках программирования.
Пример правильной и эффективной программы на языке Паскаль:
var М2, М7, М14, R, MAX, dat, res, i, N: longint;
begin
M2 := 0; M7 := 0; M14 := 0; MAX := 0;
readln(N);
for i := 1 to N do begin
readln(dat);
if ((dat mod 2) = 0) and ((dat mod 7) >0) and (dat > M2) then M2 := dat;
if ((dat mod 7) = 0) and ((dat mod 2) > 0) and (dat > M7) then M7 := dat;
if (dat mod 14 = 0) and (dat > M14) then begin
if M14 > MAX then MAX := M14;
M14 := dat;
end
else
if dat > MAX then MAX := dat;
end;
readln(R);
if (M2*M7 < M14 *MAX) then
res := M14*MAX
else
res := M2*M7;
writeln('Вычисленное контрольное значение: ',res);
if R = res then writeln('Контроль пройден')
else writeln('Контроль не пройден');
end.
Пример правильной и эффективной программы на языке Бейсик:
М14 = 0
М2 = 0
М7 = 0
МАХ = 0
INPUT N
FOR I = 1 ТО N
INPUT DAT
IF DAT MOD 2=0 AND DAT > M2 THEN
M2 = DAT
ELSE
IF DAT MOD 7=0 AND DAT > M7 THEN
M7 = DAT
END IF
END IF
IF DAT MOD 14 = 0 AND DAT > M14 THEN
IF M14 > MAX
THEN
MAX = M14
END IF
M14 = DAT
ELSE
IF DAT > MAX THEN
MAX = DAT
END IF
END IF
NEXT I
INPUT R
IF M7 * M2 < M14 * MAX THEN
RES = M14 * MAX
ELSE
RES = M7 * M2
END IF
PRINT "Вычисленное контрольное значение:"; RES
IF RES = R THEN
PRINT "Контроль пройден"
ELSE
PRINT "Контроль не пройден"
END IF
END
Пример решения задачи А на языке Паскаль.
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 14 = 0) then max := a[i] * a[j];
readln(R);
writeln('Вычисленное контрольное значение: ', max);
if R=max then writeln('Контроль пройден')
else writeln('Контроль не пройден');
end.
Приводим эффективное решение Николая Артюхина на C++.
#include <iostream>
using namespace std;
int main()
{
int i, n, mk14=0, mk7=0, mk2=0, max=0, k=0, res, mpr=0, x;
cin >> n;
for(i=0;i<n;i++){
cin >> x;
if ((x%7==0)&&(x%2!=0)&&(x>mk7)) mk7=x;
if ((x%2==0)&&(x%7!=0)&&(x>mk2)) mk2=x;
if ((x%14==0)&&(x>mk14)){
if(mk14>max) max=mk14;
mk14=x;
}
else if (x>max) max=x;
}
cin >> res;
if(mk14*max>mk7*mk2){
cout <<"Вычисленное контрольное значение: " << mk14*max << endl;
mpr=mk14*max;
}
else {
cout <<"Вычисленное контрольное значение: " << mk7*mk2 << endl;
mpr=mk7*mk2;
}
if (res==mpr) cout << "Контроль пройден";
else cout << "Контроль не пройден";
return 0;
}