Мы можем построить все числа, меньшие произвольной цели, у которых нет такого шаблона, отметив, что нам будет разрешено добавлять 1 к любому двоичному числу, которое заканчивается на 00, 11 или 01, и добавлять 0 в любом случае,Мы можем использовать обычное «цифровое» динамическое программирование, которое также хранит состояние двух последних цифр, из которых имеется всего четыре возможности, а затем вычитает счет из цели.
Код JavaScript:
function f(s, i, x, y, limited){
if (i == s.length - 1){
if ((limited && s[i] == '0') || (x + y == '10'))
return 1
else
return 2
// Prefix has less than two digits
} else if (x == -1){
if (limited && s[i] == 0){
return f(s, i+1, y, '0', true)
} else {
return f(s, i+1, y, '0', false) +
f(s, i+1, y, '1', limited)
}
// Prefix has at least two digits
} else {
if (limited && s[i] == 0){
return f(s, i+1, y, '0', true)
} else {
result = f(s, i+1, y, '0', false)
if (x + y != '10')
result += f(s, i+1, y, '1', limited)
return result
}
}
}
var n = 2555
var s = n.toString(2)
var c = 0
c += f(s, 1, -1, '0', false)
c += f(s, 1, -1, '1', true)
// (+ 1) removes the count for zero
console.log(`Count without the pattern: ${c}\nSolution: ${n - c + 1}`)
// Brute force
c = 0
for (let x=1; x<=n; x++)
if (/101/.test(x.toString(2)))
c++
console.log(`Brute force: ${c}`)