Całkowita poprawność programu - prośba o wytłumaczenie

0

Wykaż całkowitą poprawność programu (tj. wykaż częściową poprawność oraz wskaż zbieżnik pętli uzasadniając, dlaczego program się zatrzymuje). Zaproponuj specyfikację. Oblicz liczbę wykonywanych przez funkcję operacji arytmetycznych o na tej podstawie oszacuj pesymistyczną (O-duże) złożoność obliczeniową.

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



Wytłumaczy mi ktoś jak liczyć tą całkowitą poprawność programu i jak proponować specyfikację do tego?

0
int potega(int a, int b) 
{                                                      //3 + 5n  liczba wykonywanych przez funkcję operacji
     int i = 0;         // 1
     int y = 1;          // 1
     while(i <= b)        // 1
     {
          y = y * a;       // 2
          i = i + 1;        // 2
     }
     return y;               // 1
}

Czyli tak ma być?

0

Chciałem zrobić jedno i drugie na raz tam

1

Jakbyś to Przepisał tak:

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

To za jednym zamachem Masz oszacowaną złożoność O(n), (w tym przypadku O(b)), oraz zbieżnik. Aby udowodnić całkowitą poprawnośc pozostaje znaleźć niezmiennik.

0

Czyli niezmiennik to i = i + 1?

0

Tutaj: http://sesjawpigulce.cba.pl/?notatka=niezmienniki-i-zbiezniki jest to wytłumaczone, więc nie muszę się powtarzać.

0

Nie wiem czy dobrze to zrozumiałem czy coś pokręciłem ale wydaje mi się, że będzie y^i=y*a^b

0

Nie jestem pewien, najlepiej, Przepisz program, tak jak oni to zrobili (oczywiście Zostaw Swoje liczenie w pętli - tam mają inny algorytm) i Będziesz miał taki sam niezmiennik.

0

Skoro tam jest tak : z^m * y = x^n to tu nie będzie i^y*y=a^b ?

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