cout Columns! i )=:: ; cin w;

Rows.push back(h); Columns.push back(w);

cout endl GetOps(1, N) endl; cout RepresentSolutiond, N); return 0;

Пример:

9.4.2. Календарь чемпионата Составление расписания игр

Дан список из N команд (число N считается чётным). Требуется сгенерировать распечатку туров для проведения чемпионата по круговой системе. В каждом туре всегда играют N/2 пар команд (каждой команде находится пара для игры в текущем туре).

Чемпионат состоит из N - 1 туров, поскольку любая команда в итоге должна сыграть с каждой из оставшихся N - 1 команд. Ответные матчи не играются.

Например, календарь для четырёх комшед Спартак , Зенит , Локомотив и Рубин может выглядеть так:

Тур 1

Спартак - Зенит Локомотив - Рубин

Тур 2

Спартак - Локомотив Зенит - Рубин

Тур 3

Спартак ~ Рубин Зенит - Локомотив

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

Первый подход часто приводит к тому, что под конец чемпионата из остав шихся команд уже невозможно составить корректный набор пар. Это неоче видно, так что приведу пример. Предположим, что в чемпионате участвуе-шесть команд: Спартак , Алания , Зенит , Локомотив , Рубюг и Динамо Первые два тура генерируются случайным алгоритмом без проблем:

Спартак - Алания Зенит - Локомотив Рубин - Динамо

Спартак - Динамо Зенит - Рубин Алания - Локомотив

Далее, предположим, что в третьем туре алгоритм выбрал первые две napi команд:

Спартак - Рубин Зенит - Динамо

Теперь в нашем распоряжении лишь две команды - Локомотив Алания , но они уже играли между собой!

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

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

Очевидно, задача сводится к тому, чтобы придумать хорошую схему выбо! команд, участвующих в очередном туре.

С++ мастер-класс. 85 нетривиальных проектов, решений и задач Решение

Алгоритм генерации туров на самом деле несложен. Представьте себе круг, в центре которого записана первая команда, а по окружности (как цифры на циферблате часов) - все остальные. Первая команда отрезком соединяется с командой, имеющей номер N/2 + 1. Остальные команды попарно соединены хордами, как изображено на рис. 9.9.

N/2 + 2

N/2+1

Рис 9.9. Генерация туров чемпионата

Соединённые пары команд формируют первый тур чемпионата. Повернув круг так, чтобы первая команда оказалось соединённой с командой, имеющей номер N/2 + 2, мы получим все пары второго тура и так далее. Через N - 1 итераций календарь чемпионата будет готов.

Для полноты картины не помешает привести листинг на С++:

int main(int argc, char* argv[]) {

int N;

String line, teaml; list<string> Teams; cin N; cin teaml;

/ / количество команд / / первая команда

все остальные команды считать количество команд считать первую команду считать остальные команды и добавить их в список Teams for(int i = 0; i < N - 1; i++) {

cin line;

Teams.push back(line);

cout endl;

for(int i = 0; i < N - 1; i++) {

pi, p2 - итераторы на начало и конец списка команд list<string>::iterator pi = Teams.begin();

list<string>: :iterator p2 = Teams.endO; p2--;

cout << Tour << (i + 1) endl; номер очередного тура пока итераторы не сравняются в нижней части круга while(р1 != р2) {

cout *р1 - *р2 endl; переходим к следующей паре

р1++; р2-;

cout teaml - *р1 endl endl; пара teaml - *р1

сдвигаем команды по кругу Teams.push back(Teams.front()); Teams.pop front();

return 0;

9.4.3. Исследование структуры спроса

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

САМОУчителы

[Заказать >>]

Занимательное программирование; Самоучитель

Автор(ы) МпугпвоУ! . В.

I Раздел. Компьюгернвя литература

Серия. Гамоучитепь

1 Тема; Программирование. Обцие вопросы

старая тепа Общие conpocbi пригрйипиро&мия

Издание 1-е, 2004 гол

ISBN: 5 94723-853 5

Формат 17x24 CP*

Объем: 208 стр.

Переплет- ияггэя обложка

Срок выуода: е продаже

Цена: 108 р 6. [варианты доставки и оплаты] Цена для членов клуба Лрофессмснап. 92 руб. [Специальнйе предпр*ение]

содержание отрывок {лйлы к кнчге

отзывы

оценка читателей; -k-k-k-i с эглй инигой чладе всего .и-л зыешот

Интернет, протсксч безопасности. Учебный курс V Бпэк аена: 20 руб.

Элепронньй MdiajHH на lava и XML. Библиотека 1рСГраммиста C+CD) Ъ. Брогден, К. Минник иена: 32 руб.

Рис 9.10. Страница интернет-магазина издательства Питер

Определённый интерес представляют популярные сочетания из большого количества товаров: их знание может вывести торговлю на качественно новый уровень. Например, сейчас во многих магазинах электроники можно приобрести готовый комплект из часто покупаемых совместно корпуса, памяти, процессора, винчестера, клавиатуры и ещё некоторых устройств. Этот комплект называется персональным компьютером . Обратите внимание, что для проведения полноценного исследования нет надобности изучать все возможные сочетания товаров. Начните с пар. Если популярность сочетания двух товаров уже ниже требуемой, добавление третьего товара ситуацию к лучшему не изменит. То же верно и для любого набора из К товаров: изучать их сочетание с каким-либо новым товаром имеет смысл только тогда, когда популярность исходного набора не ниже минимально допустимой популярности в системе.

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

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

1 хлеб

2 молоко

3 бананы

4 кукурузные хлопья

5 картофель

12 3 2 4 5 12

Здесь первый покупатель приобрёл хлеб, молоко и бананы, второй - молоко и кукурузные хлопья, а третий - картофель, хлеб и молоко.

На выходе программа печатает список самых популярных сочетаний товаров. Для приведённых выше данных они таковы:

хлеб, молоко (2/3) то есть сочетание встречается в двух покупках из трёх

хлеб, бананы (1/3)

молоко, бананы (1/3)

молоко, кукурузные хлопья (1/3)

хлеб, картофель (1/3)

молоко, картофель (1/3)

хлеб, молоко, бананы (1/3)

хлеб, молоко, картофель (1/3)

Популярность, по существу, представляет собой вероятность встретить сочетание среди всех соверпюнных покупок. В нашем случае эти вероятности равны 2/3,1/3 и О (например, для сочетания бананы, картофель ). Минимально допустимая популярность, интересующая пользователя, вводится с клавиатуры.