Project Euler Problem 53

Project Euler 53. Problem ve Çözümü

53. Problem’de 1 <= n <= 100 ve C(n,r) > 1000000 koşullarını sağlayan kaç adet C(n,r) şeklinde kombinasyon olduğunu bulmamız isteniyor.

Bu problemin çözümü için akla gelen pek çok yol içerisinden hızlı ve basit olan bir yol ile problemi çözmeye çalışalım. Problemimizde kombinasyonu hesaplayarak 1000000’dan büyük olup olmadığını sınamak yerine kombinasyonun ve kontrol değerinin logaritmasını alarak logaritmaları karşılatırıyoruz.  Öncelikle bazı kombinasyon formüllerini hatırlayalım:

Faktöriyel ve kombinasyonun formülü

ve bazı logaritma formüllerini:

Çarpımın logaritması

Bölümün logaritması

Yukarıdaki formülleri kullanarak faktoriyelin logaritmasını aşağıdaki gibi yazabiliriz:

Faktöriyelin logaritması

Bu fonksiyon project euler ile doğrudan ilgili olmasa da gammaln fonksiyonunun analogudur.

Böylece kombinasyonun logaritmasını da aşağıdaki şekilde yazabiliriz:

Kombinasyonun logaritması

Buraya kadar yazdıklarımızdan çıkarmak istediğimiz sonuç olan problem 53‘ün logaritmalar ile ifadesini aşağıda görebiliriz:Logarithm of one million

Euler Problem 53

Böylece logaritmanın da yardımı ile kendimizi big-integer çarpım, bölüm ve karşılaştırmalarından kurtararak işimizi double toplamlara ve karşılaştırmalara indirgemiş olduk. Aynı zamanda faktoriyelin logaritma fonksiyonunu tasarlarken memoization tekniğini de kullanabiliriz. Problemi çözen örnek C# kodu aşağıda verilmiştir:

// 2009-06-29
using System;
using System.Collections.Generic;
using System.Text;

namespace ProjectEuler53
{
    class Program
    {
        static void Main(string[] args)
        {
            // count will be the answer of the problem.
            int count = 0;

            for (int n = 1; n <= 100; n++) // upper limit imposed by the problem on 'n' is 100
                for (int r = 1; r <= n; r++) // n > r
                {
                    if (LogCombination(n, r) > 6) // log(1000000) = log(10^6) = 6 log10 = 6
                        count++;
                }

            Console.WriteLine(count);
            Console.ReadKey(true);
        }

        // Memoization dictionary for logarithm of factorials.
        static Dictionary<int, double> dictLogFactorial = new Dictionary<int, double>();

        // Returns logarithm of the combination C(n,r)
        static double LogCombination(int n, int r)
        {
            return LogFactorial(n) - LogFactorial(r) - LogFactorial(n - r);
        }

        /// Returns logarithm of n!, if called before value comes from a dictionary.
        static double LogFactorial(int n)
        {
            if (n == 0 || n == 1)
                return 1;

            if (dictLogFactorial.ContainsKey(n))
                return dictLogFactorial[n];

            double ret = 0;
            for (int i = 1; i <= n; i++)
            {
                ret += Math.Log10(i);
            }
            dictLogFactorial.Add(n, ret);
            return ret;
        }

    }
}