По каналу связи передаются данные в виде последовательности положительных целых чисел. Количество чисел заранее неизвестно, но не менее двух, признаком конца данных считается число 0. После данных передаётся контрольное значение. Оно равно такому максимально возможному произведению двух чисел из переданного набора, которое делится на 7, но не делится на 49. Если такое произведение получить нельзя, контрольное значение считается равным 1.
Напишите эффективную, в том числе по памяти, программу, которая будет моделировать процесс приёма данных. Программа должна ввести все числа и контрольное значение и напечатать краткий отчёт, включающий количество принятых чисел, принятое контрольное значение, вычисленное контрольное значение и вывод о совпадении значений. Перед текстом программы кратко опишите алгоритм решения задачи и укажите используемый язык программирования и его версию.
Вам предлагаются два задания, связанные с этой задачей: задание А и задание Б. Вы можете решать оба задания А и Б или одно из них по своему выбору.
Итоговая оценка выставляется как максимальная из оценок за задания А и Б. Если решение одного из заданий не представлено, то считается, что оценка за это задание составляет 0 баллов.
Задание Б является усложненным вариантом задания А, оно содержит дополнительные требования к программе. Перед программой укажите версию языка программирования.
А. Напишите на любом языке программирования программу для решения поставленной задачи, в которой входные данные будут запоминаться в массиве, после чего будут проверены все возможные пары элементов.
Обязательно укажите, что программа является решением задания А.
Максимальная оценка за выполнение задания А – 2 балла.
Б. Напишите программу для решения поставленной задачи, которая будет эффективна как по времени, так и по памяти (или хотя бы по одной из этих характеристик).
Программа считается эффективной по времени, если время работы программы пропорционально количеству элементов последовательности N, т. е. при увеличении N в k раз время работы программы должно увеличиваться не более чем в k раз. Обязательно укажите, что программа является решением задания Б.
Описание входных данных.
В каждой строке исходных данных содержится одно целое число. Сначала идут строки с основными данными — положительными числами, затем число 0 (признак окончания данных), в последней строке — контрольное значение.
Программа должна вывести отчёт по форме, приведённой ниже в примере.
Пример входных данных:
6
7
8
9
0
64
Пример выходных данных для приведённого выше примера входных данных:
Введено чисел: 4
Контрольное значение: 64
Вычисленное значение: 63
Значения не совпали
Произведение двух чисел будет кратно 7 и не кратно 49 в том и только в том случае, когда один из сомножителей делится на 7 и при этом не делится на 49, а второй — не делится на 7. Произведение будет максимальным, если оба сомножителя будут максимально возможными в своих группах. Искомое произведение не существует (контрольное значение считается равным 1), если в одной из указанных групп не окажется ни одного числа.
Программа читает входные данные, не запоминая числа в массиве, и находит два максимальных значения: максимум из чисел, кратных 7 и при этом не кратных 49, и максимум из чисел, не кратных 7. Затем программа вычисляет контрольное значение, равное произведению этих двух максимумов, и сравнивает его с введённым контрольным значением.
Пример правильной и эффективной программы на языке Паскаль.
program с4;
var
k: integer; {введенное число}
n: integer; {количество чисел} pin: integer;{введенное контрольное значение}
m: integer; {максимум среди чисел, не кратных 7}
m7: integer; {максимум среди чисел, кратных 7 и не кратных 49}
р: integer; {вычисленное контрольное значение}
begin
m:=0; m7:=0;
n:=0;
while true do begin
readln(k);
if k=0 then break;
n:=n+1;
if (k mod 7 <> 0) and (k>m) then m:=k;
if (k mod 7 = 0) and (k mod 49 <> 0) and (k>m7)
then m7:= k;
end;
readln(pin);
p:=m*m7;
if p=0 then p:= 1;
writeln('Введено чисел: ',n);
writeln('Контрольное значение ',pin);
writeln('Вычисленное значение ' ,P);
writeln( 'Значения ');
if p<>pin then write ('не ');
writeln('совпали');
end.
Пример решения задачи А на языке Паскаль.
vara: array[1..10000] of integer; {исходные данные}
N: integer; {количество элементов последовательности}
R: integer; {принимаемое контрольное значение}
max: integer; {вычисляемое контрольное значение}
count: integer; {количество введёных чисел}
i, j: integer;
begin
count := 0;
max := 1;
while true do begin
readln(a[count+1]);
if a[count+1] = 0 then break;
count := count + 1;
end;
for i := 1 to count − 1 do
for j := i + 1 to count do
if (a[i]*a[j] mod 7 = 0) and (a[i]*a[j] mod 49 <> 0) and (a[i]*a[j] > max) then max := a[i]*a[j];
readln(R);
writeln('Введено чисел: ', count);
writeln('Принятое контрольное значение: ', R);
writeln('Вычисленное контрольное значение: ', max);
if R=max then writeln('Значения совпали')
else writeln('Значения не совпали');
end.
Приводим эффективное решение Николая Артюхина на C++.
#include <iostream>
using namespace std;
int main()
{
int i, mk7=0, max=0, mpr=0, x, res, n=0;
do{
cin >> x;
if ((x%7==0)&&(x%49!=0)&&(x>mk7)) mk7=x;
if ((x>max)&&(x%7!=0)) max=x;
n++;
} while(x!=0);
cin >> res;
mpr=mk7*max;
if(mpr==0) mpr=1;
cout <<"Введено чисел: " << n-1 << endl;
cout << "Контрольное значение " << res << endl;
cout << "Вычисленное значение " << mpr << endl;
cout << "Значения ";
if (res!=mpr) cout << "не ";
cout << "совпали" ;
return 0;
}