Категория C4 • задача №2
Условие задачи
Дано:
по каналу связи передается последовательность положительных целых чисел, все числа не превышают 1000, их количество заранее неизвестно. Каждое число передается отдельной входной строке. Признаком конца передаваемой последовательности является число 0. После числа 0 передается контрольное значение - наибольшее число R, удовлетворяющее следующим условиям:
R - произведение двух различных переданных элементов последовательности ("различные" означают, что не рассматриваются квадраты переданных чисел);
R делится на 6 без остатка.
Размер памяти, которую использует программа, не должен зависеть от длины передаваемой последовательности чисел. Перед текстом программы кратко опишите используемый вами алгоритм решения задачи.
Пример входных данных:
60
17
3
7
9
60
0
3600
Пример выходных данных для приведенного выше примера входных данных:
Получено 6 чисел
Полученное контрольное значение: 3600
Вычисленное контрольное значение: 1020
Контроль не пройден
Найти:
напишите эффективную программу, которая получает последовательность чисел и следующие за ней признак конца и контрольное значение, а также проверяет правильность контрольного значения. Программа должна напечатать отчет по следующей форме:
Получено ... чисел
Полученное контрольное значение: ...
Вычисленное контрольное значение: ...
Контроль пройден (или - контроль не пройден)
Решение
I этап: разработка алгоритма поставленной задачи
Попробуем провести математическое обобщение алгоритма предложенной задачи.
В условии сказано, что R - произведение двух различных чисел, то есть:
a · b = R (a <> b).
Поскольку известно, что R является кратным шести, то можно рассмотреть две ситуации:
хотя бы один из множителей должен быть кратен шести (причем, необходимо выбрать наибольшее число кратное шести), а другой множитель - максимально большим числом из входной последовательности, то есть:
a - наибольшее число кратное шести;
b - наибольшее число из входной последовательности не равное a.один из множителей (например, а) должен быть кратен двум (причем, необходимо выбрать наибольшее число кратное двум), а другой множитель (например, b) должен быть кратен трем и не равен a (причем, необходимо выбрать наибольшее число кратное трем), то есть:
а - наибольшее число кратное двум;
b - наибольшее число кратное трем не равное а.
Промежуточный вывод: необходимо в процессе подачи входных чисел запоминать необходимые значения в четыре различных переменных:
наибольшее кратное двум;
наибольшее кратное трем;
наибольшее кратное шести;
наибольшее число не кратное шести.
Максимальное произведение нужно искать среди двух произведений:
[наибольшее кратное двум]·[наибольшее кратное трем];
[наибольшее кратное шести]·[наибольшее число].
Программа пройдет контроль в том случае, если наибольшее произведение (наибольшее из двух представленных выше) совпадет по значению с контрольным значением. Иначе - контроль не будет успешно пройден.
II этап: тестирование алгоритма на конкретных входных данных
Пусть на вход программе последовательно подаются следующие числа: 60, 17, 3, 7, 9, 60, 0, 3600.
Напомню, что число 0 означает конец ввода входной последовательности чисел.
Отталкиваясь от входной последовательности 60, 17, 3, 7, 9, 60 можно сделать следующие выводы:
максимальное число кратное двум: 60;
максимальное число кратное трем (причем не кратное двум): 9;
максимальное число кратное шести: 60;
максимальное число среди всех чисел (не кратных шести): 17.
В итоге, имеем два произведения:
60 · 9 = 540
60 · 17 = 1020
Абсолютно очевидно, что второе произведение больше первого (1020 > 540), то есть вычисленное контрольное значение равно 1020.
Сравним вычисленное контрольное значение с заданным (эталонным) контрольным значением: 1020 <> 3600, следовательно, делаем вывод "Контроль не пройден", так как значения не совпали.
III этап: реализация задачи на языке программирования
Останавливаем свой выбор на современном языке программирования Pascal от корпорации Borland (которая на сегодняшний день уже официально не существует). В качестве интегрированной среды разработки будем использовать Turbo Pascal.
program C4;
{раздел подключения модулей и сторонних расширений}
uses
{crt - Console Run Time: специализированный модуль для обработки звука, текста,
клавиатурных событий. Чрезвычайно важен при серьезном программировании}
crt;
{раздел декларации переменных}
var
{текущее число введенное с клавиатуры}
n : integer;
{максимальное четное число не кратное шести}
k2 : integer;
{максимальное число кратное трем и не кратное шести}
k3 : integer;
{максимальное число кратное шести}
k6 : integer;
{максимальное число не кратное шести}
kmax : integer;
{общее количество введенных чисел для анализа}
k : integer;
{контрольное значение для проверки}
R : integer;
{рассчитанное контрольное значение, которое нужно сравнить с эталонным
контрольным значением, то есть сравнить со значением R}
kz : longInt;
{начало главного блока программы}
begin
{очистка экрана от прошлых выводов}
clrscr;
{до начала анализа входных чисел обнуляем все переменные. Причем можно
переменные к2, к3, к6 и кmax сделать равными нулю, так как на вход программе
подаются положительные целые числа}
k2 := 0;
k3 := 0;
k6 := 0;
kmax := 0;
k := 0;
{запрашиваем первое число с клавиатуры}
readln(n);
{до тех пор, пока пользователь не введет 0 начинается анализ входного числа}
while(n <> 0) do
begin
{увеличиваем счетчик входных чисел на единицу}
k := k + 1;
{если текущее число кратно шести и при этом больше, чем самое максимальное из
кратных шести, то}
if(n mod 6 = 0) and (n > k6) then
{данное число становится максимальным из чисел кратных шести}
k6 := n;
{если текущее число не кратно шести и оно больше, чем самое максимальное из
всех введенных чисел, то}
if(n <> k6) and (n > kmax) then
{запоминаем данное число, как самое максимальное из всех чисел не кратных шести}
kmax := n;
{если текущее число кратно двум и одновременно с этим не кратно шести и
одновременно с этим больше, чем самое максимальное из чисел кратных двум, то}
if(n mod 2 = 0) and (n mod 6 <> 0) and (n > k2) then
{запоминаем данное число, как самое максимальное из всех чисел кратных двум и
не кратных шести
ВАЖНО: для чего ставится проверка, чтобы число не было кратно шести?
Ответ: для хранения максимальных чисел кратных шести используется другая
переменная, а также, чтобы не возникало путаницы в последствии, так как число
кратное шести, еще кратно и трем. Возникает проблема с распознаванием
максимальных чисел кратных двум и кратных трем. По условии, они должны быть
различными}
k2 := n;
{если текущее число кратно трем и одновременно с этим не кратно шести и
одновременно с этим больше, чем самое максимальное из чисел кратных трем, то}
if(n mod 3 = 0) and (n mod 6 <> 0) and (n > k3) then
{запоминаем данное число, как самое максимальное среди чисел кратных трем и
одновременно с этим не кратных шести}
k3 := n;
{считывается следующее число вводом с клавиатуры}
readln(n);
end;
{когда ввод чисел закончен, необходимо считать контрольное эталонное значение}
readln(R);
{выпечатываем общее количество входных чисел}
writeln('Получено: ', k, ' чисел');
{выпечатываем введенное эталонное контрольное значение}
writeln('Получено контрольное значение: ', R);
{чтобы проверить правильность контрольного значения, необходимо выбрать
максимальное из двух произведений, так как по условию контрольное эталонное
значение является максимальным значением двух произведений}
if(k2 * k3 > k6 * kmax) then
kz := k2 * k3
else
kz := k6 * kmax;
{выпечатываем рассчитанное контрольное значение на экран пользователя}
writeln('Вычисленное контрольное значение: ', kz);
{если эталонное контрольное значение совпало с рассчитанным контрольным значением, то}
if(kz = R) then
{печатаем диалог об успешном прохождении контроля}
writeln('Контроль пройден')
else
{печатаем диалог об неуспешном прохождении контроля}
writeln('Контроль не пройден');
{задержка программы. Программа будет закрыта после нажатия произвольной
клавиши на клавиатуре}
readkey;
{финализирующий оператор программы}
end.
Резюме
внимательное знакомство с постановкой задачи;
разработка математической модели;
проверка математической модели на конкретных данных;
реализация задачи на языке программирования Pascal.
Категория C4 • задача №2
Остальные решения из билета №2 для подготовки к ЕГЭ по информатике 2013
| Условие задачи (наведите курсор мыши на ссылку) |
Аудиовизуальное решение |
Мультимедийная видеопрезентация |
Решение в формате слайд-шоу |
Текстовое решение |
|---|
Комментарии