0

La función SuperSuma se define como:     SuperSuma(0,n)=nSuperSuma(0,n)=n, para todo n positivo          SuperSuma(k,n)=SuperSu

La función SuperSuma se define como:     SuperSuma(0,n)=nSuperSuma(0,n)=n, para todo n positivo          SuperSuma(k,n)=SuperSuma(k−1,1)+SuperSuma(k−1,2)+...+SuperSuma(k−1,n)SuperSuma(k,n)=SuperSuma(k−1,1)+SuperSuma(k−1,2)+...+SuperSuma(k−1,n), para todo entero positivo k,nk,n. Dados k,nk,n, devuelva el valor para SuperSuma(k,n)SuperSuma(k,n).

12th Oct 2019, 9:27 PM
Jhovany Condori
Jhovany Condori - avatar
1 Respuesta
0
Ah, this one is interesting. Recall the Hockey-stick identity: https://en.m.wikipedia.org/wiki/Hockey-stick_identity And the fortunate fact that SuperSuma(1, n) = n(n+1)/2 = choose(n+1, 2) by Gauss. By induction you get SuperSuma(k, n) = choose(n + k, k + 1). Now all you have to do is cook up a choose function that doesn't blow up for large inputs, so beware to reinterpret C(2000, 1999) as C(2000, 1) to avoid performance loss.
10th Apr 2020, 10:04 PM
Zuke
Zuke - avatar