Euler Problem 230


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:

a(n) = \left \lfloor (n+2)*r \right \rfloor-\left \lfloor (n+1)*r \right \rfloor

gdje je

a(n) = \left \lfloor x\right \rfloor floor funkcija (najveći cijeli broj r<=x),

r=\frac{\varphi }{1+2\cdot \varphi}

\varphi=\frac{1+\sqrt{5} }{2} – 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();
}

About Bahrudin Hrnjica

PhD in Mechanical Engineering, Microsoft MVP for .NET. Likes .NET, Math, Mechanical Engineering, Evolutionary Algorithms, Blogging.

Posted on 19/03/2010, in C#, Project Euler and tagged . Bookmark the permalink. Leave a comment.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s