Yhden muutos

Tehtäväsi on laskea, monellako tavalla merkeistä a–z voidaan muodostaa $n$ merkin pituinen merkkijono, jossa kaikki vierekkäiset merkit ovat myös vierekkäin aakkosissa.

Kun $n=2$, haluttu vastaus on $50$. Tässä merkkijonon ensimmäinen merkki voi olla mikä tahansa merkki väliltä a–z (yhteensä $26$ vaihtoehtoa). Jos merkki on a tai z, seuraavan merkin valintaan on yksi vaihtoehto. Muuten seuraavan merkin valintaan on kaksi vaihtoehtoa. Tästä saadaan vastaus $2 + 24 \cdot 2 = 50$.

Kun $n=5$, haluttuja merkkijonoja ovat esimerkiksi ababa, cdcba ja bcdef.

Toteuta tiedostoon onediff.py funktio count_strings, jolle annetaan merkkijonon pituus. Funktion tulee palauttaa merkkijonojen määrä.

Funktion tulee toimia tehokkaasti, kun merkkijonon pituus on välillä $1 \dots 100$.

def count_strings(n):
    # TODO

if __name__ == "__main__":
    print(count_strings(1)) # 26
    print(count_strings(2)) # 50
    print(count_strings(3)) # 98
    print(count_strings(4)) # 192

    print(count_strings(42)) # 36766943673096
    print(count_strings(100)) # 7073450400109633000218032957656