Компьютерные книги
Главное меню
Главная Поиск по сайту Добавить материал О нас Карта книг Карта сайта
Реклама
computersbooks.net -> Добавить материал -> Языки программирования -> Кубенский А.А. -> "Структуры и алгоритмы обработки данных. Объектно-ориентированный подход и реализация на C++" -> 150

Структуры и алгоритмы обработки данных. Объектно-ориентированный подход и реализация на C++ - Кубенский А.А.

Кубенский А.А. Структуры и алгоритмы обработки данных. Объектно-ориентированный подход и реализация на C++ — Спб.: БВХ-Петербург , 2004. — 464 c.
ISBN 5-94157-506-8
Скачать (прямая ссылка): strukturiialgoritmiobrabotkidannih2004.djvu
Предыдущая << 1 .. 144 145 146 147 148 149 < 150 > 151 152 153 154 155 156 .. 161 >> Следующая

Функции как носитель информации
433
лучена позиция со всеми имеющимися в наличии горизонталями. По существу, новый алгоритм повторяет ту же схему, которая использовалась нами в алгоритмах листингов 8.3 и 8.4, разница состоит только в способе представления позиции и, соответственно, в способе установки нового ферзя в уже имеющуюся.
I Листинг 8.5. Расстановка ферзей с помощью j функционального представления позиции
// Рекурсивная функция, получающая новую правильную позицию из старой // с помощью добавления нового ферзя на следующую горизонталь.
// Аргумент row задает количество уже расставленных ферзей // (заполненных горизонталей)
SmartPtr<Position> recQueen2(const SmartPtr<Position> & position,
int row, int maxQueens) {
if (row = maxQueens) {
// Уже расставлены все ферзи return position;
} else {
// Пытаемся поставить нового ферзя в ряд с номером row for (int col = 1; col <= maxQueens; col++) { if (position->permits(row, col)) {
// Новый ферзь не атакует ни одного из уже расставленных.
// Формируем новую позицию и делаем рекурсивный вызов SmartPtr<Position> nextPos(
new NewPosition(position, col, row, maxQueens)); SmartPtr<Position> newPos =
recQueen2(nextPos, row + 1, maxQueens);
// Если удалось обнаружить правильную позицию с таким ферзем if (newPos) return newPos;
}
}
//He удалось поставить нового ферзя ни на одну вертикаль return SmartPtr<Position>(NULL);
}
}
SmartPtr<Position> queen2(int n) {
// В начале работы позиция пуста и ни одного ферзя еще не расставлено return recQueen2(SmartPtr<Position>(new EmptyPosition()), 0, n);
}
Новая функция нахождения расстановки работает медленнее обоих предыдущих вариантов. Так, например, на моей машине расстановку ферзей на
434
Глава 8
доске 28x28 функциональный вариант программы нашел только за 48 секунд, в то время как предыдущие версии справилась с этой работой за 24 и 9 секунд соответственно. Памяти новый вариант программы, несмотря на отсутствие массивов в представлении позиции, тоже требует несколько больше, поскольку представление позиции в виде массива целых чисел достаточно компактно. Кроме того, удается в процессе работы функции один и тот же массив использовать для хранения разных позиций. Таким образом, наш последний вариант программы служит не столько для практического применения, сколько для иллюстрации принципа функционального представления информации.
Конечно, этот принцип применим не только к задаче о расстановке ферзей и работе с бесконечными множествами. Почти в любой задаче наряду с объектным представлением существует и параллельный вариант решения с функциональным представлением информации. Вопрос лишь в том, какое представление более выгодно и естественно для данной задачи. Конечно, необходимо правильно определить набор функций, адекватно представляющий нужную информацию. Для случая работы с бесконечными множествами функциональное представление помогло в таком случае, когда физическое представление элементов множества может быть вообще неприменимо.
В качестве еще одного примера рассмотрим классическую задачу о назначениях, несколько напоминающую задачу о расстановке ферзей.
Пусть имеется п рабочих мест и п работников, каждый из которых может выполнять любую работу, но производительность труда у каждого рабочего на разных рабочих местах различна. Неотрицательная величина производительности труда работников задается функцией, которая по заданным номеру работника и номеру рабочего места выдает вещественное число, характеризующее производительность труда работника на заданном рабочем месте. Мы зададим тип этой функции fProd с помощью следующего определения типа данных:
typedef double (*fProd) (int, int);
Требуется расставить рабочих по рабочим местам так, чтобы их суммарная производительность на всех рабочих местах была максимальной.
Так же, как и в случае расстановки ферзей, одно из возможных представлений расстановки рабочих — это вектор длины и, в котором /-й элемент представляет порядковый номер рабочего, поставленного на /-е рабочее место. Ясно, что если этот вектор обозначить Р, то все значения />[/'] должны быть различны, поскольку никакого рабочего нельзя поставить сразу на два рабочих места. При таком представлении данных можно построить решение задачи в виде рекурсивной функции, несколько напоминающей второй вариант решения задачи о расстановке ферзей.
Функции как носитель информации
435
Другое возможное представление данных — функциональное. Прежде всего надо решить, какие функции могут адекватно представлять расстановку некоторого количества к рабочих по имеющимся п рабочим местам. Назовем рангом этой расстановки число расставленных работников к, а ее производительностью — суммарную производительность труда расставленных работниках на тех рабочих местах, на которых они находятся в этой расстановке. Все, что нам нужно знать о каждой расстановке, — это ее производительность, информация о том, свободен ли некоторый /-й рабочий (если ранг расстановки меньше п) и способ вывода расстановки в качестве результата в выходной поток. Таким образом, как и в случае задачи о ферзях на шахматной доске, тип данных, представляющий некоторую расстановку рабочих по рабочим местам, может быть записан в виде следующего абстрактного класса:
Предыдущая << 1 .. 144 145 146 147 148 149 < 150 > 151 152 153 154 155 156 .. 161 >> Следующая
Книги
Web-программирован-
ие
Аппаратное обеспечение Графика Руководство по П.О. Самоучитель Теория программирования Фотошоп Языки программирования
Новые книги
Вирт Н. "Систематическое программирование " (Теория программирования)

Эком "Microsoft Excel 2000 шаг за шагом Русская версия самоучитель " (Самоучитель)

Поляков А.Ю. "Методы и алгоритмы компьютерной графики в примерах Vizual C++" (Графика)

Баяковский Ю.М. "Графическая библиотека Open GL " (Графика)

Валиков А. "Технология " (Языки программирования)
Авторские права © 2013 ComputersBooks. Все права защищены.