Skocz do zawartości
Briker

Niezmiennik Algorytmu

Rekomendowane odpowiedzi

Witam, potrzebuje odpowiedzi na takie pytanie:

 

Jaki jest niezmiennik pętli poniższego algorytmu?

-------------------------------------------------------

cin>>m;

cin>>n;

x=0;

y=m;

 

do

{

x=x+n;

y=y-1;

}

while(y!=0);

cout<<x;

 

Z góry dzięki za pomoc

Pozdrawiam

Udostępnij tę odpowiedź


Odnośnik do odpowiedzi
Udostępnij na innych stronach

"m" oraz "n" są liczbami naturalnymi różnymi od 0. Na początku x=0. Przy pierwszym obiegu pętli x=x+n a więc x=0+n=n. Gdyby niezmiennikiem było x=m*n, to m musiałoby być równe 1, a tak nie musi być. "m" może być dowolną liczbą naturalną. Fakt, że x=m*n jest prawdziwy, ale po ostatnim obiegu pętli. Jest to bowiem algorytm mnożenia dwóch liczb naturalnych. Niezmiennik musi być natomiast prawdziwy przy każdym obiegu pętli, i powinien być w postaci x=...

 

Prosze pomóżcie :cry:

Udostępnij tę odpowiedź


Odnośnik do odpowiedzi
Udostępnij na innych stronach

Heja!

 

To nasz algorytm:

 

x=0; y=m;

do { x=x+n; y=y-1; } while(y!=0);

 

Niezmiennik jest to pewien warunek, który w ustalonym miejscu algorytmu jest zawsze prawdziwy. Tutaj można podać warunek, który jest prawdziwy na początku i na końcu każdego obrotu pętli while:

 

x = n * (m - y)

 

Sprawdźmy:

 

- Przed pierwszym obrotem pętli mamy x = 0, y = m, jeśli wstawimy to do naszego niezmiennika, to dostaniemy 0 = 0, czyli ok, niezmiennik jest prawdziwy

- Jeśli przed którymś z kolejnych obrotów pętli niezmiennik był prawdziwy, to widać że po zwiększeniu x o n i zmniejszeniu y o 1 (kod pętli) dalej będzie prawdziwy, bo zwiększamy lewą stronę niezmiennika o n, i prawą też zwiększamy o n (po prawej mamy n * "coś", i "coś" zwiększyło się o 1, bo y zmniejszyło się o 1)

 

I co nam to daje? Daje nam to tyle, że skoro w pewnym momecie y staje się w końcu 0 (po ostatnim obrocie pętli), a niezmiennik nadal jest zachowany (tak jak po każdym obrocie), to x = n * (m - y) = n * m. Czyli wnioskujemy, że "to" rzeczywiście mnoży.

 

Contrast: nie podaję maila, którego wpisałem Ci do komórki, bo nie chcę żeby "poszedł w świat" :) Ale to ja jestem :)

Udostępnij tę odpowiedź


Odnośnik do odpowiedzi
Udostępnij na innych stronach

Dzieki Bolu!!

A widzisz na to nie wpadłem , kombinowałem jak mnożnik zwiękrzyć od 1 do m , ale nie przyszło mi do głowy aby odjąć od niego y (m-y)!!

 

Ale na to wychodzi że moja teza z m*n to niezmiennik była prawdziwa choć metoda wnioskowania troche inna :mur:

Udostępnij tę odpowiedź


Odnośnik do odpowiedzi
Udostępnij na innych stronach

Dołącz do dyskusji

Możesz dodać zawartość już teraz a zarejestrować się później. Jeśli posiadasz już konto, zaloguj się aby dodać zawartość za jego pomocą.

Gość
Dodaj odpowiedź do tematu...

×   Wklejono zawartość z formatowaniem.   Przywróć formatowanie

  Dozwolonych jest tylko 75 emoji.

×   Odnośnik został automatycznie osadzony.   Przywróć wyświetlanie jako odnośnik

×   Przywrócono poprzednią zawartość.   Wyczyść edytor

×   Nie możesz bezpośrednio wkleić grafiki. Dodaj lub załącz grafiki z adresu URL.

Ładowanie


×
×
  • Dodaj nową pozycję...