Mając daną zależność rekurencyjną:
\(\displaystyle{ C_N = C_{\left\lfloor \frac{N}{2} \right\rfloor} + C_{\left\lceil \frac{N}{2} \right\rceil} + N,\ \ N \ge 2}\)
\(\displaystyle{ C_1 = 0}\)
wyznacz rekurencję dla \(\displaystyle{ C_{N+1} - C_N}\). Wykorzystaj ją do pokazania, że
\(\displaystyle{ C_N = \sum_{1 \le k < N} \left( \left\lfloor \lg k + 2 \right\rfloor \right)}\)
Udowodnij, że \(\displaystyle{ C_N = N \left\lceil \lg N \right\rceil + N - 2^{\left\lceil \lg N \right\rceil}}\).
Zależność rekurencyjna, sufity i podłogi
- arek1357
- Użytkownik
- Posty: 5748
- Rejestracja: 6 gru 2006, o 09:18
- Płeć: Mężczyzna
- Lokalizacja: blisko
- Podziękował: 131 razy
- Pomógł: 526 razy
Zależność rekurencyjna, sufity i podłogi
łatwo zauważyć, że ciąg ten to taki zmutowany ciąg arytmetyczny i zachodzi:
\(\displaystyle{ 2^n+1 \le i,i+1 \le 2^{n+1}}\)
\(\displaystyle{ C_{i+1}-C_{i}=n+2}\)
\(\displaystyle{ 2^n+1 \le i,i+1 \le 2^{n+1}}\)
\(\displaystyle{ C_{i+1}-C_{i}=n+2}\)