On torba altın sikke var. Dokuz torbadaki sikkelerden her birisi on gram ağırlığında, bir torbadaki sikkelerden her birisi ise bir gram eksik. Hileli torbayı tek ölçüde bulmanız gerekiyor. Üzerine yerleştirilen nesnenin ağırlığını gösteren dijital bir teraziniz var.

Ali

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

Bu soruyu daha önceden duymuştum:

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

struct Altın
{
   Ağırlık ağırlık;
}

/* Ağırlık türünün tam tanımının yalnızca Tartı'ya göründüğünü
* varsayalım. Gerçekçi olabilmesi için kullanıcıların Ağırlık.miktar'ı
* doğrudan değil, Tartı aracılığıyla okumalarını istiyorum. */
struct Ağırlık
{
   size_t miktar;
}

/* Kullanıcılar Ağırlık nesnesi oluşturmak için ağırlıkYap()'ı çağırmak
* zorundalar. */
Ağırlık ağırlıkYap(size_t miktar)
{
   return Ağırlık(miktar);
}

struct Tartı
{
   /* Başka her yerde dilim kullanmışken burada parametre olarak öylesine
    * aralık kullanmak istedim. */
   size_t tart(R)(R nesneAğırlıkları)
       if (is(ElementType!R == Ağırlık))
   {
       size_t toplam = 0;
       foreach (ağırlık; nesneAğırlıkları) {
           /* Ağırlık'ın tanımını görebildiği için basitçe içindeki miktarı
            * kullanabiliyor. */
           toplam += ağırlık.miktar;
       }

       return toplam;
   }
}

/* Kuyumcuların işlemlerini belirleyen arayüz. */
interface Kuyumcu
{
   Altın[] altınYap(size_t adet, size_t ağırlıkMiktarı);
}

/* Asıl Kuyumcu türlerine hizmet eden bir ara sınıf. */
abstract class MaharetliKuyumcu : Kuyumcu
{
   Altın[] üret(size_t adet, size_t ağırlıkMiktarı)
   {
       return iota(adet).map!(_ => Altın(ağırlıkYap(ağırlıkMiktarı))).array;
   }
}

class DürüstKuyumcu : MaharetliKuyumcu
{
   Altın[] altınYap(size_t adet, size_t ağırlıkMiktarı)
   {
       return üret(adet, ağırlıkMiktarı);
   }
}

class SahtekarKuyumcu : MaharetliKuyumcu
{
   Altın[] altınYap(size_t adet, size_t ağırlıkMiktarı)
   {
       enforce(ağırlıkMiktarı > 1,
               format("En az 2 gram olmazsa sahterkarlık yapamam."));
       return üret(adet, ağırlıkMiktarı - 1);
   }
}

/* Kuyumcular üretir. */
Kuyumcu[] kuyumcuYap(size_t adet)
{
   size_t sahtekar = uniform(0, adet);

   writefln("Beklenen sahtekar: %s", sahtekar);

   return iota(adet).map!(i => (i == sahtekar
                                ? cast(Kuyumcu)new SahtekarKuyumcu
                                : cast(Kuyumcu)new DürüstKuyumcu)).array;
}

/* Verilen torbalardaki altınları kullanarak sahtekarı tek ölçümde ortaya
* çıkartır. */
struct AkıllıAdam
{
   Tartı tartı;

   size_t sahtekarıBul(Altın[][] torbalar, size_t gerçekAltınAğırlığı)
   {
       Altın[] küfe;

       /* Herkes dürüst olsa altınların beklenen ağırlığı. */
       size_t dürüstAğırlık = 0;

       foreach (i, torba; torbalar) {
           const adet = i + 1;
           enforce(torba.length >= adet,
                   format("%s numaralı torbada yeterli altın yok.", i));
           küfe ~= torbalar[i][0 .. adet];
           dürüstAğırlık += (adet * gerçekAltınAğırlığı);
       }

       /* İşte programdaki tek ölçüm: */
       const ölçüm = tartı.tart(küfe.map!(a => a.ağırlık));

       enforce(ölçüm < (küfe.length * gerçekAltınAğırlığı),
               format("Hiç sahte altın yok."));

       const sahtekar = dürüstAğırlık - ölçüm - 1;
       return sahtekar;
   }
}

void main()
{
   enum kuyumcuAdedi = 10;
   enum torbaBaşınaAltın = 10;
   enum altınAğırlığı = 10;

   Kuyumcu[] kuyumcular = kuyumcuYap(kuyumcuAdedi);

   Altın[][] torbalar = kuyumcular
                        .map!(k => k.altınYap(torbaBaşınaAltın, altınAğırlığı))
                        .array;

   Tartı tartı;
   auto akıllıAdam = AkıllıAdam(tartı);
   const sahtekar = akıllıAdam.sahtekarıBul(torbalar, altınAğırlığı);
   writefln("Bulunan sahtekar : %s", sahtekar);
}

Ali

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