Algorytmy rekurencyjne

Odkrywanie patternów w sekwencjach liczbowych może być skomplikowane, jednak można to uprościć za pomocą kilku technik, które przedstawię poniżej:

1. Obserwacja sekwencji:

• Dokładnie przyjrzyj się danej sekwencji.
• Zwróć uwagę na zmiany między kolejnymi wyrazami i spróbuj zauważyć zależność między liczbami.
• Zidentyfikuj ewentualne powtarzające się elementy lub regularne zmiany.

2. Różnicowanie

• Oblicz różnice między kolejnymi wyrazami sekwencji.
• Jeśli różnice tworzą prostszy wzór, można na ich podstawie wywnioskować pierwotny wzór.

3. Klasyfikacja wyrazów

• Podziel wyrazy na grupy według ich pozycji (np. wyrazy na parzystych pozycjach, wyrazy na nieparzystych pozycjach).

4. Formułowanie hipotezy

• Na podstawie obserwacji sformułuj potencjalne reguły lub wzory generowania wyrazów.
• Przetestuj te reguły na początkowych wyrazach, aby sprawdzić, czy są prawdziwe.

5. Rekursja i indukcja

• Użyj indukcji matematycznej co to indukcja do zaproponowania wzoru rekurencyjnego.
• Zweryfikuj przypadki bazowe, a następnie udowodnij, że jeśli wzór działa dla pewnych liczb, to będzie działał dla kolejnych.

Przykłady z kodem w Pythonie

Przykład 1: Prosta sekwencja
Mamy daną sekwencję: (−3,1,−4,−5,19,−96,−1825,175199,…)

Specyfikacja: a1 = -3, a2 = 1

Kod w Pythonie do rozwiązania tego algorytmu:

def gs(n):

    if n == 1:
        return -3
    elif n == 2:
        return 1
    return gs(n - 1) * gs(n - 2) - 1

number = int(input("Wprowadź liczbę: "))
print(gs(number))

Pattern: An = An − 1 ⋅ An − 2 −1

Przykład 2: Średnio skomplikowana sekwencja
Mamy daną sekwencję: −2, 2.5, 3, −5, 7.5, −4.5, −0.5, 8, −12.5…

Specyfikacja: a1 = -2, a2 = 2.5, a3 = 3

Kod w Pythonie do rozwiązania tego algorytmu:

def gs2(n):
    # Określamy kiedy program ma się skończyć
    if n == 1:
        return -2
    elif n == 2:
        return 2.5
    elif n == 3:
        return 3
    return gs2(n - 3) - gs2(n - 1)

number = int(input("Wprowadź liczbę: "))
print(gs2(number))

Pattern: An = An − 3 − An − 1

Przykład 3: Bardziej skomplikowana sekwencja
Mamy daną sekwencję: −1,0,0.5,1.5,1.5,1,−0.5,−2,−3,…

Specyfikacja: a1 = -1, a2 = 0, a3 = 0.5

Kod w Pythonie do rozwiązania tego algorytmu:

def gs3(n):
    if n == 1:
        return -1
    elif n == 2:
        return 0
    elif n == 3:
        return 0.5
    return (gs3(n - 1) * -1) + gs3(n - 3)

number = int(input("Wprowadź liczbę: "))
print(gs1(number))

Pattern: An = (An − 1 ⋅ −1) + An − 3

Mam nadzieję, że moje wyjaśnienie przynajmniej trochę wam pomogło pokonać swój strach przed algorytmami rekurencyjnymi. Będę wdzięczny za waszą łapkę w górę oraz subskrypcję na mojego GitHuba, jeśli uważasz, że to ci pomogło.

Kontakt:
Telegram: https://t.me/Supermario3
Email: smokejrhd@gmail.com