Форум » Обработка числовых последовательностей » Реализация алгоритма в задании 27 » Ответить
Реализация алгоритма в задании 27
Иванов: Здравствуйте. Прошу ответить. Я буду иметь в виду решение задания 27 на 4 балла. У меня всегда возникал вопрос: почему в решении задания 27 часто используют объединенные условия и особо не используют ветвление? Например, задание из варианта досрочного ЕГЭ: По каналу связи передаётся последовательность положительных целых чисел, все числа не превышают 1000. Количество чисел известно, но может быть очень велико. Затем передаётся контрольное значение последовательности – наименьшее число R, удовлетворяющее следующим условиям: 1) R является произведением двух различных переданных элементов последовательности («различные» означает, что не рассматриваются квадраты переданных чисел, произведения различных элементов последовательности, равных по величине, допускаются); 2) R кратно 6. Если такого числа R нет, то контрольное значение полагается равным 0. В результате помех при передаче как сами числа, так и контрольное значение могут быть искажены. Напишите эффективную, в том числе по используемой памяти, программу (укажите используемую версию языка программирования, например, Borland Pascal 7.0), которая будет проверять правильность контрольного значения. Программа должна напечатать отчёт по следующей форме: Вычисленное контрольное значение: … Контроль пройден (или – Контроль не пройден) Перед текстом программы кратко опишите используемый Вами алгоритм решения. На вход программе в первой строке подаётся количество чисел N; в программе можно считать, что 2 ≤ N ≤ 10 000. В каждой из последующих N строк записано одно натуральное число, не превышающее 1000. В последней строке записано контрольное значение – натуральное число, не превышающее 1 000 000. Пример входных данных: 6 30 6 5 3 4 300 12 Пример выходных данных для приведённого выше примера входных данных: Вычисленное контрольное значение: 12 Контроль пройден Вот решение от "Решу ЕГЭ": Пояснение. Произведение двух чисел делится на 6, если: − один из сомножителей делится на 6 (второй может быть любым), либо − ни один из сомножителей не делится на 6, причём один из сомножителей делится на 2, а другой — на 3. Поэтому программа, вычисляющая контрольное число, может работать так. Программа читает все входные данные один раз, не запоминая все данные в массиве. Программа для прочитанного фрагмента входной последовательности хранит значения четырех величин: М2 — самое маленькое чётное число, не кратное 3; М3 — самое маленькое число, кратное 3, но не кратное 2; М6 — самое маленькое число, кратное 6; MIN — самое маленькое число среди всех элементов последовательности, отличное от M6 (если число М6 встретилось более одного раза и оно же является минимальным, то MIN = M6). После того как все данные прочитаны, искомое контрольное слово вычисляется как минимум из произведений M6*MIN и М2*М3. Ниже приведён пример программы на языке Паскаль, которая реализует описанный алгоритм. Пример правильной и эффективной программы на языке Паскаль: Program C4; var М2, М3, М6, MIN, dat: int; R, res, i, N: longint; begin M2 := 1001; M3 := 1001; M6 := 1001; MIN := 1001; readln(N); for i := 1 to N do begin readln(dat); if (dat mod 2 = 0) and (dat mod 3 > 0) and (dat < M2) then M2 := dat; if (dat mod 3 = 0) and (dat mod 2 > 0) and (dat < M3) then M3 := dat; if (dat mod 6 = 0) and (dat < M6) then begin if M6 < MIN then MIN := M6; M6:= dat; end else if dat < MIN then MIN:= dat; end; if (M2*M3 > M6*MIN) then res := M6*MIN else res := M2*M3; if (M6 >= 1001) and ((M2 >= 1001) or (M3 >= 1001)) then res := 0; writeln('Вычисленное контрольное значение: ',res); readln(R); if R = res then writeln('Контроль пройден') else writeln('Контроль не пройден'); end. Вот мое решение: 27) Б) (эффективная по использованию памяти и быстрая программа). Программа находит минимальное число без дополнительных свойств и минимальные числа, обладающие одной из следующих вариантов кратности: 2, 3, 6. Минимальное число R может получится либо вследствие умножения числа кратного 6 на минимальное число среди всех данных, либо вследствие умножения числа кратного 2 на число кратное 3. Среди двух этих произведений программа выбирает меньшее. Затем проверяется соответствие предполагаемого ответа R (данного ответа) с получившимся в результате расчетов результатом Rcurrent. Множители являются "различными". var N, x, i: integer; R, Rcurrent: longint; q1,q2,q3, m: integer; begin q1:= 1001; q2:= 1001; q3:= 1001; m:= 1001; Rcurrent:= 0; readln(N); for i:= 1 to N do begin readln(x); if (x mod 6 = 0) and (x<q3) then begin if (q3<m) then m:= q3; q3:= x; end; end else if (x<m) then m:= x; if (x mod 2 = 0) and (x<q1) then q1:= x; else if (x mod 3 = 0) and (x<q2) then q2:= x; end; readln(R); if (q1<1001) and (q2<1001) or (q3<1001) then if q3*m < q1*q2 then Rcurrent:= q3*m else Rcurrent:= q1*q2; writeln('Вычисленное контрольное значение: ',Rcurrent); if Rcurrent = R then writeln('Контроль пройден') else writeln('Контроль не пройден'); end. Если мое решение обрабатывает число не кратное 3 и не кратное 2 (а значит и не кратное 6), то проверяется только 7 условий ((x mod 6 = 0) and (x<q3), (x<m), (x mod 2 = 0) and (x<q1), (x mod 3 = 0) and (x<q2)). В решение от Решу ЕГЭ такому же числу придется пройти через проверку 9 условий. Или я ошибаюсь в подсчете и основные операторы не выполняются, уже если одно из условий, объединенных and'ами, ложно? Как работает проверка условий, объединенных and'ами?
Ответов - 2
Иванов: Такие входные данные не противоречат моему решению. 4 16 78 55 6 330 16*6 - минимальное число, удовлетворяющее условию. 96 != 330, значит должно выводиться: "Контроль не пройден". Все так и работает при запуске программы.
Иванов: var N, x, i: integer; R, Rcurrent: longint; q1,q2,q3, m: integer; begin q1:= 1001; q2:= 1001; q3:= 1001; m:= 1001; Rcurrent:= 0; readln(N); for i:= 1 to N do begin ----readln(x); ----if (x mod 6 = 0) and (x<q3) then begin ------------if (q3<m) then m:= q3; ------------q3:= x; ----end --------else ------------if (x<m) then m:= x; ------------if (x mod 2 = 0) and (x<q1) then q1:= x -------------- else ------------------ if (x mod 3 = 0) and (x<q2) then q2:= x; end; readln(R); if (q1<1001) and (q2<1001) or (q3<1001) then ----if q3*m < q1*q2 then Rcurrent:= q3*m --------else Rcurrent:= q1*q2; writeln('Вычисленное контрольное значение: ',Rcurrent); if Rcurrent = R then writeln('Контроль пройден') ----else writeln('Контроль не пройден'); end.
полная версия страницы