Euler Problem 230: Fibonacci Words

Članak o Fibonacci words može se pogledati na wikipedia. Fibonacci Words predstavlja L-System. Formula pomoću koje se dobije n-to slovo u Fibonaccijevom nizu data je izrazom:

gdje je

floor funkcija (najveći cijeli broj r<=x),

– zlatni rez (Golden ratio)

Obzirom da su ovdje u pitanju riječi A i B, koje čine 100 cifara (karaktera), potrebno je formulu modificirati nanačin da je n-to slovo koje se traži mora oduzeti od 200 odnosno Length(A+B). Nakon toga n se podjeli sa 100 i izračuna spomenuta formula. Ostatak djeljenja n sa 100 je cifra u riječi A ili B, zavisno od evaluacije formule.

static string a = "1415926535897932384626433832795028841971693993751058209749445923078164062862089986280348253421170679";
static string b = "8214808651328230664709384460955058223172535940812848111745028410270193852110555964462294895493038196";
static double phi = (1 + Math.Sqrt(5)) / 2.0;//Golden Ratio
static double r = phi / (1 + 2 * phi);

public static int D(long n)
{

    if (n > 200)
        n -= 200;      // -> ab-200
    else if (n > 100)
        n -= 100;      //B -> ab-100
    //else
    //    n = n;       //A -> a

    long m = n / 100;

    int index = (int)(n % 100);//Index of digit of word A or B

    //nth Fibonacci Word http: // research.att.com/~njas/sequences/A003849
    double nthDigit = (long)((m + 2) * r) - (long)((m + 1) * r);

    if (nthDigit == 1)//A
        return int.Parse(a[index - 1].ToString());
    else//B
        return int.Parse(b[index - 1].ToString());
}

static void Main(string[] args)
{
    long sum = 0;
    for (int i = 0; i <= 17; i++)
    {
       long m = (127 + 19 * i) * (long)Math.Pow(7, i);

        int digit = D(m);

        sum += digit * (long)Math.Pow(10, i);
    }
    Console.WriteLine(sum);
    Console.ReadLine();
}