582 Biti3

[•DITzoneC]

Aici puteţi discuta despre problema Biti3.

[•recviem]

In articolul de solutii formula pentru numarul de secvente de lungine i cu j biti este gresita.

num[i, j] = num[i-1, j] + num[i, j-1]

ar trebui sa fie

num[i, j] = num[i-1, j] + num[i-1, j-1].

De exemplu Combinari (x, x) = 1. Dupa formula = Combinari (x-1,x) + Combinari (x,x-1) = 0 + x = x.
(cele 2 variante corespund deciziei de a plasa un bit de 0 pe pozitia i, caz in care pe pozitiile 1,..,i-1 se afla j biti de 1, respectiv un bit de 1 pe pozitia i, caz in care pe pozitiile 1,..,i-1 se mai afla doar j-1 biti de 1). rezulta chiar si din explicatie.
Eu am luat 100 cu a doua formula.

P.S. puteti pune un f la "or i = N -> 1"