Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Pomocný program k řešení úlohy do DIM
#! /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)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment