Скачать презентацию
Идет загрузка презентации. Пожалуйста, подождите
Презентация была опубликована 8 лет назад пользователемЗинаида Башкирёва
1 Задача «Несчастливые билеты» РОИ 2008 Автор задачи: Владимир Алексеевич Кузнецов Разбор: Федор Николаевич Царев
2 Общий подход Две части решения: –Проверка «несчастливости» номера –Перебор номеров Обе части могут быть реализованы двумя способами
3 Проверка номера Задан билет с номером d 1 d 2 d 3 …d n Пусть S = d 1 + d 2 + d 3 +…+ d n Проверить, что не существует поднабора цифр числа, сумма по которому равна S/2». Решим противоположную задачу – «проверить, существует ли поднабор цифр числа, сумма по которому равна S/2» Задача о сумме подмножеств – известная NP-полная задача (подробнее об NP-полных задачах – см. google.com) Ее иногда не совсем правильно называют «задача о рюкзаке»
4 Задача о сумме подмножеств Решение описано в книге Шень А. Программирование: теоремы и задачи. – М.: МЦНМО, и на сайте раздел «Динамическое программирование» Два варианта: –Перебор за O(2 n ) –Динамическое программирование – O((k+1)n 2 )
5 40 баллов Перебор всех номеров за O((k+1) n ) Решение задачи о рюкзаке любым способом Позволяет вычислить ответ для восьми тестов
6 100 баллов Важен не сам номер, а мультимножество его цифр Пусть в номере можно использовать цифры от 0 до d, цифра 0 может входить в номер n 0 раз, цифра 1 может входить в номер n 1 раз, …, цифра d может входить в номер n d раз, при этом
7 Вычисление числа номеров по мультимножеству цифр Цифра 0 способов расставить Цифра 1 способов расставить на оставшихся позициях … Цифра d способов расставить на оставшихся позициях
8 Правильное решение Перебор мультимножеств Решение задачи о рюкзаке динамическим программированием Отсечение по сумме цифр – любой билет с нечетной суммой цифр является «несчастливым» Все 20 ответов вычисляются примерно за 5 минут
9 85 баллов Правильное решение без «длинной» арифметики
10 Частные случаи K = 1 : 10 баллов K = 2 : 15 баллов
Еще похожие презентации в нашем архиве:
© 2024 MyShared Inc.
All rights reserved.