|
Titlul: 582 Biti3 Scris de: Adrian Diaconu din Noiembrie 19, 2007, 00:13:00 Aici puteţi discuta despre problema Biti3 (http://infoarena.ro/problema/biti3).
Titlul: Răspuns: 582 Biti3 Scris de: Alexandru Pana din Martie 11, 2008, 23:57:29 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" |