[Algorytmy] Niezmiennik pętli
: 24 paź 2017, o 23:14
Cześć!
Mam takie zadanie:
Niech m, n będą liczbami naturalnymi takimi, że m \(\displaystyle{ \le}\) n. Rozważmy algorytm Alg(m,n)
Zbadaj, która z wymienionych formuł jest niezmiennikiem petli w tym algorytmie?
a) \(\displaystyle{ s = \sum_{i=m}^{k} 2^i}\)
b) \(\displaystyle{ s = \sum_{i=1}^{k} 2^i}\)
Odpowiedz poprzyj dowodem indukcyjnym.
Szczerze mówiąc nie bardzo wiem jak się do tego zabrać, więc rozpisałem:
\(\displaystyle{ k_1=m}\)
\(\displaystyle{ S_1=2^m=2^{k_1}}\)
\(\displaystyle{ k_2=k_1+1=m+1}\)
\(\displaystyle{ S_2=S_1+2^{k_2}}\)
...
\(\displaystyle{ k_n = k_{n-1}+1=m+n-1}\)
\(\displaystyle{ S_n=S_{n-1}+2^{k_n}= \sum_{i=m}^{n}2^i}\)
Więc widzę, że to raczej a) będzie, ale czy takie rozważania można traktować jako dowód indukcyjny?
Mam takie zadanie:
Niech m, n będą liczbami naturalnymi takimi, że m \(\displaystyle{ \le}\) n. Rozważmy algorytm Alg(m,n)
Kod: Zaznacz cały
k = m;
s = 2^m;
while ( k < n) {
k = k + 1;
s = s + 2^k;
}
a) \(\displaystyle{ s = \sum_{i=m}^{k} 2^i}\)
b) \(\displaystyle{ s = \sum_{i=1}^{k} 2^i}\)
Odpowiedz poprzyj dowodem indukcyjnym.
Szczerze mówiąc nie bardzo wiem jak się do tego zabrać, więc rozpisałem:
\(\displaystyle{ k_1=m}\)
\(\displaystyle{ S_1=2^m=2^{k_1}}\)
\(\displaystyle{ k_2=k_1+1=m+1}\)
\(\displaystyle{ S_2=S_1+2^{k_2}}\)
...
\(\displaystyle{ k_n = k_{n-1}+1=m+n-1}\)
\(\displaystyle{ S_n=S_{n-1}+2^{k_n}= \sum_{i=m}^{n}2^i}\)
Więc widzę, że to raczej a) będzie, ale czy takie rozważania można traktować jako dowód indukcyjny?