50 Lira Problemi

Son güncelleme 19 Mart 2007 Pazartesi

Soru şöyle: 1, 5, 10, 25 ve 50 Liralık paralardan dilediğiniz kadar kullanarak 50 Lirayı kaç farklı şekilde tamamlayabilirsiniz? Bunlar nelerdir?

Aklıma gelen ilk çözüm tüm olasılıkarı sırayla deneyen ve uygun olanları listeleyen minik bir kod yazmak oldu. Bu durumda ilk olarak “kaç farklı olasılığı test etmemiz gerekiyor” sorusuna cevap arayalım.

Problemdeki ulaşılması istenen miktar olan 50’ye hedef, kullanılabilecek paralar kümesi olan { 1, 5, 10, 25, 50} ye de dizi, ismini verelim. Yazacağımız kod esnek olsun, hedef ve dizi değişken olabilsin.

İşin içerisinde sadece pozitif tamsayılar var (Z+) ve en küçük pozitif tamsayı 1’dir, dolayısıyle 50’yi yada herhangi bir pozitif tamsayıyı oluşturmak için o sayının kendisi kadar 1 gereklidir. Bu da dizi de tek bir sayı bulunduğunda test etmemiz gereken olasılık adedini sayının kendisi kadar yapar. Ama dizi içerisindeki bir sayı hedef sayıdan büyük olabilir yada dizi ‘deki sayılar olasılıkların birkısmında kullanılırken bir yada birkaçı kullanılmayabilir, bu durumda 0’ı da olasılık adedine dahil etmemiz gerekiyor, dolayısıyle test etmemiz gereken olasılık adedimiz dizi ’de tek bir eleman olduğunda hedef + 1 kadardır.

Problemde olduğu gibi dizi ’de eleman sayısı birden fazla ise test edilecek olasılık adedini hesaplamak için:

n = dizi’deki eleman adedi ise; (hedef + 1)ⁿ

şeklinde bir formül kullanabiliriz. Bu problem için test edeceğimiz olasılık adedimiz: (50 + 1)⁵ dir.

Tıpkı ondalık sistemde 10³ – 1 = 999’un her bir basamağında 0..9 arası 10 farklı olasılık olduğu gibi, 51⁵ – 1 sayısının 51’lik bir sayı sisteminde her basamağında 0..50 arası 51 farklı olasılık vardır. Dolayısıyle bu problemin çözümünde bir döngü içerisinde 1’den başlayarak 51⁵ - 1 e kadar sayan bir sayı tüm test edeceğimiz olasılıkları vermenin yanı sıra, (hedef + 1) ’lik bir sayı sistemindeki her bir basamak dizi ’deki bir sayıya eşlendiğinde bize şu anki olasılık için dizi ’deki her bir elemanı kaç defa toplamamız gerektiğini de vermektedir. Bunları elde ettikten sonra geriye kalan tek şey o anki test edilecek olasılık için toplamları yapıp hedef sayıya eşitse ekranda yazdırmak değilse döngüye devam etmektir.

İlk denememde bu problemde 300 milyondan fazla test edilecek olasılık olduğundan işlemin sonucunun gelmesi biraz zaman alıyordu, bu sebeple kodda da göreceğiniz üzere biraz hız optimizasyonuna gitmek zorunda kaldım.

private void Form1_Load(object sender, EventArgs e) { label1.Text = "Toplam Olasılık Adedi : " + OlasilikHesapla(50, new int[] { 1, 5, 10, 25, 50 }, listBox1).ToString(); } public static int OlasilikHesapla(int hedef, int[] dizi, ListBox lbox) { int sonuc = 0; for (long i = 1, toplam = 0, tamamlayan = 0, h = hedef + 1; i < Math.Pow(h, dizi.Length); i++, toplam = 0, tamamlayan = 0) { StringBuilder s = new StringBuilder(); for (int j = 0; j < dizi.Length; j++) { long y = (long)Math.Truncate(i / Math.Pow(h, j)) % h; long ek = dizi[j] * y; toplam += ek; if (y != 0) // listbox gösterimi için s.AppendFormat("{0}{1} x {2}", (s.Length == 0 ? "" : " + "), dizi[j], y); if (tamamlayan == 0 && ek != 0) // hız optimasyonu için tamamlayan = (hedef - y) * (long)Math.Pow(h, j); if (toplam > hedef) // hız optimasyonu için { i += tamamlayan; break; } } if (toplam == hedef) { sonuc++; lbox.Items.Add(string.Format("{1} = {0}", hedef, s.ToString())); } } return sonuc; }

 argelab_50_lira_problemi.zip (62K)

ArgeLab.net, bu sitenin eksiksiz ve hatasız olduğu
konusunda bir garanti veremez. Bu sitede yer alan bilgilerin ve
programların kullanımı sonucu oluşabilecek zararlardan
sorumlu tutulamaz.