[Условия задач] [Список тренировок]
4A. Совершенные числа
[perfect]
Хорошая несложная задача. Есть один подвох, на который натыкаются многие. Желаю наткнуться на него всем начинающим, чтобы глубже проникнуться задачей.
4B. Разложение на слагаемые
[decomp]
Компактная рекурсивная реализация. В ходе решения встает только одна проблема: как не генерировать комбинации слагаемых, которые уже были до этого? Для этого, по рекомендации Меньшикова, условимся, что в получаемой комбинации предыдущее слагаемое не превышает текущего. Этим приемом можно пользоваться и в других подобных задачах для обеспечения уникальности последовательностей.
4C. Гангстеры
[gangster]
Очень неплохая задача на ДП. Заставляет подумать. По своему решению перекликается с задачей о поиске максимальной возрастающей подпоследовательности [1C]. Читаем исходник – все довольно прозрачно.
4D. Площадь многоугольника
[area]
Пронумеруем все точки многоугольника в порядке обхода как {0,1,2,… n-1}. В качестве базовой точки возьмем 0-ую точку. Будем последовательно находить ориентированные площади треугольников 0:1:2, 0:2:3,… 0:n-3:n-2, 0:n-2:n-1, используя векторное произведение. Сумма площадей этих треугольников будет равно ориентированной площади общего многоугольника.
4E. Деление длинного числа на короткое
[divshort]
Очередная полезная операция на длинную арифметику. Отметим тот факт, что для поиска частного и остатка от деления можно использовать одну функцию.
4F. Скобки
[bracket]
Классика жанра. При использовании одного типа скобок можно без проблем обойтись целочисленным счетчиком, считая баланс на каждом шаге. Если дело имеем с несколькими типами скобок, то лучшее решение основано на использовании стека. Эту задачу мы уже разбирали ранее в рамках курса первой книги Долинского.
[Все решения]
Комментариев нет:
Отправить комментарий