Категория C4 • задача №2

 
 
 

Условие задачи

Дано:
по каналу связи передается последовательность положительных целых чисел, все числа не превышают 1000, их количество заранее неизвестно. Каждое число передается отдельной входной строке. Признаком конца передаваемой последовательности является число 0. После числа 0 передается контрольное значение - наибольшее число R, удовлетворяющее следующим условиям:

  1. R - произведение двух различных переданных элементов последовательности ("различные" означают, что не рассматриваются квадраты переданных чисел);

  2. R делится на 6 без остатка.

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

Пример входных данных:
60
17
3
7
9
60
0
3600

Пример выходных данных для приведенного выше примера входных данных:
Получено 6 чисел
Полученное контрольное значение: 3600
Вычисленное контрольное значение: 1020
Контроль не пройден

 

Найти:
напишите эффективную программу, которая получает последовательность чисел и следующие за ней признак конца и контрольное значение, а также проверяет правильность контрольного значения. Программа должна напечатать отчет по следующей форме:

Получено ... чисел
Полученное контрольное значение: ...
Вычисленное контрольное значение: ...
Контроль пройден (или - контроль не пройден)

 

Решение

I этап: разработка алгоритма поставленной задачи

Попробуем провести математическое обобщение алгоритма предложенной задачи.
В условии сказано, что R - произведение двух различных чисел, то есть:
a · b = R (a <> b).

Поскольку известно, что R является кратным шести, то можно рассмотреть две ситуации:

  1. хотя бы один из множителей должен быть кратен шести (причем, необходимо выбрать наибольшее число кратное шести), а другой множитель - максимально большим числом из входной последовательности, то есть:
    a - наибольшее число кратное шести;
    b - наибольшее число из входной последовательности не равное a.

  2. один из множителей (например, а) должен быть кратен двум (причем, необходимо выбрать наибольшее число кратное двум), а другой множитель (например, b) должен быть кратен трем и не равен a (причем, необходимо выбрать наибольшее число кратное трем), то есть:
    а - наибольшее число кратное двум;
    b - наибольшее число кратное трем не равное а.

Промежуточный вывод: необходимо в процессе подачи входных чисел запоминать необходимые значения в четыре различных переменных:

  • наибольшее кратное двум;

  • наибольшее кратное трем;

  • наибольшее кратное шести;

  • наибольшее число не кратное шести.

 

Максимальное произведение нужно искать среди двух произведений:

  1. [наибольшее кратное двум]·[наибольшее кратное трем];

  2. [наибольшее кратное шести]·[наибольшее число].

Программа пройдет контроль в том случае, если наибольшее произведение (наибольшее из двух представленных выше) совпадет по значению с контрольным значением. Иначе - контроль не будет успешно пройден.

 

II этап: тестирование алгоритма на конкретных входных данных

Пусть на вход программе последовательно подаются следующие числа: 60, 17, 3, 7, 9, 60, 0, 3600.
Напомню, что число 0 означает конец ввода входной последовательности чисел.

Отталкиваясь от входной последовательности 60, 17, 3, 7, 9, 60 можно сделать следующие выводы:

  • максимальное число кратное двум: 60;

  • максимальное число кратное трем (причем не кратное двум): 9;

  • максимальное число кратное шести: 60;

  • максимальное число среди всех чисел (не кратных шести): 17.

В итоге, имеем два произведения:

  1. 60 · 9 = 540

  2. 60 · 17 = 1020

Абсолютно очевидно, что второе произведение больше первого (1020 > 540), то есть вычисленное контрольное значение равно 1020.
Сравним вычисленное контрольное значение с заданным (эталонным) контрольным значением: 1020 <> 3600, следовательно, делаем вывод "Контроль не пройден", так как значения не совпали.

 

III этап: реализация задачи на языке программирования

Останавливаем свой выбор на современном языке программирования Pascal от корпорации Borland (которая на сегодняшний день уже официально не существует). В качестве интегрированной среды разработки будем использовать Turbo Pascal.

  1. {заголовок программы}
  2. program C4;
  3. {раздел подключения модулей и сторонних расширений}
  4. uses
  5. {crt - Console Run Time: специализированный модуль для обработки звука, текста,
  6.  клавиатурных событий. Чрезвычайно важен при серьезном программировании}
  7.     crt;
  8. {раздел декларации переменных}
  9. var
  10. {текущее число введенное с клавиатуры}
  11.     n    : integer;
  12. {максимальное четное число не кратное шести}
  13.     k2   : integer;
  14. {максимальное число кратное трем и не кратное шести}
  15.     k3   : integer;
  16. {максимальное число кратное шести}
  17.     k6   : integer;
  18. {максимальное число не кратное шести}
  19.     kmax : integer;
  20. {общее количество введенных чисел для анализа}
  21.     k    : integer;
  22. {контрольное значение для проверки}
  23.     R    : integer;
  24. {рассчитанное контрольное значение, которое нужно сравнить с эталонным
  25.  контрольным значением, то есть сравнить со значением R}
  26.     kz   : longInt;
  27. {начало главного блока программы}
  28. begin
  29. {очистка экрана от прошлых выводов}
  30.     clrscr;
  31. {до начала анализа входных чисел обнуляем все переменные. Причем можно
  32.  переменные к2, к3, к6 и кmax сделать равными нулю, так как на вход программе
  33.  подаются положительные целые числа}
  34.     k2 := 0;
  35.     k3 := 0;
  36.     k6 := 0;
  37.     kmax := 0;
  38.     k := 0;
  39. {запрашиваем первое число с клавиатуры}
  40.     readln(n);
  41. {до тех пор, пока пользователь не введет 0 начинается анализ входного числа}
  42.     while(n <> 0) do
  43.     begin
  44. {увеличиваем счетчик входных чисел на единицу}
  45.         k := k + 1;
  46. {если текущее число кратно шести и при этом больше, чем самое максимальное из
  47.  кратных шести, то}
  48.         if(n mod 6 = 0) and (n > k6) then
  49. {данное число становится максимальным из чисел кратных шести}
  50.             k6 := n;
  51. {если текущее число не кратно шести и оно больше, чем самое максимальное из
  52.  всех введенных чисел, то}
  53.         if(n <> k6) and (n > kmax) then
  54. {запоминаем данное число, как самое максимальное из всех чисел не кратных шести}
  55.             kmax := n;
  56. {если текущее число кратно двум и одновременно с этим не кратно шести и
  57.  одновременно с этим больше, чем самое максимальное из чисел кратных двум, то}
  58.         if(n mod 2 = 0) and (n mod 6 <> 0) and (n > k2) then
  59. {запоминаем данное число, как самое максимальное из всех чисел кратных двум и
  60.  не кратных шести
  61.  ВАЖНО: для чего ставится проверка, чтобы число не было кратно шести?
  62.  Ответ: для хранения максимальных чисел кратных шести используется другая
  63.  переменная, а также, чтобы не возникало путаницы в последствии, так как число
  64.  кратное шести, еще кратно и трем. Возникает проблема с распознаванием
  65.  максимальных чисел кратных двум и кратных трем. По условии, они должны быть
  66.  различными}
  67.             k2 := n;
  68. {если текущее число кратно трем и одновременно с этим не кратно шести и
  69.  одновременно с этим больше, чем самое максимальное из чисел кратных трем, то}
  70.         if(n mod 3 = 0) and (n mod 6 <> 0) and (n > k3) then
  71. {запоминаем данное число, как самое максимальное среди чисел кратных трем и
  72.  одновременно с этим не кратных шести}
  73.             k3 := n;
  74. {считывается следующее число вводом с клавиатуры}
  75.         readln(n);
  76.     end;
  77. {когда ввод чисел закончен, необходимо считать контрольное эталонное значение}
  78.     readln(R);
  79. {выпечатываем общее количество входных чисел}
  80.     writeln('Получено: ', k, ' чисел');
  81. {выпечатываем введенное эталонное контрольное значение}
  82.     writeln('Получено контрольное значение: ', R);
  83. {чтобы проверить правильность контрольного значения, необходимо выбрать
  84.  максимальное из двух произведений, так как по условию контрольное эталонное
  85.  значение является максимальным значением двух произведений}
  86.     if(k2 * k3 > k6 * kmax) then
  87.         kz := k2 * k3
  88.     else
  89.         kz := k6 * kmax;
  90. {выпечатываем рассчитанное контрольное значение на экран пользователя}
  91.     writeln('Вычисленное контрольное значение: ', kz);
  92. {если эталонное контрольное значение совпало с рассчитанным контрольным значением, то}
  93.     if(kz = R) then
  94. {печатаем диалог об успешном прохождении контроля}
  95.         writeln('Контроль пройден')
  96.     else
  97. {печатаем диалог об неуспешном прохождении контроля}
  98.         writeln('Контроль не пройден');
  99. {задержка программы. Программа будет закрыта после нажатия произвольной
  100.  клавиши на клавиатуре}
  101.     readkey;
  102. {финализирующий оператор программы}
  103. end.

 

Резюме

  1. внимательное знакомство с постановкой задачи;

  2. разработка математической модели;

  3. проверка математической модели на конкретных данных;

  4. реализация задачи на языке программирования Pascal.

 
 
Рейтинг:
 
Проголосовало: 6
Количество просмотров: 2954
 
 
 

Категория C4 • задача №2

 

Комментарии

Для комментирования или зарегистрируйтесь
 

Остальные решения из билета №2 для подготовки к ЕГЭ по информатике 2013

 
Условие задачи
(наведите курсор мыши на ссылку)
Аудиовизуальное
решение
Мультимедийная
видеопрезентация
Решение в формате
слайд-шоу
Текстовое
решение
 
© 2011-2019 ООО "СтадиМен". Все права сохранены.
Перепечатка и использование материалов с данного сайта, разрешена только по согласию с владельцем.
Владелец оставляет за собой право воспользоваться 146 статьей УК РФ при нарушении авторских и смежных прав.
 
 
 
 
Авторизация на сайте
 
 
 
Обнаружили
ошибку на сайте?