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(); }