Aynı büyüklükte 8 topunuz var. Yedi tanesi aynı ağırlıkta ama bir tanesi biraz daha ağır. Ağır olan topu kollu terazi ile yalnızca iki ölçümle nasıl belirleyebilirsiniz?

Ali

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

Aha bu kolaymış.

3-3-2 düzeni yaparız. 3'lü grubu beraber tartarız. Eşitse zaten bir hakkımız kaldığı için 2 topu tartarız.

Eğer eşit değilse 3 top içinden rastgele 2 tanesini seçeriz. Eşitse ağır top kefenin dışında olan toptur. Ağırsa zaten ağır topu bulmuş oluruz.

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

Bana da kolay geldi. Hatta neden daha önceden duyduğum gibi 9 top değil? Senin yöntemin 9 topu da çözüyor.

Neyse... Bunların hepsi için D işlevleri yazmamız da gerek. ;)

Ali

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

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

struct Ağırlık
{
   size_t miktar;
}

struct Top
{
   size_t numara;
   Ağırlık ağırlık;
}

struct KolluTerazi
{
   enum KolYönü { orta, sol, sağ };
   size_t sayaç;

   private size_t toplamAğırlık(R)(R ağırlıklar)
   {
       /* Burada daha kısa olarak şunu yazmak isterdim ama dilim yerine R
        * gibi bi aralık kullanınca şablon türleri çıkarsanamıyor. (?)
        *
        *   return ağırlıklar.reduce!((toplam, a) => toplam + a.miktar)(OU);
        */
       size_t toplam = 0;

       foreach (ağırlık; ağırlıklar) {
           toplam += ağırlık.miktar;
       }

       return toplam;
   }

   /* Sor ve sağdaki küfeleri karşılaştırır ve terazi kolunun yönünü
    * döndürür. */
   KolYönü tart(SolR, SağR)(SolR solKüfe, SağR sağKüfe)
       if (isInputRange!SolR && isInputRange!SağR)
   {
       ++sayaç;

       const solToplam = toplamAğırlık(solKüfe.map!(k => k.ağırlık));
       const sağToplam = toplamAğırlık(sağKüfe.map!(k => k.ağırlık));

       if (solToplam == sağToplam) {
           return KolYönü.orta;

       } else if (solToplam > sağToplam) {
           return KolYönü.sol;

       } else {
           return KolYönü.sağ;
       }
   }
}

struct AkıllıAdam
{
   KolluTerazi terazi;

   /* Ağır olan topun numarasını döndürür. İki top eşitse size_t.max
    * döndürür. */
   size_t ağırOlanıBul(Top[] toplar)
   {
       if (toplar.length == 1) {
           /* Tek topun ağır olanı kendisidir. */
           return toplar[0].numara;

       } else if (toplar.length == 2) {
           /* İki topun ağır olanı terazi koluna bakarak anlaşılır. */
           size_t ağırTopunNumarası = 0;
           const taraf = terazi.tart(only(toplar[0]), only(toplar[1]));

           final switch (taraf) with (KolluTerazi.KolYönü) {
           case orta:
               ağırTopunNumarası = size_t.max;
               break;

           case sol:
               ağırTopunNumarası = toplar[0].numara;
               break;

           case sağ:
               ağırTopunNumarası = toplar[1].numara;
               break;
           }

           return ağırTopunNumarası;

       } else if (toplar.length == 3) {
           /* Topların ilk ikisini tart; eşit iseler üçüncü topu döndür. */
           size_t sonuç = ağırOlanıBul(toplar[0 .. 2]);
           return (sonuç == size_t.max ? toplar[2].numara : sonuç);

       } else {
           /* Topları üç gruba ayır; ilk iki grubu tartarak karşılaştır; eşit
            * olduklarından üçüncü grubu kullanarak devam et. */
           size_t küfeBüyüklüğü = toplar.length / 3;

           /* Üçe tam olarak bölünemiyorsa ve bölümden kalan iki ise o iki
            * topu ilk karşılaştırılacak olan gruplara paylaştır. */
           const kalan = toplar.length % 3;
           if (kalan == 2) {
               ++küfeBüyüklüğü;
           }

           const taraf = terazi.tart(
               toplar[0 .. küfeBüyüklüğü],
               toplar[küfeBüyüklüğü .. 2 * küfeBüyüklüğü]);

           final switch (taraf) with (KolluTerazi.KolYönü) {
           case orta:
               /* Ağır olan kenarda bekleyen grubun içindedir. */
               return ağırOlanıBul(toplar[2 * küfeBüyüklüğü .. $]);

           case sol:
               /* Ağır olan sol küfededir. */
               return ağırOlanıBul(toplar[0 .. küfeBüyüklüğü]);

           case sağ:
               /* Ağır olan sağ küfededir. */
               return ağırOlanıBul(toplar[küfeBüyüklüğü .. 2 * küfeBüyüklüğü]);
           }
       }
   }
}

/* Belirtilen adette ve ağırlıkta toplar üretir. Daha sonradan deney
* sonuçlarını karşılaştırmak amacıyla kullanılsın diye hangi topun ağır
* olduğunu da bildirir. */
Top[] topYap(size_t adet, size_t ağırlık, ref size_t ağırTopİpucu)
{
   const ağırTopunNumarası = uniform(0, adet);

   ağırTopİpucu = ağırTopunNumarası;

   return iota(adet)
          .map!(n => Top(n, (n == ağırTopunNumarası
                             ? Ağırlık(ağırlık + 1)
                             : Ağırlık(ağırlık))))
          .array;
}

void main()
{
   enum deneyAdedi = 10_000;
   enum topAğırlığı = 42;

   foreach (deney; 0 .. deneyAdedi) {
       const topAdedi = uniform(1, 100);
       size_t ağırTopİpucu;

       Top[] toplar = topYap(topAdedi, topAğırlığı, ağırTopİpucu);

       auto akıllıAdam = AkıllıAdam();
       const ağırTop = akıllıAdam.ağırOlanıBul(toplar);

       /* Sonucu denetle. */
       assert(ağırTop == ağırTopİpucu);

       /* Hiç olmazsa asıl problemdeki durumu da denetle. */
       if (topAdedi == 8) {
           assert(akıllıAdam.terazi.sayaç == 2);
       }
   }
}

Ali

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