Как работает код? JS

212

17 июля 2018, 14:40

Реализуйте и экспортируйте по умолчанию функцию, которая принимает на вход два аргумента - количество нулей и количество единиц, и определяет сколько есть способов размещения этих нулей и единиц так, что бы не было двух нулей идущих подряд.

Например, определим все способы размещения двух нулей и двух единиц. Существует шесть возможных способов размещения: 0011, 0101, 0110, 1001, 1010, 1100. В трех случаях содержится два нуля, идущих подряд: 0011, 1001 и 1100. Вычитаем их из общего числа и получаем три возможных способа: 0101, 0110 и 1010. Ответ - 3.

// BEGIN (write your solution here) 
const withoutTwoZeros = (a, b) => { 
  if (a > b + 1) { 
    return 0; 
  } else if (a === 0 || b === 0) { 
    return 1; 
  } 
 
  return withoutTwoZeros(a, b - 1) + withoutTwoZeros(a - 1, b - 1); 
}; 
 
//export default withoutTwoZeros; 
// END 
 
console.log(withoutTwoZeros(2,2));

В результате задание решено с помощью комбинаторики, а приведенное решение на ресурсе не понятно.

Answer 1

Если число нулей больше чем число единиц хотя бы на 2, то это сделать невозможно:
```
if (a > b + 1) {
  return 0;
}
```
Если нужно расставить только нули или только единицы, то способ только один:
```
if (a === 0 || b === 0) {
  return 1;
}
```
Если начнём число с 1, то количество способов для хвоста withoutTwoZeros(a, b - 1).
Если начнём с 01, то количество способов для хвоста withoutTwoZeros(a - 1, b - 1).
Ставить в начало 00 мы не можем. Итого получается
```
return withoutTwoZeros(a, b - 1) + withoutTwoZeros(a - 1, b - 1);
```