Month: February 2016

Project Euler 114

Posted by

114 epey kısa ama güzel bir Project Euler sorusu; Elimizde n uzunluğunda bir sıra var. Bu sıradaki elemanları siyaha ya da ardışık olarak en az 3 hücre olacak şekilde kırmızıya boyamak istiyoruz, kaç farklı şekilde boyayabiliriz?

Ben şöyle bir yol izledim; F(n, k) şeklinde bir fonksiyon olsun ve bu fonksiyon n uzunluğunda ve son k hücresi kırmızı olan sıraların sayısını tutsun. Fonksiyon için aşağıdakileri yazabiliriz:

  • 3’ten daha kısa kırmızı alt sıra olamayacağından F(1, 0) = 1 ve F(2, 0) = 1. Ayrıca aynı mantıkla tüm n değerleri için F(n, 1) = 0 ve F(n, 2) = 0.
  • F(i, 0) = \sum\limits_{k=0}^{i-1} F(i-1, k). Yani, n-1 uzunluktaki herhangi bir sıranın sonuna ancak 1 siyah hücre ekleyerek onu n uzunlukta ve sıfır kırmızı hücre ile biten bir sıra yapabiliriz.
  • n uzunlukta ve k tane kırmızı hücre ile biten sıra sayıları, n-k uzunlukta ve 0 kırmızı hücre ile biten sıra sayılarına eşittir. Çünkü 0’dan daha fazla kırmızı ile biten sıra sayılarını da dahil edersek, k‘dan daha fazla kırmızı hücre ile biten sıraları da hesaplamış oluruz.

Bu üç maddeye göre F(n, k) fonksiyonunun değerlerini hesapladığımızda cevap

(1)   \begin{equation*} \sum\limits_{i=0}^{50} F(50, i) \end{equation*}

toplamının sonucu olacak.

Amcalar ve Şapkalar

Posted by

Dün akşam bir tane soruya denk geldim. Bir tane şirket soruyu yazmış, bunu çözebiliyorsanız başvurun falan demiş. Soru şu şekilde;

8 tane amca var, kağıtlara kendi isimlerini yazıp bir kutuya atıyorlar. Sonra hepsi kutudan rastgele bir kağıt çekiyor. Bu da herkes kendi adından farkli bir kağıt çekene kadar devam ediyor. Herkesin kendi adından farklı kağıt çekme olasılığı kaçtır?

Brute force çözüm olarak düşününce elimizde toplam {n!} tane olasılık var, yani isimleri {n!} farklı şekilde atayabiliriz. Tüm permütasyonları oluşturup başarılı permütasyonlari sayarsak olasılığı da, çıkan toplamı {n!}‘e bölerek bulabiliriz. Yani aşağıdaki gibi.

Kodu en kısa nasıl olabilir diye yazdığım için performans olarak idealden uzak. Bu haliyle n=9 için de hesaplayabildim ama n=10 için epey zorlandı.

Peki n > 9 gibi durumlar için ne yapabiliriz? Burada tüm olasılıkları hesaplamak artık biraz zorlaşıyor. Onun yerine bir fonksiyon tanımlayip soruyu daha kısa zamanda cözebiliriz.

Diyelim ki D matrisi, n elemanli bir durum için k elemanın kendi adını çektiği durumları içeren bir matris olsun. Burada şöyle ön çıkarımlar yapabiliriz;

– 0 elemanlı her durum için sonuç sıfırdır, yani D_{0, i} = 0, i = 0 .. n
– Herhangi bir durumda herkesin kendi ismini bulduğu durumlarin sayisi 1‘dir, yani D_{i, i} = 1, i = 1 .. n.

Bu durumların dışında ise şunu söyleyebiliriz; D_{i, k} bize i elemanın olduğu durumda k elemanın kendi adını bulduğu, diğerlerinin yani i-k elemanın ise kendi adından farkli adları bulduğu durumların sayısını versin. Burada k elemanı \binom{i}{k} farklı şekilde seçebiliriz. Her bir seçenek icin geriye kalan i-k eleman ise kendi adından farklı bir adı seçecek. Bu da aslında bizim fonksiyonumuzdaki D_{i-k, 0} sonucuna denk geliyor. Yani formülünü yazarsak;

(1)   \begin{equation*} D_{i, k} =\binom{i}{k} * D_{i-k, 0} \end{equation*}

Burada tek istisnai durum ise şu; k = 0 durumunda ne yapacagiz? k = 0 iken denklem

(2)   \begin{equation*} D_{i, 0} =\binom{i}{0} * D_{i, 0} \end{equation*}

oluyor yani sonsuz döngüye giriyor. Bundan da şu şekilde kurtulabiliriz; daha öncesinde tüm olası D_{i, k} değerlerini hesaplamıştık. D_i satırındaki değerlerin toplamı, i elemanlı durum için permütasyon sayısını veriyor. D_{i, 0} değerini de bu mantığı kullanarak

(3)   \begin{equation*} D_{i, 0} ={i!} - \sum\limits_{k=1}^i D_{i, k} \end{equation*}

formülüyle hesaplayabiliriz.

Bunun da kodunu kısa olsun diye uğraşarak aşağıdaki gibi yazdim

Kodlarda ya da mantığımda herhangi bir hata var mı sizce?