Matura 2011 (maj). Zadanie 2. Potęgowanie

Dana jest następująca specyfikacja oraz algorytm obliczania potęgi o wykładniku naturalnym:

Specyfikacja:

Dane: liczba rzeczywista a oraz liczba naturalna n, n ≠ 0

Wynik: liczba rzeczywista p = aⁿ = a * a * a * … * a (n razy)

Algorytm:

krok 1. p = 1 , b = a
krok 2. dopóki n > 0 wykonuj:

a) jeśli a mod 2 ≠ 0, to p = p * b
b) b = b * b
c) n = n div 2

Uwaga:
n div 2 oznacza wynik dzielenia całkowitego n przez 2, a n mod 2 oznacza resztę z dzielenia całkowitego n przez 2.

1. Przeanalizuj podany algorytm i uzupełnij tabelę wartościami zmiennych p, b oraz n po kolejnych wykonaniach kroku 2 dla dowolnej początkowej wartości a oraz dla początkowej wartości zmiennej n równej 12.

Opis:
Algorytm w języku c++:

#include <iostream>
using namespace std;
int main()
{
  double a;
  int n;
  cout << "Podaj a: ";
  cin >> a;
  cout << "Podaj n: ";
  cin >> n;
  double p=1, b=a;
  cout << " n = " << n << " b = " << b << " p = " << p << endl;
  while (n>0) {
     if (n%2!=0) p=p*b;
     b=b*b;
     n=n/2;
  cout << " n = " << n << " b = " << b << " p = " << p << endl;
 }
 return 0;
}

Komentarz:
Z algorytmu wynika, iż zmienna b jest podnoszona do kwadratu, czyli b=b*b daje nam: a, a², a⁴, a⁸, a¹⁶, a³², itd. Pod b jest podstawiana wartość zmiennej a.
Pod zmienną n przypisywane jest dzielenie całkowite, tzn. dzielenie dwóch liczb całkowitych, gdzie wynikiem jest liczba całkowita.
n=12/2, n=6
n=6/2, n=3
n=3/2, n=1
n=1/2, n=0
Zmienna  p jest zwiększana, tylko wtedy gdy zmienna n jest nieparzysta oraz jest zwiększana tyle razy, ile ma wartość zmienna b w danym kroku.

2. Uzupełnij poniższą tabelę, wpisując liczby wszystkich mnożeń, wykonywanych przez powyższy algorytm dla podanych wartości n, tzn. liczby wykonanych instrukcji p = p * b i b = b * b.

Opis:
Algorytm w języku c++:

#include <iostream>
using namespace std;
int main()
{
  double a;
  int n;
  cout << "Podaj a: ";
  cin >> a;
  cout << "Podaj n: ";
  cin >> n;
  cout << "n = " << n;
  double p=1, b=a;
  int ile=0;
  while (n>0) {
    if (n%2!=0) {
       p=p*b;
       ile++;
    }
  b=b*b;
  ile++;
  n=n/2;
  }
  cout << " Mnozen = " << ile << endl;
  return 0;
}

Komentarz:
W naszym algorytmie mnożeń, czyli instrukcja b=b*b wykonywana jest tyle ile razy pętla while, zaś instrukcja p=p*b jest wykonywana tyle ile razy instrukcja if.

3. Podkreśl funkcję, której wartość jest równa liczbie mnożeń wykonywanych przez powyższy algorytm dla wartości n będącej potęgą dwójki:
   • ƒ(n) = 2 + log₂n
   • ƒ(n) = 1 + n
   • ƒ(n) = 2n² – 1
   • ƒ(n) = 2ⁿ

Opis:
rozwiązując funkcje dla n = 2, 3, 4, 5 ,6 daje nam:

ƒ(n) = 2 + log₂n
ƒ(2) = 2 + log₂2 = 2 + 1 = 3
ƒ(4) = 2 + log₂4 = 2 + 2 = 4

ƒ(n) = 1 + n
ƒ(2) = 1 + 2 = 3
ƒ(3) = 4
ƒ(4) = 5
ƒ(5) = 6
ƒ(6) = 7

ƒ(n) = 2n² – 1
ƒ(2) = 2 * 2² – 1 = 7
ƒ(3) = 17
ƒ(4) = 31
ƒ(5) = 49
ƒ(6) = 71

ƒ(n) = 2ⁿ
ƒ(2) = 2² = 4
ƒ(3) = 8
ƒ(4) = 16
ƒ(5) = 32
ƒ(6) = 64