1. Зарегистрируйтесь на сайте repl.it;
2. Перейдите в раздел my repls;
3. Нажмите кнопку Start coding now! - если вы приступаете впервые, или New Repl - если у вас уже есть работы;
4. В списке языков выберите тот язык, который изучаете;
5. Код пишите в левой части окна - в редакторе кода;
6. Чтобы посмотреть результат выполнения файла, нажмите на кнопку Run. Результат появится в правой части окна;
7. После окончания работы скопируйте ссылку на ваш repl в адресной строке браузера;
8. Скопированную ссылку (ваше решение ДЗ) нужно отправить на проверку. Для этого перейдите в личный кабинет на сайте netology.ru, в поле комментария к домашней работе вставьте скопированную ссылку и отправьте работу на проверку;
В стране есть n региональных команд, каждая состоит из 10 игроков, у каждого игрока есть рейтинг. Вам надо написать программу, которая из всех региональных команд соберёт команду национальную - топ-10 игроков по рейтингу. Каждая команда задаётся в виде массива с рейтингами игроков в порядке убывания. Ваша программа должна вывести такой же массив для национальной команды. Целевая асимптотика: O(n) времени, константная память.
Давайте воспользуемся алгоритмом слияния. Если мы сольём два массива команд, то получим массив команды из 20 человек, упорядоченный по убыванию. Нам нужно только 10 человек, так что модифицируем алгоритм слияния таким образом, что будем прерывать его как только в итоговом массиве набралось 10 человек (это всегда будут топ-10 человек из двух массивов).
Возьмём первую региональную команду и сольём её так со второй. Так мы получим топ-10 человек из обеих команд. Давайте полученную команду сольём с третьей - так мы получим топ-10 человек из трёх команд. Проделаем так со всеми региональными командами, в итоге получив топ-10 человек из всех региональных команд.
national_team(regional_teams):
team = regional_teams[0]
for i от 1 до длина(regional_teams)
team = merge(team, regional_teams[i])
return team
Операцию merge реализуйте сами, модифицировав алгоритм с лекции так, чтобы слияние прекращалось после первых 10 элементов.
Оценим асимптотику: каждый раз мы сливаем команды длинною 10, т.е. время работы слияния двух команд не зависит от количества регионов, а стало быть это константная для n операция как для времени, так и для памяти. Таких операций мы сделаем n-1 раз, пройдясь по всем регионам. Итого: асимптотика O(n).
- Создайте массив региональных команд, в котором будут храниться команды:
[45, 31, 24, 22, 20, 17, 14, 13, 12, 10],[31, 18, 15, 12, 10, 8, 6, 4, 2, 1],[51, 30, 10, 9, 8, 7, 6, 5, 2, 1]. - Напишите метод слияния команд для выбора топ-10 из обеих команд.
- Напишите метод для выбора национальной команды из массива региональных команд.
- Запустите метод выбора национальной команды на примере и выведите на экран, убедитесь, что она совпадает с:
[51, 45, 31, 31, 30, 24, 22, 20, 18, 17]. - Загрузите ваше решение на сайт repl.it, отправьте ссылку на него на проверку.