Задачи на анализ и обработку данных - Программирование

Конспект

Решение задач типа С4 требует не только умения применять типовые алгоритмы обработки данных (поиск минимума/максимума, вычисление среднего значения, определение количества элементов массива, удовлетворяющих заданному условию, сортировка и пр.), но и умений анализировать условие задачи, выделять “ключевые” данные (и определять, какие данные являются излишними и не требуют запоминания), применять нестандартные приёмы ввода данных, формировать индексные массивы и массивы-счётчики и т.д.

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

Пропуск текстовых данных из потока символов

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

При чтении данных из такой входной строки оператором read (readln) чтение данных должно производиться слева направо с начала и до конца.

Если какие-то данные не нужны для работы программы, то для их пропуска можно использовать следующие приёмы:

а) для пропуска числовых данных — считать ненужные данные в отдельно объявленную “буферную” переменную соответствующего типа, которая в программе далее не используется (при чтении следующего ненужного данного используется та же переменная).

Пример:

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

Пример:

Массивы-счётчики

При определении количества элементов массива, соответствующих заданному условию (например, количества чётных элементов или количества элементов, равных максимальному), использовалась переменная-счётчик, которая увеличивалась на 1 при обнаружении подходящего элемента.

При необходимости подсчёта количеств нескольких объектов используется массив-счётчик размера, соответствующего количеству объектов. При обнаружении в потоке входных данных объекта, соответствующего условию, нужно увеличить на 1 значение ячейки массива-счётчика, соответствующей данному объекту.

Пример.

Для каждого из 8 филиалов фирмы (пронумерованных от 1 до 8) вразброс вводятся записи из трёх чисел: <номер филиала> <номер месяца> <прибыль/убыток> где прибыль выражена положительной суммой в рублях, а убыток — отрицательной. Завершение входных данных — номер филиала, равный нулю.

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

Решение.

1. Выделяется массив-счётчик. Количество филиалов равно 8, поэтому массив-счётчик должен состоять из 8 элементов с индексами от 1 до 8:

2. Считывается очередная строка данных (три числа в переменные Filial, Mes и Summ).

3. Строится цикл с предусловием:

4. В цикле обрабатываются входные данные:

• если обнаружен убыток, т.е. Summ < 0, то значение ячейки массива-счётчика, соответствующей номеру филиала, увеличиваем на 1.

5. Считывается очередная порция данных (три числа в переменные Filial, Mes и Summ) — если номер филиала не равен нулю, то выполняется очередной проход цикла.

Такое построение цикла позволяет отследить ситуацию, когда входных данных нет (т.е. сразу вводится завершающая строка с нулевым номером филиала).

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

При формировании массива-счётчика нужно не забывать, что в качестве индексов его элементов в Паскале могут использоваться не только произвольные диапазоны целых чисел, но и диапазоны символов, например букв алфавита.

Индексные массивы

Возможна ситуация, когда в качестве индексов массива-счётчика невозможно (или не рационально) использовать значения, считываемые из входных данных в качестве идентификатора объектов, например:

• если вводятся словесные названия месяцев, для которых нужно выполнять подсчёт (строковые данные нельзя использовать как индексы элементов массива);

• если номера объектов идут не подряд. Например, известно, что вводятся номера школ, для которых обрабатываются какие-то данные: 215, 386, 512, 1167, 3160, тогда при создании массива-счётчика с полным диапазоном индексов от 215 до 3160 подавляющее большинство его элементов, кроме пяти с перечисленными индексами, будут не использованы.

В этих случаях применяется индексный массив;

1) массив-счётчик объявляется по количеству обрабатываемых объектов (например, в случае с месяцами — на 12 элементов, в случае со школами — на 5 элементов);

2) отдельно объявляется массив того же размера, который содержит обозначения соответствующих объектов (для месяцев — их словесные названия, для школ — их номера);

3) при считывании входных данных соответствующее обозначение объекта ищется в индексном массиве (путём его просмотра с начала до конца); номер ячейки индексного массива, содержащей искомое обозначение объекта, запоминается;

4) если данный объект соответствует требуемому условию, то в массиве-счётчике увеличивается на 1 элемент, индекс которого равен запомненному индексу элемента в индексном массиве, содержащего обозначение этого объекта.

Связь индексного массива и массива-счётчика осуществляется через общий индекс элемента.

Если при выводе полученных данных требуется выводить обозначения объектов, то они берутся из индексного массива.

Проверить, входит ли символ в заданное множество символов, позволяет оператор in. Запись вида <символ> in [<множество>] истинна, если символ входит в данное множество. При этом требуемое множество в квадратных скобках записывается как перечисление через запятую отдельных символов или интервалов символов. Примеры:

• множество знаков препинания:

• множество латинских букв:

Получить число из его символьной записи (строки цифр) можно:

• при помощи стандартных функций:

- сору(<строка>, <начальная позиция>, <длина>) (извлекает из строки подстроку заданной длины, начинающуюся с символа с заданной начальной позицией),

- LeftStr(<строка>, <длина>) (извлекает из строки подстроку заданной длины слева),

- RightStr (<строка>, <длина>) (извлекает из строки подстроку заданной длины справа),

- StrToInt(<строковая запись числа>) (преобразует запись целого числа в виде строки цифр в само число);

• путём обработки кодов символов цифр: код символа позволяет получить стандартная функция ord (<символ>), при этом разность кода символа заданной цифры и кода символа цифры “нуль” равна числовому значению заданной цифры (см. таблицу кодировки ASCII). Тогда можно получить число, отдельно обрабатывая каждую его цифру указанным способом и суммируя полученные числовые значения цифр с учётом их разрядов (умножением на 10 в степени, равной номеру разряда).

Проверка равенства вещественных значений

Как известно, вещественные значения в памяти компьютера представлены приближенно. Поэтому, например, вычисленное значение 2.0 + 2.0 в общем случае может оказаться не равно вычисленному значению 2.0 * 2.0 (из- за погрешностей вычислений). Из-за этого использовать при сравнении вещественных значений оператор равенства не совсем корректно. Вместо этого производится сравнение модуля разности сравниваемых величин с некоторым малым значением, определяемым точностью вычислений. В данном случае в качестве такого малого значения можно использовать число 0,0 001.

Разбор типовых задач

Задача 1. На автозаправочных станциях (АЗС) продаётся бензин с маркировкой 92, 95 и 98. В городе N был проведен мониторинг цены бензина на различных АЗС.

Напишите эффективную по времени работы и по используемой памяти программу (укажите используемую версию языка программирования, например, Borland Pascal 7.0), которая будет определять для каждого вида бензина, сколько АЗС продают его дешевле всего. На вход программе в первой строке подаётся число данных о стоимости бензина. В каждой из последующих Nстрок находится информация в следующем формате:

<Компания> <Улица> <Марка> <Цена>

где <Компания> — строка, состоящая не более, чем из 20 символов без пробелов, <Улица> — строка, состоящая не более, чем из 20 символов без пробелов, <Марка> — одно из чисел — 92, 95 или 98, <Цена> — целое число в диапазоне от 1000 до 3000, обозначающее стоимость одного литра бензина в копейках. <Компания> и <Улица>, <Улица> и <Марка>, а также <Марка> и <Цена> разделены ровно одним пробелом. Пример входной строки:

Синойл Цветочная 95 2250

Программа должна выводить через пробел 3 числа — количество АЗС, продающих дешевле всего 92-й, 95-й и 98-й бензин соответственно. Если бензин какой-то марки нигде не продавался, то следует вывести 0. Пример выходных данных:

12 1 0

Решение

1. Необходимо вычислять минимальную цену на бензин каждого вида и количество таких значений. Это можно делать сразу при обработке введённых данных без организации массива-счётчика.

Вместо этого удобно определить два массива (взаимосвязанных через индексы элементов), в элементах которых будут храниться соответственно текущее минимальное значение цены бензина соответствующей марки (массив min) и количество элементов, равных этому минимуму (массив ans).

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

2. Входные данные: сначала отдельно считывается количество строк N, а затем в цикле с параметром считываются сами строки.

При этом строковые данные <Компания> и <Улица> — лишние, их нужно пропустить путём посимвольного чтения до завершающего пробела включительно.

Номер бензина и цена (целые числа) считываются в соответствующие переменные.

3. Обработка считанных данных: считанное значение номера марки бензина используется как индекс и определяет, какая пара переменных (предполагаемый минимум и счётчик значений, равных ему) разбирается в данном случае. Считанное значение цены обрабатывается в типовом алгоритме поиска минимума с подсчётом количества значений, равных минимуму, аналогично элементу массива:

1) цена, по условию, не превышает 3000, поэтому при начальной инициализации ячеек массива min в качестве предполагаемых минимумов задаётся константа, заведомо большая максимально возможного значения цены (число 3001 или большее); счётчики количества значений, равных минимальному (массив ans), обнуляются.

Все эти инициализационные действия производятся в цикле (индексы массивов меняются от 92 до 98) до начала цикла чтения входных строк.

2) после чтения номера марки бензина k и цены b выполняется проверка: если b < min [k], то:

• значение b запоминается как новое значение предполагаемого минимума min [k];

• значение счётчика ans [k] устанавливается в 1 (т.е. одно такое значение уже найдено);

В зависимости от номера марки бензина, работаем с соответствующей парой ячеек “минимум — счётчик”.

3) иначе если значение b равно текущему значению минимума для данной марки бензина min [k], то значение счётчика ans [k] увеличивается на 1.

Если бензина какой-то марки не было вообще, то значение соответствующего счётчика не изменится (останется равным нулю).

По завершении обработки входных данных в ячейках ans [92], ans [95] и ans [98] имеются искомые количества встреченных значений цен, равных минимальным (для каждой из трёх этих марок), либо нули.

4. Вывод данных: на экран выводятся полученные значения ans [92], ans [95] и ans [98].

Полный текст программы:

Задача 2. На вход программе подаётся набор символов, заканчивающийся точкой (в программе на языке Бейсик символы можно вводить по одному в строке, пока не будет введена точка, или считывать данные из файла). Напишите эффективную, в том числе и по используемой памяти, программу (укажите используемую версию языка программирования, например, Borland Pascal7.0), которая сначала будет определять, есть ли в этом наборе символы, соответствующие десятичным цифрам. Если такие символы есть, то можно ли переставить их так, чтобы полученное число было симметричным (читалось одинаково как слева направо, так и справа налево). Ведущих нулей в числе быть не должно, исключение — число 0, запись которого содержит ровно один нуль.

Если требуемое число составить невозможно, то программа должна вывести на экран слово “N0”. А если возможно, то в первой строке следует вывести слово “YES”, а во второй — искомое симметричное число. Если таких чисел несколько, то программа должна выводить максимальное из них. Например, пусть на вход подаются следующие символы:

Do not 911 to 09 do.

В данном случае программа должна вывести

YES

91019

Решение

1. Необходимо вычислять количества каждой из цифр от 0 до 9, поэтому объявляется массив-счётчик с индексами элементов от '0' до '9'.

Внимание! Индексы элементов массива — это символы '1' .. '9', а не числа 1 .. 9 (либо при использовании в качестве индексов именно чисел нужно считанные из входной строки символы цифр преобразовывать в их числовые значения).

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

2. Входные данные: считываются посимвольно до завершающей точки (цикл с предусловием).

3. Обработка считанных данных: если считанный символ представляет собой цифру, то в массиве-счётчике увеличивается на 1 значение элемента с индексом, равным этому символу цифры.

4. Обработка полученного массива-счётчика.

Построение максимального по величине симметричного числа возможно в трёх случаях:

• если количества всех цифр чётны;

• если есть только одна цифра, количество которой нечётно (цепочка этих цифр будет в полученном симметричном числе стоять в середине);

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

Исходя из анализа этих условий решается задача:

1) просматривая массив-счётчик, подсчитывается в нём (в переменной k) количество цифр, встречающихся нечётное число раз. При этом в переменной c_odd запоминается символ цифры, которая последней встретилась нечётное число раз, а в переменной s независимо от чётности количества каждой цифры подсчитывается суммарное количество всех цифр (оно понадобится позже для проверки другого условия).

2) проверяется условие: количество нулей равно 1, а количества других цифр равны нулю (что понятно из равенства общей суммы количеств всех цифр всё той же единице). Если это истинно, то выводится слово “YES” и число 0.

3) иначе проверяется условие: если нули — не единственные цифры и при этом k = 0 или k = 1, то выводится слово “YES” и конструируется число; иначе выводится слово “NO”:

4) симметричное число конструируется так:

• перебираются цифры с 9 до 0 (цикл с параметром, изменяемым в обратном порядке — от '9' до '0'):

• выводится цепочку таких цифр (цифра — текущее значение параметра цикла), длина которой равна половине всего количества таких цифр (если это количество нечётно, то дробная часть отбрасывается, т.е. используется целочисленное деление):

Способ 1: с использованием стандартной функции	Способ 2: без использования стандартной функции

• по завершении цикла перебора цифр от 9 до 0, если k = 1, выводится одна цифра, количество которой было нечётно (она запомнена в переменной c_odd):

• перебирается цифры с 0 до 9:

• выводится цепочка таких цифр (цифра — текущее значение параметра цикла), длина которой равна половине всего количества таких цифр (если это количество нечётно, то дробная часть отбрасывается, т.е. используется целочисленное деление):

Способ 1: с использованием стандартной функции	Способ 2: без использования стандартной функции

Полный текст программы:

Задача 3. В командных олимпиадах по программированию для решения предлагается не больше 11 задач. Команда может решать предложенные задачи в любом порядке. Подготовленные решения команда посылает в единую проверяющую систему соревнований.

Вам предлагается написать эффективную, в том числе по используемой памяти, программу, которая будет статистически обрабатывать пришедшие запросы, чтобы определить наиболее популярные задачи. Следует учитывать, что количество запросов в списке может быть очень велико, так как многие соревнования проходят с использованием Интернет.

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

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

Пример входных данных:

Программа должна вывести список из трёх наиболее популярных задач с указанием количества запросов по ним. Если в запросах упоминаются менее трёх задач, то выведите информацию об имеющихся задачах. Если несколько задач имеют ту же частоту встречаемости, что и третья по частоте встречаемости задача, их тоже нужно вывести.

Пример выходных данных для приведённого выше примера входных данных:

Решение

1. Требуется подсчёт количества каждой из задач. Всего задач может быть 11 видов. Следовательно, необходим массив-счётчик на 11 ячеек. Поскольку названия задач не могут являться индексами массива-счётчика, требуется также индексный массив из 11 ячеек, который должен хранить названия этих задач.

Однако есть дополнительная сложность: названия задач, которые нужно запоминать, и даже реальное количество их разновидностей неизвестны. Поэтому требуется динамически формировать индексный массив.

2. Входные данные: вначале отдельно считывается количество строк, а затем в цикле с параметром вводятся строки — названия задач.

3. Обработка входных данных:

1) в индексном массиве путём просмотра с его начала количества заполненных его элементов (это количество изначально равно нулю) ищется элемент, равный считанному названию задачи;

2) если такой элемент найден, то элемент массива-счётчика с соответствующим индексом (j) увеличивается на 1;

3) иначе (если такой элемент не найден) индексный массив наращивается на один элемент:

• в текущую (незанятую) ячейку индексного массива с индексом у записывается считанное новое название задачи;

• в соответствующую ячейку (с индексом j) массива-счётчика записывается единица (одна такая задача уже встречена);

• количество заполненных элементов индексного массива увеличивается на 1.

Результат: заполненные по всем встреченным задачам индексный массив с названиями задач и массив-счётчик с их количествами.

4. Обработка массива-счётчика: требуется определить три вида задач, для которых количества будут наибольшими. Для этого проще всего отсортировать по убыванию массив-счётчик (и синхронно с ним — индексный массив). Используется метод “пузырька” (попарное сравнение элементов и при необходимости их обмен местами); для упрощения решения задачи — с полным просмотром (без контроля досрочного прерывания сортировки, если массив уже отсортирован).

Внимание! При перестановке элементов в массиве-счётчике нужно одновременно переставлять соответствующие им элементы индексного массива, чтобы сохранить соответствие этих массивов.

5. Вывод данных;

1) если найдено только три вида задач или меньше, то надо выводить информацию обо всех них (тогда в переменной j запоминается номер последней запомненной задачи), иначе (если видов задач больше) — только о трёх первых видах (тогда в переменной j запоминается номер 3);

2) массив-счётчик просматривается с начала и до тех пор, пока не исчерпано количество заполненных его элементов (Num) и пока количество задач текущего вида не меньше количества задач того вида, что в отсортированных массивах (счётчике и индексном) расположен в месте под номером j. При этом, если различных задач меньше трёх, то будет выведена информация обо всех них, а если их больше трёх, то будет выведена информация о трёх первых по количеству видах задач, а также о следующих задачах (четвёртой и т.д.), если их количество совпадает с количеством задач третьего вида.

Полный текст программы: