dziel i rządź

warning: Creating default object from empty value in /usr/share/drupal6/modules/taxonomy/taxonomy.pages.inc on line 33.

Ćwiczenia 1: poprawność i złożność algorytmu

Zadanie 1 (Potęgowanie binarne)

Zaprojektuj algorytm, który dla danych nieujemnej liczby całkowitej \( \displaystyle n \) i liczby całkowitej \( \displaystyle a \), policzy wartość \( \displaystyle a^n \). Przyjmij za operację dominującą mnożenie dwóch liczb całkowitych i w tym modelu:

  1. zaproponuj algorytm działający w czasie \( \displaystyle O(\log n) \),
  2. udowodnij poprawność swojego algorytmu metodą niezmienników.

Zadanie 2 (Liczby Fibonacciego)

Liczby Fibonacciego definiuje się jak następuje:

Subskrybuje zawartość