Klasa III: algorytmy tablicowe

Jeśli mamy dwie liczby i chcemy znaleźć większą lub mniejszą z nich, to możemy po prostu użyć instrukcji warunkowej if:

Python

# max i min
#-----------------------

import random

a = random.randint(-10,10)
b = random.randint(-10,10)
maxab,minab = b,b
if a > b: maxab = a
if a < b: minab = a
print(a,b,"  MAX:",maxab,"MIN:",minab)

Jeśli liczb jest więcej, to program się komplikuje. W takiej sytuacji korzystamy z funkcji wbudowanych:

max(x₁,x₂[,...x_n])

Zwraca największą wartość wśród liczb x₁...x_n (co najmniej dwie).

min(x₁,x₂[,...x_n])

Zwraca najmniejszą wartość wśród liczb x₁...x_n (co najmniej dwie).

Nasz program wygląda teraz następująco:

Python

# max i min
#-----------------------

import random

a = random.randint(-10,10)
b = random.randint(-10,10)
print(a,b,"  MAX:",max(a,b),"MIN:",min(a,b))

Zaletą stosowania funkcji wbudowanych jest uproszczenie programu.

Funkcje max( ) i min( ) potrafią również wyszukiwać wartość maksymalną i minimalną wśród elementów tablicy/listy:

Python

# max i min
#----------

import random

# Tworzymy listę o pseudolosowych elementach

t = [random.randint(-99,99) for i in range(10)]

print(t)
print("MAX:",max(t))
print("MIN:",min(t))

Do zapamiętania:

Funkcja max( ) z pojedynczymi argumentami oraz z argumentem tablicą/listą.
Funkcja min( ) z pojedynczymi argumentami oraz z argumentem tablicą/listą.

Zadanie

Mamy 500 wartości całkowitych:

747 -37 -9 782 829 -367 -622 362 888 704 138 -700 776 761 123 -70 829 -274 -214 310 -918 -389 -663 -49 110 503 467 -583 971 -268 -248 633 -954 597 439 600 224 386 -830 646 20 -108 -278 -104 -8 713 -95 -206 182 22 -50 69 -208 24 -264 -200 65 19 266 457 -246 -783 762 -914 -96 -184 767 624 -118 166 -633 -609 -839 67 690 -998 101 775 -460 621 -286 53 508 929 -389 131 -516 571 -692 304 988 -14 -873 -739 -896 479 761 911 -811 451 -447 -493 -910 -661 641 846 -498 178 669 230 -95 138 265 552 -445 257 575 -962 253 -818 175 741 -824 248 515 114 628 -733 905 -537 -944 160 858 276 123 -667 824 -491 -606 212 538 -910 696 -941 -895 732 901 -607 287 622 869 -469 816 -407 -164 980 -390 -714 -725 -53 811 -189 -940 678 -86 865 -49 -718 -51 489 -341 985 -308 -149 -516 -841 -426 153 523 182 -937 142 -78 -263 -734 -844 -156 314 -606 -372 -779 811 245 381 422 -980 -969 107 -542 -224 -158 -909 73 -210 478 -437 -604 -447 327 -502 364 -396 458 128 276 721 -277 641 -883 386 -512 826 358 -226 1 123 478 112 -931 -387 -239 -702 249 -184 -665 296 -20 -592 896 329 631 355 588 970 10 -560 889 47 998 907 89 414 -545 786 -154 -908 -582 -183 99 123 662 -444 491 -902 460 -638 -871 864 -104 86 -463 847 276 884 71 -676 -774 747 466 702 -410 81 170 521 -330 840 -834 -335 306 157 599 816 594 634 223 -468 923 -544 267 -301 474 117 -606 895 -937 997 364 -152 -533 -92 821 -498 554 -797 -354 827 -219 -591 -221 599 113 -664 -244 -19 -795 229 -662 -163 -169 425 -694 480 -465 -400 -990 -24 683 616 -691 434 385 214 208 716 239 -647 981 570 -528 845 451 -600 -597 -852 294 569 -301 628 -161 -675 369 -368 -930 904 -858 -706 -961 -270 -367 53 -684 -981 572 -7 -713 -524 457 -922 308 -642 -572 -756 -450 484 585 -792 -522 125 485 -767 -722 -913 -799 -677 512 521 -863 -648 677 -415 175 967 -813 -502 -79 -680 179 470 -174 139 -54 709 17 -307 -785 966 603 990 531 -305 645 -751 -76 -778 -407 37 -679 -902 14 -669 -354 -879 -831 -488 569 -543 166 236 -210 -877 713 -310 -181 156 -690 331 -965 -612 589 -433 -362 954 -306 35 -915 690 387 -700 885 -16 664 -161 10 -192 123 757 466 -934 936 874 758 135 551 -25 -844 -245 -861 99 766 -747 383 -694 219 390 -553 -10 -300 -200 -182 598 605 694 244 -804 848 -343 238 -269 -542 -546

Znajdź wśród nich różnicę pomiędzy wartością największą i najmniejszą.

do podrozdziału do strony

Sortowanie elementów tablicy polega na takim ich ułożeniu, aby kolejne elementy występowały w określonym porządku:

porządek rosnący: każdy następny element jest większy od poprzedniego,
np: [1, 2, 3, 4,...].
porządek malejący: każdy następny element jest mniejszy od poprzedniego,
np: [5, 3, 2, 1, -3, -5...].
porządek niemalejący: każdy następny element jest albo większy, albo równy swojemu poprzednikowi,
np: [4, 4, 5, 7, 9, 9, 9, ...].
porządek nierosnący: każdy następny element jest albo mniejszy, albo równy swojemu poprzednikowi,
np: [ 9, 7, 6, 6, 5, 3, 1, 1, ...].

Dwa pierwsze porządki, to tzw. porządki mocne. Dwa ostatnie, to porządki słabe. Porządki słabe dopuszczają elementy równe.

Jeśli mamy tylko dwa elementy, to możemy je uporządkować przy pomocy instrukcji if:

Python

# Sortowanie
#-----------

import random

# Losujemy dwa elementy
a = random.randrange(1000)
b = random.randrange(1000)

print("Przed sortowaniem:",a,b)
if a > b: a,b = b,a
print("Po sortowaniu    :",a,b)

Jeśli elementów jest więcej, to umieszczamy je w tablicy i wykorzystujemy jej metodę sort( ):

Python

# Sortowanie
#-----------

import random

# Tworzymy tablicę o 100 elementach
t = [random.randrange(-100,101) for i in range(100)]

# Tablicę wyświetlamy
print(t)
print()

# Tablicę sortujemy niemalejąco
t.sort()

# Wyświetlamy wyniki
print(t)

Metoda sort( ) sortuje elementy tablicy/listy w porządku niemalejącym. Sortowane elementy muszą być liczbami. Jeśli chcemy zmienić kolejność na przeciwną, to dodajemy parametr reverse=True:

Python

# Sortowanie
#-----------

import random

# Tworzymy tablicę o 100 elementach
t = [random.randrange(-100,101) for i in range(100)]

# Tablicę wyświetlamy
print(t)
print()

# Tablicę sortujemy nierosnąco
t.sort(reverse=True)

# Wyświetlamy wyniki
print(t)

Do zapamiętania:

Metoda tablica.sort( ) i tablica.sort(reverse=True)

Zadanie

Mamy 500 wartości całkowitych:

747 -37 -9 782 829 -367 -622 362 888 704 138 -700 776 761 123 -70 829 -274 -214 310 -918 -389 -663 -49 110 503 467 -583 971 -268 -248 633 -954 597 439 600 224 386 -830 646 20 -108 -278 -104 -8 713 -95 -206 182 22 -50 69 -208 24 -264 -200 65 19 266 457 -246 -783 762 -914 -96 -184 767 624 -118 166 -633 -609 -839 67 690 -998 101 775 -460 621 -286 53 508 929 -389 131 -516 571 -692 304 988 -14 -873 -739 -896 479 761 911 -811 451 -447 -493 -910 -661 641 846 -498 178 669 230 -95 138 265 552 -445 257 575 -962 253 -818 175 741 -824 248 515 114 628 -733 905 -537 -944 160 858 276 123 -667 824 -491 -606 212 538 -910 696 -941 -895 732 901 -607 287 622 869 -469 816 -407 -164 980 -390 -714 -725 -53 811 -189 -940 678 -86 865 -49 -718 -51 489 -341 985 -308 -149 -516 -841 -426 153 523 182 -937 142 -78 -263 -734 -844 -156 314 -606 -372 -779 811 245 381 422 -980 -969 107 -542 -224 -158 -909 73 -210 478 -437 -604 -447 327 -502 364 -396 458 128 276 721 -277 641 -883 386 -512 826 358 -226 1 123 478 112 -931 -387 -239 -702 249 -184 -665 296 -20 -592 896 329 631 355 588 970 10 -560 889 47 998 907 89 414 -545 786 -154 -908 -582 -183 99 123 662 -444 491 -902 460 -638 -871 864 -104 86 -463 847 276 884 71 -676 -774 747 466 702 -410 81 170 521 -330 840 -834 -335 306 157 599 816 594 634 223 -468 923 -544 267 -301 474 117 -606 895 -937 997 364 -152 -533 -92 821 -498 554 -797 -354 827 -219 -591 -221 599 113 -664 -244 -19 -795 229 -662 -163 -169 425 -694 480 -465 -400 -990 -24 683 616 -691 434 385 214 208 716 239 -647 981 570 -528 845 451 -600 -597 -852 294 569 -301 628 -161 -675 369 -368 -930 904 -858 -706 -961 -270 -367 53 -684 -981 572 -7 -713 -524 457 -922 308 -642 -572 -756 -450 484 585 -792 -522 125 485 -767 -722 -913 -799 -677 512 521 -863 -648 677 -415 175 967 -813 -502 -79 -680 179 470 -174 139 -54 709 17 -307 -785 966 603 990 531 -305 645 -751 -76 -778 -407 37 -679 -902 14 -669 -354 -879 -831 -488 569 -543 166 236 -210 -877 713 -310 -181 156 -690 331 -965 -612 589 -433 -362 954 -306 35 -915 690 387 -700 885 -16 664 -161 10 -192 123 757 466 -934 936 874 758 135 551 -25 -844 -245 -861 99 766 -747 383 -694 219 390 -553 -10 -300 -200 -182 598 605 694 244 -804 848 -343 238 -269 -542 -546

Znajdź sumę 5 największych z nich.

do podrozdziału do strony

Elementy tablicy/listy zliczamy przy pomocy metody:

tablica.count(wartość)

Wynikiem jest liczba wystąpień danej wartości w tablicy/liście. Wartość może być dowolnym elementem: liczbą, tekstem...

Poniższy program tworzy tablicę/listę 10-elementową i wypełnia ją liczbami pseudolosowymi w zakresie od 1 do 7 (wyniki rzutów kostką: 1, 2, ..., 6). Następnie zlicza liczbę wystąpień każdego elementu.

Python

# Zliczanie

import random

# Tworzymy tablicę o 12 elementach
t = [random.randrange(1,7) for i in range(12)]

# Tablicę wyświetlamy
print(t)
print()

# Zliczamy elementy
for i in range(len(t)):
    print(t[i],':',t.count(t[i]))

Aby znaleźć najczęstszy element musimy zapamiętywać wartość elementu oraz liczbę jego wystąpień. Jeśli znajdziemy w tablicy/liście element częstszy, to wartości te podmieniamy.

Poniższy program tworzy tablicę/listę o 100 pseudolosowych elementach z zakresu od 1 do 21 (liczby 1, 2, 3, ..., 20). Następnie wyszukuje najczęstszą wartość.

Python

# Najczęstsza wartość

import random

# Tworzymy tablicę o 100 elementach
t = [random.randrange(1,21) for i in range(100)]

# Tablicę wyświetlamy
print(t)
print()

# Zliczamy elementy i szukamy najczęstszego
maxc = 0 # liczba wystąpień
maxe = 0 # wartość elementu
for i in range(len(t)):
    mc = t.count(t[i]) # zliczamy
    if mc > maxc:
        maxc = mc
        maxe = t[i]

# Wyświetlamy wyniki
print(maxe,"występuje",maxc,"razy.")

Do zapamiętania:

Metoda tablica.count(wartość)

do podrozdziału do strony

Zadanie polega na wylosowaniu ciągu liczb pseudolosowych w taki sposób, aby wylosowane liczby się nie powtarzały. Wyobraź sobie, iż piszesz symulację Lotto, gdzie komputer losuje 6 liczb z przedziału [1,49] jako bile. Wylosowane liczby nie mogą się powtarzać.

Jeśli przedział, z którego losujemy liczby, jest mały, to zadanie możemy rozwiązać następująco:

Python

# Symulacja Lotto
#----------------

import random

# Liczba bil
NB = 49
# Liczba bil losowanych
NL = 6

# Tworzymy tablicę bil 1..NB
bile = [i for i in range(1,NB+1)]

# Tablicę wyświetlamy dla sprawdzenia
print(bile)
print()

# Tablicę mieszamy pseudolosowo
for i in range(3 * NB):
    # Losujemy dwa indeksy
    x = random.randrange(NB)
    y = random.randrange(NB)
    # Zamieniamy miejscami bile
    bile[x],bile[y] = bile[y],bile[x]

# Tablicę wyświetlamy dla sprawdzenia
print(bile)
print()

# Kopiujemy NL początkowych elementów
los = bile[:NL+1]
los.sort()

# Wyświetlamy wyniki
print(los)

Przy kopiowaniu fragmentu tablicy bile zastosowaliśmy tzw. slicing. Działa to w sposób następujący:

W klamerkach za nazwą tablicy podajemy dwa indeksy rozdzielone dwukropkiem, indeks startu i indeks stopu (zwróć uwagę na podobieństwo do argumentów range(...)): Efektem jest fragment tablicy:

tablica[start:stop] → komórki o indeksach od start do stop - 1,
tablica[:stop] → komórki o indeksach od 0 (pierwsza komórka w tablicy) do stop - 1,
tablica[start:] → komórki o indeksach od start do końca tablicy,
tablica[:] → komórki od początku do końca tablicy

Jeśli przedział, z którego losujemy liczby jest duży, to tworzenie tablicy na kolejne liczby z przedziału staje się nieefektywne. W takim przypadku postępujemy np. tak:

Python

# Losowanie bez powtórzeń
#------------------------

import random

# Dolna granica
A = 1
# Górna granica
B = 1000
# Ilość liczb do wylosowania
N = 100

# Przygotowujemy pustą tablicę na
# wylosowane liczby

los = []

# Losujemy
while len(los) < N:
    while True:
        # Losujemy liczbę
        x = random.randint(A,B)
        # Sprawdzamy, czy liczba była
        # już wylosowana. Jeśli nie,
        # to przerywamy pętlę nieskończoną
        if not los.count(x): break
    # Wylosowaną liczbę dołączamy do
    # tablicy los
    los.append(x)

# Wyświetlamy posortowane wyniki
los.sort()
print(los)

Do zapamiętania:

Losowanie bez powtórzeń z małego i dużego przedziału liczbowego
Zastosowanie slicingu.

do podrozdziału do strony

Klasa III

Algorytmy tablicowe

SPIS TREŚCI

Wartość max i min

Do zapamiętania:

Zadanie

Sortowanie tablicy

Do zapamiętania:

Zadanie

Najczęstszy element

Do zapamiętania:

Losowanie bez powtórzeń

Do zapamiętania: