|
Programming Taskbook |
|
|
||
|
Электронный задачник по программированию |
||||
|
© М. Э. Абрамян (Южный федеральный университет, Университет МГУ-ППИ в Шэньчжэне), 1998–2024 |
|
|
Задачи повышенной сложности: ExamExt25, ExamExt53Группы ExamExt и ExamFExt содержат задания, аналогичные тем которые предлагались на ЕГЭ по информатике в качестве задач повышенной сложности. Начальную часть данной группы составляют задания на обработку сложных наборов данных (записей) с элементами-полями различных типов. В подобных заданиях требуется правильно выбрать способ хранения данных и организовать их эффективную обработку; при этом обычно требуется применить несколько базовых алгоритмов, например, алгоритм суммирования или нахождения минимума/максимума и алгоритм поиска нужного элемента или сортировки набора данных по требуемому ключу. Следует заметить, что возможность автоматической генерации больших наборов исходных данных, предоставляемая задачником Programming Taskbook, позволяет существенно ускорить тестирование учебных программ и сделать его более надежным. В заданиях групп ExamExt и ExamFExt ввод и вывод имеет те же особенности, что и в заданиях групп ExamBase и ExamFBase. Подобно группам ExamBase и ExamFBase, группы ExamExt и ExamFExt отличаются только способом ввода исходных данных (в заданиях группы ExamFExt исходные данные требуется читать их текстового файла). Рассмотрим следующее задание. ExamExt25°. На вход подаются сведения об абитуриентах. В первой строке
указывается количество абитуриентов N, каждая из последующих N строк имеет
формат Программа-заготовка, созданная для этого задания, подобно заготовкам для заданий группы ExamBase, будет использовать заголовочный файл pt4exam.h: #include <iostream>
#include <fstream>
#include <iomanip>
#include "pt4exam.h"
using namespace std;
// Для ввода используйте поток cin
// Для вывода используйте поток cout
// Между полученными результатами надо выводить символ пробела
void Solve()
{
Task("ExamExt25");
}
При запуске этой программы на экране появится окно задачника, содержащее следующие данные:
Окно будет иметь такой вид, если при его предшествующем закрытии оно находилось в режиме отображения всех данных. Для отображения всех данных на экране может потребоваться увеличить высоту окна; для этого достаточно зацепить мышью заголовок окна и переместить его вверх (для перемещения заголовка окна задачника вверх и вниз можно также воспользоваться клавиатурными комбинациями [Ctrl]+{Up] и [Ctrl]+[Down]). При первом тестовом испытании программы ей будет предложен для обработки набор данных не слишком большого размера (порядка 10–20 элементов). Вначале следует определиться со структурами данных, которые будут использоваться в программе. Поскольку требуется найти одну характеристику для каждого года, а число лет невелико, можно использовать числовой массив year, каждый элемент которого соответствует определенному году. Будем считать, что индекс 0 соответствует 1990 году, индекс 1 — 1991 году и т. д. (количество элементов будет равно 21). В начале программы массив следует инициализировать, положив значения всех его элементов равными 0 (заметим, что если после обработки исходных данных некоторые элементы массива year останутся будут нулевыми, то это будет означать, что соответствующие годы не были представлены в наборе исходных данных, и выводить информацию о них не следует). После инициализации массива следует прочесть информацию о количестве абитуриентов и организовать цикл, в котором будут обрабатываться данные о каждом абитуриенте и соответствующим образом корректироваться элементы массива year. В дальнейшем сведения об уже обработанном абитуриенте нам не будут нужны, поэтому сохранять их в специальном наборе данных (например, массиве) не требуется. Заметим также, что фамилия абитуриента для решения задачи не требуется, поэтому после чтения двух числовых данных можно сразу переходить к новой строке, пропуская строковый элемент данных (фамилию). В данной задаче не нужно использовать и номера школ, однако их придется считывать, так как только после номера школы указывается интересующий нас год поступления абитуриента. Когда данные обо всех абитуриентах будут обработаны, в массиве year будет содержаться вся необходимая информация, которую останется вывести в формате, указанном в условии задачи. Приведем первый вариант решения (этот вариант содержит одну ошибку): #include <iostream>
#include <fstream>
#include <iomanip>
#include "pt4exam.h"
using namespace std;
// Для ввода используйте поток cin
// Для вывода используйте поток cout
// Между полученными результатами надо выводить символ пробела
void Solve()
{
Task("ExamExt25");
int n;
int year[21];
for (int i = 0; i < 21; i++)
year[i] = 0;
cin >> n;
for (int i = 0; i < n; i++)
{
int k, m;
cin >> k >> m; // k - номер школы, m - год поступления
while (cin.get() != '\n') // пропуск оставшейся части строки
;
year[m-1990]++;
}
for (int i = 0; i < 21; i++)
cout << i + 1990 << " " << year[i] << endl;
}
Ошибка связана с тем, что на экран выводится информация о годах, отсутствующих в наборе исходных данных. Поэтому она сразу будет выявлена при обработке наборов данных небольшого размера, предлагаемых программе при первом тестовом запуске (для большей наглядности приведем окно задачника в режиме сокращенного отображения данных, при котором выводятся только пять первых элементов из каждого набора данных):
Обратите внимание на многоточия, указанные в нижней части разделов с исходными данными, полученными результатами и примером правильного решения. Эти многоточия показывают, что во всех разделах отображается только часть связанных с ними данных. Для исправления ошибки достаточно добавить в последний цикл условный оператор: for (int i = 0; i < 21; i++)
if (year[i] > 0)
cout << i + 1990 << " " << year[i] << endl;
Теперь все 9 тестовых испытаний программы, требуемых для того, чтобы решение было зачтено как выполненное, будут пройдены успешно. Завершая рассмотрение этого задания, опишем некоторые дополнительные возможности, связанные с просмотром больших наборов данных. Начиная со второго испытания, программе может быть предложен для обработки набор исходных данных большего размера (порядка 50–100 элементов). При этом уже не удастся отобразить на экране все данные, связанные с заданием. В подобной ситуации у правой границы окна задачника появится полоса прокрутки, позволяющая перемещаться к той части данных, которая первоначально не отображается на экране. Прокрутку данных можно выполнять не только с помощью полосы прокрутки, но и используя клавиши со стрелками, [PgUp], [PgDn], [Home], [End], а также колесико мыши. Помимо стандартных действий по прокрутке данных, в окне задачника предусмотрены возможности «интеллектуальной» прокрутки, позволяющие быстро перейти к началу каждого раздела задания, а также сравнить соответствующие фрагменты полученных результатов и примера верного решения. Для циклического перебора разделов сверху вниз предназначена клавиша [+] (а также комбинация [Ctrl]+[PgDn]), для циклического перебора разделов снизу вверх — клавиша [–] (а также комбинация [Ctrl]+[PgUp]). Для быстрого переключения между соответствующими фрагментами разделов с результатами и с примером верного решения предназначена клавиша [/] (а также комбинация [Ctrl]+[Tab]). Все эти действия можно выполнить и с помощью мыши; для этого предусмотрены кнопки в левом верхнем углу прокручиваемой области окна, отведенной под отображение разделов задания (эти кнопки отображаются на экране, если размер данных, связанных с заданием, превышает размеры окна). Приведем вид окна задачника с полосой прокрутки и дополнительными кнопками:
Обозначения на кнопках совпадают с клавишами, выполняющими те же действия; при наведении мышью на кнопку рядом с ней появляется всплывающая подсказка. Кроме трех кнопок, связанных с «интеллектуальной» прокруткой, в приведенном на рисунке окне отображаются еще две дополнительные кнопки. Первая из них располагается в правом верхнем углу раздела с формулировкой и позволяет временно скрыть (а в дальнейшем опять отобразить) раздел с формулировкой (эти же действия можно выполнить с помощью клавиши [Del] или двойного щелчка мышью на разделе с формулировкой). Вторая дополнительная кнопка расположена в правом верхнем углу раздела с исходными данными. Как уже отмечалось ранее, эта кнопка позволяет переключаться между полным и сокращенным отображением наборов данных. Напомним, что изображение на этой кнопке показывает текущий режим отображения данных. Например, если на кнопке изображена стилизованная стрелка, направленная вверх (как на приведенном выше рисунке), значит, в данный момент в окне отображаются все данные, а нажатие на эту кнопку переведет окно в режим отображения нескольких начальных (как правило, пяти) элементов каждого набора данных. Решение с файловым вводом исходных данныхПриведем решение, в котором используется ввод данных из текстового файла (соответствующая задача имеет имя ExamFExt25). #include <iostream>
#include <fstream>
#include <iomanip>
#include "pt4exam.h"
using namespace std;
// Исходные данные следует вводить с помощью функций файлового ввода
// Для вывода используйте поток cout
// Между полученными результатами надо выводить символ пробела
void Solve()
{
Task("ExamFExt25");
string filename = GetString(); // имя исходного файла
int n;
int year[21];
for (int i = 0; i < 21; i++)
year[i] = 0;
ifstream fin(filename);
fin >> n;
for (int i = 0; i < n; i++)
{
int k, m;
fin >> k >> m; // k - номер школы, m - год поступления
while (fin.get() != '\n') // пропуск оставшейся части строки
;
year[m - 1990]++;
}
fin.close();
for (int i = 0; i < 21; i++)
if (year[i] > 0)
cout << i + 1990 << " " << year[i] << endl;
}
После проверки программы на девяти наборах тестовых данных будет выведено сообщение о том, что задание выполнено:
Теперь рассмотрим более сложное задание. ExamExt53°. На вход подаются сведения о ценах на бензин на автозаправочных станциях (АЗС).
В первой строке содержится значение M одной из марок бензина, во второй строке указывается
целое число N, а каждая из последующих N строк имеет формат Приведем окно задачника, которое появится на экране при запуске программы-заготовки для данного задания (в данном окне скрыт раздел с формулировкой; в результате оказались скрытыми и кнопки, отвечающие за «интеллектуальную» прокрутку, поскольку в окне полностью отображается содержимое оставшихся разделов):
Выясним, какая структура является наиболее подходящей для хранения информации, необходимой для решения задачи. Нам требуется информация, связанная с различными улицами, которых по условию не более 30, причем для каждой улицы надо хранить сведения двух видов: ее название и максимальную цену бензина марки M. Поэтому мы можем либо завести массив из 30 элементов-записей с двумя полями, либо два массива: один содержащий названия улиц, а другой — максимальные цены. Учитывая, что в конце программы нам потребуется выполнять сортировку полученных данных, целесообразнее использовать массив записей (данных типа struct), поскольку это позволит записать алгоритм сортировки в более компактной форме. Определим тип-структуру Street с двумя полями name и max и опишем массив s из 30 элементов типа Street. Следует также завести переменную ns, в которой будет храниться количество заполненных элементов массива s. При обработке каждой строки с исходными данными нам будут нужны прежде всего сведения о марке бензина. Если марка бензина не равна M, то оставшуюся часть строки обрабатывать не требуется, и можно сразу перейти к разбору следующей строки. Если марка бензина равна M, то необходимо узнать название улицы s0 и цену бензина p. Заметим, что название компании для решения задачи не требуется, однако его необходимо прочесть, чтобы определить следующий элемент данных — цену бензина. Если улица с названием s0 еще не была включена в массив s, то ее необходимо включить в массив, присвоив полю max значение p. Если же улица уже присутствует в массиве, то необходимо сравнить поле max для данной улицы и значение p, изменив при необходимости поле max (здесь мы используем базовый алгоритм нахождения максимального значения). Для ввода названий улиц и компаний в нашем случае удобно организовать посимвольное чтение строковых данных; признаком завершения такого чтения будет обнаружение пробельного символа. После обработки набора исходных данных необходимо проверить, найдена ли хотя бы одна улица с АЗС, предлагающей марку бензина M (для этого достаточно сравнить значение ns с нулем). Если ни одна улица не найдена, то надо вывести строку «No»; в противном случае требуется выполнить сортировку массива s по указанному набору ключей и вывести полученные данные в указанном порядке. Поскольку размер массива невелик, для его сортировки вполне допустимо использовать один из простых алгоритмов, например, алгоритм пузырьковой сортировки. Приведем один из вариантов правильного решения задачи (для хранения строк используется тип string, описанный в одноименном заголовочном файле): #include <iostream>
#include <fstream>
#include <iomanip>
#include <string>
#include "pt4exam.h"
using namespace std;
// Для ввода используйте поток cin
// Для вывода используйте поток cout
// Между полученными результатами надо выводить символ пробела
void Solve()
{
Task("ExamExt53");
struct Street
{
string name;
int max;
};
int m, n, ns;
Street s[30];
cin >> m >> n; // m - марка бензина
ns = 0;
for (int i = 0; i < n; i++)
{
int k;
cin >> k;
if (k != m)
while (cin.get() != '\n')
; // пропускаем оставшуюся часть строки
else
{
string s0;
cin.get(); // пропускаем пробел после первого числа
cin >> s0; // читаем название улицы
cin.get(); // пропускаем пробел после названия улицы
while (cin.get() != ' ')
; // пропускаем название компании
int p;
cin >> p; // читаем цену бензина
// Обработка прочитанной информации
int k = 0;
for (int j = 0; j < ns; j++)
if (s[j].name == s0) // улица уже содержится в массиве s
{
k = 1;
if (s[j].max < p)
s[j].max = p;
break;
}
if (k == 0) // улица еще не содержится в массиве s
{
s[ns].name = s0;
s[ns].max = p;
ns++;
}
}
}
if (ns == 0) // ни одной улицы не найдено
cout << "No" << endl;
else
{
// Сортировка по возрастанию максимальной цены,
// а для одинаковых цен - по названиям улиц
for (int k = 0; k < ns - 1; k++)
for (int i = 0; i < ns - 1 - k; i++)
if (s[i].max > s[i + 1].max ||
s[i].max == s[i + 1].max &&
s[i].name > s[i + 1].name)
{
Street x = s[i];
s[i] = s[i + 1];
s[i + 1] = x;
}
// Вывод результатов в требуемом порядке
for (int i = 0; i < ns; i++)
cout << s[i].max << " " << s[i].name << endl;
}
}
Решение с файловым вводом исходных данныхКак и для предыдущей задачи, приведем решение, в котором используется ввод данных из текстового файла (соответствующая задача имеет имя ExamFExt53).
#include <iostream>
#include <fstream>
#include <iomanip>
#include "pt4exam.h"
using namespace std;
// Исходные данные следует вводить с помощью функций файлового ввода
// Для вывода используйте поток cout
// Между полученными результатами надо выводить символ пробела
void Solve()
{
Task("ExamFExt53");
string filename = GetString(); // имя исходного файла
struct Street
{
string name;
int max;
};
int m, n, ns;
Street s[30];
ifstream fin(filename);
fin >> m >> n; // m - марка бензина
ns = 0;
for (int i = 0; i < n; i++)
{
int k;
fin >> k;
if (k != m)
while (fin.get() != '\n')
; // пропускаем оставшуюся часть строки
else
{
string s0;
fin.get(); // пропускаем пробел после первого числа
fin >> s0; // читаем название улицы
fin.get(); // пропускаем пробел после названия улицы
while (fin.get() != ' ')
; // пропускаем название компании
int p;
fin >> p; // читаем цену бензина
// Обработка прочитанной информации
int k = 0;
for (int j = 0; j < ns; j++)
if (s[j].name == s0) // улица уже содержится в массиве s
{
k = 1;
if (s[j].max < p)
s[j].max = p;
break;
}
if (k == 0) // улица еще не содержится в массиве s
{
s[ns].name = s0;
s[ns].max = p;
ns++;
}
}
}
fin.close();
if (ns == 0) // ни одной улицы не найдено
cout << "No" << endl;
else
{
// Сортировка по возрастанию максимальной цены,
// а для одинаковых цен - по названиям улиц
for (int k = 0; k < ns - 1; k++)
for (int i = 0; i < ns - 1 - k; i++)
if (s[i].max > s[i + 1].max ||
s[i].max == s[i + 1].max &&
s[i].name > s[i + 1].name)
{
Street x = s[i];
s[i] = s[i + 1];
s[i + 1] = x;
}
// Вывод результатов в требуемом порядке
for (int i = 0; i < ns; i++)
cout << s[i].max << " " << s[i].name << endl;
}
}
После проверки программы на девяти наборах тестовых данных будет выведено сообщение о том, что задание выполнено:
|
|
|
Разработка сайта: |
Последнее обновление: |