NWD i NWW - zastosowania

Wprowadzenie

NWD (Największy Wspólny Dzielnik) i NWW (Najmniejsza Wspólna Wielokrotność) to fundamentalne pojęcia w teorii liczb, które mają liczne praktyczne zastosowania w programowaniu, matematyce i życiu codziennym.

W tej lekcji poznamy zaawansowane zastosowania NWD i NWW oraz rozwiążemy praktyczne problemy.

Zastosowania NWD i NWW obejmują:

Problemy czasowe (synchronizacja, cykle, harmonogramy)
Geometria (kratki, podziały, płytki)
Upraszczanie obliczeń (ułamki, proporcje)
Optymalizacja (minimalizacja, maksymalizacja)
Kryptografia (generowanie kluczy, szyfrowanie)
Muzyka (rytmy, harmonie, interwały)

Podstawowe wzory i własności

Relacja między NWD i NWW

Wyjście:

=== Relacja: NWD × NWW = a × b ===

a        b        NWD      NWW      a×b          NWD×NWW      Równe?
---------------------------------------------------------------------------
12       18       6        36       216          216          ✓
15       25       5        75       375          375          ✓
7        11       1        77       77           77           ✓
48       64       16       192      3072         3072         ✓

Własności NWD i NWW

1. NWD(a, b) × NWW(a, b) = a × b
2. NWD(a, b) ≤ min(a, b)
3. NWW(a, b) ≥ max(a, b)
4. NWD(a, b) | NWW(a, b)
5. Jeśli NWD(a, b) = 1, to NWW(a, b) = a × b

Zastosowanie 1: Problemy czasowe i cykliczne

Problem: Kiedy spotkają się ponownie?

Sytuacja: Dwa autobusy odjeżdżają z przystanku jednocześnie. Pierwszy wraca co 12 minut, drugi co 18 minut. Po jakim czasie spotkają się ponownie na przystanku?

Wyjście:

=== Problem autobusów ===

Autobus A: co 12 min, Autobus B: co 18 min
  Spotkają się ponownie za: 36 minut
  Autobus A: 3 kursów
  Autobus B: 2 kursów

Autobus A: co 15 min, Autobus B: co 20 min
  Spotkają się ponownie za: 60 minut
  Autobus A: 4 kursów
  Autobus B: 3 kursów

Autobus A: co 10 min, Autobus B: co 25 min
  Spotkają się ponownie za: 50 minut
  Autobus A: 5 kursów
  Autobus B: 2 kursów

Problem: Synchronizacja sygnałów świetlnych

Wyjście:

=== Synchronizacja świateł ===

Cykle świateł: 30s, 45s, 60s
  Synchronizacja za: 180s (3 min 0s)
  Światło 1: 6 cykli
  Światło 2: 4 cykli
  Światło 3: 3 cykli

Cykle świateł: 20s, 25s, 30s
  Synchronizacja za: 300s (5 min 0s)
  Światło 1: 15 cykli
  Światło 2: 12 cykli
  Światło 3: 10 cykli

Zastosowanie 2: Problemy geometryczne

Problem: Kafelkowanie podłogi

Sytuacja: Pokój ma wymiary 360cm × 480cm. Jaki największy kwadratowy kafelek (bez cięcia) możemy użyć?

Wyjście:

=== Kafelkowanie podłogi ===

Pokój 1: 360cm × 480cm
  Największy kafelek: 120cm × 120cm
  Liczba kafelków: 12
  Układ: 3 × 4

Pokój 2: 240cm × 360cm
  Największy kafelek: 120cm × 120cm
  Liczba kafelków: 6
  Układ: 2 × 3

Łazienka: 150cm × 225cm
  Największy kafelek: 75cm × 75cm
  Liczba kafelków: 6
  Układ: 2 × 3

Problem: Punkty całkowite na odcinku

Pytanie: Ile punktów kratowych (całkowitych) leży wewnątrz odcinka od (0,0) do (a,b)?

Wyjście:

=== Punkty kratowe na odcinku ===

Odcinek         NWD      Punkty wewnątrz    Wszystkie punkty
-----------------------------------------------------------------
(0,0) → (6,9)    3        2                  4
(0,0) → (12,18)  6        5                  7
(0,0) → (7,11)   1        0                  2
(0,0) → (10,15)  5        4                  6

Zastosowanie 3: Upraszczanie i obliczenia

Problem: Dodawanie ułamków

Wyjście:

=== Dodawanie ułamków ===

1/6 + 1/4 = 5/12
  Wspólny mianownik (NWW): 12

2/3 + 3/4 = 17/12
  Wspólny mianownik (NWW): 12

5/12 + 7/18 = 29/36
  Wspólny mianownik (NWW): 36

Problem: Skalowanie proporcji

Wyjście:

=== Skalowanie proporcji ===

Mieszanka: 15:25, suma = 80
  Proporcja uproszczona: 3:5
  Wynik: 30:50 (suma = 80)

Stosunek: 6:9, suma = 100
  Proporcja uproszczona: 2:3
  Wynik: 40:60 (suma = 100)

Podział: 4:6, suma = 50
  Proporcja uproszczona: 2:3
  Wynik: 20:30 (suma = 50)

Zastosowanie 4: Harmonogramy i planowanie

Problem: Wspólne dni wolne

Wyjście:

=== Wspólne dni wolne ===

Osoba A: co 3 dni, Osoba B: co 4 dni, okres: 30 dni
  Wspólne dni wolne: [0, 12, 24]
  Liczba spotkań: 3
  Częstotliwość: co 12 dni

Osoba A: co 5 dni, Osoba B: co 7 dni, okres: 70 dni
  Wspólne dni wolne: [0, 35, 70]
  Liczba spotkań: 3
  Częstotliwość: co 35 dni

Problem: Rotacja zmian

Wyjście:

=== Rotacja zmian roboczych ===

Zmiana A: 2 dni, Zmiana B: 3 dni
  Cykl powtarza się po: 6 dniach
  Zmiana A: 3 rotacji
  Zmiana B: 2 rotacji

Zmiana A: 4 dni, Zmiana B: 6 dni
  Cykl powtarza się po: 12 dniach
  Zmiana A: 3 rotacji
  Zmiana B: 2 rotacji

Zmiana A: 5 dni, Zmiana B: 7 dni
  Cykl powtarza się po: 35 dniach
  Zmiana A: 7 rotacji
  Zmiana B: 5 rotacji

Zastosowanie 5: Problemy kombinatoryczne

Problem: Dzielenie przedmiotów

Wyjście:

=== Równy podział przedmiotów ===

24 cukierki, 36 czekoladek
  Maksymalna liczba osób: 12
  Każda osoba dostanie: 2 + 3

48 długopisów, 72 zeszyty
  Maksymalna liczba osób: 24
  Każda osoba dostanie: 2 + 3

15 jabłek, 25 pomarańczy
  Maksymalna liczba osób: 5
  Każda osoba dostanie: 3 + 5

Problem: Najmniejsza liczba paczek

Wyjście:

=== Minimalna liczba paczek ===

Paczki 6 i 8 sztuk, potrzeba: 50
  NWW(paczek): 24
  Minimalna liczba przedmiotów: 72
  Paczek typu 1: 12 (6 szt/paczka)
  Paczek typu 2: 9 (8 szt/paczka)

Paczki 12 i 15 sztuk, potrzeba: 100
  NWW(paczek): 60
  Minimalna liczba przedmiotów: 120
  Paczek typu 1: 10 (12 szt/paczka)
  Paczek typu 2: 8 (15 szt/paczka)

Zastosowanie 6: Muzyka i rytmy

Problem: Synchronizacja rytmów

Wyjście:

=== Synchronizacja rytmów muzycznych ===

Rytm 3/4 i 4/4
  Synchronizacja po: 12 taktach
  Rytm 1: 4 cykli
  Rytm 2: 3 cykli

Rytm 2/4 i 3/4
  Synchronizacja po: 6 taktach
  Rytm 1: 3 cykli
  Rytm 2: 2 cykli

Rytm 5/4 i 7/4
  Synchronizacja po: 35 taktach
  Rytm 1: 7 cykli
  Rytm 2: 5 cykli

Kompleksowy przykład

Problem: Organizacja wydarzeń

Wyjście:

=== Kompleksowy planer wydarzeń ===

Wydarzenia synchronizują się po: 42 dniach

Zebranie zespołu (co 7 dni):
  Wystąpienia w cyklu: 6
  Pierwsze dni: [0, 7, 14, 21, 28, 35]

Szkolenie (co 14 dni):
  Wystąpienia w cyklu: 3
  Pierwsze dni: [0, 14, 28, 42]

Audyt (co 21 dni):
  Wystąpienia w cyklu: 2
  Pierwsze dni: [0, 21, 42]

Złożoność obliczeniowa

Analiza wydajności

Operacja	Złożoność	Uwagi
NWD(a, b)	O(log min(a, b))	Algorytm Euklidesa
NWW(a, b)	O(log min(a, b))	Wymaga NWD
NWD wielu liczb	O(n log max)	n liczb
NWW wielu liczb	O(n log max)	n liczb

Podsumowanie

Kluczowe zastosowania

✅ Problemy czasowe: Autobusy, sygnalizacja, harmonogramy ✅ Geometria: Kafelkowanie, punkty kratowe, podziały ✅ Ułamki: Dodawanie, odejmowanie, upraszczanie ✅ Planowanie: Wydarzenia cykliczne, rotacje zmian ✅ Podział: Równe dzielenie przedmiotów ✅ Muzyka: Synchronizacja rytmów, harmonie

Kiedy używać NWD?

Upraszczanie (ułamki, proporcje)
Maksymalizacja podziału (największy kafelek)
Liczby względnie pierwsze
Wspólne dzielniki

Kiedy używać NWW?

Synchronizacja (cykle, wydarzenia)
Minimalizacja okresu (spotkania, rytmy)
Wspólny mianownik (ułamki)
Harmonogramy

Co dalej?

Po opanowaniu zastosowań NWD i NWW, następne kroki to:

Lekcja 69: Rozkład na czynniki pierwsze
Faktoryzacja liczb
Algorytmy rozkładu
Zastosowania w kryptografii
Lekcja 70: Liczby doskonałe
Definicja i własności
Algorytmy znajdowania
Liczby obfite i niedoborne
Lekcja 71: Pierwiastkowanie - metoda Newtona
Algorytm aproksymacji
Pierwiastki wyższych stopni
Zastosowania numeryczne

Zadania praktyczne

Zadanie 1: Kalkulator ułamków

Napisz pełny kalkulator do operacji na ułamkach (dodawanie, odejmowanie, mnożenie, dzielenie) z automatycznym upraszczaniem.

Zadanie 2: Planer transportu

System autobusowy ma 5 linii z różnymi interwałami. Znajdź optymalny harmonogram synchronizacji.

Zadanie 3: Kafelkowanie 3D

Rozszerz problem kafelkowania na prostopadłościan o wymiarach a×b×c. Znajdź największy sześcian.

Zadanie 4: Muzyczny sekwencer

Symuluj synchronizację 4 różnych rytmów muzycznych i wizualizuj momenty synchronizacji.

Zadanie 5: Problem chińskiego tw. o resztach

Użyj NWD/NWW do rozwiązania układu kongruencji: x ≡ a₁ (mod m₁), x ≡ a₂ (mod m₂).

Następna lekcja: Rozkład na czynniki pierwsze - faktoryzacja liczb