Informatyka · Zakres podstawowy
Porządkuj i powtarzaj — wstawianie oraz ciąg Fibonacciego
Układając karty w ręce, wsuwasz następną we właściwe miejsce. Podobnie działa sortowanie przez wstawianie.
- Przewidź
- Sprawdź
- Wyjaśnij
Po tej lekcji: Wykonasz sortowanie przez wstawianie i obliczysz element ciągu metodą iteracyjną.
Zakres podstawowy · materiał otwarty
Uporządkowana lewa strona
Pierwsza karta tworzy posortowany fragment. Bierzemy następną, przesuwamy większe elementy w prawo i wkładamy ją w wolne miejsce. Fragment po lewej pozostaje posortowany. Warunek > zamiast >= zachowuje kolejność równych elementów.
Sprawdź w działaniu
Wsuń kartę w odpowiednie miejsce
Wybieraj kolejną kartę. Obserwuj przesuwanie większych wartości, nie zamienianie przypadkowych par.
Najpierw przewidź wynik, potem sprawdź i wyjaśnij różnicę.
Sortowanie przez wstawianie
liczby = [5, 2, 4, 2]
for i in range(1, len(liczby)):
karta = liczby[i]
j = i - 1
while j >= 0 and liczby[j] > karta:
liczby[j + 1] = liczby[j]
j -= 1
liczby[j + 1] = karta
print(*liczby)2 2 4 5
Co porównujesz z bąbelkami?
Wstawianie przesuwa elementy posortowanego fragmentu. Bąbelkowe zamienia sąsiadów podczas kolejnych przejść. Obie metody mają pesymistycznie O(n²) porównań; wstawianie na już uporządkowanych danych wykonuje liniową liczbę prób warunku. Porównaj liczbę operacji na tych samych danych, nie sam czas pojedynczego uruchomienia.
Ciąg iteracyjny: pamiętaj dwa poprzednie
def fibonacci(n):
poprzedni, obecny = 0, 1
for _ in range(n):
poprzedni, obecny = obecny, poprzedni + obecny
return poprzedni
print(fibonacci(0), fibonacci(1), fibonacci(7))0 1 13
Ćwiczenie z pomocą · samodzielna praca
Wykonaj dwie próby
Posortuj ręcznie [4,1,3,2]. Następnie wypisz F0 do F6, przyjmując F0=0 i F1=1.
1 2 3 4 0 1 1 2 3 5 8
? Potrzebujesz pomocy? Rozwiązuj krok po kroku.
Krok 1 — pokaż podpowiedź
Po wstawieniu 1 lewy fragment to [1,4].
Krok 2 — pokaż podpowiedź
Przy 3 przesuwasz 4.
Krok 3 — pokaż podpowiedź
Każdy kolejny Fibonacci jest sumą dwóch poprzednich.
Otwórz tylko tyle podpowiedzi, ile potrzebujesz. Po każdym kroku wróć do zadania i sprawdź wynik.
Podsumowanie
Zapamiętaj
- Lewy fragment wstawiania jest już uporządkowany.
- Nie gub wyjmowanej karty — zapisz ją przed przesuwaniem.
- Iteracja ciągu potrzebuje stanu początkowego.
Po zalogowaniu zobaczysz dodatkowe lekcje i materiały oznaczone jako rozszerzenie. Podstawowe quizy i zadania pozostają dostępne w biurku.
Dalej na swoim koncie
Rozgrzewki, quiz i zadania są w biurku ucznia.
Teoria jest otwarta dla wszystkich. Żeby rozwiązywać zadania, zapisywać szkice i widzieć swój postęp, zaloguj się.
Zaloguj się →