Zajęcia 4 (2025-11-14)

Zadanie domowe (na 2025-11-21)

Stwórz krótki (około 30 sekund) utwór w Sonic Pi spełniający następujące wymagania:

Wykorzystujący algorytm jako główny motyw/element kompozycyjny utworu

Algorytmy

Algorytm - zbiór instrukcji pozwalający na rozwiązanie jakiegoś problemu. Przedstawiany zazwyczaj w jednej z następujących form:

Lista kroków - lista uporządkowana opisująca słownie czynności (podobne do przepisu kulinarnego)
Schemat blokowy - rysunek ilustrujący kolejne kroki algorytmu jako bloki połączone ścieżkami
Pseudokod - zapis w języku przypominającym język programowania
Przykładowa implementacja w języku programowania

Przeszukiwanie liniowe

Cel: znalezienie wartości w tablicy

Zapis algorytmu przy pomocy listy kroków

Zainicjalizuj zmienną n wartością 0. Będzie ona indeksem dla przeszukiwanej tablicy.
Sprawdź czy n-ta wartość w tablicy jest szukaną wartością. Jeśli tak zakończ algorytm.
Zwiększ n o 1
Jeśli n jest większe bądź równe ilości elementów w tablicy zakończ niepowodzeniem
Przejdź do kroku 2

Zapis algorytmu z użyciem schematu blokowego

Na rysunku x jest poszukiwaną wartością, A tablicą, n licznikiem początkowo równym 0

Implementacja w Sonic Pi

Dodano do niej warstwę dźwiękową, w której odtwarzamy odwiedzane dźwięki, a w momencie znalezienia - dostajemy dźwięk chóru.

A = [:c4, :e4, :g4, :f4, :c5, :d6, :e6]
x = :c5
n = 0

live_loop :linear_search do
    if A[n] == x then
        sample :ambi_choir
        stop
    end

    play A[n]
    sleep 1
    n = n + 1
end

Przyklad możemy powtarzać w nieskończoność, poprzez reset licznika i losowanie nowej szukanej wartości po znalezieniu poprzedniej:

A = [:c4, :e4, :g4, :f4, :c5, :d6, :e6]
x = :c5
n = 0

live_loop :linear_search do
  if A[n] == x then
    sample :ambi_choir
    sleep sample_duration(:ambi_choir)
    x = A.choose # wylosuj losowy element z A
    n = 0
  else
    play A[n]
    sleep 1
    n = n + 1
  end
end

Przeszukiwanie binarne

Cel: znalezienie wartości w posortowanej tablicy

Algorytm przeszukiwania binarnego pozwala na (średnio) dużo szybsze znalezienie wartości w tablicach, poprzez wykorzystania faktu posortowania tablicy - tzn. elementy muszą być uporządkowane niemalejąco.

Zapis algorytmu z użyciem listy kroków

Zdefiniuj zmienne: dolna = 0, górna = długość tablicy
Wylicz środek tablicy: (dolna + górna) / 2
Jeśli tablica[środek] jest równa poszukiwanej wartości, zakończ
Jeśli tablica[środek] jest mniejsza od poszukiwanej wartości, dolna = środek i przejdź do punktu 2
górna = środek i przejdź do punktu 2

Zapis algorytmu z użyciem schematu blokowego

Implementacja w Sonic Pi

A = [60, 61, 63, 66, 68, 70, 77, 80, 81]
x = 66
dolna = 0
górna = A.length

live_loop :binary_search do
  środek = (dolna + górna)/2
  if A[środek] == x then
    sample :ambi_choir
    stop
  end
  
  play A[środek]
  sleep 1
  if A[środek] < x then
    dolna = środek
  else
    górna = środek
  end
end

Porównywanie dźwięków używając symboli, np. :c4 < :a4 może dać nieoczekiwane rezultaty! Symbole porównywane są leksykograficznie - znak po znaku, a nie wg wartości muzycznych. Stąd dla muzyka :C4 to niższy dźwięk niż :A4, a dla Sonic Pi - wyższy (a przynajmniej przed odtworzeniem albo skonwertowaniem na postać liczbową). Z tego powodu powyższy przykład wykorzystuje wartości midi, a nie symbole.

Podobnie do przykładu przeszukiwania liniowego, obliczenia możemy powtarzać w nieskończoność przez reset do stanu początkowego zmiennych dolna, górna oraz wybór innego celu przeszukiwania poprzez losowanie

A = [60, 61, 63, 66, 68, 70, 77, 80, 81]
# spróbuj zamiast ręcznie tworzonej automatycznie stworzonej od 50 do 80: A = 50.upto(80).to_a
x = 66
dolna = 0
górna = A.length

live_loop :binary_search do
  środek = (dolna + górna)/2
  if A[środek] == x then
    sample :ambi_choir
    sleep sample_duration(:ambi_choir)
    dolna = 0
    górna = A.length
    x = A.choose
  else
    play A[środek]
    sleep 1
    if A[środek] < x then
      dolna = środek
    else
      górna = środek
    end
  end
end