Kodowanie

Zapisywanie algorytmu w języku programowania to ''kodowanie''. Istnieje prawdopodobnie kilka tysięcy języków programowania, a kilkadziesiąt z nich zdobyło większą popularność. Zawodowy programista zna zazwyczaj od kilkunastu do kilkudziesięciu języków, zaś w codziennej pracy posługuje się kilkoma. Większość języków jest uniwersalna, tzn. daje się w nich zapisać każdy algorytm, chociaż w niektórych językach pewne algorytmy zapisuje się wygodniej, niż w innych.

Instrukcja warunkowa

W poprzednim rozdziale skonstruowaliśmy algorytm wyznaczający najlżejszy z trzech odważników i opisaliśmy go w sposób sformalizowany w języku polskim:

czy A jest lżejszy od B?
jeśli tak, to
    czy A jest lżejszy od C? 
    jeśli tak, to
        daj odpowiedź, że najlżejszy jest A
    jeśli nie, to
        daj odpowiedź, że najlżejszy jest C
jeśli nie, to
    czy B jest lżejszy od C? 
    jeśli tak, to
        daj odpowiedź, że najlżejszy jest B
    jeśli nie, to
        daj odpowiedź, że najlżejszy jest C

W bardzo podobny sposób ten sam algorytm możemy zapisać w języku programowania Python.

if lzejszy_od(a, b):
    if lzejszy_od(a, c):
        return a
    else:
        return c
else:
    if lzejszy_od(b, c):
        return b;
    else:
        return c

Opis w języku polskim zawiera instrukcje warunkowe, czyli konstrukcje które wyglądają tak:

czy zachodzi warunek?
    jeżeli tak, zrób to
    jeżeli nie, zrób owo

W języku programowania Python będzie to wyglądało tak:

    if warunek():
        zrob_to()
    else:
        zrob_owo()

Zwróć uwagę na lewy margines w kodzie programu; różne wiersze są wcięte na różną głębokość. Wcięcia oddają strukturę programu - instrukcje wcięte bardziej znajdują się "głębiej", wewnątrz innych instrukcji. Stosowanie wcięć bardzo pomaga czytać programy, a w niektórych językach, w tym języku Python, jest to obowiązkowe!

Uwaga: numeracja z lewej strony nie jest częścią programu; jest wprowadzona tylko na potrzeby wykładu.

Funkcje

Pisanie programów polega na tworzeniu wielu małych kawałków kodu, takich jak pokazana powyżej instrukcja warunkowa. Żeby się wśród wielu takich kawałków nie pogubić, programiści nadają im nazwy.

def wyznacz_najlzejszy_odwaznik(a, b, c):
    if czy_pierwszy_lzejszy(a, b):
        if czy_pierwszy_lzejszy(a, c):
            return a
        else:
            return c
    else:
        if czy_pierwszy_lzejszy(b, c):
            return b;
        else:
            return c

Taki nazwany kawałek kodu to funkcja. Funkcja odpowiada specyfikacji problemu algorytmicznego. W nagłówku funkcji:

def wyznacz_najlzejszy_odwaznik(a, b, c):

wyszczególnione są argumenty (czyli dane, np. wagi a, b i c trzech odważników). Funkcja zwraca (oblicza) pewną wartość (czyli wynik, np. wagę najlżejszego odważnika).

Niektóre funkcje nie zwracają żadnej wartości, ale za to mają jakiś efekt, np. przełożenie dysków na inny palik przez maszynę wyposażoną w manipulator, albo odtworzenie piosenki przez wyjście audio.

Raz zapisana funkcja może być wykorzystywana do zapisania innych funkcji. W powyższym przykładzie funkcja czy_pierwszy_lzejszy (służąca określeniu, który z dwóch odważników jest lżejszy) jest wykorzystana (kilkukrotnie) do zapisania funkcji wyznacz_najlzejszy_odwaznik. Oto przykładowa definicja funkcji czy_pierwszy_lzejszy:

def czy_pierwszy_lzejszy(a, b):
    return a < b

Funkcjom nadajemy nazwy złożone z liter, cyfr i znaków podkreślenia (_). W wielu językach programowania zabronione są nazwy funkcji zaczynające się od cyfry.

W przykładzie powyżej występują dwie powiązane ze sobą funkcje (''czy_pierwszy_lzejszy'' oraz ''wyznacz_najlzejszy_odwaznik''). Kod przeglądarki Firefox 3.5 zawiera definicje ponad dwudziestu trzech tysięcy funkcji.

Pętle

W poprzednim rozdziale skonstruowaliśmy algorytm rozwiązujący Problem Wieże Dysków:

  usiądź wewnątrz koła,
  przenieś najmniejszy dysk o jeden palik w prawo
  dopóki wszystkie dyski nie znajdą się na jednym trzpieniu
    przenieś dysk różny od najmniejszego na ten palik, na którym nie ma najmniejszego dysku
    przenieś najmniejszy dysk o jeden palik w prawo

W tym algorytmie występuje pętla, czyli konstrukcja, która wygląda tak.

  dopóki warunek
    rób coś

Tak jak w przypadku instrukcji warunkowych, taką zapisaną po polsku pętlę można łatwo "przetłumaczyć" na język programowania:

while warunek():
  rob_cos()

Uruchamianie

Programy piszemy po to, żeby uruchamiać je na komputerach. Najwygodniejszym sposobem uruchamiania programów przedstawionych w tej prezentacji jest użycie edytora SEWI (http://sf.net/projects/sewi). W górnym oknie edytora wskazujemy język programowania (C++ lub Python), następnie wpisujemy kod funkcji (można np. skopiować kod z niniejszej prezentacji, ale bez numeracji wierszy). W dolnym oknie edytora wpisujemy nazwę funkcji oraz parametry. Dla przykładu po wpisaniu:

wyznacz_najlzejszy_odwaznik(5,3,8)

edytor SEWI obliczy wartość funkcji i w środkowym oknie poda wynik, czyli dostaniemy:

>>> wyznacz_najlzejszy_odwaznik(5,3,8)
3

ZADANIA

Zadanie 1

Konstrukcja assert przerywa wykonanie programu, jeżeli jej argument ma wartość logiczną "fałsz". Skorzystaj z instrukcji assert do zapisania testów upewniających Cię, że funkcja "wyznacz_najlzejszy_odwaznik" rzeczywiście działa poprawnie. Test może wyglądać np. tak:

    assert wyznacz_najlzejszy_odwaznik(2, 3, 1) == 1

Postaraj się, aby Twoich testów było jak najmniej, ale żeby sprawdzały poprawność funkcji jak najlepiej.

• Dołącz do programu dodatkową funkcję, która uruchamia testy.
• Wprowadź błąd do kodu funkcji ''wyznacz_najlzejszy_odwaznik'' i sprawdź, czy któryś z Twoich testów to wykryje.

Rozwiązanie

Przykładowe rozwiązanie punktu pierwszego:

    def testuj_wyznacz_najlzejszy_odwaznik():
        assert wyznacz_najlzejszy_odwaznik(0,0,0) == 0
        assert wyznacz_najlzejszy_odwaznik(0,0,1) == 0
        assert wyznacz_najlzejszy_odwaznik(0,1,0) == 0
        assert wyznacz_najlzejszy_odwaznik(0,1,1) == 0
        assert wyznacz_najlzejszy_odwaznik(1,0,0) == 0
        assert wyznacz_najlzejszy_odwaznik(1,0,1) == 0
        assert wyznacz_najlzejszy_odwaznik(1,1,0) == 0
        assert wyznacz_najlzejszy_odwaznik(1,1,1) == 1
        assert wyznacz_najlzejszy_odwaznik(2,5,7) == 2
        assert wyznacz_najlzejszy_odwaznik(2,7,5) == 2
        assert wyznacz_najlzejszy_odwaznik(5,2,7) == 2
        assert wyznacz_najlzejszy_odwaznik(5,7,2) == 2
        assert wyznacz_najlzejszy_odwaznik(7,2,5) == 2
        assert wyznacz_najlzejszy_odwaznik(7,5,2) == 2

Zadanie 2

Funkcja ''wyznacz_najlzejszy_odwaznik'' ma elegancką opisową nazwę, dzięki czemu osoba czytająca program z łatwością ją zrozumie; gdy jednak wpisujemy tę nazwę w interpreterze poleceń, cierpną palce. Zdefiniuj funkcję 'wno', która robi dokładnie to samo, co ''wyznacz_najlzejszy_odwaznik''. Zapisz tę funkcję w ten sposób, żeby nie powielać kodu wpisanego już raz w ciele funkcji ''wyznacz_najlzejszy_odwaznik''.

Uwaga: funkcji ''wno'' nie używaj w programie, bo stanie się on nieczytelny; ta funkcja to tylko skrót dla wygody osoby korzystającej z interpretera poleceń!

Rozwiązanie

def wno(a, b, c):
    return wyznacz_najlzejszy_odwaznik(a, b, c)

wno = wyznacz_najlzejszy_odwaznik

Zadanie 3

Zapisz, uruchom i przetestuj program porządkujący niemalejąco trzy liczby a, b, c (zobacz algorytm 4 z wykładu 1).

Wskazówka: żeby wypisać trójkę "c, a, b" piszemy po prostu return c, a, b

Rozwiązanie

def uporzadkuj(a, b, c):
    if a < b:
        if a < c:
            if b < c: return a,b,c
            else: return a,c,b
        else: return c,a,b
    else:
        if b < c:
            if a < c: return b,a,c
            else: return b,c,a
        else: return c,b,a

Zadanie 4

Napisz program porządkujący 4 liczby za pomocą co najwyżej 5 porównań. Używaj tylko instrukcji warunkowych.

Zadanie 5

Instrukcja warunkowa ma dwa człony, jeden z nich wybierany jest w zależności od prawdziwości warunków. Czasami jednak potrzebny jest tylko jeden człon, np.

    if stan_alarmowy_przekroczony():
        alarmuj()
    else:
        pass  # nie rób nic

Wiele języków programowania pozwala w takim przypadku w ogóle opuścić całą klauzulę ''else''. Skorzystaj z tej właściwości by uprościć poniższy programy wyznaczania najmniejszej z 3 liczb. (Wskazówka: zmniejsz liczbę wystąpień ''else'' o dwa, a liczbę wystąpień "return" o jeden).

def najmniejsza(a, b, c):
    if a < b:
        if a < c:
            return a
        else: 
            return c
    else: 
        if b < c:
            return b
        else:
            return c

Rozwiązanie

def najmniejsza(a, b, c):
    if a < b:
        if a < c:
            return a
    else: 
        if b < c:
            return b
    return c 

Zadanie 6 (rodzielność sekwencjonownia względem if-then-else)

Na pewno nie są Ci obce przekształcenia algebraiczne, np. poniższe wyrażenia są równoważne

\[x * z + y * z\] \[(x + y) * z\]

Programy też można przekształcać w ten sposób, np. poniższe programy są równoważne:

    if W:               if W:
        X                   X
        Z               else:
    else:                   Y
        Y               Z
        Z

Takie przekształcenia programów nazywamy "refaktoringami". Zaproponuj inne refaktoringi.