Раздел C • Категория C4 (демонстрационный вариант-2012)

 
 
 

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

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

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

Пример входных данных:
6
А+B
Крестики-Нолики
Прямоугольник
Простой делитель
А+В
Простой делитель,

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

Пример выходных данных для приведённого выше примера входных данных:
А+В 2
Простой делитель 2
Крестики-Нолики 1
Прямоугольник 1

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

 

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

 

Методические указания

Когда требуется запрограммировать задачу "с нуля", то методика существует и состоит из следующих конститутивных этапов:

  1. техническое задание (постановка задачи);

  2. формализация (математическая постановка задачи);

  3. выбор (или разработка) метода (или способа) решения задачи;

  4. алгоритмизация (разработка алгоритма для решения упражнения);

  5. запись программы на конкретном языке программирования (кодирование задачи);

  6. тестирование и отладка;

  7. выполнение программы и обработка полученных результатов;

  8. документирование.

Перечисленные выше этапы свойственны методикам в основном для крупных и средних проектов и, как правило, для программ, состоящих из 40 - 150 строк кода, некоторые этапы целесообразно опустить. Тем более что при сдаче ЕГЭ по информатике и ИКТ 2012 в вашем распоряжении не будет персонального компьютера, следовательно, не будет даже возможности произвести компиляцию созданного кода. В обобщенном варианте, в процессе сдачи официального экзамена вы сможете воспользоваться пунктами 1, 2, 3, 4, 5. Оставшиеся пункты в методике реализации будут физически недоступны.

 

Теоретические сведения

Язык программирования – специальная кодовая система для записи компьютерных программ. Каждый язык программирования обладает определенной семантикой, лексикой и синтаксисом. В мире придумано и реализовано свыше 8000 тысяч языков программирования, но востребованными являются не более 20 – 30 различных языков.

Синтаксис языка – набор правил, определяющий конструкции языка и формат их представления.
Семантика языка – набор правил, определяющий содержание и смысл конструкций языка.

Наиболее популярные языки программирования:

  • C;

  • C++;

  • C#;

  • Java;

  • Basic;

  • Pascal;

  • Delphi;

  • Oberon;

  • Ada;

  • Fortran;

  • Assembler.

 

Решение

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

Рассмотрим алгоритм решения представленной задачи на конкретном примере (количество пришедших запросов составило 10 штук).

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

  • условие задачи;

  • частотность задачи, показывающая, сколько раз данная задача была решена на соревновании командами-участницами;

  • некий индекс, характеризующий порядковый номер задачи в данном массиве.

подытожив все вышесказанное имеем:

 

Начнем сканирование задач от 1 до 10 при этом одновременно заполнять комплексный массив анализируемой информацией (для справки: комплексный результирующий массив расположен в нижней части).

Итак, после обработки первой задачи (ее название "Фермер") имеем:

 

Продолжаем обработку входной информации:

 

Завершаем обработку входной информации:

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

 

Мы только обработали входную информацию и поместили ее в некоторую структуру данных, но для решения поставленной задачи мы еще провели не все манипуляции.
Что же делать дальше?
Для ответа на поставленный вопрос надо обратиться к условию упражнения и вспомнить, что надо в результате отобразить информацию о наиболее часто встречающихся задачах. Следовательно, необходимо отсортировать названия задач по убыванию их количества.

В качестве метода сортировки можно выбрать один из прямых методов:

  • обменом (пузырьком);

  • выбором (минимального или максимального значения);

  • вставками (минимального или максимального значения).

*примечание: для столь простой задачи не рекомендую использовать улучшенные методы сортировки (Шелла, Хоара, пирамидальная и пр.).

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

Ниже я привожу иллюстрации процесса сортировки:

После сортировки массив принял вид:


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

Ответ:

  • Фермер 3

  • Змейка 3

  • Колобок 2

 

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

Производим сортировку массива методом вставками:

Промежуточный вывод: общее количество различных задач равно 5, следовательно, выводим на дисплей пользователя список из трех наиболее популярных задач с указанием запросов по ним. Также учтем, что существует одна задача («Бомбермен»), имеющая такую же частоту как и третья задача («Змейка»).

Ответ:

  • Колобок 3

  • Армагедон 2

  • Змейка 2

  • Бомбермен 2

 

И заключительный пример входных и выходных данных:

 

Также не забудьте ознакомиться с программным кодом по данной задаче на различных языках программирования (Turbo Pascal, C, C++, C#).

 

Вывод:

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

Резюме

  1. внимательное чтение и осознание условия задания;

  2. моделирование и алгоритмизация на простых входных данных;

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

  4. программная реализация на одном из 4-рех современных языках программирования.

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

Раздел C • Категория C4 (демонстрационный вариант-2012)

 

Комментарии

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