[Algorytmy] Niezmiennik pętli

gienia
Użytkownik
Użytkownik
Posty: 339
Rejestracja: 25 lip 2014, o 16:13
Płeć: Kobieta
Lokalizacja: Polska
Podziękował: 243 razy

[Algorytmy] Niezmiennik pętli

Post autor: gienia » 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)

Kod: Zaznacz cały

k = m;
s = 2^m;
while ( k < n) {
  k = k + 1;
  s = s + 2^k;
}
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?

Awatar użytkownika
leg14
Użytkownik
Użytkownik
Posty: 3132
Rejestracja: 5 lis 2014, o 20:24
Płeć: Mężczyzna
Lokalizacja: Radom
Podziękował: 154 razy
Pomógł: 475 razy

Re: [Algorytmy] Niezmiennik pętli

Post autor: leg14 » 25 paź 2017, o 00:35

Więc widzę, że to raczej a) będzie, ale czy takie rozważania można traktować jako dowód indukcyjny?
Nie można - dowód ma być czytelny i precyzyjny. A to jest na razie zbieranina znaczków -potrzebny jest komentarz.

ODPOWIEDZ