Briker Opublikowano 3 Czerwca 2005 Zgłoś Opublikowano 3 Czerwca 2005 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 Cytuj Udostępnij tę odpowiedź Odnośnik do odpowiedzi Udostępnij na innych stronach Więcej opcji udostępniania...
civi Opublikowano 3 Czerwca 2005 Zgłoś Opublikowano 3 Czerwca 2005 Nie posiadam żadnej wiedzy z analizy teoretycznej algorytmów ale zgadujmy: n ? Cytuj Udostępnij tę odpowiedź Odnośnik do odpowiedzi Udostępnij na innych stronach Więcej opcji udostępniania...
Domik Opublikowano 3 Czerwca 2005 Zgłoś Opublikowano 3 Czerwca 2005 czyżby for :>? Cytuj Udostępnij tę odpowiedź Odnośnik do odpowiedzi Udostępnij na innych stronach Więcej opcji udostępniania...
Artur.M Opublikowano 3 Czerwca 2005 Zgłoś Opublikowano 3 Czerwca 2005 NIe wiem czy dobrze rozumię o co tu chodzi ale wydaje mi się że jako y trzeba podać wartość 1 PS> To by było za proste. Jak mi wytłumaczysz o co chodzi to może pomogę. Cytuj Udostępnij tę odpowiedź Odnośnik do odpowiedzi Udostępnij na innych stronach Więcej opcji udostępniania...
Contrast Opublikowano 3 Czerwca 2005 Zgłoś Opublikowano 3 Czerwca 2005 m*n Zawsze wynik pod X będzie równy m*n to by było sensowną odpowiedzią chyba... Bo niezmiennik pętli: x:=1;n:=N; While(n>0) {x:= x*n ; n:= n-1;} Jest równy x*n!= N! Cytuj Udostępnij tę odpowiedź Odnośnik do odpowiedzi Udostępnij na innych stronach Więcej opcji udostępniania...
Briker Opublikowano 3 Czerwca 2005 Zgłoś Opublikowano 3 Czerwca 2005 "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: Cytuj Udostępnij tę odpowiedź Odnośnik do odpowiedzi Udostępnij na innych stronach Więcej opcji udostępniania...
Contrast Opublikowano 3 Czerwca 2005 Zgłoś Opublikowano 3 Czerwca 2005 Niezmiennik gwarantuje poprawną inicjalizacje oraz zachowuje ostatni warunek....(tak chyba jest) A pozatym zajrzyj: http://www.ipipan.gda.pl/~stefan/Dydaktyka...ajdy/04-19a.pdf Cytuj Udostępnij tę odpowiedź Odnośnik do odpowiedzi Udostępnij na innych stronach Więcej opcji udostępniania...
Briker Opublikowano 4 Czerwca 2005 Zgłoś Opublikowano 4 Czerwca 2005 No to pomoże mi ktoś, bo kompletnie nie wiem co to może być :cry: Cytuj Udostępnij tę odpowiedź Odnośnik do odpowiedzi Udostępnij na innych stronach Więcej opcji udostępniania...
bolu Opublikowano 4 Czerwca 2005 Zgłoś Opublikowano 4 Czerwca 2005 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 :) Cytuj Udostępnij tę odpowiedź Odnośnik do odpowiedzi Udostępnij na innych stronach Więcej opcji udostępniania...
Contrast Opublikowano 5 Czerwca 2005 Zgłoś Opublikowano 5 Czerwca 2005 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: Cytuj Udostępnij tę odpowiedź Odnośnik do odpowiedzi Udostępnij na innych stronach Więcej opcji udostępniania...