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

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 = an = 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.
   b   n 
 1  a  12
 1  a2 6
 1 a4 
 a4 a8 
a12  a16 

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, a2, a4, a8, a16, a32, 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.

  1. 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.
n liczba mnożeń
2 3
3
4
5
6
7

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.

  1. 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 + log2n
    • ƒ(n) = 1 + n
    • ƒ(n) = 2n2 – 1
    • ƒ(n) = 2n

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

ƒ(n) = 2 + log2n
ƒ(2) = 2 + log22 = 2 + 1 = 3
ƒ(4) = 2 + log24 = 2 + 2 = 4

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

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

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

Leave a Reply

Twój adres email nie zostanie opublikowany. Pola, których wypełnienie jest wymagane, są oznaczone symbolem *

You may use these HTML tags and attributes:

<a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>