Рекурсия и перестановки

Допустим, у нас есть две коробки карандашей (в первой коробке только синие, а во второй только красные карандаши). Итак, вопрос теперь в том, сколькими способами мы можем поставить в линию x красных и y синих карандашей?

Пример: у нас есть 3 красных карандаша и 1 синий. Тогда у нас есть 4 разных пути. Комбинации: БРРР, РРРР, РРРР, РРРБ.

Таким образом, с 10 красными и 10 синими карандашами у нас есть 184756 различных способов поставить их в ряд. Итак, ребята, как написать это рекурсивным способом?

Большое спасибо за Вашу помощь.


java recursion math permutation
person Davor    schedule 07.11.2009    source источник
comment
Это домашнее задание? Если это не так, то зачем вам использовать рекурсию - не проще ли использовать соответствующие формулы для перестановок и комбинаций?   -  person Thomas Owens    schedule 07.11.2009
comment
Незначительная ошибка: тогда у нас есть 4 разных пути. Комбинации: БРРР, РРРР, РРРР, РРРРБ. должно быть Тогда у нас есть 4 разных пути. Комбинации: БРРР, РРРР, РРРР, РРРБ.   -  person Dafydd Rees    schedule 07.11.2009
comment
Да, это всего лишь часть одной очень большой домашней работы :(. Так что рекурсивный способ должен быть. @cartoonfox: я отредактировал, спасибо.   -  person Davor    schedule 07.11.2009
comment
@Davor: Если это домашнее задание, сообщите об этом заранее. В противном случае это выглядит так, как будто вы пытаетесь заставить других делать вашу домашнюю работу за вас.   -  person MAK    schedule 07.11.2009

Ответы (3)


arrow_upward
5
arrow_downward

Звучит как домашнее задание, поэтому вот несколько советов:

Имея дело с рекурсией, вам нужно думать о базовом случае. Здесь этот базовый случай равен 0 карандашей. Сколькими способами можно заказать 0 карандашей?

Хорошо, теперь рекурсивные случаи: сколькими способами можно заказать ненулевое количество карандашей? Если у вас есть красные карандаши, вы можете начать с красного карандаша, а затем с остальными карандашами. Если у вас есть синие карандаши, вы можете начать с синего карандаша, а затем с остальными карандашами.

person Laurence Gonsalves    schedule 07.11.2009

arrow_upward
0
arrow_downward

Подумайте о бинарном дереве, глубина = количество карандашей в строке.

Корень - ноль карандашей. На уровне 1 был один синий карандаш и один красный карандаш. Уровень 2... вы видите закономерность.

person duffymo    schedule 07.11.2009

arrow_upward
-1
arrow_downward

нет необходимости делать это в форме рекурсии, так как это можно рассчитать с помощью (x+y)!/(x!y!), но если вы настаиваете, вы можете использовать что-то вроде этого: C(x,y)=C(x-1,y)+C(x,y-1) с базовыми вариантами: C(z,0)=C(0,z)=1 что z - любое натуральное число

person Unknown    schedule 07.11.2009
comment
Извините, -1 от меня за вас и вас. Это не Твиттер — произнесите их по буквам. - person duffymo; 07.11.2009
comment
Спасибо, Дэвид, эта формула C(x,y)=... была всем, что мне было нужно. Нерекурсивный способ, который вы предложили, является второй частью программы, но мы не можем использовать факториал, чтобы формула (x+y)!/(x!y!) не учитывалась. Вы должны использовать треугольник Паскаля. Но я уже разобрался ;) - person Davor; 08.11.2009