Hej,
policzyłem to zadanie i przepisałem algorytm w C (jeśli znasz to skopiuj i sprawdź działanie) i wg mnie to odpowiedzi do 3.3 powinny wyglądać tak:
1. 1
2. 1
3. 2
4. 3
5. 4
6. 2
Sprawdzałem to kilka razy, ale najlepiej gdyby ktoś to jeszcze policzył.
Funkcja F(4,9) wywołuje F(4,3), później F(4,3) wywołuje F(4,1), F(4,1) odpowiada, że wynosi 4 i wracamy.... F(4,3) przypisujemy do k i zwracamy k * k * k (pierwsza gwiazdka *) do F(4,9) jako wynik. F(4,9) przypisuje wynik znowu do k i zwraca tak jak poprzednio k * k * k (druga gwiazdka *) czyli mamy (k * k * k)^2 czyli k^9.
Poniżej masz kod:
//Potęgowanie rekurencyjne
//F(x,n)
#include <stdio.h>
int pow( int x, int n);
int *wsk1, *wsk2, count_1 = 0, count_2 = 0;
int main()
{
int wynik;
printf("--------------\n");
wynik = pow(2,2);
printf("Odpowiedź: %d\n", wynik);
printf("Liczba mnożen * = %d oraz ** = %d\nSuma mnożeń = %d\n", *wsk1,
*wsk2, *wsk1 + *wsk2);
*wsk1 = 0;
*wsk2 = 0;
printf("--------------\n");
wynik = pow(2,3);
printf("Odpowiedź: %d\n", wynik);
printf("Liczba mnożen * = %d oraz ** = %d\nSuma mnożeń = %d\n", *wsk1,
*wsk2, *wsk1 + *wsk2);
*wsk1 = 0;
*wsk2 = 0;
printf("--------------\n");
wynik = pow(3,4);
printf("Odpowiedź: %d\n", wynik);
printf("Liczba mnożen * = %d oraz ** = %d\nSuma mnożeń = %d\n", *wsk1,
*wsk2, *wsk1 + *wsk2);
*wsk1 = 0;
*wsk2 = 0;
printf("--------------\n");
wynik = pow(4,7);
printf("Odpowiedź: %d\n", wynik);
printf("Liczba mnożen * = %d oraz ** = %d\nSuma mnożeń = %d\n", *wsk1,
*wsk2, *wsk1 + *wsk2);
*wsk1 = 0;
*wsk2 = 0;
printf("--------------\n");
wynik = pow(4,8);
printf("Odpowiedź: %d\n", wynik);
printf("Liczba mnożen * = %d oraz ** = %d\nSuma mnożeń = %d\n", *wsk1,
*wsk2, *wsk1 + *wsk2);
*wsk1 = 0;
*wsk2 = 0;
printf("--------------\n");
wynik = pow(4,9);
printf("Odpowiedź: %d\n", wynik);
printf("Liczba mnożen * = %d oraz ** = %d\nSuma mnożeń = %d\n", *wsk1,
*wsk2, *wsk1 + *wsk2);
return 0;
}
int pow( int x, int n)
{
int k, result;
wsk1 = &count_1;
wsk2 = &count_2;
if( n == 1) {
return x;
}
else {
if( n % 3 == 0) {
k = pow( x, n / 3 );
result = k * k * k;
++count_1;
printf("*\n\n");
return result;
}
else {
++count_2;
printf("**\n\n");
return x * pow(x , n-1);
}
}
}