Niezmienniki pętli

Question

Witam!

Znajdzie się ktoś kto jest w stanie mi wytłumaczyć jak działają niezmienniki pętli? W jaki sposób się je wyznacza i ewentualnie liczy?

Podam przykład:

Dane: liczba naturalna n.

Wynik: s=1+.....+n.

begin

s:=0; i:=0;

while (i<n) do

{

i:=i+1;

s:=s+1;

}

end

Proszę nie wklejajcie linków gdzieś z internetów gdzie jest sucho wyjaśnione co to jest niezmiennik pętli bo tego najzwyczajniej w świecie nie rozumiem. Prosiłbym, aby ktoś był w stanie to wytłumaczyć na powyższym przykładnie.

Pozdrawiam!

Answer 1

Niezmiennik pętli - pojęcie używane w projektowaniu, analizie i dowodzeniu poprawności algorytmów. Mówimy, że zdanie P jest niezmiennikiem pętli, jeżeli po każdym jej przebiegu jest ono prawdziwe.

W twojej pętli warunek i<n nie spełnia powyższej definicji, ponieważ i się zwiększa a n jest liczbą naturalną więc w pewnym momencie twoja pętla się zakończy (warunek zwróci w pewnym momencie false). Gdyby warunek w pętli był np. taki: 0==0 to to byłby niezmiennik pętli bo warunek zawsze byłby spełniony i pętla by się wykonywała w nieskończoność.

Comments

A to nie chodzi o to żeby jakieś zdanie logiczne było zawsze prawdziwe przed obiegiem jak i zakończeniu pętli?

Bo skoro za pomocą tych niezmienników wyznacza się poprawność algorytmu to na podstawie twojej wypowiedzi wynika, że powyższy algorytm jest zły, a przecież daje poprawne wyniki.

---

Jeżeli pętla wykonuje się w nieskończoność bo warunek został źle ułożony to to świadczy o złym ułożeniu warunku. Innymi słowy jeżeli warunek i<n byłby po każdym przejściu pętli spełniony to to byłby niezmiennik pętli a to świadczyłoby o tym, że warunek jest źle skonstruowany. Nie otrzymałbyś żadnego wyniku skoro pętla by się wykonywała w nieskończoność (przynajmniej ja tak to rozumiem).

---

Ja to rozumiem tak że są 2 warunki:

1) n=>0 (zakładam, że 0 jest liczbą naturalną)

2)i<n

Dajmy, że n=5

Oba warunki przed obiegiem pętli są prawdziwe ale już po wykonaniu pętli warunek 1) jest tylko prawdziwy.

I tu w tym miejscu pojawia się pytanie czy można na te niezmienniki popatrzeć w taki sposób jak ja to rozumiem, czyli... Wszystkie założenia przed wykonaniem pętli muszą być prawdziwe ale już po wykonaniu musi być prawdziwe tylko jedno założenie.

---

W definicji, którą przytoczyłem z Wikipedii jest napisane:

Mówimy, że zdanie P jest niezmiennikiem pętli, jeżeli po każdym jej przebiegu jest ono prawdziwe.

że nie. Niezmiennik pętli oznacza taki warunek, który przed jak i po każdym wykonaniu pętli będzie spełniony. W przypadku, który wymieniłeś warunek 1 będzie niezmiennikiem bo zawsze będzie prawdziwy a warunek 2 już nie. Przynajmniej ja tak to widzę.

---

Ok, już mniej więcej wiem z czym się te niezmienniki "je". Resztę zweryfikuje profesor na egzaminie.

Dziękuje za zaangażowanie i pozdrawiam!