infalo

Filmy

Psie sprawki

1. Wyszukiwanie liniowe

—

by

karrolinna
in

Wyszukiwanie liniowe polega na sprawdzaniu elementów po kolei, od początku do końca.

To najprostszy sposób szukania danych.

Przykład z życia:

Masz stos kartek i szukasz kartki z nazwiskiem „Kowalski”. Nie wiesz, gdzie ona leży, więc bierzesz pierwszą kartkę, potem drugą, potem trzecią — aż znajdziesz właściwą.

Tak samo działa komputer.

Ma listę:

liczby = [8, 3, 10, 5, 2]

Szukamy liczby:

10

Program sprawdza:

8  → to nie 10
3  → to nie 10
10 → znaleziono

  1. Weź pierwszy element.
  2. Sprawdź, czy jest równy szukanej wartości.
  3. Jeśli tak — zakończ szukanie.
  4. Jeśli nie — przejdź do następnego elementu.
  5. Powtarzaj do końca listy.
  6. Jeśli dojdziesz do końca i nic nie znajdziesz — elementu nie ma.

dla każdego elementu w tablicy:    
  jeżeli element = szukana_wartość:        
    wypisz "znaleziono"        
    zakończ
wypisz "nie znaleziono"

Lista:

[4, 7, 12, 9, 15]

Szukamy:

9

Kolejne porównania:

4 == 9?  nie
7 == 9?  nie
12 == 9? nie
9 == 9?  tak

Wynik:

Liczba 9 znajduje się na pozycji 3

Uwaga: w Pythonie numerowanie pozycji zaczyna się od 0.

Błąd 1: mylenie indeksu z wartością

if i == szukana:

To sprawdza numer pozycji, a nie element listy.

Poprawnie:

if liczby[i] == szukana:

Błąd 2: brak informacji, gdy elementu nie ma

Uczeń pisze program, który wypisuje wynik tylko wtedy, gdy coś znajdzie. Jeśli nie znajdzie — program milczy.

Błąd 3: niepotrzebne dalsze szukanie po znalezieniu elementu

Jeśli szukamy tylko pierwszego wystąpienia, po znalezieniu można użyć:

break

Błąd 4: złe rozumienie pozycji

Uczeń wypisuje pozycję 3, a oczekuje 4, bo myli indeksowanie od 0 z liczeniem „po ludzku” od 1.

Zadanie 1

Dana jest lista:

liczby = [6, 11, 4, 19, 8]

Sprawdź, czy znajduje się w niej liczba 19.

Rozwiązanie zadania 1 — omówienie

Lista:

[6, 11, 4, 19, 8]

Szukamy liczby 19.

Program sprawdza:

6  → nie
11 → nie
4  → nie
19 → tak

Pseudokod

znaleziono = fałsz
dla każdej liczby w liście:
    jeśli liczba = 19:
      znaleziono = prawda
jeśli znaleziono:
  wypisz "jest"
inaczej:
  wypisz "nie ma"

Python

liczby = [6, 11, 4, 19, 8]
szukana = 19
znaleziono = False
for liczba in liczby:    
  if liczba == szukana:        
    znaleziono = True
    
if znaleziono:    
  print("Liczba znajduje się na liście")
else:    
  print("Liczby nie ma na liście")

Analiza krok po kroku

Zmienna „znaleziono” na początku ma wartość „False„, ponieważ jeszcze niczego nie znaleźliśmy.

Pętla przechodzi przez kolejne liczby.

Gdy trafia na 19, warunek:

liczba == szukana

jest prawdziwy, więc zmienna „znaleziono” zmienia się na „True„.

Po zakończeniu pętli program sprawdza, czy „znaleziono” jest prawdziwe.

Zadanie 2

Dana jest lista:

imiona = ["Ala", "Ola", "Jan", "Ewa"]

Sprawdź, czy na liście znajduje się imię "Jan".

Rozwiązanie zadania 2 — omówienie

Lista:

["Ala", "Ola", "Jan", "Ewa"]

Szukamy imienia "Jan".

Program sprawdza:

Ala → nie
Ola → nie
Jan → tak

Pseudokod

znaleziono = fałsz
dla każdego imienia w liście:
    jeśli imię = "Jan":        
      znaleziono = prawda
      
jeśli znaleziono:
  wypisz "jest"
inaczej:    
    wypisz "nie ma"

Python

imiona = ["Ala", "Ola", "Jan", "Ewa"]
szukane = "Jan"
znaleziono = False
for imie in imiona:
  if imie == szukane:
    znaleziono = True
if znaleziono:    
  print("Imię znajduje się na liście")
else:    
  print("Imienia nie ma na liście")

Analiza krok po kroku

Zmienna "znaleziono" na początku ma wartość "False", ponieważ jeszcze nie znaleźliśmy szukanego imienia.

Pętla przechodzi przez kolejne elementy listy.

Gdy trafia na "Jan", warunek:

imie == szukane

jest prawdziwy, więc zmienna "znaleziono" zmienia się na "True".

Po zakończeniu pętli program sprawdza, czy "znaleziono" jest prawdziwe.

Zadanie 3

Dana jest lista:

liczby = [5, 3, 5, 7, 5, 9]

Policz, ile razy występuje liczba 5.

Rozwiązanie zadania 3 — omówienie

Lista:

[5, 3, 5, 7, 5, 9]

Szukamy liczby 5.

Program sprawdza:

5 → znaleziono (licznik = 1)
3 → nie
5 → znaleziono (licznik = 2)
7 → nie
5 → znaleziono (licznik = 3)
9 → nie

Ostatecznie liczba 5 występuje 3 razy.

Pseudokod

licznik = 0
dla każdej liczby w liście:
  jeśli liczba = 5:
    licznik = licznik + 1
    
wypisz licznik

Python

liczby = [5, 3, 5, 7, 5, 9]
licznik = 0
for liczba in liczby:
  if liczba == 5:
    licznik += 1
    
print("Liczba 5 występuje", licznik, "razy")

Analiza krok po kroku

Zmienna "licznik" na początku ma wartość 0, ponieważ jeszcze nie znaleźliśmy żadnej liczby 5.

Pętla przechodzi przez kolejne elementy listy.

Dla każdej liczby program sprawdza warunek:

liczba == 5

Jeżeli warunek jest prawdziwy, zmienna "licznik" zostaje zwiększona o 1.

Przebieg działania programu:

5 → licznik = 1
3 → licznik = 1
5 → licznik = 2
7 → licznik = 2
5 → licznik = 3
9 → licznik = 3

Po zakończeniu pętli program wypisuje wartość zmiennej "licznik".

Wynik:

Liczba 5 występuje 3 razy

Dana jest lista wyników punktowych uczniów:

punkty = [12, 45, 18, 45, 30, 27, 45, 10]

Napisz program, który:

  1. sprawdzi, czy ktokolwiek zdobył 45 punktów,
  2. policzy, ile osób zdobyło 45 punktów,
  3. wypisze pierwszą pozycję, na której pojawia się wynik 45.

Rozwiązanie

punkty = [12, 45, 18, 45, 30, 27, 45, 10]
szukana = 45
ile = 0
pierwsza_pozycja = -1
for i in range(len(punkty)):
    if punkty[i] == szukana:
        ile += 1        
    
        if pierwsza_pozycja == -1:            
            pierwsza_pozycja = i
      
if ile > 0:
    print("Wynik 45 wystąpił")
    print("Liczba wystąpień:", ile)
    print("Pierwsza pozycja:", pierwsza_pozycja)
else:    
    print("Wynik 45 nie wystąpił")

Najważniejszy fragment:

if pierwsza_pozycja == -1:    
    pierwsza_pozycja = i

Dzięki temu zapamiętujemy tylko pierwsze wystąpienie.