Forum: Ders Arası RSS
The Algorithm Design Manual, problem 2-47
On torba altın sikke
acehreli (Moderatör) #1
Kullanıcı başlığı: Ali Çehreli
Üye Haz 2009 tarihinden beri · 4527 mesaj
Grup üyelikleri: Genel Moderatörler, Üyeler
Profili göster · Bu konuya bağlantı
Konu adı: The Algorithm Design Manual, problem 2-47
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
acehreli (Moderatör) #2
Kullanıcı başlığı: Ali Çehreli
Üye Haz 2009 tarihinden beri · 4527 mesaj
Grup üyelikleri: Genel Moderatörler, Üyeler
Profili göster · Bu konuya bağlantı
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
Doğrulama Kodu: VeriCode Lütfen resimde gördüğünüz doğrulama kodunu girin:
İfadeler: :-) ;-) :-D :-p :blush: :cool: :rolleyes: :huh: :-/ <_< :-( :'( :#: :scared: 8-( :nuts: :-O
Özel Karakterler:
Forum: Ders Arası RSS
Bağlı değilsiniz. · Şifremi unuttum · ÜYELİK
This board is powered by the Unclassified NewsBoard software, 20100516-dev, © 2003-10 by Yves Goergen
Şu an: 2017-11-19, 06:13:03 (UTC -08:00)