№№ заданий Пояснения Ответы Ключ Добавить инструкцию Критерии
Источник Раздел кодификатора ФИПИ Справка
PDF-версия PDF-версия (вертикальная) PDF-версия (крупный шрифт) PDF-версия (с большим полем) Версия для копирования в MS Word
Задания
Задание 27 № 9708

Последовательность натуральных чисел характеризуется числом Х — наибольшим числом, кратным 14 и являющимся произведением двух элементов последовательности с различными номерами.

 

 

Вам предлагаются два задания, связанные с этой задачей: задание А и задание Б. Вы можете решать оба задания А и Б или одно из них по своему выбору.

Итоговая оценка выставляется как максимальная из оценок за задания А и Б. Если решение одного из заданий не представлено, то считается, что оценка за это задание составляет 0 баллов.

Задание Б является усложненным вариантом задания А, оно содержит дополнительные требования к программе.

 

А. Напишите на любом языке программирования программу для решения поставленной задачи, в которой входные данные будут запоминаться в массиве, после чего будут проверены все возможные пары элементов.

Перед программой укажите версию языка программирования. Обязательно укажите, что программа является решением задания А.

Максимальная оценка за выполнение задания А – 2 балла.

Б. Напишите программу для решения поставленной задачи, которая будет эффективна как по времени, так и по памяти (или хотя бы по одной из этих характеристик).

Программа считается эффективной по времени, если время работы программы пропорционально количеству элементов последовательности N, т.е. при увеличении N в k раз время работы программы должно увеличиваться не более чем в k раз.

Обязательно укажите, что программа является решением задания Б.

 

Перед текстом программы кратко опишите используемый Вами алгоритм решения.

На вход программе в первой строке подаётся количество чисел N. В каждой из последующих N строк записано одно натуральное число, не превышающее 1000.

Пример входных данных:

5

40

1000

7

28

55

Пример выходных данных для приведённого выше примера входных данных:

28000

Решение.

Произведение двух чисел делится на 14, если:

— один из сомножителей делится на 14 (второй может быть любым) либо

— ни один из сомножителей не делится на 14, но один из сомножителей делится на 7, а другой – на 2.

Поэтому программа, вычисляющая число X, может работать так.

Программа читает все входные данные один раз, не запоминая все данные в массиве. Программа для прочитанного фрагмента входной последовательности хранит значения четырёх величин:

М7 – самое большое число, кратное 7, но не кратное 2;

M2 – самое большое число, кратное 2, но не кратное 7;

M14 – самое большое число, кратное 14;

МAX – самое большое число среди всех элементов последовательности, отличное от М14 (если число М14 встретилось более одного раза и оно же является максимальным, то MAX = M14).

После того как все данные прочитаны, искомое число X вычисляется как максимум из произведений М14*MAX и М7*М2.

Ниже приведён пример программы на языке Паскаль, которая реализует описанный алгоритм.

Кроме того, приведён пример программы на языке Бейсик, которая правильно решает задачу, но использует алгоритм, немного отличающийся от описанного выше. Возможны и другие правильные алгоритмы.

Допускаются решения, записанные на других языках программирования.

 

Пример правильной и эффективной программы на языке Паскаль

var M7,M2,M14,MAX,dat,res,i,N: longint;

begin

  M7 := 0;

  M2 := 0;

  M14 := 0;

  MAX := 0;

  readln(N);

  for i := 1 to N do

  begin

    readln(dat);

    if ((dat mod 7) = 0) and ((dat mod 2) > 0) and (dat > M7) then

      M7 := dat;

    if ((dat mod 2) = 0) and ((dat mod 7) > 0) and (dat > M2) then

      M2 := 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;

  if (M7*M2 < M14*MAX) then

    res := M14*MAX

  else

    res := M7*M2;

  writeln(res);

  end.

 

Пример правильной и эффективной программы на языке Бейсик:

M14 = 0

M7 = 0

M2 = 0

MAX = 0

INPUT N

FOR I = 1 TO N

  INPUT DAT

  IF DAT MOD 7 = 0 AND DAT > M7 THEN

    M7 = DAT

    ELSE

      IF DAT MOD 2 = 0 AND DAT > M2 THEN

      M2 = 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

IF M2 * M7 < M14 * MAX THEN

  RES = M14 * MAX

ELSE

  RES = M2 * M7

END IF

PRINT RES

END

 

Пример решения задачи А на языке Паскаль.

var

a: array[1..10000] of integer; {исходные данные}

N: 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];

writeln(max);

end.

· ·