poleca:

dla maturzysty

uczelnie

zadania z informatyki do części I egzaminu, p. rozszerzony - wskazówki, odpowiedzi

zadania z informatyki - Analiza algorytmów

Zadanie: 1 2 3 4 5 6 7 8 9 10

Zadanie 10.

Wiązka zadań Dzielenie wielomianu

Rozważamy wielomiany P(x) stopnia n − 1, gdzie n jest potęgą dwójki:
P(x) = a₀ + a₁x + a₂x² + ... + a_n–1 x^{n -1} , n = 2^m

Do obliczania wartości P(x) można zastosować technikę „dziel i zwyciężaj” w następujący sposób: dzielimy postać ogólną wielomianu P(x) na dwie części:

gdzie k = n/2. Jeśli w drugiej części wydzielimy czynnik x^k, to otrzymamy równość,
(*)P(x) = A(x) + B(x) ⋅ x^k
gdzie A(x) i B(x) (są wielomianami stopnia k − 1:
A(x) = a_k_{– 1}x^k^{– 1} + ... + a₂x² + a₁x + a₀
B(x) = a_n_{– 1}x^k^{– 1} + ... + a_k_{+ 2}x² + a_k_{+ 1}x + a_k

W ten sposób problem obliczenia wartości P(x) dzielimy na dwa podproblemy — obliczenia A(x) i obliczenia B(x) przy czym każdy z nich ma rozmiar o połowę mniejszy. Na przykład aby obliczyć wartość wielomianu (n = 8)
P(x) = –8 + 7x + 6x² – x³ + 4x⁴ + 5x⁵ – 2x⁶ + 3x⁷,
obliczamy

k = n/2 = 4,

A(x) = –8 + 7x + 6x² – x³

oraz

B(x) = 4 + 5x – 2x² + 3x³.

Następnie korzystamy ze wzoru P(x) = A(x) + B(x) ⋅ x⁴.
Ponieważ do pełnej realizacji algorytmu we wzorze (*) potrzebne jest obliczenie wartości x^k więc najpierw obliczamy wszystkie potęgi x, x², x⁴, ..., x^{2^{m – 1}} i zapamiętujemy je w tablicy Z[0 .. m – 1], np. za pomocą poniższej procedury.
Obliczanie tablicy Z[0..m – 1]:

Dane:
n — liczba całkowita postaci 2^m, gdzie m jest liczbą całkowitą nieujemną,
x — liczba rzeczywista.
Wynik:
tablica Z[0 ..m – 1], dla której Z[j] = x^{2^j}

Z[0] ← x
m ← 1
w ← 2
dopóki w < n wykonuj
Z[m] ← Z[m – 1] ⋅ Z[m – 1]
m ← m + 1
w ← 2 ⋅ w

Mając tablicę Z, obliczamy wartość P(x) za pomocą funkcji rekurencyjnej F.
Dane:
tablica liczb rzeczywistych T[0..n − 1] ze współczynnikami ܽa₀, a₁, ..., a_n – 1, gdzie n = 2^m, a m jest liczbą całkowitą nieujemną;
tablica Z[0..m – 1], dla której Z[j] = x^{2^j}.
Wynik:
wartość ܽa_n_{– 1}xⁿ^{– 1} + ... + a₂x² + a₁x + a₀.

funkcja F(T[0..n − 1]):
jeżeli n = 1
zwróć T[0] i zakończ
k ← n/2
A[0..k – 1] ← T[0..k – 1]
B[0..k – 1] ← T[k..n – 1]
zwróć F(A) + F(B) ⋅ Z[m – 1] i zakończ

Prześledźmy na przykład obliczenie wartości wielomianu
P(x) = –8 + 7x + 6x² – x³ + 4x⁴ + 5x⁵ – 2x⁶ + 3x⁷, (n = 2^m m = 3) dla x = 3.

W pierwszym kroku algorytm obliczy tablicę Z[0..2]:
ܼZ[0] = 3, Z[1] = 3², Z[2] = 3⁴ = 81.

Następnie algorytm obliczy F([-8,7,6,-1,4,5,-2,3]), tzn.

F([-8,7,6,-1,4,5,-2,3]) = F([-8,7,6,-1]) + F([4,5,-2,3])*Z[2]

Obliczanie F([4,5,-2,3]) i F([-8,7,6,-1]) odbywa się w analogiczny sposób, tzn.
F([-8,7,6,-1]) = F([-8,7])+ F([6,-1])*Z[1]
= F([-8])+F([7])*Z[0]+(F([6])+F([-1])*Z[0])*Z[1]
= (-8)+7*Z[0] + (6+(-1)*Z[0])*Z[1]
= (-8)+7*3+(6+(-1)*3)*9 = 40,

F([4,5,-2,3]) = F([4,5])+F([-2,3])*Z[1]
= F([4])+F([5])*Z[0]+(F([-2])+F([3])*Z[0])*Z[1]
= 4+5*Z[0]+((-2)+3*Z[0])*Z[1]
= 4+5*3+((-2)+3*3)*9=82.

Zatem

F([-8,7,6,-1,4,5,-2,3]) = F([-8,7,6,-1])+F([4,5,-2,3])*Z[2] = 40+82*81 = 6682.

Można zauważyć, że podczas obliczania F([-8,7,6,-1,4,5,-2,3]) łącznie zostanie wykonanych 7 mnożeń:
• 3 mnożenia podczas obliczania F([-8,7,6,-1])=40,
• 3 mnożenia podczas obliczania F([4,5,-2,3])=82,
• 1 mnożenie przy obliczaniu F([-8,7,6,-1])+ F([4,5,-2,3])*Z[2] = 40+82*Z[2].

Liczba wszystkich wywołań rekurencyjnych jest równa 15. Oto wszystkie wywołania funkcji F:
• F([-8,7,6,-1,4,5,-2,3])
o F([-8,7,6,-1])
▪ F([-8,7])
• F([-8])
• F([7])
▪ F([6,-1])
• F([6])
• F([-1])
o F([4,5,-2,3])
▪ F([4,5])
• F([4])
• F([5])
▪ F([-2,3])
• F([-2])
• F([3])

Zadanie 10.4.

Do obliczania wartości wielomianu P(x)
P(x) = a₀ + a₁x + a₂x² + ... + a_n_{– 1}xⁿ^{– 1}
(n = 3^m)
a więc gdy n jest potęgą trójki, można zastosować podział na trzy części

gdzie ݇k = n/3. Wówczas uzyskujemy
P(x) = A(x) + B(x) ⋅ x^k + C(x) ⋅ x^2k = (A(x) + B(x) + C(x) ⋅ x^k) ⋅ x^k
gdzie A(x), B(x), C(x) są wielomianami, w których liczba współczynników jest trzykrotnie mniejsza niż w wyjściowym wielomianie P(x).

Wzorując się na funkcji F, możemy skonstruować rekurencyjną funkcję G(T[0..n – 1]), obliczającą wartość P(x) przez podział tablicy T na trzy równe części, o ile n > 1. Po obliczeniu trzech wyników dla każdej z części, powiedzmy A(x), B(x), C(x)funkcja oblicza swój wynik, wykonując dodatkowo dwa mnożenia:
• jedno mnożenie przy obliczaniu C(x) ⋅ x^k
• jedno mnożenie przy obliczaniu (B(x) + C(x) ⋅ x^k) ⋅ x^k

Podobnie jak poprzednio pomijamy problem obliczania potęg x^k dla k =3^j (j ≥ 0), tzn. przyjmujemy, że potęgi te są przechowywane w pewnej tablicy Z[0 .. m – 1], a więc ich obliczanie nie jest wliczane do kosztu obliczeniowego funkcji G.

W ten sposób na przykład dla n = 3 funkcja G wykona dokładnie 2 mnożenia, a dla n = 9 funkcja wykona łącznie 8 mnożeń:
• po 2 mnożenia dla każdej z trzech części A(x), B(x), C(x)
• jedno mnożenie przy obliczaniu C(x) ⋅ x^k
jedno mnożenie przy obliczaniu (B(x) + C(x) ⋅ x^k) ⋅ x^k

Uzupełnij poniższą tabelkę, podając liczbę mnożeń, jaka zostanie wykonana przez funkcję G dla n-elementowej tablicy współczynników T.

n	Liczba operacji mnożenia
3	2
9	8
27
81
243

pokaż wskazówkę »

pokaż odpowiedź

Udostępnij

« powrót

źródło: CKE

Reklama - Wykorzystajmy wspólnie nasz potencjał! • Kontakt • Patronat • Praca dla studentów •