Форум программистов, компьютерный форум, киберфорум
Наши страницы

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 9, средняя оценка - 5.00
Includenv
#1

Задача «Футбол» - C++

20.10.2011, 14:50. Просмотров 1278. Ответов 4
Метки нет (Все метки)

Добрый день. Никак не могу придумать, как решить данную задачу с помощью динамического программирования.

Условие:
Олег — большой любитель футбола и статистики. Недавно он нашел результаты участия его любимой команды в каком-то давнем чемпионате. К сожалению, единственной сохранившейся информацией оказалось то, сколько матчей было сыграно и сколько очков набрала команда. Напоминаем, что если матч завершается победой команды, то ей присуждается три очка, ничьей — одно очко, и если команда проигрывает матч, то она не получает ни одного очка.

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

Формат входных данных
Первая строка входного файла содержит два целых числа: n_ (0 ≤ _n ≤ 36) — количество набранных командой очков, и k_ (1 ≤ _k ≤ 12) — количество матчей, сыгранных этой командой в чемпионате.

Формат выходных данных
В выходной файл выведите число различных вариантов прохождения чемпионата любимой команды Олега.

Примеры:
InputOutput
3 22
4 36
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
20.10.2011, 14:50
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Задача «Футбол» (C++):

Футбол. Какая команда покинет высшую лигу? сделате! - C++
Помогите пожалуйста. 1. Даны список футбольных команд высшей лиги России и количество очков, набранных каждой командой в чемпионате...

Задача про футбол - Prolog
Нашел в интернете задачу. Ее условие: Создать БД с таблицей игр чемпионата по футболу: Первая команда, Вторая команда, Счет игры. ...

Футбол - Pascal
Турнирная таблица представлена квадратной матрицей А(n,n), каждый элемент aij которой есть число голов,забитых i-й командой в ворота...

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

Простая программа(футбол) - Delphi
Помогите з программой..Сделать грани ворот(можна с 4 label) тоесть правые и левые ворота...И по очереди ставить мяч(если в левые ворота то...

Связь ячеек БД Футбол - MS Access
Я только начал осваивать Access и даже не знаю сможет ли он мне помочь прошу вашей помощи моя задача из списка (как в примере) ...

4
valeriikozlov
Эксперт С++
4673 / 2499 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
20.10.2011, 19:03 #2
Цитата Сообщение от Includenv Посмотреть сообщение
Никак не могу придумать, как решить данную задачу с помощью динамического программирования.
код писать не буду, но алгоритм решения напишу:
заводим массив mas[k], внутри которого каждый элемент представляет собой массив mas1[n+1]. Хотите делайте это с помощью двумерного массива, можете с помощью структур.
В mas[0] заполняем вручную mas1[n+1] так: mas1[0]=1 (это значит, что в первом матче кол-во вариантов проигрыша равно 1), mas1[1]=1 (кол-во вариантов в первом матче ничьи равно 1) и mas1[3]=1 (кол-во вариантов в первом матче выигрыша равно 1). Остальные элементы mas1[] в mas[0] равны 0. (Но и здесь уже нужно учитывать возможность выхода из границ массива mas1[] - ведь n может быть равно даже 0).
Можно уже на этом этапе все элементы mas1[] во всех элементах mas[1...n-1] обнулить.
Затем сама динамика:
перебираем элементы mas[i] по порядку. Для каждого mas[i] заполняем mas1[n+1] учитывая значения mas1[n+1] предыдущего mas[i-1]. Т.е. перебираем значения mas1[j] элемента mas[i-1] и если оно не равно 0, то (из этого состояния могли выиграть +3, ничья +1, проиграть +0) прибавляем это значение к mas1[j+3] (элемента mas[i]), к mas1[j+1] (элемента mas[i]), к mas1[j] (элемента mas[i]). (естественно учитываем границы массива mas1[] элемента mas[i]).
По окончании такого прохода результат будет находится в mas[n], в mas1[k].
1
Includenv
21.10.2011, 15:22 #3
Код и не надо было писать. Это было бы слишком.
Спасибо, сегодня попробую реализовать.
valeriikozlov
Эксперт С++
4673 / 2499 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
21.10.2011, 15:52 #4
Цитата Сообщение от Includenv Посмотреть сообщение
Код и не надо было писать. Это было бы слишком.
Вообще-то, код даже проще было написать. Если что не получится, обращайтесь.
1
Includenv
22.10.2011, 14:05 #5
Цитата Сообщение от valeriikozlov Посмотреть сообщение
Вообще-то, код даже проще было написать. Если что не получится, обращайтесь.
Спасибо. Всё получилось.
22.10.2011, 14:05
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
22.10.2011, 14:05
Привет! Вот еще темы с ответами:

Футбол. Нужно создать массив с всеми матчами лиги - Java SE
когда в классе методс пытаюсь выявить сколько первая команда играла дома мне выдает странные результаты, хотя если ищу вторую или третью то...

Просмотр футбол через программу Sopcast: собеседник в Skype стал слышать лишь трансляцию - Софт
Всем доброго времени суток. Сегодня возникла следующая проблема, во время разговора по скайпу решил посмотреть футбол через программу...

Невозможно играть в "улетный футбол" при входе с фэйка - Спортивные игры
в игре улетный футбол пишет что невозможно играть в чемпионат так как захожу с фейка до этого не играл как исправить?

Создать базу данных "Футбол" - MS Access
Добрый день) помогите пожалуйста, нужно создать базу данных "Футбол", состоящую из трех таблиц: "ФУтбольные клубы", "Тренеры" и "Игроки". ...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
5
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru