SoP
Дополнительные задания для школы программирования HH
Язык: Python
Версия языка: 2.7
Задание 1 - find_nearest_points.py
Задание 2 - find_balance.py
Оба скрипта поддерживают стардартные потоки ввода-вывода
Пример вызова скрипта с перенаправлением в Windows:
python scrip-name.py < input-file.txt
Кто использует другие ОС, думаю сами разберутся с перенаправлением потоков )
Для ручного ввода данные необходимо ввести данные, далее нажать клавишу "Enter",
далее для Windows сочетание клавиш Ctrl+Z, для Unix Ctrl+D.
Далее для Windows
Протестировать работоспособность первого задания можно выполнив команду:
python find_nearest_points.py < points.txt
Протестировать работоспособность второго задания можно выполнив команду:
python find_balance.py < balance_test_1.txt
Задание №1 - Минимальное расстояние
Дан набор из N точек на плоскости (для простоты можно считать, что у всех точек целочисленные координаты).
Найдите минимальное расстояние между двумя точками из этого набора.
Пример входных данных:
10 10
20 10
20 15
Пример выходных данных:
5
Решение:
- Сортируем точки сначала по координате X, а при равных X по Y.
- Рекурсивно делим все точки на две части, соотвественно каждую часть еще на две части и т.д.
- Выбираем наименьшее из расстояний между точками в левой и правой частях.
- Далее обрабатываем точки которые находились на границе деления.
- Выбираем точки которые находятся от границы деления по X не дальше наименьшего
расстояния, для каждой точки определяем точки которые находятся по X и Y не дальше наименьшего расстояния. Рассчитываем расстояния между точками и выбираем наименьшее.
Задание №2 - Баланс весов
Дана конечная последовательность натуральных чисел. Считая их массами имеющихся в наличии предметов, определить, можно ли все эти предметы положить на весы так, чтобы весы находились в равновесии. Вывести вариант расположения. Определить, можно ли из них отобрать какое-то количество предметов с суммарным весом 100 (вывести yes или no, в зависимости от результата).
Пример входных данных:
2 4 3 6 5
Пример выходных данных:
2 3 5 - 4 6
no
Решение:
- Сортируем все числа по возрастанию
- Проверяем что сумма всех чисел делится на 2 без остатка
- Находим половину от всей суммы, эту половину мы и будем искать для левой и правой частей
- Далее в цикле проходим по графу чисел (первая версия была реализована как рекурсия, но при колчестве чисел свыше 1000,
приложение достигало максимума вложенности функций, версия с циклом сложнее и медленее но работает для большого количества
чисел)
для чисел 2 3 4 5 6 7 8 9
Граф выглядит примерно следующим образом:
2 - 3 - 4 - 5 - 6 - 7 - 8 - 9
| - 4 - 5 - 6 - 7 - 8 - 9
| - 5 - 6 - 7 - 8 - 9
| - 6 - 7 - 8 - 9
| - 7 - 8 - 9
| - 8 - 9
| - 9
3 - 4 - 5 - 6 - 7 - 8 - 9
| - 5 - 6 - 7 - 8 - 9
| - 6 - 7 - 8 - 9
| - 7 - 8 - 9
| - 8 - 9
| - 9
и т.д.
То есть от числа 2 идут ребра ко всем числам больше 2-х, от числа 3 ко всем числам больше 3-х и т.д.
Для оптимизации прохода по графу и линейной обработки графа, введена переменная bad_edges - в которой для каждого пройденного пути, хранится список тупиков узлов т.е. сумма не будет достигнута, сумма будет превышена, правая часть не можеть быть собрана.