Решение задачи
Программы обычно пишутся для того, чтобы решить какую-то конкретную задачу. Например, книжный магазин ведет запись проданных книг. Регистрируется название книги и издательство, причем запись идет в том порядке, в каком книги продаются. Каждые две недели владелец магазина вручную подсчитывает количество проданных книг с одинаковым названием и количество проданных книг от каждого издателя. Этот список сортируется по издателям и используется для составления последующего заказа книг. Нас попросили написать программу для автоматизации этой деятельности.
Один из методов решения большой задачи состоит в разбиении ее на ряд задач поменьше. В идеале, с маленькими задачами легче справиться, а вместе они помогают одолеть большую. Если подзадачи все еще слишком сложны, мы, в свою очередь, разобьем их на еще меньшие, пока каждая из подзадач не будет решена. Такую стратегию называют пошаговой детализацией или принципом “разделяй и властвуй”. Задача книжного магазина делится на четыре подзадачи:
Прочитать файл с записями о продажах.
Подсчитать количество продаж по названиям и по издателям.
Отсортировать записи по издателям.
Вывести результаты.
Решения для подзадач 1, 2 и 4 известны, их не нужно делить на более мелкие подзадачи. А вот третья подзадача все еще слишком сложна. Будем дробить ее дальше.
3a. Отсортировать записи по издателям.
3b. Для каждого издателя отсортировать записи по названиям.
3c. Сравнить соседние записи в группе каждого издателя. Для каждой одинаковой пары увеличить счетчик для первой записи и удалить вторую.
Эти подзадачи решаются легко. Теперь мы знаем, как решить исходную, большую задачу. Более того, мы видим, что первоначальный список подзадач был не совсем правильным. Правильная последовательность действий такова:
Прочитать файл с записями о продажах.
Отсортировать этот файл: сначала по издателям, внутри каждого издателя– по названиям.
Удалить повторяющиеся названия, наращивая счетчик.
Вывести результат в новый файл.
Результирующая последовательность действий называется алгоритмом. Следующий шаг – перевести наш алгоритм на некоторый язык программирования, в нашем случае – на С++.
