Программирование сложных алгоритмов

Программирование сложных алгоритмов Часть 1, 2, 3

Подготовка к ЕГЭ

Разработчик: Черевичкина И.Н.

Май, 2020

Цель: научиться разрабатывать алгоритмы.

Задачи: проанализировать текст задачи, создать математическую модель; написать программу; составить тест для проверки и протестировать программу.

ЗАДАЧА:

Дан набор из N+1 целых положительных чисел. Первое число определяет количество, следующих за ним N чисел, рассматриваемой последовательности.

Для каждого числа вычисляется сумма двух последних цифр в его десятичной записи (для однозначных чисел предпоследняя цифра считается равной нулю). Необходимо определить, какая сумма при этом получается чаще всего. Если таких сумм несколько, необходимо вывести наибольшую из них.

Например:

N

ДАНО: 5 , 452, 26, 7, 12, 9

N чисел

Вопрос №1: как определить сумму двух последних цифр?

Ch=452, Cif_10:=(Ch MOD 100 - Ch MOD 10) DIV 10; Cif_1:=Ch MOD 10;

Вопрос №2: как определить количество разных сумм?

Можно создать массив Summ из 19 элементов (от 0 до 18), так как сумма больше 18 быть не может, а 0 быть может (100, 1000 и т.д.). Считаем, что чисел со значение нуль в последовательности нет по условию.

Вопрос №3: как определить какая сумма встречалась наиболее часто (наибольшее количество раз) и при этом является наибольшей?

Нужно «пройти по полученному массиву» и каждый раз в переменную МАХ_KOL и в переменную Max_S сохранять найденные значения.

Итак, по трем обозначенным вопросами этапам мы и построим разработку нашего алгоритма.

Этап первый:

Нахождение суммы двух последних цифр каждого числа в последовательности по порядку.

Этап второй:

Создание массива счетчиков найденных сумм двух последних цифр каждого числа в последовательности по порядку.

Этап третий:

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

Разработка сложного алгоритма

Часть 1

Нахождение суммы двух последних цифр каждого числа в последовательности по порядку.

Например:

N

Начнем писать программу методом пошагового уточнения.

На первом этапе проверим как считается сумма?

ДАНО: 5 , 452, 26, 7, 12, 9

N чисел

Пример №1

Ch=452,

Cif_10:=(Ch MOD 100 - Ch MOD 10) DIV 10;

Cif_1:=Ch MOD 10;

Например:

N

ДАНО: 5 , 452, 26, 7, 12, 9

N чисел

Рассмотрим алгоритм примера программы №1:

1) Заводим переменные: MaxS, Ch, Cif_10, Cif_1, k, N

2) Нужно прочитать число N (или сгенерировать его случайным образом).

3) Организовать цикл от 1 до N.

4) В цикле: прочитываем одно число и анализируем его на предмет вопроса задачи: находим сумму двух последних цифр.

Генератор случайных чисел: Randomize; Ch:=Random (1000)+1;

Задание для самостоятельной работы (часть1):

• Напишите алгоритм обработки чисел последовательности из N целых чисел, заданных с клавиатуры или сформированных генератором случайных чисел.

• Получите три варианта трассировки алгоритма, оформите своей ответ и сдайте учителю: разместите в папку доступа свои результаты с полными копиями экрана ( с датой и временем!). Можно добавить слайд в эту презентацию и подписать его.

Разработка сложного алгоритма

Часть 2

Создание массива счетчиков найденных сумм двух последних цифр каждого числа в последовательности по порядку.

Итак, мы получили сумму двух последних чисел числа.

Теперь нам нужно организовать счетчик одинаковых сумм и сохранение этих счетчиков в массиве KOL (18) фиксированной длины. Так как максимальная сумма двух цифр 18 мы можем задать длину массива от 1 до 18. Нуля быть не может, так как нуль не положительное целое число!

Структура массива KOL (18)

Счетчики сумм с одинаковыми значениями, равными значению индекса элемента массива

0 1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

Дополним наш алгоритм описанием структуры массив с обязательной инициализацией и подсчетом количества одинаковых сумм.

Var KOL: array[0..18] of integer;

For k:=0 to 18 do Kol[k]:=0;

ИНИЦИАЛИЗАЦИЯ: Для переменных типа СЧЕТЧИК, наращивание суммы требуется задавать начальное значение в зависимости от задачи, например ОБНУЛЕНИЕ.

Kol[Sum]:=Kol[Sum]+1; или inc(Kol[Sum]);

Рассмотрим результат первого тестирования:

Сгенерированы пять чисел:

5639, 8168, 7765, 5414, 9469

Получены соответственно суммы:

12, 14, 11, 5, 15

В этом примере ни одна сумма не повторилась, следовательно в качестве ответа мы должны выдать наибольшую их них, то есть: 15.

Как видно из трассировки это будет при проходе по массиву последний максимум.

Именно поиском последнего максимума мы и займемся на следующем этапе написания алгоритма.

Пример №2

Рассмотри результаты еще двух трассировок нашего примера №2:

Трассировка №1

Трассировка №2

Назовите самостоятельно какой ответ должен быть по первой трассировке, а какой по второй?

Задание для самостоятельного выполнения (часть №2)

• Напишите программу по примеру №2
• Произведите 4 компиляции и опишите результат по примеру рассмотрения компиляции первого тестирования.
• Ответ оформите в виде файла Ч2_12_05_Петров Иван_11А. doc

Ответ: 15

Разработка сложного алгоритма

Часть 3

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

Допишем в алгоритм последний этап: поиск последнего максимума в одномерном массиве.

Заведем дополнительные переменные: Max_Kol и Max_S

Пример №3

Пример №4

В этом примере мы отключим генератор случайных чисел («закомментируем» его).

И отключим промежуточные выводы.

Мы видим, что из пяти чисел:

12, 100, 63, 48, 6

Соответственно, суммы двух последних цифр:

3, 0, 9, 12, 6

Программа выбрала одинаковое по частотности (1), но наивысшее по сумме цифр значение: 12 .

Третий этап:

нахождение последнего максимума в массиве, с учетом варианта нулевой суммы последних двух цифр.

Дополнительные исследования закономерностей поиска.

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

В приведенном примере мы видим, что числа:

25, 14, 3, 7, 3.

Дают частоту по два случая равных сумм 3 и 7.

В ответ выходит наименьшая сумма 3.

Задание части №3

• Разработайте наборы последовательностей и определите какой ответ должна дать программа.
• Наберите текст программы самостоятельно и проверьте свои тесты.
• Создайте файл отчета со своими тестами и сканами компиляций.
• Сдайте ответ учителю. Поместите свой ответ в папку общего доступа: https:// drive.google.com/open?id=1ob0BJ1IwFKAWvMF7s7GMosLEcZbHLFXq

Источники:

• Для рассмотрения взята задача из типовых заданий КИМов ЕГЭ по информатике ФИПИ.
• Решение авторское.