100 katlı bir binanız ve bir kaç misketiniz var. Bırakıldığında misketin kırılacağı en alçak katı belirlemeniz gerekiyor. Sonsuz sayıda misketiniz olsa bu katı en hızlı olarak nasıl belirlerdiniz? Peki ya yalnızca iki misketiniz olsaydı?

Ali

--
[ Bu gönderi, http://ddili.org/forum'dan dönüştürülmüştür. ]

Daha önce de söylediğim gibi, bu sorular kağıt üzerinde çözülse de ben zevkine program yazmak istedim. :) (Daha sonradan internetteki başka çözümlere bakınca bu programda yanlış yöntem kullandığımı farkettim.)

import std.stdio;
import std.random;
import std.exception;
import std.range;
import std.algorithm;

/* Aldığı darbenin büyüklüğüne bağlı olarak kırılabilen misket kavramını
* temsil eder. */
struct Misket
{
   enum Durum { sağlam, kırık }

   Durum durum;
   size_t dayanıklılık;

   /* kalite, dayanıklılık ile aynı kavram */
   this(size_t kalite)
   {
       this.durum = Durum.sağlam;
       this.dayanıklılık = kalite;
   }

   pure void darbeAl(size_t enerji)
   {
       if (enerji > dayanıklılık) {
           durum = Durum.kırık;
       }
   }
}

/* Belirli kalitede misketler üretir. */
struct Fabrika
{
   size_t kalite;

   Misket[] üret(size_t adet)
   {
       return iota(adet).map!(_ => Misket(kalite)).array;
   }
}

/* Kendisine verilen fabrikayı kullanarak gereken sayıda ürettiği misketlerden
* yararlanarak misketlerin kaçıncı kata kadar dayanıklı olduklarını bulur. */
struct SonsuzMisketleBulan
{
   Fabrika fabrika;

   this(Fabrika fabrika)
   {
       this.fabrika = fabrika;
   }

   /* İkili arama algoritmasını kullanır.
    *
    * Normal ikili aramadan farklı olarak, "belirli bir değere eşit olan"
    * eleman değil, "misketin bırakıldığında kırılmadığı en yüksek katı"
    * bulur. */
   private size_t ara(size_t düşükKat, size_t yüksekKat)
   {
       if (düşükKat == yüksekKat - 1) {
           return düşükKat;
       }

       /* İşte sonsuz misket kaynağı. :) */
       auto misket = fabrika.üret(1).front;
       const ortaKat = (düşükKat + yüksekKat) / 2;
       misket.darbeAl(ortaKat);

       final switch (misket.durum) {
       case Misket.Durum.kırık:
           return ara(düşükKat, ortaKat);

       case Misket.Durum.sağlam:
           return ara(ortaKat, yüksekKat);
       }
   }

   size_t bul(size_t enÜstKat)
   {
       return ara(1, enÜstKat + 1);
   }
}

/* Misketlerin kaçıncı kata kadar dayanıklı olduklarını yalnızca iki misketle
* bulur. Birinci misketi (koşucu) gittikçe büyüyen (ve sona yaklaştığında
* küçülen) adımlar atmak için kullanır. O kırıldığında ikinci misketle
* (yürüyücü) adım adım ilerler.
*
* NOT: Koşucu misketle hemen 50. kata gitmenin akıllıca olmadığını sezmişim
*      ve o yüzden koşucunun adımlarını (adım += adım / 2) diye arttırmışım
*      ama ne yazık en iyi çözüm o değilmiş. Doğru çözüm internette "two
*      marbles puzzle" diye aratınca bulunuyor. */
struct İkiMisketleBulan
{
   Misket koşucu;
   Misket yürüyücü;

   this(Misket[] misketler)
   {
       enforce(misketler.length == 2,
               format("İki misket olmalı; %s değil.", misketler.length));

       this.koşucu = misketler[0];
       this.yürüyücü = misketler[1];
   }

   size_t bul(size_t enÜstKat)
   {
       size_t düşükKat = 1;
       size_t yüksekKat = enÜstKat + 1;

       /* Önce koşucu misketle büyük adımlar atarak aday katları azaltmaya
        * çalışıyoruz. */
       {
           size_t adım = 1;
           size_t kat = düşükKat;
           while (koşucu.durum == Misket.Durum.sağlam) {
               koşucu.darbeAl(kat);

               final switch (koşucu.durum) {
               case Misket.Durum.kırık:
                   yüksekKat = kat;
                   break;

               case Misket.Durum.sağlam:
                   düşükKat = kat;
                   break;
               }

               kat += adım;

               if (adım > (yüksekKat - düşükKat) / 2) {
                   /* Bu adımın fazla büyük olduğunu sezerek tekrar yarıya
                    * indirerek devam ediyoruz. */
                   adım /= 2;

               } else {
                   if (adım == 1) {
                       adım = 2;

                   } else {
                       /* Yüzde elli adım artışı iyidir (diye düşünmüşüm ama
                        * yukarıda da söylediğim gibi, bu en iyi çözüm
                        * değilmiş. :-/) */
                       adım += adım / 2;
                   }
               }
           }
       }

       size_t kırılmayanKat = düşükKat;

       /* Sonra aday katları adım adım ilerleyerek misketin kırılmadığı en
        * yüksek katı buluyoruz. */
       foreach (kat; düşükKat .. yüksekKat + 1) {
           yürüyücü.darbeAl(kat);

           if (yürüyücü.durum == Misket.Durum.sağlam) {
               kırılmayanKat = kat;
           }
       }

       return kırılmayanKat;
   }
}

void main()
{
   enum enÜstKat = 100;

   /* Her katta doğru işlediğini denetle. */
   foreach (kat; 1 .. enÜstKat) {
       /* Kalite miktarını belirli kattan düşmeye karşı dayanıklılık olarak
        * tanımlıyorum. */
       const kalite = kat;
       auto fabrika = Fabrika(kalite);

       auto bulucu1 = SonsuzMisketleBulan(fabrika);
       assert(bulucu1.bul(enÜstKat) == kat);

       auto bulucu2 = İkiMisketleBulan(fabrika.üret(2));
       assert(bulucu2.bul(enÜstKat) == kat);
   }
}

Ali

--
[ Bu gönderi, http://ddili.org/forum'dan dönüştürülmüştür. ]