Stwórz proste algorytmy

Skip to content

To jest tekst przetłumaczony maszynowo, który może zawierać błędy!

Quote

„Algorytm”, słowo używane przez programistów, gdy nie chcą wyjaśnić, co zrobili.

Algoritme?

Co to jest algorytm?

Algorytm to logiczna funkcja, która wykonuje daną operację. Zatem, technicznie rzecz biorąc, można nazwać funkcję, która dodaje dwie liczby, „algorytmem”, ale najczęściej algorytm jest czymś nieco bardziej skomplikowanym. Często algorytmy są używane do przyspieszenia operacji, które zajmują dużo czasu.

Algorithm Meme

Czy muszę używać Pythona w tych zadaniach?

Nie! Możesz użyć dowolnego języka programowania, który preferujesz w tych zadaniach.

Wbudowane biblioteki?

Celem tych zadań jest unikanie używania wbudowanych bibliotek lub specjalnych funkcji Pythona. Na przykład, istnieje prosty “one-liner” do odwracania tekstu: text[::-1], ale tutaj chcemy, abyś spróbował rozwiązać takie zadania bez używania tego. Może się zdarzyć, że wspomnimy o wbudowanej funkcji, jeśli rozwiązanie jest nieco trudne do znalezienia. Zostanie to oznaczone ❗.

W praktyce powinno być w pełni możliwe rozwiązanie wszystkich tych zadań za pomocą if, for, while i zwykłych operacji na listach.

Jak “zaprojektować” algorytm?

Najczęściej algorytmy są projektowane iteracyjnie. Co to oznacza?

1. ✅ Najpierw rozbij problem na mniejsze części.
  • Najpierw pomyśl o tym, co jest absolutnie najważniejsze, aby algorytm działał
    • Czy ma zwrócić wartość? boolean? Listę?
    • Czy potrzebuję jakichś funkcji pomocniczych?

2. ❓ Czy istnieją jakieś „przypadki brzegowe”?
  • Co się stanie, jeśli wprowadzisz pustą listę lub tekst?

3. ✅ Zacznij od samego spróbowania stworzenia rozwiązania

4. ✅ Sprawdź, czy algorytm działa poprawnie pod względem czasu wykonania
  • Spróbuj większe dane wejściowe, czy zajmuje to dużo czasu?

5. ❓ Zastanów się nad swoim rozwiązaniem, czy potrzebujesz wszystkich kroków, które wykorzystałeś?
  • Czy wszystkie sprawdzenia if są konieczne?
  • Jeśli masz więcej niż jedną pętlę for, czy istnieją jasne sposoby, aby zrobić to w jednej pętli for?
    • To zależy, czy masz pętle zagnieżdżone czy pętle następujące po sobie. Pętle następujące po sobie często można uniknąć.

6. ✅ Rozważ ekstremalne scenariusze z danymi wejściowymi:
  • Przykład z liczbami: duże liczby, małe liczby, liczby ujemne
  • Przykład tekstu: dużo tekstu, wiele małych słów, dodatkowe spacje, duże i małe litery.

7. ❓ Czy używanie pseudo-kodu pomaga lepiej zrozumieć logikę?

Easy Zadanie 1 - Sprawdzenie, czy lista zawiera daną liczbę

Stwórz algorytm (funkcję), który sprawdzi, czy lista zawiera daną liczbę. Powinna ona zwracać True lub False w zależności od tego, czy liczba występuje na liście, czy nie.

Oto lista z danymi testowymi:

Test-data for algoritme:
Test-Data Sjekk Svar
[1, 2, 3, 4, 5, 6, 7, 8, 9] 5 True
[1, 2, 3, 4, 5, 6, 7, 8, 9] 10 False
[2, 3, 5, 7, 11, 13, 17, 19, 23] 2 True
[2, 3, 5, 7, 11, 13, 17, 19, 23] 10 False
[-1, 0, 1, -34, 321, 22, 98, -214] -214 True
[-1, 0, 1, -34, 321, 22, 98, -214] 0 True
[-1, 0, 1, -34, 321, 22, 98, -214] 2 False

Tips til framgangsmåte
  1. Przekaż listę i wartość listy do funkcji. W tym zadaniu będą to liczby, ale mogą to być również teksty.
  2. Użyj pętli for do iteracji po liście.
  3. Jeśli liczba jest równa liczbie kontrolnej, zwróć True.
  4. Jeśli pętla for się zakończy i nie znajdziesz jej, zwróć False.

Svaret (i python) 
def exists_in_list(the_list, check):
    for number in the_list:
        if number == check:
            return True
    return False

Easy Zadanie 2 - Sumowanie

Stwórz algorytm, który sumuje listę liczb.

Test-data for algoritme:
  • [1, 2, 3, 4, 5, 6], daje odpowiedź 21.
  • [5, 1, 23, 68, 22, 13, 4], daje odpowiedź 136
  • [3, 3, -3, -3, 3] daje odpowiedź 3. Ewentualnie możesz zignorować liczby ujemne i dać odpowiedź 9.

Tips til framgangsmåte
  1. Umieść listę w funkcji.
  2. Zapisz tymczasową sumę jako 0.
  3. Użyj pętli for do przeiterowania listy.
  4. return suma listy.

Svaret (i python) 
def sum_list(numbers):
    total = 0
    for num in numbers:
        total += num
    return total

Medium Zadanie 3a - Wartość maksymalna w liście

Stwórz algorytm, który znajduje największą wartość w liście.

Test-data for algoritme:
  • [1, 2, 3, 4, 5, 6], daje odpowiedź 6.
  • [6, 17, 227, 1, 23, 42, 12], daje odpowiedź 227
  • [2, -2, 2, -2, -2, 2] daje odpowiedź 2.

Tips til framgangsmåte
  1. Umieść listę w funkcji.
  2. Ustaw tymczasową wartość na pierwszy element listy.
  3. Użyj pętli for aby przejść przez listę i porównać z wartością ustawioną w punkcie 2.
  4. Jeśli wartość jest większa, ustaw tymczasową wartość na nową wartość.
  5. return ta tymczasowa wartość.

Svaret (i python) 
def find_max(numbers):
    largest = numbers[0]
    for num in numbers:
        if num > largest:
            largest = num

    return largest

Easy Zadanie 3b - Jeśli lista jest pusta?

Dodaj sprawdzenie, czy lista zawiera elementy. Jeśli nie, zwróć None.

Svaret (i python) 
def find_max(numbers):
    if len(numbers) == 0:
        return None

    largest = numbers[0]
    for num in numbers:
        if num > largest:
            largest = num

    return largest

Easy Zadanie 4 - Liczenie liczby danego elementu w liście

Stwórz algorytm, który zlicza liczbę danego elementu w liście.

Test-data for algoritme:
  • ["apple", "banana", "orange", "apple", "apple", "banana"] z apple daje odpowiedź 3.
  • [1, 4, 5, 2, 4, -3, -4, 4, 2, 4, 221, 3, 1, 1, 4, 1, 12, 33, 4, 4, 2, -4, 1, 4] z 4 daje odpowiedź 8.
  • ["cat", "dog", "cat", "mouse", "cat", "dog", "dog"] z dog daje odpowiedź 3.
  • [7, 7, 2, 9, 7, 1, 0, 7, 3, 7, 9] z 7 daje odpowiedź 5.
  • ["red", "blue", "green", "red", "yellow", "red"] z red daje odpowiedź 3.
  • [10, -2, -2, -2, 5, 10, 10, -2] z -2 daje odpowiedź 4.

Tips til framgangsmåte
  1. Przyjmij listę i wartość kontrolną w funkcji
  2. Zacznij od tymczasowej wartości licznika ustawionej na 0.
  3. Przejdź przez listę za pomocą pętli for.
  4. Jeśli element jest równy sprawdzeniu, zwiększ wartość licznika o 1.
  5. Zwróć wartość licznika.

Svaret (i python) 
def count(the_list, check):
    count = 0
    for element in the_list:
        if element == check:
            count += 1

    return count

Medium Zadanie 5 - Odwrócenie stringa, tekstu

Stwórz algorytm, który odwraca dany string.

Test-data for algoritme:
  • Hello there! staje się !ereht olleH.
  • heisann alle sammen staje się nemmas ella nnasieh
  • Python staje się nohtyP
  • racecar staje się racecar
  • 12345abc staje się cba54321
  • god morgen staje się negrom dog

Tips til framgangsmåte
  1. Przyjmij string jako argument funkcji.
  2. Utwórz zmienną tymczasową do przechowywania pustego string.
  3. Przejdź przez tekst za pomocą pętli for z range. Możesz przejść przez listę od tyłu, ale można również rozwiązać to, przechodząc do przodu po liście.
  4. Dodawaj każdy znak do zmiennej tymczasowej po kolei.
  5. Zwróć tymczasowy tekst.

Svaret (i python) 
def reverse(text):
    result = ""
    # Ta linia jest nieco skomplikowana, ale zaczyna się
    # od końca, przechodzi (włącznie) do 0 (pisząc
    # -1 jako koniec) i odlicza w dół o 1 za każdym razem
    for i in range(len(text) - 1, -1, -1):
        result += text[i]
    return result

Opcjonalnie możesz użyć algorytmu, który dodaje na początku zamiast tego:

def reverse(text):
   result = ""
   for i in range(0, len(text)):
       # dodaj na początku zamiast tego
       result = text[i] + result
   return result

Medium Zadanie 6 - Algorytm palindromu

Stwórz algorytm, który sprawdza, czy dane słowo jest palindromem. Przykładami palindromów są abba, racecar, regninger.

Tips til framgangsmåte
  1. Utwórz funkcję, która przyjmuje tekst do sprawdzenia.
  2. Użyj pętli for, aby sprawdzić, czy litery po każdej stronie tekstu są takie same.
  3. Zwróć False, jeśli litera się nie zgadza, a jeśli wszystkie się zgadzają (pętla for się zakończy), zwróć True.

Ekstra:
Czy widzisz, jak możesz uczynić algorytm dwa razy szybszym?

Hint

Musisz sprawdzić tylko połowę!

Odpowiedź (w pythonie) 
def palindrome(text):
    for i in range(0, len(text)):
        if text[i] != text[len(text) - i - 1]:
            return False
    return True
Szybszy algorytm

def palindrome(text):
for i in range(0, int(len(text) / 2)):
if text[i] != text[len(text) - i - 1]:
return False
return True

Medium Zadanie 7 - Sprawdzenie, czy lista jest posortowana

Stwórz algorytm, który sprawdza, czy lista jest posortowana. Najłatwiejszym sposobem na sprawdzenie tego jest rozpoczęcie od początku i porównywanie, czy następny element jest „większy”. Jeśli element nie jest „większy”, lista nie jest posortowana.

Test-data for algoritme:
  • [1, 2, 3, 4, 5, 6], daje odpowiedź True.
  • [6, 17, 227, 1, 23, 42, 12], daje odpowiedź False
  • [2, -2, 2, -2, -2, 2] daje odpowiedź False.
  • [2, 2, 3, 4, 4, 6], daje odpowiedź True.
  • [12, 23, 34, 45, 56, 67], daje odpowiedź True.

Tips til framgangsmåte
  1. Utwórz funkcję, która przyjmuje listę
  2. Użyj pętli for aby przejść przez całą listę (użyj range do długości listy, minus 1 len(list) - 1)
  3. Porównaj element \(n\) z \(n + 1\), czyli bieżący element z następnym elementem.
  4. Jeśli \(n\) jest mniejsze niż \(n + 1\), przejdź do następnego porównania.
  5. Jeśli nie jest mniejsze, ale większe, lista nie jest posortowana. Zwróć False tutaj.
  6. Jeśli dotrzesz do końca, lista jest posortowana, zwróć True.

Svaret (i Python) 
def is_sorted(the_list):
    for i in range(len(the_list) - 1):
        if the_list[i] > the_list[i + 1]:
            return False
    return True

Medium Zadanie 8 - Tasowanie

Stwórz algorytm, który tasuje listę elementów. Istnieje wiele sposobów, aby to zrobić, ale jednym z dobrych jest algorytm tasowania Fishera-Yatesa. Możesz dowiedzieć się więcej na ten temat tutaj Wikipedia.

Test Data
  • ["a", "b", "c", "d", "e"] → może stać się np. ["c", "e", "a", "d", "b"]
  • [1, 2, 3, 4, 5, 6] → może stać się np. [4, 1, 6, 3, 2, 5]
  • ["apple", "banana", "orange"] → może stać się np. ["orange", "apple", "banana"]
  • ["x"] → pozostaje nadal ["x"]
  • [] → pozostaje nadal []

Działa to tak:

Algoritmen
  1. Utwórz funkcję, która przyjmuje listę liczb
  2. Utwórz nową pustą listę, która będzie przechowywać mieszany wynik.
  3. Użyj random do wybrania losowego indeksu w liście.
  4. Dodaj ten element do pustej listy i usuń go ze starej
  5. Zwróć nową listę z funkcji

Svaret (i Python) 
import random

def shuffle(the_list):
    shuffled = []

    while len(the_list) > 0:
        i = random.randrange(0, len(the_list))
        shuffled.append(the_list[i])
        the_list.pop(i)

    return shuffled

Medium Zadanie 9 - Bogo-sort

W tym zadaniu musisz stworzyć (praktycznie) okropny, ale niezwykle prosty algorytm sortowania. Jest on niezwykle słaby, jeśli chodzi o duże listy (zajmie wieczność z więcej niż 12-13 elementami). Na poziomie 2 stworzymy lepszy algorytm sortowania, bubble-sort.

Test Data
  • [3, 1, 2] → [1, 2, 3]
  • [5, 4, 3, 2, 1] → [1, 2, 3, 4, 5]
  • [10, 7, 8, 2] → [2, 7, 8, 10]
  • [1, 1, 1] → [1, 1, 1]
  • [9, 3, 6, 3, 9] → [3, 3, 6, 9, 9]
  • [0, -1, 4, -2] → [-2, -1, 0, 4]

Algorytm działa w następujący sposób:

Algoritmen
  1. Utwórz funkcję, która przyjmuje listę nieposortowanych liczb.
  2. Wymieszaj listę losowo (użyj funkcji shuffle z zadania 8).
  3. Sprawdź, czy lista jest posortowana (użyj sprawdzenia, które stworzyłeś w zadaniu 7).
  4. Jeśli lista nie jest posortowana, powtórz kroki 2 i 3.
  5. Powtarzaj, aż lista będzie posortowana, a następnie zwróć ją.

Prosto mówiąc: bogo-sort miesza całą listę i liczy na to, że będzie posortowana.

Gru bogo sort meme
Dowiedz się o notacji Big O w Level 2.

Wskazówka: Chętnie użyj shuffle z zadania 8, aby utworzyć nieposortowaną listę dla swojego algorytmu.

Svaret (i Python) 
def bogo_sort(the_list):
    while not is_sorted(the_list):
        the_list = shuffle(the_list)
    return the_list

Hard Zadanie 10a - Szukanie tekstu - “substring” (Trudne!)

Stwórz algorytm, który może znaleźć słowo kluczowe w tekście. Oznacza to, że jeśli masz zdanie takie jak hello there, zwrócisz True dla słowa kluczowego hello i False dla słowa kluczowego takiego jak hahah. Ten algorytm powinien działać dla dowolnych danych wejściowych i wyjściowych.

Użyj danych tekstowych poniżej, aby sprawdzić, czy twój algorytm działa.

Test-data for algoritme:
  • hello there everyone z there = True
  • hello there everyone z ever = True
  • hello there everyone z then = False
  • qwecvyufavsjekkftyergwcery z sjekk = True

Tips til framgangsmåte
  1. Utwórz funkcję, która przyjmuje dwa stringi, dane i słowo kluczowe.
  2. Użyj pętli for z range, aby przejść przez tekst.
  3. Ważne jest, aby pomyśleć, jak daleko ma sięgać pętla.
  4. Utwórz tymczasową zmienną, która mówi, czy słowo kluczowe zostało znalezione, ustaw ją na True domyślnie.
  5. Użyj kolejnej pętli for z range, aby porównać miejsce, w którym jesteś w tekście, ze słowem kluczowym.
  6. Jeśli coś w słowie kluczowym nie pasuje do miejsca, które sprawdzasz teraz, ustaw tymczasową zmienną na True i break z wewnętrznej pętli.
  7. Jeśli dojdziesz do końca tekstu, nie znajdując nic, zwróć False.

Svaret (i Python) 
def search(data, word): 
    for i in range(0, len(data) - len(word) + 1):
        found = True
        for j in range (0, len(word)):
            if data[i + j] != word[j]:
                found = False
                break
        if found:
            return True

    return False

Easy Zadanie 10b

Dodaj również dodatkową kontrolę, która upewni się, że słowo kluczowe nie jest dłuższe niż zdanie.

Tips til framgangsmåte
  • Dodaj tę kontrolę przed pętlą for.

Svaret (i python) 
def search(data, word): 
    if len(word) > len(data):
        return False

    for i in range(0, len(data) - len(word) + 1):
        found = True
        for j in range (0, len(word)):
            if data[i + j] != word[j]:
                found = False
                break
        if found:
            return True

    return False

Hard Zadanie 11 - Odwracanie słów w zdaniu (Trudne)

Przypomnij sobie Zadanie 5 dotyczące odwracania zdania. Zmodyfikuj (lub zacznij od nowa) algorytm, który odwraca każde pojedyncze słowo w zdaniu, a następnie łączy je z powrotem.

Test-data for algoritme:
  • hello there everyone staje się olleh ereht enoyreve
  • This is the way it goes! staje się sihT si eht yaw ti !seog
  • does this racecar go? of course! staje się seod siht racecar ?og fo !esruoc

Tips til framgangsmåte
  1. Utwórz funkcję, która przyjmuje string.
  2. ❗Podziel tekst używając .split(" ").
  3. Utwórz tymczasową zmienną do przechowywania wartości końcowej.
  4. Użyj pętli for do przechodzenia przez każde słowo.
  5. Użyj tej samej metody odwracania, co w Zadaniu 5
  6. Użyj wyniku i dodaj go do zmiennej utworzonej w kroku 2.
  7. Zwróć wartość końcową

Svaret (i Python) 
def reverse_words(words):
    sentence = words.split(" ")
    output = ""

    for word in sentence:
        reversed_word = ""
        for i in range(0, len(word)):
            reversed_word = word[i] + reversed_word
        output += reversed_word + " "

    return output

➕Dodatkowo:

Cracked Zadanie E1 - Usuwanie duplikatów z listy

Załóżmy, że masz listę zawierającą liczby lub tekst, ale chcesz usunąć duplikaty. Stwórz algorytm, który usuwa wszystkie duplikaty z listy i zawiera tylko pierwsze wystąpienie każdego unikalnego elementu w liście.

Tips til framgangsmåte
  1. Zacznij od funkcji, która przyjmuje listę
  2. Tutaj użyjemy pętli while zamiast for. Ułatwia to w Pythonie, w innych językach for z zmiennymi liczącymi działa dobrze.
  3. Utwórz zmienną liczącą idx (dla indeksu, lub i)
  4. Użyj pętli while, która ma przebiegać do długości listy
  5. Porównamy element na idx ze wszystkimi innymi elementami
  6. Utwórz zmienną liczącą jdx (lub j), która zaczyna się od idx + 1
  7. Porównaj element na idx z elementem na jdx, jeśli są takie same, usuń jdx za pomocą pop(jdx).
  8. PAMIĘTAJ! Jeśli usuniesz element, lista się zmniejszy, dlatego musimy cofnąć się o jeden krok przy jdx -= 1.
  9. Zwiększ jdx o 1 i przetestuj następny element
  10. Po wewnętrznej pętli while zwiększ idx o 1, a zewnętrzna pętla while będzie kontynuować
  11. Na koniec zwróć listę z usuniętymi duplikatami

Test Data
  • [1, 2, 2, 3, 1, 4, 3] → staje się [1, 2, 3, 4]
  • ["a", "b", "a", "c", "b", "d"] → staje się ["a", "b", "c", "d"]
  • [5, 5, 5, 5] → staje się [5]
  • ["x", "y", "z", "x", "y", "x"] → staje się ["x", "y", "z"]
  • [10, -1, 10, -1, 0, 0, 10] → staje się [10, -1, 0]
  • ["apple", "apple', "banana", "orange", "apple", "orange", "pear", "apple"]
    • Powinno dać: ["apple", "banana", "orange", "pear"]

Svaret (i Python) 
def delete_duplicates(the_list):
    idx = 0

    while idx < len(the_list):
        jdx = idx + 1

        while jdx < len(the_list):
            if the_list[idx] == the_list[jdx]:
                the_list.pop(jdx)
                jdx -= 1
            jdx += 1
        idx += 1

    return the_list

Cracked Zadanie E2 - Counting Sort

Counting sort jest jednym z niewielu algorytmów sortowania, które działają w czasie, który nazywamy \(O(n)\). Oznacza to, że nie zajmuje on dużo więcej czasu niż liczba elementów na liście. Więcej o notacji Big O można przeczytać w Level 2.

Trochę zależy to od zakresu elementów. Jeśli najmniejszy to 0, a największy to 100000, może to trochę potrwać, więc można go użyć, jeśli zakres wartości jest niewielki. Nie działa on również dla liczb ujemnych, ale można zmodyfikować algorytm, aby działał z liczbami ujemnymi.

Algorytm działa następująco:

  • Dowiedz się, jak duży jest największy element, zapisz wartość tego elementu jako \(k\).
  • Utwórz listę zawierającą \(k + 1\) elementów, count.
  • Przejdź przez nieposortowaną listę i użyj wartości liczby jako indeksu. Oznacza to, że jeśli element ma wartość 47, przejdź do count[47] i zwiększ go o 1.
  • Przejdź przez listę count i umieść liczbę liczb, którą jest indeks. Na przykład: jeśli na indeksie 1 znajduje się 3, dodaj trzy liczby 1.

Testdata
Usortert Data Sortert Data
[7, 3, 9, 1, 4, 3, 0, 6, 8, 6, 2, 1, 9, 0, 5, 4] [0, 0, 1, 1, 2, 3, 3, 4, 4, 5, 6, 6, 7, 8, 9, 9]
[12, 13, 15, 0, 8, 15, 8, 5, 16, 8, 0, 20, 4, 9, 17, 16, 1, 3, 6, 15, 5, 2, 3, 1, 19, 13, 17, 5, 3, 10] [0, 0, 1, 1, 2, 3, 3, 3, 4, 5, 5, 5, 6, 8, 8, 8, 9, 10, 12, 13, 13, 15, 15, 15, 16, 16, 17, 17, 19, 20]

Tips til framgangsmåte
  1. Zacznij od stworzenia funkcji z listą jako danymi wejściowymi
  2. Stwórz pustą listę output
  3. Użyj pętli for aby przejść przez całą listę
  4. Śledź wartość maksymalną w zmiennej przed pętlą for.
  5. Zaktualizuj wartość maksymalną, jeśli znajdziesz coś większego
  6. Stwórz listę, która zawiera tę liczbę zer + 1. Przykład: największa wartość to 47, wtedy tworzysz listę z 48 zerami. Możesz to zrobić za pomocą [0] * (maks + 1) lub pętli for. Nazwij ją count.
  7. Przejdź przez listę ponownie za pomocą pętli for.
  8. Użyj wartości elementu jako indeksu i zwiększ o 1. count[value] += 1
  9. Użyj pętli for aby przejść przez listę count.
  10. Użyj wartości na każdym indeksie, aby dodać tę liczbę elementów
  11. Zwróć posortowaną listę

Svaret (i Python) 
def counting_sort(input_list):
    output = []

    max_val = input_list[0]

    for n in input_list:
        if n > max_val:
            max_val = n

    # to stworzy stos zer
    count = [0] * (max_val + 1)

    for n in input_list:
        count[n] += 1

    for i in range(len(count)):
        # użyj _ aby zignorować wartość
        for _ in range(count[i]):
            output.append(i)

    return output