Школа олимпийского резерва. (задача) - презентация, доклад, проект скачать

Содержание ▲

Вы можете ознакомиться и скачать презентацию на тему Школа олимпийского резерва. (задача). Доклад-сообщение содержит 6 слайдов. Презентации для любого класса можно скачать бесплатно. Если материал и наш сайт презентаций Mypresentation Вам понравились – поделитесь им с друзьями с помощью социальных кнопок и добавьте в закладки в своем браузере.

Слайды и текст этой презентации

Слайд 1

Описание слайда:

Задача “Школа олимпийского резерва” Автор задачи Елена Андреева

Слайд 2

Описание слайда:

Создадим 3 массива, согласно году рождения Создадим 3 массива, согласно году рождения Отсортируем каждый из массивов по убыванию баллов Переберем значения M94, M95, M96: проверяем M94 + M95 + M96 = M и T94[M94] > T95[M95], T95[M95] > T96[M96] T94 Т95 Т96 Ищем минимум М96 Сложность O(N3) M94 M95 25 баллов

Слайд 3

Описание слайда:

Заметим, что если мы фиксировали значения M94 и M95, то M96 = A + B + C – (M94 + M95), так как Заметим, что если мы фиксировали значения M94 и M95, то M96 = A + B + C – (M94 + M95), так как A + B + C = M94 + M95 + M96 = M по условию Остается проверить, что полученное значение M96 удовлетворяет условиям 1 ≤ M96 ≤ N96, T94[M94] > T95[M95], T95[M95] > T96[M96] и найти среди таких троек ту, на которой достигается минимум функции Сложность O(N2) 50 баллов

Слайд 4

Описание слайда:

Оптимальное решение T94 Т95 Т96 М96 M94 M95 Переберем значение M95. M94 обозначим за X, тогда M96=M–M95–X. Требуется минимизировать |X − A| + | M − M95 − X − C| 1 ≤ X ≤ N94, 1 ≤ M − M95 − X ≤ N96

Слайд 5

Описание слайда:

Допустимые значения X T94 Т95 Т96 m96 m94 M95 1 ≤ X ≤ N94, 1 ≤ M − M95 − X ≤ N96 X ≤ m94, M − M95 − X ≥ m96 (F(m94) > F(M95) > F(m96)) Пересчет m94, m96 при изменении M95: Пока F(m96) > F(M95) m96 = m96 + 1 Пока F(m94+1) > F(M95) m94 = m94 + 1

Слайд 6

Описание слайда:

Минимизируемая функция Минимизируемая функция |X − A| + |M − M95 − X − C| имеет вид Минимум достигается на одном из значений A, |M − M95 − C|, 1, N94, M − M95, M − M95 − N96, m94, M − M95 − m96 Сложность O(N), 100 баллов