Данная Запись перекочевала из обсуждения задачи "Без двух нулей" доп испытаний "Введения в программирование"
собсно сама задача
>Реализуйте и экспортируйте по умолчанию функцию, которая принимает на вход два аргумента - количество нулей и количество единиц, и определяет сколько есть способов размещения этих нулей и единиц так, что бы не было двух нулей идущих подряд. > >Например, определим все способы размещения двух нулей и двух единиц. Существует шесть возможных способов размещения: 0011, 0101, 0110, 1001, 1010, 1100. В трех случаях содержится два нуля, идущих подряд: 0011, 1001 и 1100. Вычитаем их из общего числа и получаем три возможных способа: 0101, 0110 и 1010. Ответ - 3.
Шли третьи сутки ...
Легкий lo-fi сменили жесткие треки The Prodigy, банка кофе заканчивалась, пепельница напоминала супер саяна из японских мультиков, пол был завален записями с нулями и единицами, квартира походила на палату сумасшедшего .....
Комбинаторика поддавалась крайне туго, из обсуждений не было понятно ровным счетом ничего. Несколько обсуждающих указывали на треугольник Паскаля, про который я узнал в первый день изучения комбинаторики. Смотрел на него, как баран на новые ворота, с единственной мыслью "И чё???". Конечно, было понятно сразу, что это просто наглядный способ посчитать количество перестановок, но это я мог и без треугольника, функция факториала была написана за первые пять минут. Другое дело, что это никак не подходило под два нуля.
После ознакомления со статьёй Павла Кима (спасибо ему за проделанную работу), "И ЧЁ!!?" не покидала меня никак, треугольник тот же, подобранные ответы казались мне случайным совпадением, и я продолжал искать общую формулу. Сегодня, проснувшись, ко мне пришло озарение, и хотя из-за плохого абстрактного мышления я всё еще считаю, что моя рабочая формула просто подгонка под результаты, она работает.
Решение учителя я понял сразу, так как после того, как нашел общий принцип решения, подумывал посчитать именно так, но на первый взгляд было не понятно, какой способ лучше - просчитать значения в треугольнике или взять общую формулу перестановок. При вычислении треугольника рекурсия грозила переполнить стек при неверной настройке и более высоких значениях нулей и единиц, а в общей формуле были высокие значения факториалов. К моему решению склонила лень - функция факториала была уже написана, и оставалось дописать всего одну строчку с формулой.
Пы. Сы. После всего этого осталось чувство какой-то не завершенности, так как до конца не разобрался в комбинаторике, и как уже говорил - просто подогнал формулу под набор ответов. Наверное именно так чувствуют себя ученые первооткрыватели законов, когда есть просто набор значений и надо их привести к общему закону.
пойду забудусь сном ...
