[MD-sorular] Vezir ve keseler sorusu (ozel bir durum)

[Omer Kucuksakalli]

Merhabalar,

Vezir sorusunun basitlestirilmis bir versiyonu icin
yorumumu yolluyorum. Genel duruma direk yonelmektense,
boyle basit durumlardan baslamak daha iyidir.

Diyelim ki n=10 toplam kese sayisi olsun ve keselerin
icindeki altin sayisi 1 <= a_i <= 1000 ile gosterilsin.
Herhangi bir kesede belirli bir sayida altin bulunma
olasiligi 1/1000 olsun. (a_i lerin birbirinden farkli olma
varsayimini kaldirdik.)

Ilk kesedeki altin sayisi b_1 olsaydi, sonraki keselerin
hepsininde b_1'den az altin bulunma olasiligi

( (b_1-1) / 1000 ) ^ 9 

olacakti. Bu olasiligi 1/2 ye en yakin yapan deger b_1 =
926 olur. Yani eger vezir ilk adimda 926'dan yuksek bir
rakam gorur ve durursa kazanma sansi yuzde elliden fazla
olacak (1000 gorurse yuzde yuz mesela). Diger taraftan
926'da az bir sayide altin gorurse de kese acmaya devam
etmesi faydasina olacak.

Yani birinci adim icin 

a_1 => 926 ise dur, aksi halde devam et.

stratejisini izlemelidir. Ikinci adim icin

( (b_2-1) / 1000 ) ^ 8 = 1 / 2

denklemini cozer ve b_2 = 918 buluruz. Yani vezir soyle
yapmalidir: 

a_2 => 918 ise dur, aksi halde devam et.

Vezir buna benzer bir sekilde ilerler.

a_3 => 906 dur, aksi halde devam et.
a_4 => 891 dur, aksi halde devam et.
a_5 => 871 dur, aksi halde devam et.
a_6 => 841 dur, aksi halde devam et.
a_7 => 794 dur, aksi halde devam et.
a_8 => 708 dur, aksi halde devam et.
a_9 => 501 dur, aksi halde devam et.
a_10 mecburen sec.

Bu stratejiyle vezirin kazanma sansi neredeyse yuzde 50'dir
(Bilgisayardaki hesaplarima gore 0.499).

------------------------------------------

Bir kesede 900 altin cikma olasiligi hep aynidir. Degisen
vezirin deneme sanslarinin azalmasidir. Dorduncu adimda 900
altin bulmussa ilerki 6 alti keseye artik cok
guvenmemelidir. Bu durum en guzel ornegi dokuzunce kesede
gorulur. Eger 501 ve fazlasi sayida altin varsa vezir artik
durmalidir. Cunku sonuncu keseden buyuk ihtimalle daha az
altin cikacaktir.

-------------------------------------------

Keselerin icinde cok altin bulunma olasiligi, az altin
bulunma olasiligindan gercek hayattaki gibi az olsaydi,
yukaridaki b_i rakamlari daha dusuk cikacakti. Bu yuzden
basta sabitledigimiz 1/1000 olasiligi sorunun cevabindan
etkili.

Omer Kucuksakalli

--- ihsan yÿfffffccel <ihsan_einstein at yahoo.com> wrote:

> Ömer Sakalli demis:''Su durumu dusunelim. Vezir ulke
> butcesinin 2 milyon altin
> oldugunu biliyor ve sans bu ya ilk keseden 1 bucuk milyon
> altin cikiyor.
> 
> Acaba diger 99 keseyle ilgilenir mi? Hayir! Cunku diger
> keselerde 1 bucuk milyondan fazla altin cikma olasiligi
> sifir!
> ''
>   Ä°ste zaten sorun burada! Yani ilk k tane keseyi
> acmaliyiz ki algoritmamizi buna gore insa edecegiz.
> Aslinda sorunun kerameti de burada. Yani k sayimiz bu isi
> kotarabilmemiz icin bize en iyi stratejiyi verebilecek
> ozellikte olmali. Mesela islemler uzadi ama bunun yani k
> nin n/3 e yakin bir sayi oldugu son hesaplamalarimizda
> cikti gibi... 
>    
>   ihsan (...)
>


       
____________________________________________________________________________________
Be a better Heartthrob. Get better relationship answers from someone who knows. Yahoo! Answers - Check it out. 
http://answers.yahoo.com/dir/?link=list&sid=396545433