Pomocný program k řešení úlohy do DIM

dim-abeceda-2.py

#! /usr/bin/env python

"""
Zadání úlohy:
    Kolik slov délky n lze sestavit v abecedě {A,B,C,D} za podmínky, že prvky A a B nesousedí
    (ale A může sousedět s A, B může sousedět s B).
"""

import itertools
from math import sqrt

abeceda = ["A", "B", "C", "D"]
n = 10

# zkontrolovat, jestli A a B nesousedí
def check(slovo):
    for i in range(1, len(slovo)):
        if slovo[i] == "A" and slovo[i-1] == "B":
            return False
        if slovo[i] == "B" and slovo[i-1] == "A":
            return False
    return True

# brute-force
def count_for_n(n):
    counter = 0
    slova = itertools.product( *([abeceda] * n) )
    for slovo in slova:
        if check(slovo):
            counter += 1
#            print(slovo)
    return counter

# napočítat členy rekurentní posloupnosti
def compute(n):
    # počáteční podmínky
    if n == 1:
        compute.values.append(4)
    elif n == 2:
        compute.values.append(14)

    else:
        compute.values.append( 2*compute.values[n-2] + 3*compute.values[n-1] )

    return compute.values[n]

# inicializovat statické proměnné
compute.values = [0]    # celkový počet možností

for i in range(1, n+1):     # count from 1 to n inclusive
    print("n =", i)

    # spočítat metodou brute-force
    counted = count_for_n(i)
    print("počet slov =\t", counted)
    
    # napočítat členy rekurentní posloupnosti
    computed = compute(i)
    print("rekurentně =\t", computed)

    # vzorec pro n-tý člen
    computed = round( (17+5*sqrt(17)) / 34 * ((3+sqrt(17))/2)**i + (17-5*sqrt(17)) / 34 * ((3-sqrt(17))/2)**i )
    print("n-tý člen =\t", computed)