5.1. Algorytmy

Poniżej kody klasycznych algorytmów w Pythonie. [Komentarz do dopisania]

5.1.1. Trójkąt

Kod nr 
 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
31
32
33
34
35
36
#!/usr/bin/env python
# -*- coding: utf-8 -*-
#
# Badanie możliwości zbudowania trójkąta i obliczanie jego pola
# za pomocą wzoru Herona
# <eCG>

import math  # dołączamy bibliotekę matematyczną

op = "t"  # deklarujemy i inicjujemy zmienną pomocniczą
while op != "n":  # dopóki wartość zmiennej op jest inna niż znak "n"
    a, b, c = input("Podaj 3 boki trójkąta (oddzielone przecinkami): ")
    # alternatywna forma pobrania danych
    # a, b, c = [int(x) for x in raw_input(
    #     "Podaj 3 boki trójkąta (oddzielone spacjami): ").split()]

    if a + b > c and a + c > b and b + c > a:  # warunek złożony
        print "Z podanych boków można zbudować trójkąt."
        # czy boki spełniają warunki trójkąta prostokątnego?
        if (a**2 + b**2 == c**2 or
                a**2 + c**2 == b**2 or
                b**2 + c**2 == a**2):
            print "Do tego prostokątny!"

        # na wyjściu możemy wyprowadzać wyrażenia
        print "Obwód wynosi:", (a + b + c)
        p = 0.5 * (a + b + c)  # obliczmy współczynnik wzoru Herona
        # liczymy pole ze wzoru Herona
        P = math.sqrt(p * (p - a) * (p - b) * (p - c))
        print "Pole wynosi:", P
        op = "n"  # ustawiamy zmienną na "n", aby wyjść z pętli while
    else:
        print "Z podanych odcinków nie można utworzyć trójkąta prostokątnego."
        op = raw_input("Spróbujesz jeszcze raz (t/n): ")

print "Do zobaczenia..."

5.1.2. Silnia

Wersja iteracyjna i rekurencyjna.

Kod nr 
 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
#!/usr/bin/env python
# -*- coding: utf-8 -*-
#
# Obliczanie silni metodą iteracyjną i rekurencyjną
# <eCG>


def sil_rek(n):
    if n == 0:
        return 1
    return sil_rek(n - 1) * n


def sil_iter(n):
    wynik = 1
    for i in range(1, n + 1):
        wynik = wynik * i
    return wynik


def main(args):
    n = int(raw_input("Podaj liczbę: "))
    print "sil_iter(%s) = %s" % (n, sil_iter(n))
    print "sil_rek(%s) = %s" % (n, sil_rek(n))
    return 0


if __name__ == '__main__':
    import sys
    sys.exit(main(sys.argv))

5.1.3. Algorytm Euklidesa

Kod nr 
 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
31
32
33
34
35
36
37
38
#!/usr/bin/env python
# -*- coding: utf-8 -*-
#
# Algorytm Euklidesa – znajdowanie najwększego wspólnego dzielnika
# <eCG>


def nwd_klasyczny(a, b):
    while a != b:
        if a > b:
            a -= b
        else:
            b -= a

    return a


def nwd_optymalny(a, b):
    while a > 0:
        a = a % b
        b = b - a

    return b


def main(args):
    a = int(input("Podaj liczbę a: "))
    b = int(input("Podaj liczbę b: "))

    print("Nwd(%, %) klasyczny =", nwd_klasyczny(a, b))
    print("Nwd(%, %) optymalny =", nwd_optymalny(a, b))

    return 0


if __name__ == '__main__':
    import sys
    sys.exit(main(sys.argv))

5.1.4. Ciąg Fibonacciego

Wersja iteracyjna i rekurencyjna.

Kod nr 
 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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
#
# Ciąg Fibonacciego
# <eCG>


def fib_iter0(n):
    """Funkcja zwraca n-ty wyraz ciągu Fibonacciego
       F(0) = 0
       F(1) = 1
       F(n) = F(n-2) + F(n-1) dla n > 1
    """
    if n == 0:
        return 0
    elif n == 1:
        return 1
    a, b = (0, 1)
    for i in range(1, n - 1):
        a, b = b, a + b
    return b


def fib_iter1(n):  # definicja funkcji
    """
        Funkcja drukuje kolejne wyrazy ciągu Fibonacciego
        aż do wyrazu n-tego, który zwraca.
        Wersja iteracyjna z pętlą while.
    """
    # dwa pierwsze wyrazy ciągu zapisane w tupli
    a, b = (0, 1)  # przypisanie wielokrotne, rozpakowanie tupli
    print(a, end=' ')
    while n > 1:
        print(b, end=' ')
        a, b = b, a + b  # przypisanie wielokrotne
        n -= 1


def fib_iter2(n):
    """
        Funkcja drukuje kolejne wyrazy ciągu Fibonacciego
        aż do wyrazu n-tego, który zwraca.
        Wersja iteracyjna z pętlą for.
    """
    a, b = 0, 1
    print("wyraz", 1, a)
    print("wyraz", 2, b)
    for i in range(1, n - 1):
        # wynik = a + b
        a, b = b, a + b
        print("wyraz", i + 2, b)

    print()  # wiersz odstępu
    return b


def fib_rek(n):
    """
        Funkcja zwraca n-ty wyraz ciągu Fibonacciego.
        Wersja rekurencyjna.
    """
    if n < 1:
        return 0
    if n < 2:
        return 1
    return fib_rek(n - 1) + fib_rek(n - 2)


def main(args):
    n = int(input("Podaj nr wyrazu: "))
    print("Wyraz {:d}: {:d}".format(n, fib_iter0(n)))
    print("=" * 40)
    fib_iter1(n)
    print()
    print("=" * 40)
    fib_iter2(n)
    print("=" * 40)
    print(fib_rek(n - 1))
    return 0


if __name__ == '__main__':
    import sys
    sys.exit(main(sys.argv))

5.1.5. Sortowanie

5.1.5.1. Przez wybór

Kod nr 
 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
31
32
33
34
#!/usr/bin/env python
# -*- coding: utf-8 -*-
#
# Sortowanie przez wybór
# <eCG>


from random import randint


def sort_wybor(lista):
    n = len(lista)
    for i in range(n):
        k = i
        for j in range(i + 1, n):
            if lista[j] < lista[k]:
                k = j
        # pythonowy składnia dla zamiany wartości
        lista[i], lista[k] = lista[k], lista[i]

    return lista


def main(args):
    lista = []
    for i in range(10):
        lista.append(randint(0, 100))
    print lista
    print sort_wybor(lista)


if __name__ == '__main__':
    import sys
    sys.exit(main(sys.argv))

5.1.6. Konwersja liczby

Kod nr 
 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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#!/usr/bin/env python
# -*- coding: utf-8 -*-
#
# Konwersja liczby dziesiętnej na system o podanej podstawie
# <eCG>

cyfry = {10: 'A', 11: 'B', 12: 'C', 13: 'D', 14: 'E', 15: 'F'}
cyfry2 = {v: k for k, v in cyfry.items()}


def do10(liczba, podst):
    """
    Funkcja konwertuje liczbę o podanej podstawie na system dziesiętny
    Liczba konertowana jest na napis
    """
    p = len(str(liczba)) - 1
    liczba10 = 0
    for l in str(liczba):
        if l.isdigit():
            liczba10 += int(l) * podst**p
        else:
            liczba10 += cyfry2[l] * podst**p
        p -= 1
    print liczba10


def konwertuj(liczba, podst):
    """
    Funkcja konwertuje podaną liczbę dziesiętną na system o podanej podstawie
    wykorzystując dzielenie z resztą, zwraca listę reszt.
    """

    global cyfry

    # słownik ze znakami cyfr większych od 9
    reszty = []  # pusta lista
    while liczba > 0:
        reszty.append(liczba % podst)
        liczba = liczba / podst

    reszty.reverse()  # odwrócenie elemnetów listy
    if podst > 10:  # zamiana cyfr większych od 9
        reszty = [cyfry[x] if x > 9 else x for x in reszty]
    return reszty


def main(args):
    liczba = raw_input("Podaj liczbę: ")
    podst = int(raw_input("Podaj podstawę (2-16): "))
    # cel = raw_input("Podaj podstawę systemu docelowego: ")
    do10(liczba, podst)
    # liczbaP = "".join(str(x) for x in konwertuj(int(liczba), podst))
    # print "Liczba(10):", liczba10
    # print "Liczba(%s): %s" % (podst, liczbaP)

    return 0


if __name__ == '__main__':
    import sys
    sys.exit(main(sys.argv))

5.1.7. Szyfr Cezara

Wersja ze stałym kluczem.

Kod nr 
 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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
#!/usr/bin/env python
# -*- coding: utf-8 -*-
#
# Implementacja klasycznego szyfru Cezara
# <eCG>

"""
    ZADANIE
    Pobierz od użytkownika ciąg znaków, zaszyfruj go przy wykorzystaniu
    szyfru Cezara o kluczu podanym przez użytkownika,
    wyświetl zaszyfrowany ciąg. Następnie zdeszyfruj go
    i ponownie wyświetl wynik operacji.
"""


def szyfruj(tekst, klucz):
    szyfrogram = ""
    for znak in tekst:
        znak = znak.lower()
        if znak == ' ':
            pass
        elif ord(znak) + klucz > 122:
            znak = chr(ord(znak) + klucz - 26)
        else:
            znak = chr(ord(znak) + klucz)
        szyfrogram += znak
    return szyfrogram


def deszyfruj(szyfrogram, klucz):
    tekst = ""
    for znak in szyfrogram:
        if znak == ' ':
            pass
        elif ord(znak) - klucz < 97:
            znak = chr(ord(znak) - klucz + 26)
        else:
            znak = chr(ord(znak) - klucz)
        tekst += znak
    return tekst


def main(args):
    tekst = raw_input("Podaj tekst do zaszyfrowania:\n")
    try:
        klucz = int(raw_input("Podaj klucz:\n"))
        klucz = klucz % 26
        szyfrogram = szyfruj(tekst, klucz)
        deszyfr = deszyfruj(szyfrogram, klucz)
        assert deszyfr == tekst.lower()
        print "Szyfrogram:\n", szyfrogram
        print "Deszyfracja:\n", deszyfr
    except ValueError:
        print "Błędny klucz!"
    return 0


if __name__ == '__main__':
    import sys
    sys.exit(main(sys.argv))


"""
    JAK TO DZIAŁA
    try ... except to konstrukcja która przechwytuje błędy: w bloku try
    użytkownik może wprowadzić niewłaściwy klucz, np. literę, wtedy wykona się
    kod w bloku except.
    def nazwa_funkcji(argumenty): – tak definiujemy funkcje
    return zmienna – instrukcja zwraca wartość przypisaną zmiennej
    nazwa_funkcji(argumenty) – tak wywołujemy funkcje.
    Napisy mogą być indeksowane (od 0), co daje dostęp do pojedynczych znaków.
    Funkcja len(str) zwraca długość napisu, wykorzystana jako argument funkcji
    range() pozwala iterować po znakach napisu.
    Operator += oznacza dodanie argumentu z prawej strony do wartości z lewej.
"""

5.1.8. Pierwiastek kwadratowy

Użycie metody Herona.

Kod nr 
 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
#!/usr/bin/env python
# -*- coding: utf-8 -*-
#
# Obliczanie wartości pierwiastka kwadratowego z podanej liczby
# przy użyciu metody Herona: a(n) = (a(n-1) + x / a(n-1)) / 2
# <eCG>


def pierwiastek(x, d):
    a = x  # inicjalizacja szkuanej wartości
    while abs(a - (x / a)) > d:
        a = (a + (x / a)) / 2
    return a


def main(args):
    # liczba dla której szukamy pierwiastka
    x = float(raw_input("Podaj liczbę: "))
    # dokładność obliczeń
    d = float(raw_input("Podaj dokładność: "))
    # drukujemy wynik z dokładnością do 6 miejsc
    print "Pierwiastek kwadratowy: {:.6f}".format(pierwiastek(x, d))
    return 0


if __name__ == '__main__':
    import sys
    sys.exit(main(sys.argv))

5.1.9. Pole obszaru

Całka nieoznaczona Riemanna. [Sprawdzić poprawność obliczeń.]

Kod nr 
 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
31
32
33
#!/usr/bin/env python
# -*- coding: utf-8 -*-
#
# Obliczanie pola obszaru ograniczoneg wykresem funkcji:
# y = x^2, prostymi x = a, x = b i osią OX
# (oznaczona całka Riemanna)
# <eCG>


def funkcja(x):
    return x * x


def pole(a, b, n):
    p = 0  # wyliczane pole
    d = (b - a) / n  # długość przedziałów w zakresie <a;b>
    for i in range(n):
        x = a + (d * i) + (d / 2)  # punkty pośrednie przedziałów
        p += abs(funkcja(x))  # suma pól prostokątów
    return p


def main(args):
    a = int(raw_input("Podaj lewy kraniec: "))
    b = int(raw_input("Podaj prawy kraniec: "))
    n = int(raw_input("Podaj liczbę przedziałów: "))
    print "Pole: {:.3f}".format(pole(a, b, n))
    return 0


if __name__ == '__main__':
    import sys
    sys.exit(main(sys.argv))
Utworzony:2022-05-27 o 15:34 w Sphinx 1.4.5