zbieżnik jak znaleźć

0

majać taka funkcje

int potega(int a, int b) 
{
     int i = 0;
     int y = 1;
     while(i != b)
     {
          y = y * a;
          i = i + 1;
     }
     return y;
}

Jak znaleźć zbieżnik? wiem ze algorytm musi osiągnąć swój punkt końcowy i zatrzymac się poprawnie.. patrząc na pierwszy rzut oka to zatrzyma się gdy i=b, ale watpie ze to o to chodzi, proszę o pomoc

1

Zbieżnik zapewnia nas, że algorytm się zatrzyma. Z definicji (dla pętli) jest to wielkość, która zmniejsza się po każdej iteracji. Inaczej, jak Znajdziesz zbieżnik, to Wiesz, że algorytm się zatrzyma. Tutaj może to być, b - i.

EDIT: Zgodnie z postem poniżej, ostatnie zdanie powinnno wyglądać:
Tutaj, przy założeniu, b całkowite i b >= 0 może to być, b - i.

1

Tu tak różowo chyba nie ma, bo co jeśli b=-2, pewnie się przepełni zakres i "zbieżnik" będzie miał falę wzrostu.

0

a można prosić o jakies uzasadnienie ? bo chciałbym to zrozumieć a samo napisanie

b-i

nie wiele mi mowi :)

0

Zajrzyj do tych linków: https://4programmers.net/Forum/C_i_C++/322112-calkowita_poprawnosc_programu_prosba_o_wytlumaczenie?p=1564079#id1564079 . to Ci sie trochę rozjaśni. b - i dlatego, że to spełnia definicję zbieżnika (zmniejsza się przy każdej iteracji), mogłem też wybrać -i. BTW, nie Jesteście czasem z tej samej klasy?:)

0

nie potrafie tego zrozumieć...

b-i

mam to gdzies w kodzie umiescic i sprawdzic czy program sie zatrzyma?

1

"Zbieżnik jest bezpośrednio związany z podstawową własnością poprawnego algorytmu – własnością zatrzymywania się. Własność zatrzymywania się oznacza, że algorytm istotnie osiągnie swój punkt końcowy i zatrzyma się poprawnie. W celu udowodnienia tej własności należy znaleźć pewną wielkość (zbieżnik) zależną od zmiennych i struktur danych algorytmu i wykazać, że zmierza do osiągnięcia określonej wartości progowej będącej warunkiem stopu."
Masz to udowodnić analizując algorytm. Możesz też to empirycznie pokazać, zmieniając warunek w pętli na: while (b - i > 0).

1 użytkowników online, w tym zalogowanych: 0, gości: 1