Forum: Ders Arası RSS
The Algorithm Design Manual, problem 2-48
Aynı büyüklükte 8 top
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-48
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
erdem (Moderatör) #2
Üye Tem 2009 tarihinden beri · 978 mesaj · Konum: Eskişehir
Grup üyelikleri: Genel Moderatörler, Üyeler
Profili göster · Bu konuya bağlantı
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.
acehreli (Moderatör) #3
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ı
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
acehreli (Moderatör) #4
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ı
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
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-18, 22:34:37 (UTC -08:00)