CENG Okuyacaklar İçin Örnek Algoritma Sorusu

Pardon hocam yanlış olmasın soru olarak değil de bir problemler kitabının önsözünde görmüştüm sanırım, baya hoşuma gitmişti o zamanlar aklımda kalmış. Daha sonra da 1 veri yapıları kitabında da görmüştüm galiba.

iyi ki ceng yazmamışım  

kimya

Benim aklıma ilk gelen şu oldu: mesela 200 tane madeni para varsa:

50'şer 50'şer 4 parçaya ayırırım. Örneğin A B C D harflerinden her harf 50 adet parayı temsil etsin. Hafif veya Ağır olan para bu 4'ünden birinde. Rastgele 2 harften birini seçip tartıda karşılaştırırım, eğer eşit gelirlerse zaten para C veya D'nin içindedir.

Eğer ilk seçtiğim 2 harf eşit gelirse (örneğin A = B olsun):

Eşit gelen 2 harften (A ve B) örneğin A'yı alır, ilk önce A-C daha sonra A-D yaparım. 2'sinden biri eşit, diğerinde ise bir kol aşağıda bir kol yukarıda bulunacaktır. Eğer dengesiz duran tartı işleminde A'nın olduğu kol aşağıda kalırsa sahte para hafiftir. A yukarıda olursa sahte para ağırdır. Sonrası işte ağır veya hafif olma durumuna göre hedef paranın içinde bulunduğu taraf ile 2'ye böle böle bulma işlemi yapılır.

Eğer ilk seçtiğim 2 harf eşit gelmezse (örneğin A != B olsun)

C veya D'den birini seçer üstte saydığım işlemlerin aynısını gerçekleştiririm.

Var mı bundan daha kısa bir yol hocam? merak ettim açıkçası.

Hocam galiba bu en uzun yoldu.Paralaei tek tek sağa ve sol kefeye atarım.Dengeyi bozan ilk 2 paradan biridir

*

2'ye ayırırım. 2 taraftan birini 2'ye böldüğümüzde zaten terazi dengede kalacak. Diğer tarafa 2'ye bölme işlemlerini uygulayıp parayı bulurum. Yanlış çözdüm herhalde ama aklıma bu geldi.

Mantıklar doğru gibi ancak biraz daha iyileştirilebilir. Parayı iki gruba ayıralım. A, B. A daha ağır olsun. Daha sonra A’yı ikiye ayırırım. Eğer bu tartma işleminde dengesizlik varsa bingo. Sahte para daha ağırmış. Buradan devam ederim. Değilse yine bingo. Sahte para B’de imiş ve B daha hafif. Demek ki sahte para hafif. B’den böl parçala işlerini yapmaya devam ederim.

A’da çıkması durumunda ekstra tartma işlemi yapmadık.

B’de çıkması durumunda ekstra 1 tartma işlemi yaptık(A’yı tarttığımız)

4 tane esit kumeye ayırırım.2'li 2'li gruplarsak grupların birinde 2 tanesi birbirine esit olacaktır zaten.digerinde ise dengesizlik olacak.buradan da birbirine esit olan 2'li gruplardan birini alıp esitsizlik olanlardan da sırasıyla birini alırım hangisi esit olursa digeriyle esitlerden birini kıyaslarım buradan hafif mi agır mı oldugu ortaya cıkar.gerisi zaten ilk sorudaki gibi aynı cozum.

aslında bu da senin cozumunle aynı sayıda geliyor. %50 ihtimalle 2 tartım %50 ihtimalle 3.

edit:eger soruda bir sart yoksa soyle bir sonuca da varılabilir: coin sayısı kac ise 2 den yuksek bolunebilecek en yuksek kume sayısına ayırıp bir kumeyi rastgele diger 2 kumeyle kıyaslayarak da minimum sonuc sayısı bulunabilir yani cevap minimum 2 tartım.bunu engelleyebilecek tek sayı 2 coin olması o da sorunun cevabı icin yeterli degil hafif veya agır olabilir yani gercek agırlıgını bulmaya yeterli degil  

Evet bu çözümler de oluyor sanırım.

Aynen bu cozum daha iyi.