Тип Д27 C4 № 9662 

Программирование. Делимость произведения пары
i
Последовательность натуральных чисел характеризуется числом Y – наибольшим числом, кратным 26 и являющимся произведением двух элементов последовательности с различными номерами.
Напишите эффективную, в том числе по используемой памяти, программу (укажите используемую версию языка программирования, например, Borland Pascal 7.0), находящую число Y для последовательности натуральных чисел, значение каждого элемента которой не превосходит 1000. Программа должна напечатать найденное число, если оно существует для заданной последовательности, или ноль в противном случае.
Перед текстом программы кратко опишите используемый Вами алгоритм решения.
На вход программе в первой строке подаётся количество чисел N. В каждой из последующих N строк записано одно натуральное число, не превышающее 1000.
Пример входных данных:
5
40
100
130
28
51
Пример выходных данных для приведённого выше примера входных данных: 13000
Спрятать решениеРешение. Произведение двух чисел делится на 26, если:
— один из сомножителей делится на 26 (второй может быть любым) либо
— ни один из сомножителей не делится на 26, но один из сомножителей делится на 13, а другой – на 2.
Поэтому программа, вычисляющая число Y, может работать так.
Программа читает все входные данные один раз, не запоминая все данные в массиве. Программа для прочитанного фрагмента входной последовательности хранит значения четырёх величин:
М13 — самое большое число, кратное 13, но не кратное 2;
M2 — самое большое число, кратное 2, но не кратное 13;
M26 — самое большое число, кратное 26;
МAX — самое большое число среди всех элементов последовательности, отличное от М26 (если число М26 встретилось более одного раза и оно же является максимальным, то MAX = M26).
После того как все данные прочитаны, искомое число Y вычисляется как максимум из произведений М26*MAX и М13*М2.
Ниже приведён пример программы на языке Паскаль, которая реализует описанный алгоритм. Кроме того, приведён пример программы на языке Бейсик, которая правильно решает задачу, но использует алгоритм, немного отличающийся от описанного выше. Возможны и другие правильные алгоритмы.
Допускаются решения, записанные на других языках программирования.
Пример правильной и эффективной программы на языке Паскаль
var M13,M2,M26,MAX,dat,res,i,N: longint;
begin
M13 := 0;
M2 := 0;
M26 := 0;
MAX := 0;
readln(N);
for i := 1 to N do
begin
readln(dat);
if ((dat mod 13) = 0) and ((dat mod 2) > 0) and (dat > M13) then
M13 := dat;
if ((dat mod 2) = 0) and ((dat mod 13) > 0) and (dat > M2) then
M2 := dat;
if (dat mod 26 = 0) and (dat > M26) then
begin
if M26 > MAX then MAX := M26;
M26 := dat
end
else
if dat > MAX then
MAX := dat;
end;
if (M13*M2 < M26*MAX) then
res := M26*MAX
else
res := M13*M2;
writeln(res);
end.
Пример правильной и эффективной программы на языке Бейсик:
M26 = 0
M13 = 0
M2 = 0
MAX = 0
INPUT N
FOR I = 1 TO N
INPUT DAT
IF DAT MOD 13 = 0 AND DAT > M13 THEN
M13 = DAT
ELSE
IF DAT MOD 2 = 0 AND DAT > M2 THEN
M2 = DAT
END IF
END IF
IF DAT MOD 26 = 0 AND DAT > M26 THEN
IF M26 > MAX THEN
MAX = M26
END IF
M26 = DAT
ELSE
IF DAT > MAX THEN
MAX = DAT
END IF
END IF
NEXT I
IF M2 * M13 < M26 * MAX THEN
RES = M26 * MAX
ELSE
RES = M2 * M13
END IF
PRINT RES
END
Спрятать критерииКритерии проверки:| Критерии оценивания выполнения задания | Баллы |
|---|
| 4 балла ставится за эффективную и правильно работающую программу, которая, возможно, содержит до трёх синтаксических ошибок. 3 балла ставится в случае, когда задача фактически решена, но программа содержит четыре-пять синтаксических ошибок, или если допущена одна содержательная ошибка, или если все входные данные сохраняются в массиве или иной структуре данных (программа неэффективна по памяти, но эффективна по времени работы). 2 балла ставится, если программа неэффективна по времени работы (перебираются все возможные пары элементов) или в программе имеются две содержательные ошибки либо шесть-семь синтаксических ошибок. 1 балл ставится, если программа написана неверно, но из описания алгоритма и общей структуры программы видно, что экзаменуемый в целом правильно представляет путь решения задачи. Далее уточняются перечисленные выше критерии. | |
| Не выполнены критерии, позволяющие поставить 1, 2, 3 или 4 балла. | 0 |
| Не выполнены условия, позволяющие поставить 2, 3 или 4 балла. При этом выполнено одно из двух условий. 1. Из описания алгоритма и общей структуры программы видно, что экзаменуемый в целом правильно представляет путь решения задачи. 2. Программа правильно работает в одном из важных частных случаев, например, в случае, когда искомое произведение – это произведение наибольшего числа, которое делится на 2, и наибольшего числа, которое делится на 13. Допускается любое количество синтаксических ошибок. | 1 |
| Не выполнены условия, позволяющие поставить 3 или 4 балла. Программа работает в целом верно, эффективно или нет, но в реализации алгоритма есть до трёх содержательных ошибок, допустимые виды ошибок перечислены в критериях на 3 балла. Количество синтаксических «описок» не должно быть более семи. Программа может быть неэффективна по времени. Например, все числа запоминаются в массиве и перебираются все возможные пары элементов последовательности, например, так:
max := 0; for i := 1 to n - 1 do for j := i + 1 to n do if ((a[i]*a[j]) mod 26 = 0) and ((a[i]*a[j]) > max) then max := a[i]*a[j]; | 2 |
| Не выполнены условия, позволяющие поставить 4 балла. Программа в целом работает правильно для любых входных данных произвольного размера. Время работы пропорционально количеству введённых чисел. Количество синтаксических ошибок («описок») указанных выше видов – не более пяти. Используемая память, возможно, зависит от количества прочитанных чисел (например, входные данные запоминаются в массиве или другой структуре данных (контейнер priority_queue, vector, set или map в С++)). Допускается ошибка при вводе данных, неверный или неполный вывод результатов или неверная работа программы в «экзотических» ситуациях. Например, при использовании 16-битного целого (integer в BPascal или Qbasic) умножаются два числа этого типа (результат по условию может не помещаться в 16 бит). Кроме того, допускается наличие одной ошибки, принадлежащей к одному из следующих видов. 1. Ошибка при инициализации максимумов. 2. Неверно обрабатывается ситуация, когда один или несколько максимумов не определены. 3. Неверно обрабатывается ситуация, когда максимальное произведение получается умножением одинаковых чисел ( но разных элементов входной последовательности). 4. При вычислении максимумов учитываются произведения вида a[i]*a[i]. 5. Допущен выход за границу массива. 6. Используется знак «<» вместо «<=»,«or» вместо «and» и т. п. | 3 |
| Программа правильно работает для любых входных данных произвольного размера. Используемая память не зависит от количества прочитанных чисел, а время работы пропорционально этому количеству. Допускается наличие в тексте программы до трёх синтаксических ошибок одного из следующих видов: — пропущен или неверно указан знак пунктуации; — неверно написано или пропущено зарезервированное слово языка программирования; — не описана или неверно описана переменная; — применяется операция, недопустимая для соответствующего типа данных (если одна и та же ошибка встречается несколько раз, то это считается за одну ошибку). | 4 |
| Максимальный балл | 4 |