Algorytmy rekurencyjne

#python #algorithms #tutorial

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