Laboratorium 7: Trochę programowania

Wojciech Myszka

1 Wstęp

Tak nieszczęśliwie się złożyło, że niektóre grupy będą miały siedem laboratoriów inne zaś osiem (co zależy od parzystości tygodnia).

Zatem ostatnie laboratorium (ostatnie dwa laboratoria) poświęcone będą programowaniu w języku Python.

Tematyka zajęć w kolejnym semestrze będzie obejmowała programowanie w języku C — nie powinien to być specjalny problem.

Studenci na zajęciach siódmych rozpoczynają realizację zadań od „wprawek” (rozdział 2), a następnie kontynuują zadania do wykonania (rozdział 3) tyle ile dadzą rady. Im kto więcej zrobi tym lepsza ocena.

Zatem dla tych, którzy istotnie mają zajęcia ósme:

powinny być one potraktowane w pierwszej kolejności jako zajęcia „odróbkowe”
można też kontynuować zadania z laboratorium siódmego.

1.1 Cel laboratorium

Celem laboratorium jest zmierzenie się z (nowym?) językiem programowania i zaprogramowanie bardzo prostych problemów. Przy czym chciałbym aby samo programowanie poprzedzone było narysowaniem prostego schematu blokowego. Jako podstawowy zestaw bloków stosowanych na schematach blokowych można przyjąć ten z Wikipedii.

1.2 Wymagania

Zapoznanie się z elementarną dokumentacją programu Python (instrukcja laboratoryjna nr 4 [1] i/lub bardziej zaawansowaną dokumentacją po polsku dostępną on-line [2].

1.3 Materiały

1.3.1 Funkcje

Bardzo często programując w jakimś języku programowania musimy skorzystać z jakiejś funkcji. Python dostarcza bardzo wiele funkcj, a na przykłąd najbardzie podstawowe funkcje matematyczne dostępne są w module math. Na początkuy programu piszemy:

import math

a poźniej możemy z funkcji korzystać swobodnie:

print math.sin(30.∗math.pi/180.)

(Sprawdź jaki będzie wynik!)

Mozemy również zdeﬁniować własną funkcję. Będzie to funkcja $f(x) = 3x2 − 5x+ 2$ . (Zwracam uwagę na wcięcie!)

def f(x):
    a = 3.
    b = −5.
    c = 2.
    return a ∗ x∗x + b ∗ x + c

Po jej zdeﬁniowaniu możemy już funkcji używać:

print f(1)

albo

z = 5 + f(10)

albo

for x in range (−10, 11):
print x, „:”, f(x)

W powyższym przykładzie x jest zmienną niezależną (tak jak w funkcji $sin (x )$ ), a polecenie return powoduje wyliczenie wartości i „podstawienie jej pod f(x)”. Funkcję można zdeﬁniować również tak:

def f(x):
    a = 3.
    b = −5.
    c = 2.
    y = a ∗ x∗x + b ∗ x + c
    return y

Teraz polecenie return zwraca (wyliczoną wcześniej) wartość y jako wartość funkcji f(x).

1.3.2 Rekurencja

Poniżej rekurencyjna deﬁnicja funkcji silnia

def silnia(n):
    if n == 0:
        return 1
    else:
        return n∗silnia(n−1)

Sprawdź czy funkcja działa.

2 Struktura laboratorium

Zaczynamy od wprawek.

Co robi ta instrukcja? Jaki będzie wyniki? Sprawdź! Zobacz co się będzie działo gdy zmienisz wartość a (na ujemną, na przykład). (Poniżej ␣ oznacza odstęp.)
a = 5
if a > 0:
print „a␣dodatnie!”
else:
print „a␣ujemne!”

Zmodyﬁkuj program tak, by rozpoznawał przypadek gdy a jest równe zero i informował o tym.
Co robi ten program? Jaki będzie wynik?
for i in range(7, 9)
print i

Zmodyﬁkuj go tak aby drukował tablicę funkcji $2 x$ dla $x$ zmieniającego się od -10 do 10 włącznie.
Co robi poniższy program?
a = 1536
while a%2 == 0:
    a = a/2
    print a

Przy okazji, jaki będzie wynik programu?

while 1:
   print „Dosc!”

A tego:

while 0:
   print „Dosc!”

Peksperymentuj i opisz działanie instrukcji while.

3 Zadania do wykonania

3.1 Rekurencyje wyliczanie wartości Największego Wspólnego Dzielnika

Wariant rekurencyjny wyznaczania NWD wygląda jakoś tak: $gcd(k,n) = n$ gdy $k = 0$ natomiast $gcd(k,n) = gcd(n mod k,k)$ gdy $k > 0$ .

Zadania

Zaprogramuj w Pythonie funkcję gcd.
Porównaj wyniki liczone każdą z trzech metod.

3.2 Ciąg Fibonacciego

Ciąg Fibonacciego jestjednym z wielu przykładów „operacji” zdeﬁniowanej rekurencyjnie.

Zadaniem jest zaprogramowanie (w Pythonie) rekurencyjnej funkcji wyliczającej zadany wyraz ciągu.

Dodatkowo programpowinien zliczać liczbę wywołań funkcji. W tym celu należy jedną zmienna przeznaczyć na licznik i zaraz po wejściu do funkcji zwiększać ten licznik o jeden.

Przed zakończeniem obliczeń program powinien wyswietlać wyliczony wyraz ciągu oraz liczbę wywołań funkcji.

3.3 Algorytm E

Oto jedna z jego wersji algorytmu Euklidesa: Dane są dwie dodatnie liczby całkowite $m$ i $n$ , należy znaleźć ich największy wspólny dzielnik (NWD) tj. największą dodatnią liczbę całkowitą, która dzieli całkowicie zarówno $m$ jak i $n$ .

[Znajdowanie reszty] Podziel $m$ przez $n$ i niech $r$ oznacza resztę z tego dzielenia. (Mamy $0 ≤ r < n$ .)
[Czy wyszło zero?] Jeśli $r = 0$ zakończ algorytm; odpowiedzią jest $n$ .
[Upraszczanie] Wykonaj $m ← n$ , $n ← r$ i wróć do kroku 1.

Schemat blokowy

SVG-Viewer needed.

Zadania

Spróbuj zaprogramować w Pythonie Algorytm E.

3.4 Algorytm B

Przyjmij $k ← 0$ , a następnie powtarzaj operacje: $k ← k + 1$ , $u ← u∕2$ , $v ← v∕2$ zero lub więcej razy do chwili gdy przynajmniej jedna z liczb $u$ i $v$ przestanie być parzysta.
Jeśli $u$ jest nieparzyste to przyjmij $t ← − v$ i przejdź do kroku 4. W przeciwnym razie przyjmij $t ← u$ .
(W tym miejscu $t$ jest parzyste i różne od zera). Przyjmij $t ← t∕2$ .
Jeśli $t$ jest parzyste to przejdź do 3.
Jeśli $t > 0$ , to przyjmij $u ← t$ , w przeciwnym razie przyjmij $v ← − t$ .
Przyjmij $t ← u− v$ . Jeśli $t ⁄= 0$ to wróć do kroku 3. W przeciwnym razie algorytm zatrzymuje się z wynikiem $u ⋅2k$ .

Zadania

Narysuj schemat blokowy algorytmu B
Spróbuj zaprogramować w Pythonie Algorytm B.

3.5 Metoda Newtona-Raphsona: pierwiastek dowolnego stopnia

Załóżmy, że mamy wyznaczyć pierwiastek stopnia $n$ z liczby $w$ , czyli znaleźć taką liczbę $x$ , że:

n x = w

(1)

lub inaczej:

n x − w = 0

(2)

Jeżeli oznaczymy $f(x) = xn − w$ to zadanie to można zapisać ogólniej: należy znaleźć takie $x$ , że $f(x) = 0$ .

Jeżeli zadanie dodatkowo uprościmy zakładając:

funkcja ma dokładnie jedno miejsce zerowe,
jest różniczkowalna,
jej pochodna w całym przedziale jest albo dodatnia albo ujemna;

to możemy naszkicować następujący rysunek ilustrujący nasze zadanie:

Zaczynamy w punkcie $g$ ; wartość funkcji w tym punkcie wynosi $f(g)$ . Musimy w jakiś sposób zdecydować w którym kierunku należy wykonać następny krok. Zauważmy, że możemy w tym celu wykorzystać pochodną (czerwona, przerywana linia na powyższym rysunku). Jeżeli przybliżymy funkcję za pomocą pochodnej (stycznej do funkcji, przechodzącej przez punk $(g,f(g)$ to następnym przybliżeniem będzie punkt przecięcia stycznej z osią $x$ .

Z równania prostej mamy:

f-(g)-−-0 ′ g − g′ = f (g)

(3)

czyli

-f(g) ′ f ′(g) = g − g

(4)

i dalej

f(g) g′ = g −--′-- f (g)

(5)

Jeżeli zauważymy, że $f(x) = xn − w$ oraz, że $f′(x ) = nxn −1$ to kolejne przybliżenie wyliczane będzie ze wzoru:

′ gn −-w- g = g − ngn−1

(6)

albo

ngn − gn + w (n − 1)gn + w 1 ( w ) g′ = -----n−-1----= ------n−1---- = -- (n − 1)g + -n−1- ng ng n g

(7)

Gdy $n = 2$ , wówczas

( ) g′ = 1 g + w . 2 g

(8)

3.5.1 Realizacja programowa

Program będzie się składał z trzech części:

blisko(a, b) – funkcja o wartościach logicznych sprawdzająca czy $|a− b| ≤ ?$ ,
lepszy(w, g) – funkcja rzeczywista wyliczająca następne, lepsze przybliżenie pierwiastka,
pierwiastek(n, w, g) – funkcja (rzeczywista) wyliczająca pierwiastek stopnia $n$ z $w$ zaczynając od przybliżenia $g$ .

3.5.2 Zadania treningowe

Narysować schematy blokowe poszczególncyh funkcji.
Zaprogramować w języku Python program wyliczający dla zadanej liczby, z wykorzystaniem trzech powyższych funkcji, pierwiastek z zadanej (wczytanej) (bez rekurencji!).
Zaprogramować wersję „rekurencyjną” powyższego algorytmu.

4 Materiały pomocnicze

4.1 Potrzebne instrukcje języka Python

Instrukcja warunkowa
Instrukcja while
Deﬁnicje funkcji

5 Wersja PDF dokumentu

Instrukcja w formie PDF.

Literatura

[1] Wojciech Myszka. Laboratorium 4: błędy obliczen, python. Instrukcja laboratoryjna dostępna: http://kmim.wm.pwr.edu.pl/myszka/dydaktyka/technologie-informacyjne/mechatronika-mcm031003/laboratorium/laboratorium-4-bledy-obliczen-python/, 2015.

[2] Mark Pilgrim. Dive Into Python. Apress, Lipiec 2004. Dostępne jest polskie tłumaczenie on-line: http://pl.wikibooks.org/wiki/Zanurkuj_w_Pythonie zatytułowane Znurkuj w Pytonie.

Wersja: Wersja: 7 z drobnymi modyﬁkacjami! z dnia 2015-10-28 10:14:46 +0100

P	W	Ś	C	P	S	N
« mar
					1	2
3	4	5	6	7	8	9
10	11	12	13	14	15	16
17	18	19	20	21	22	23
24	25	26	27	28	29	30