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

Предположим, что у нас есть две коробки с карандашами (в первом ящике только синие и во вторых красных карандашах). Итак, теперь вопрос заключается в том, как много способов мы можем положить x красные и синие карандаши в линию?Рекурсия и перестановки

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

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

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

источник

2009-11-07 Davor

Is это домашнее задание? Если это не так, почему вы должны использовать рекурсию - не было бы проще использовать соответствующие формулы для перестановок и комбинаций? –

Незначительная ошибка: «Тогда у нас есть 4 разных способа. Комбинации: BRRR, RBRR, RRBR, RRRRB». должно быть «Тогда у нас есть 4 разных способа. Комбинации: BRRR, RBRR, RRBR, RRRB». – daf

Да, это всего лишь часть одной очень большой домашней работы :(Итак, рекурсивный путь должен быть. @cartoonfox: я отредактировал, спасибо. – Davor

Это звучит как домашнее задание, так вот некоторые советы:

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

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

источник

2009-11-07 18:13:07

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

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

источник

2009-11-07 19:41:44 duffymo

-1

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

источник

2009-11-07 19:42:11

Извините, -1 из меня за «u're» и «u». Это не Twitter - заклинание их. – duffymo

@ Давид - да, это это – duffymo

Спасибо, Дэвид, что формула C (x, y) = ... была мне нужна. Рекурсивный способ, который вы предложили, является второй частью программы, но мы не можем использовать какие-либо факториалы, чтобы формула (x + y)!/(x! y!) не учитывается. Вы должны использовать треугольник Паскаля, но я уже понял это;) – Davor

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

ответ

Смежные вопросы