Strefa wyzwań - PYI_R_W14_M30 Schemat Hornera - efektywna metoda obliczania wartości wielomianów

R1GFQ6NNTMUDK

Już wiesz

Jak działa schemat Hornera zapisany iteracyjnie i rekurencyjnie.
Jak zapisać za pomocą pseudokodu obie wersje algorytmu. obliczającego wartość wielomianu z wykorzystaniem schematu Hornera oraz jak dokonać ich analizy.
Jak zaimplementować algorytm w języku programowania.

Teraz czas sprawdzić swoją wiedzę i umiejętności w praktyce.

Ćwiczenie 1

R5V1O2CP7OETX

Uzupełnij pseudokod.

Wyświetl „Podaj stopień wczytywanego wielomianu: "

StopienWielomianu <- dane z klawiatury

1. wynik <- wynik * x + wspolczynniki[i], 2.     Wyświetl i, 3. dla i = 0, 1, 2 ... StopienWielomianu wykonuj, 4. x <- dane z klawiatury

	Wyświetl "Podaj "

1. wynik <- wynik * x + wspolczynniki[i], 2.     Wyświetl i, 3. dla i = 0, 1, 2 ... StopienWielomianu wykonuj, 4. x <- dane z klawiatury

    Wyświetl "współczynnik"

    wspolczynniki[i] <- dane z klawiatury

Wyswietl „Podaj argument, dla którego chcesz obliczyć wielomian:”

1. wynik <- wynik * x + wspolczynniki[i], 2.     Wyświetl i, 3. dla i = 0, 1, 2 ... StopienWielomianu wykonuj, 4. x <- dane z klawiatury

wynik <- wspolczynniki[0]

dla i = 1,2,3... StopienWielomianu wykonuj:

	1. wynik <- wynik * x + wspolczynniki[i], 2.     Wyświetl i, 3. dla i = 0, 1, 2 ... StopienWielomianu wykonuj, 4. x <- dane z klawiatury

Uzupełnij pseudokod.

Wyświetl „Podaj stopień wczytywanego wielomianu: "

StopienWielomianu <- dane z klawiatury

1. wynik <- wynik * x + wspolczynniki[i], 2.     Wyświetl i, 3. dla i = 0, 1, 2 ... StopienWielomianu wykonuj, 4. x <- dane z klawiatury

	Wyświetl "Podaj "

1. wynik <- wynik * x + wspolczynniki[i], 2.     Wyświetl i, 3. dla i = 0, 1, 2 ... StopienWielomianu wykonuj, 4. x <- dane z klawiatury

    Wyświetl "współczynnik"

    wspolczynniki[i] <- dane z klawiatury

Wyswietl „Podaj argument, dla którego chcesz obliczyć wielomian:”

1. wynik <- wynik * x + wspolczynniki[i], 2.     Wyświetl i, 3. dla i = 0, 1, 2 ... StopienWielomianu wykonuj, 4. x <- dane z klawiatury

wynik <- wspolczynniki[0]

dla i = 1,2,3... StopienWielomianu wykonuj:

	1. wynik <- wynik * x + wspolczynniki[i], 2.     Wyświetl i, 3. dla i = 0, 1, 2 ... StopienWielomianu wykonuj, 4. x <- dane z klawiatury

Ćwiczenie 2

RKQCAN3A2HQ51

Ćwiczenie 3

R1N4F8ZG69NHX

Wskaż, ile razy zostanie wywołana funkcja rekurencyjna Horner() dla wielomianu o stopniu 5. Możliwe odpowiedzi: 1. 5, 2. 4, 3. 6, 4. 8

Ćwiczenie 4

R3ZNXD3X4RXQ3

Ćwiczenie 5

RO6GBMC7SECLO

Ćwiczenie 6

R1U28R6VT2UQG

Ćwiczenie 7

Zapoznaj się z pseudokodem i wykonaj ćwiczenie.

funkcja Horner(wspolczynniki[], StopienWielomianu, x)
	jeżeli StopienWielomianu = 0
    	zwróć x * Horner(wspolczynniki,StopienWielomianu ‑ 1,x)
    w przeciwnym razie 
		zwróć wspolczynniki[0]

StopienWielomianu <- dane z klawiatury
dla i = 1,2,3... StopienWielomianu wykonuj
	Wyświetl "Podaj współczynnik"
    wspolczynniki[i] <- dane z klawiatury
Wyswietl "Podaj argument, dla którego chcesz obliczyć wartość wielomianu:"
x <- dane z klawiatury
wynik <- Horner(wspolczynniki[],StopienWielomianu,x)
Wyświetl "Wynik = "
Wyświetl x

R163SLX5EFAON

Przykładowe rozwiązanie:

funkcja Horner(wspolczynniki[], StopienWielomianu, x)
	jeżeli StopienWielomianu = 0
    	zwróć wspolczynniki[0]
    w przeciwnym razie 
    	zwróć x * Horner(wspolczynniki,StopienWielomianu ‑ 1,x) + wspolczynniki[StopienWielomianu]
        StopienWielomianu <- dane z klawiatury
dla i = 0,1,2... StopienWielomianu wykonuj
	Wyświetl "Podaj współczynnik"
    wspolczynniki[i] <- dane z klawiatury
Wyswietl "Podaj argument, dla którego chcesz obliczyć wartość wielomianu:"
x <- dane z klawiatury
wynik <- Horner(wspolczynniki[],StopienWielomianu,x)
Wyświetl "Wynik = "
Wyświetl wynik

Ćwiczenie 8

Przedstawione zadanie zostało opracowane przez Centralną Komisję Egzaminacyjną i weszło w skład zbioru zadań przygotowujących do egzaminu maturalnego w roku 2015.

Wielomianem parzystym nazywamy wielomian stopnia 2n postaci:

$R_{(x)} = a_{n} x^{2 n} + a_{n - 1} x^{2 n - 2} + \dots + a_{2} x^{2} + a_{0}$

tzn. taki, w którym występują tylko parzyste potęgi zmiennej.

Bazując na schemacie Hornera, zdefiniuj funkcję testowa(stopien, lista_wsp, argument), która dla podanego zestawu parametrów oblicza wartość parzystego wielomianu.

Dane wejściowe:

n - liczba całkowita >= 0 (stopień wielomianu)
x - liczba rzeczywista (argument)
a... - liczby rzeczywiste (wspólczynniki wielomianu)

Wynik:

${Wartość R}_{(x)}$

Przykładowe wykonania:

print(testowa(3, [3, 2, 1, 0], 1))
6
print(testowa(3, [1, 1, 1, 0], 2.1))
109.624221
print(testowa(3, [1, 1, 1, 0], 5))
16275
print(testowa(3, [6, 8, -2, 23], 1))
35
print(testowa(3, [3, 2, 1, 0], 2))
228

R150GRMBlTbFm

Twoje zadania: 1. Zdefiniowanie funkcji testowa(stopien, lista_wsp, argument), działającej zgodnie z opisem. 2. Sprawdzenie, czy funkcja dla parametrów 3, [6, 8, -2, 23], 2 zwraca wartość 527. 3. Sprawdzenie, czy funkcja dla parametrów 3, [6, 8, -2, 23], 5 zwraca wartość 98723. 1. def testowa(stopien, lista_wsp, argument): 2. # tutaj dodaj własny kod 3. return None 4. 5. # niżej podaj przykład wywołania funkcji 6. wynik = testowa(3, [6, 8, -2, 23], 2) 7. print(wynik) 8. print(wynik==527) 9. # 10. wynik = testowa(3, [6, 8, -2, 23], 5) 11. print(wynik) 12. print(wynik==98723)

def testowa(stopien, lista_wsp, argument):
	# tutaj dodaj własny kod
	return None

# niżej podaj przykład wywołania funkcji
wynik = testowa(3, [6, 8, -2, 23], 2)
print(wynik)
print(wynik==527)
#
wynik = testowa(3, [6, 8, -2, 23], 5)
print(wynik)
print(wynik==98723)

Wskazówką do rozwiązania zadania jest obserwacja, że:

$R (x) = P (y), gdzie y = x^{2}$

Oznacza to, że wyznaczenie wartości R(x) można zrealizować bardzo efektywnie za pomocą schematu Hornera (zastosowanego do powyższego wielomianu P(Y)), ale nie dla wyjściowej wartości x, lecz dla x*x. Rozwiązanie uzyskujemy zatem, modyfikując podany schemat Hornera (obliczania wartości P(Y)) poprzez dodanie na początku instrukcji:

x = x * x

Zatem musimy „obudować” funkcję obliczającą schemat Hornera, aby do samych obliczeń użyć już wartości x^2

def testowa(stopien, lista_wsp, argument):

    def horner(stopien, lista_wsp, argument):
        if stopien == 0:
            return lista_wsp[stopien]
        else:
            return argument * horner(stopien - 1, lista_wsp, argument) + lista_wsp[stopien]

    argument = argument * argument
    return horner(stopien, lista_wsp, argument)
    
    
wynik = testowa(3, [6, 8, -2, 23], 2)
print(wynik)
print(wynik==527)
print(type(wynik) is int)
wynik = testowa(3, [6, 8, -2, 23], 5)
print(wynik)
print(wynik==98723)
print(type(wynik) is int)

Plik z programem do pobrania:

R17ER1UCZ7NU1

Plik zawiera rozwiązanie ćwiczenia w języku Python.

Plik TXT o rozmiarze 565.00 B w języku polskim

Ćwiczenie 9

Zdefiniuj funkcję suma_poteg(lista_elementow), która obliczy sumę potęg kolejnych elementów listy, gdzie podstawą będzie element, a wykładnikiem indeks tego elemenu w liście.

Elementy listy muszą być typu int lub float. Jeśli którykolwiek z elementów listy będzie innego typu, funkcja powinna zwrócić wartość False.

Przykładowe wywołania:

print(suma_poteg([2.01, 4.3, 5.4]))
34.46
print(suma_poteg([1, 22, 33, 5.01]))
1237.751501
print(suma_poteg([53245324.03, 2, 4.5, 5]))
148.25
print(suma_poteg([53245324.03, "A", 4.5, 5]))
False

R1XugM4B5qQpJ

Twoje zadania: 1. Zdefiniowanie funkcji suma_poteg(). 2. Sprawdzenie, czy funkcja suma_poteg() poprawnie zwraca wartość False dla ustalonych parametrów. 3. Sprawdzenie, czy funkcja suma_poteg() poprawnie zwraca wartość dla ustalonych parametrów. Kod: 1. def suma_poteg(lista): 2. # tutaj Twój kod 3. return None 4. 5. # tu przykładowe wywołania 6. print(suma_poteg([-2, -3, -4, 1])) 7. print(suma_poteg([-2, "3", -4, 1])) 8. print(suma_poteg([-2, -3.5, -4, 1.4]))

def suma_poteg(lista):
	# tutaj Twój kod
	return None

# tu przykładowe wywołania
print(suma_poteg([-2, -3, -4, 1]))
print(suma_poteg([-2, "3", -4, 1]))
print(suma_poteg([-2, -3.5, -4, 1.4]))

def suma_poteg(lista):
	for e in lista:
		if type(e) is not int and type(e) is not float:
			return False

	wynik = 0

	for x, a in enumerate(lista):
		wynik += a ** x

	return wynik

# przykładowe wykonania
print(suma_poteg([-2, -3, -4, 1]))
# 15
print(suma_poteg([-2, "-3", -4, 1]))
# False
print(suma_poteg([-2, -3.5, -4, 1.4]))
# 16.244

Plik z programem do pobrania:

R6F4L5AC3KVE5

Plik zawiera rozwiązanie ćwiczenia w języku Python.

Plik TXT o rozmiarze 361.00 B w języku polskim

Ćwiczenie 10

Zdefiniuj funkcję iloczyn_poteg_odwrotny(lista_elementow), która obliczy iloczyn potęg kolejnych elementów listy (w której przede wszystkim należy odwrócić ich kolejność), gdzie podstawą będzie element, a wykładnikiem indeks tego elementu w liście.

Elementy listy muszą być typu int lub float. Jeśli którykolwiek z elementów listy będzie innego typu, funkcja powinna zwrócić wartość False.

Przykładowe wywołania:

print(iloczyn_poteg_odwrotny([2, 0, 1]))
0     
print(iloczyn_poteg_odwrotny([-2, -3, -4, "A"]))
False
print(iloczyn_poteg_odwrotny([2, 1, 1]))
4    
print(iloczyn_poteg_odwrotny([2, 20.3, 324432]))
81.2      
print(iloczyn_poteg_odwrotny([3, 4, 20, 0]))
8640

RGDkYyzcfRPZm

Twoje zadania: 1. Zdefiniowanie funkcji iloczyn_poteg_odwrotny(). 2. Sprawdzenie, czy funkcja iloczyn_poteg_odwrotny() poprawnie zwraca wartość False dla ustalonych parametrów. 3. Sprawdzenie, czy funkcja iloczyn_poteg_odwrotny() poprawnie zwraca wartość dla ustalonych parametrów. Kod: 1. def iloczyn_poteg_odwrotny(lista): 2. # tutaj Twój kod 3. return None 4. 5. # tu przykładowe wywołania 6. print(iloczyn_poteg_odwrotny([-2, -3, -4, 1])) 7. print(iloczyn_poteg_odwrotny([-2, "3", -4, 1])) 8. print(iloczyn_poteg_odwrotny([-2, -3.5, -4, 1.4]))

def iloczyn_poteg_odwrotny(lista):
	# tutaj Twój kod
	return None

# tu przykładowe wywołania
print(iloczyn_poteg_odwrotny([-2, -3, -4, 1]))
print(iloczyn_poteg_odwrotny([-2, "3", -4, 1]))
print(iloczyn_poteg_odwrotny([-2, -3.5, -4, 1.4]))

def iloczyn_poteg_odwrotny(lista):
	for e in lista:
		if type(e) is not int and type(e) is not float:
			return False

	lista = lista[::-1] # odwracamy kolejność
	wynik = 1

	for x, a in enumerate(lista):
		wynik = wynik * (a ** x)

	return wynik

# przykładowe wykonania
print(iloczyn_poteg_odwrotny([-2, -3.5, -4, 1.4]))
# 392.0
print(iloczyn_poteg_odwrotny([-2, -3, -4, "A"]))
# False

Plik z programem do pobrania:

R144GXEUVEXO4

Plik zawiera rozwiązanie ćwiczenia w języku Python.

Plik TXT o rozmiarze 409.00 B w języku polskim

Misja: Ćwicz i zwyciężaj

Misja matura: zadanie 1