Python-сообщество

Всем привет!

Задача: имеется целое число N>=0 и целые числа n1, n2,…, n1 - все больше нуля.

Нужно: найти все комбинации этих чисел так, что их сумма будет равна N.

Что хочу на форуме: тут вот какой вопрос возник. Я сейчас по большей части учу именно язык, синтаксис, всякие вещи, связанные со слайсингом строк, например, плюс ООП начинаю потихоньку. А это, как я понимаю, чисто алгоритмическая задача. Что это за тип алгоритма и где можно прочитать про алгоритмы, когда из одной группы числе надо нахимичить другую группу чисел или типа того? Решение писать не прошу - мне его самому найти хочется. Прошу помощи именно в задании направления поиска.

Спасибище!

не думаю что на такую задачу есть какие-то алгоритмы
вот как бы я сделал:
отсортировал бы список и рекурсивно перебирал все возможные комбинации по очереди с каждым числом, если сумма больше N, брал следуюющее число и так далее

я бы посоветовал что-то почитать по компьютерной логике, теории чисел и дискретной математики, а потом уже смотреть алгоритмы сортировки или что-то подобное

terabayt
найти все комбинации этих чисел так, что их сумма будет равна N

На питоне это делается в одну строку. :D

alekscooper
А это, как я понимаю, чисто алгоритмическая задача.

Это перестановки, а чтобы легче понимать перестановки, нужно пройти сортировки. Их, в принципе, для того и проходят в основном, чтобы мозги развить, так как пользоваться n^2-ыми не принято.

Отредактировано py.user.next (Фев. 11, 2015 02:53:39)

py.user.next
Это перестановки, а чтобы легче понимать перестановки, нужно пройти сортировки. Их, в принципе, для того и проходят в основном, чтобы мозги развить, так как пользоваться n^2-ыми не принято.

Естественно, первое, что пришло в голову - O(n**2), то это, понятное дело, не айс. Понял, буду грызть сортировки

py.user.next
Это перестановки

То есть, Вы бы посоветовали изучить алгоритмы сортировки, а потом комбинаторику?

От простого к сложному нужно изучать.

Вот пример:
1 3 2 5 4 6
Что проще сделать с числами: отсортировать и вывести, или получить все сочетания и вывести?

Вот боян конечно про сортировки зато очень даже наглядно

Отредактировано PanovSergey (Фев. 11, 2015 09:01:51)