Задание:
Реализуйте и экспортируйте по умолчанию функцию, которая принимает на вход два аргумента - количество нулей и количество единиц, и определяет сколько есть способов размещения этих нулей и единиц так, что бы не было двух нулей идущих подряд.
Например, определим все способы размещения двух нулей и двух единиц. Существует шесть возможных способов размещения:
0011, 0101, 0110, 1001, 1010, 1100. В трех случаях содержится два нуля, идущих подряд: 0011, 1001 и 1100.
Вычитаем их из общего числа и получаем три возможных способа: 0101, 0110 и 1010. Ответ - 3.
Постановка проблемы:
Перед решением задания неприятно удивило, что процент решивших на данный момент всего 55%, для остальных заданий 90-95. Подумалось, что я что то упустил при чтении условия, может есть какой то хитрый подвох, полез читать комментарии, чего только там не было, рекурсия, деревья, комбинаторика, геометрия. В общем, по себе знаю, хочешь сделать надежно, и чтобы и через год понять свое собственное решение - делай как можно проще и прямолинейней - т.е. не плоди лишних сущностей, в данном случае хватит и простого перебора, компьютер быстрый, он справиться.
Решение:
Идея решения проста, по сути нам на вход подается множество двоичных чисел с заданным числом нулей и единиц, переберем их все, от 0 до a + b (с ведущими нулями, в этом нам очень сильно поможет метод String.padStart), где a - количество нулей, b - количество единиц, в процессе перебора будем отбрасывать числа содержащие парные нули (.includes('00')) и числа с количеством нулей и единиц в записи, отличающимся от количества нулей и единиц, заданных параметрами функции. Если запись числа с ведущими нулями не содержит парных нулей, и содержит заданное число нулей и единиц - увеличиваем счетчик на единицу, закончили перебор - вернули значение счетчика. Задание решено.
Примечание:
В переборе всех чисел от 0 до a + b нам не обойтись без метода Number.toString(n) - возвращает число в системе исчисления по основанию n.
Код:
// вернуть количество символов chr в строке str
const numberChar = (str, chr) => {
let result = 0;
for (let i = 0; i < str.length; i++) {
if (chr === str[i]) {
result++;
}
}
return result;
}
const withoutTwoZeros = (a, b) => {
let counter = 0;
let binaryNum = ''.padStart(a + b, '1');
for (let index = 0; index <= parseInt(binaryNum, 2); index++) {
let tmpStr = index.toString(2).padStart(a + b, '0');
if (!tmpStr.includes('00')) {
if ((numberChar(tmpStr, '0') === a) && (numberChar(tmpStr, '1') === b)) {
counter++;
}
}
}
return counter;
}
