UniLecs 130_1. Разбиение числа
UniLecsЗадача: давайте вспомним одну из популярных задач на вывод всех разбиений числа N.
Разбиения числа N на слагаемые — это набор целых положительных чисел, сумма которых равна N. При этом разбиения, отличающиеся лишь порядком слагаемых, считаются одинаковыми.
Необходимо вывести всевозможные разбиения N.
Условие: слагаемые в разбиениях должны идти в убывающем порядке.
Входные данные: N - натуральное число от 1 до 30.
Вывод: всевозможные разбиения числа N
Пример: N = 3
Answer:
1 + 1 + 1
2 + 1
3
Реализация:
- @akolosov364, JS: 1 балл
Рекурсивное решение, функция вызывается до тех пор пока n не станет равно 0. Из n вычитается число из промежутка от start включительно до n, чтобы избежать повторов.
https://gist.github.com/KolosovAO/de22bb87ecadef08e0a67939f956c249
Test:
https://repl.it/@AlieksieiKoloso/task130
2. @lPestl, C#, F#: 1.5 балла за два подхода + 0.1 балл за доп.язык = 1.6 балла
Подробный разбор по ссылке ниже!
C#
https://gist.github.com/lpestl/2d9a88331bfdd79968c4a109077b078d
F#
https://gist.github.com/lpestl/dfeb1799a08b5b4f0f7c31711613d3c2
3. Антон, Haskell, Python, Rust: 1.5 балла за два подхода + 0.2 балла за два доп.ЯП = 1.7 балла
Подробный разбор смотри по ссылке ниже!
Haskell:
https://gist.github.com/AnthonyMikh/5646080c43eccac455364bd11b2a1eb4
Haskell Test:
https://repl.it/repls/SecondhandDimgreyDisplaymanager
Python:
https://gist.github.com/AnthonyMikh/8aae234659d0511858e47824eee54868
Python Test:
https://repl.it/repls/InterestingFirsthandMicrokernel
Rust:
https://gist.github.com/AnthonyMikh/7d5cc7910ad6f77eea13c9ee3bd4a157
Rust Test:
https://play.rust-lang.org/?gist=28a409cb06db62b671bdb8e448f8d358
4. @jinxonik, Python, C++: 1.5 балла за два подхода + 0.1 балл за доп.язык = 1.6 балла.
Метод 1. Создаём пустой список списков (СС), который будет содержать списки слагаемых и будет возвращаться в качестве результата работы основной функции. Рекурсивная функция, выполняющая основную работу, будет иметь два параметра: n и max_i и будет дополнять последний список слагаемых и генерировать новые списки для числа n, но такие, элементы которых не будут превышать max_i. Для этого первым делом запомним длину последнего списка (назовём её count), затем добавим в этот список n единиц (т.к. выполнять рекурсию дляmax_i = 1 смысла нет, результат один и известен заранее). После запустим цикл i от 2 до меньшего из max_i и n, в который будет добавлять новые списки в СС, заполнять их count элементами из предыдущего списка, добавлять значение i и выполнять рекурсию с параметрами n - i и i, если n - i > 0, т.е., по сути, если сумма текущего списка будет < N (переданного нашему главному методу get_list1).
Метод 2. Этот метод не содержит рекурсий, но имеет 2 списка: текущий список и список (СС), оба первоначально содержащие единицы в кол-ве N штук. Организуем цикл, работающий пока размер текущего списка > 1, в котором будет находиться вложенный цикл, перебирающий элементы текущего списка с его конца (вернее, со 2-го элемента от конца), проверяя, меньше ли текущий элемент, чем предыдущий, либо является ли текущий элемент первым. Если выполняется хотя бы одно из этих условий, то: - к текущему элементу прибавляется единица; - все последующие элементы текущего списка (хвост) удаляются, а вместо них добавляются единицы в количестве суммы хвоста за вычетом единицы; - вложенный цикл прерывается. В конце внешнего цикла (while) текущий список добавляется в СС.
Подробный разбор решений на C++, Python!
https://gist.github.com/jin-x/f9ec99d55f76b1e88dd10fb02eec1117
C++ Test:
https://repl.it/@jin_x/UniLecs-130-summandscpp
Python Test:
https://repl.it/@jin_x/UniLecs-130-summandspy
5. @tvolf, PHP: 1 балл
Для решения задачи используем рекурсию. Так как по условию задачи на выходе у нас должны получаться невозрастающие последовательности, то на каждом шаге рекурсии мы перебираем значения, которые меньше либо равны предыдущему значению в последовательности.
https://gist.github.com/tvolf/bdc43eea1a052a78a4f00b5d6cc4228e
6. @egormasharskii, C++: 1 балл
В качестве первого слагаемого мы можем выбрать любое число K из диапазова [1..N]. Тогда останется решить задачу размера N-K при условиии что максимальное слагаемое будет не больше чем выбранное на данном шаге.
7. @kirillmotrichkin, Python: 1 балл
https://gist.github.com/superkiria/537d6b9f5b5778c93a9016eef99e40c4
Test:
https://repl.it/@superkiria/unilecs130decay
8. @Zernov_A, Java: 1 балл
https://github.com/AlexZDeveloper/NumberTerms/blob/master/NumberTerms.java
Test Java:
https://repl.it/repls/HeavenlyProfuseVideogames
9. @voodoo_woodpecker, Python: 1.5 балла за два подхода
https://gist.github.com/MikePeleah/948f4bbeb5ee545dd98587b4b21abf62
Test: