Bilgisayar Olimpiyatı 2023, 1. Aşama, Soru 8

Uzak bir gezegende her biri n mühendis uzaylıdan oluşan iki grup bir uzay gemisi
tasarımında çalışacaklardır. Grupları A ve B olarak isimlendirelim. A grubundan bir uzaylı
ile B grubundan bir uzaylı eşleştirilerek n adet ikili grup oluşturulacaktır. Bu eşleştirme
yapılırken uzaylıların zeka seviyelerine (IQ) göre bir yol izlenecektir. A grubu içinde
bulunan uzaylıların her biri birbirinden farklı IQ’ya sahiptir. Aynı şekilde B grubundaki
uzaylıların da her biri birbirlerinden farklı IQ’ya sahiptir. Her uzaylının diğer grupta
kendisine eşit IQ’ya sahip olan bir dengi vardır, buna uzaylının partneri diyelim. Amaç her
uzaylıyı diğer gruptaki partneri ile eşleştirmektir. Uzaylılar kendi IQ’larını sayısal bir
değer olarak bilmemektedirler, fakat şöyle bir karşılaştırma işlemi kullanabilmektedirler:
iki uzaylı, a ve b, karşılıklı durup birbirlerine bakarlarsa, (i) eğer a ve b’nin IQ’ları eşit ise
ikisinin de gözleri yanıp sönmektedir. (ii) eğer a ve b’nin IQ’ları eşit değilse, sadece IQ’su
daha yüksek olan uzaylının gözleri yanıp sönmektedir. Bu karşılaştırma yöntemi
kullanılarak her uzaylının partneri aşağıdaki özyinelemeli Eşleştir algoritması ile
bulunabilir.
Eşleştir(A, B):
1. A ve B gruplarında sadece birer uzaylı varsa bunlar birbirinin partneridir, ve
algoritma sonlandırılır. Aksi takdirde A grubundakiler tek sıra halinde yan yana
dizilir. B grubundakiler de tek sıra halinde yan yana dizilir. A grubundan rastgele
bir uzaylı seçilir, buna a diyelim. Bu uzaylı sırayla B grubundaki her bir uzaylının
karşısına geçip gözlerine bakar ve partnerini bulur. Partnerine b diyelim. Bu
basamakta a ve b partnerlerini bulmuştur.
2. Agrubundaki her bir uzaylı u, a'nın karşısına geçerek gözlerine
bakar. a ve u birbirine baktığında
2.1.a’nın gözleri yanıp sönerse, u, a’nın sol tarafına geçer.
2.2.u’nun gözleri yanıp sönerse u, a’nın sağ tarafına geçer.
3. Bgrubundaki her bir uzaylı v, b'nin karşısına
geçerek gözlerine bakar. b ve v birbirine baktığında
2.1.b’nin gözleri yanıp sönerse, v, b’nin sol tarafına geçer.
2.2.v’nin gözleri yanıp sönerse v, b’nin sağ tarafına geçer.
4. a’nın solundakilere A1, sağındakilere A2 grubu diyelim. (Gruplardan biri boş da
olabilir.)
5. b’nin solundakilere B1, sağındakilere B2 grubu diyelim. (Gruplardan biri boş da
olabilir.)
6. Bu aşamada A1 grubundakilerin partnerleri B1 grubunda ve A2 grubundakilerin
partnerleri de B2 grubunda bulunmaktadır.
6.1.Eğer A1 ve B1 grupları boş değilse algoritma özyinelemeli olarak (A1,B1)
grupları için çalıştırılır.
6.2.Eğer A2 ve B2 grupları boş değilse algoritma özyinelemeli olarak (A2,B2)
grupları için çalıştırılır.
n = 15 ise verilen algoritma kullanıldığında bütün uzaylıların partnerleri en kötü ihtimalle
(en fazla) kaç karşılaştırma işlemi sonucunda belirlenir? Karşılaştırma işlemi ifadesi
sadece iki uzaylının karşı karşıya gelip birbirine bakması işlemini belirtmektedir. (1.
basamakta a’nın rastgele seçildiğini hatırlayın.)

Şıklar:
A) 329
B) 305
C) 285
D) 279
E) 267

Cevap: A 329

Çözüm:
En fazla sayıda karşılaştırma 1. basamakta rastgele seçilen uzaylı a’nın (algoritmanın her
çağrılışında) A grubundaki en düşük veya en yüksek IQ’ya sahip uzaylı olması durumunda
gerçekleşir. Seçilen a’nın grubundaki en yüksek IQ’lu uzaylı olduğu durumu ele alalım. Bu
durumda (A ve B gruplarındaki eleman sayısı n ise) 2. ve 3. basamaklarda a’nın (ve b’nin)
solunda oluşan grup (n-1) ve sağında oluşan grup 0 (sıfır) uzaylı içerecektir.
o Algoritma ilk olarak n = 15 için çalıştırılır: 1. basamakta en fazla 15, 2. ve 3.
basamaklarda 14’er karşılaştırma işlemi yapar. Oluşan A1, B1 grupları n-1 = 14’er
uzaylı içerir. A2, B2 grupları ise boştur. Bu durumda 6. basamakta algoritma
sadece boş olmayan (A1, B1) için çalıştırılır.
o n =14 için: 1. basamakta en fazla 14, 2. ve 3. basamaklarda 13’er karşılaştırma
işlemi yapar, yine seçilen a’nın en büyük IQ’ya sahip olduğunu varsaydığımız için
oluşan A1, B1 grupları 13’er uzaylı içerir. A2, B2 grupları ise boştur, ve algoritma
sadece boş olmayan (A1, B1) için çalıştırılır,
o n=13 için: 1. basamakta en fazla 13, 2. ve 3. basamaklarda 12’şer karşılaştırma
işlemi yapar.
o …
o n=2için: 1. basamakta en fazla 2, 2. ve 3. basamaklarda 1’er karşılaştırma işlemi
yapar. (Verilen algoritma n=2 için de 2. ve 3. basamakları yapmaktadır dolayısıyla
1+1 karşılaştırma işlemi gereksiz de olsa yapılacaktır.)
o n=1 için algoritma çağırılır fakat karşılaştırma işlemi yapmadan 1. Basamakta
sonlanır.
Algoritmanın bütününe bakarsak 1. basamaklarda toplam
15+14+…+2 = 119
karşılaştırma işlemi, 2. ve 3. basamaklarda toplam 2x(14+13+…+1) = 210 karşılaştırma
işlemi yapılır. Cevap 210+119 = 329 olup A şıkkında verilmiştir.