Bilgisayar Olimpiyatı 2008, 1. Aşama, Soru 30

[28-32] soruları için açıklama
[GÖRSEL]
Bir derede daire şeklinde yerleşmiş 8 taş vardır ve kurbağalar bu taşların üzerinde güneşlenir. Bir taşta tek bir kurbağa güneşlenebilir. Kurbağalar taşlara çıkarken şekilde K ile gösterilen yerden taşların üzerine zıplarlar. Zıplarken zıpla(x) şeklinde bir fonksiyonu kullanırlar. Bu fonksiyon verilen x değeri için kurbağanın kaç kere zıplayacağını söyler.
Örneğin bu fonksiyon 3 değerini döndüyse kurbağa 3 kere zıplar ve 3. taş üzerine yerleşir.
8. taştan sonra kurbağa zıplamaya 1. taştan itibaren devam eder. Örneğin zıpla fonksiyonu
13 döndüyse kurbağa 5. taşa yerleşir.
Fakat kurbağanın zıpladığı taşta başka bir kurbağa varsa kurbağa o taşta kalamaz zıpla fonksiyonundaki tanıma göre bulunduğu yerden tekrar bir zıplama yapar. Buna göre zıpla fonksiyonu şu şekilde tanımlanır:
\[ z\mathrm{i p l a}(x)=(M/N) \]
M, zıplama miktarını, N ise zıplanan yerde kurbağa varsa yeni zıplama değerini verir.
Örneğin 'zıpla(x) = x | zıpla(x)' şeklinde tanımlanırsa ve kurbağa zıpla(3) şeklinde zıplarsa x = 3. taşa gider. 3. taşta kurbağa varsa fonksiyonun ikinci kısmındaki zıpla(x) ifadesine göre tekrar zıplar ve 6. taşa gider. 6. taşta da kurbağa varsa 9, yani 1. Taşa gider. Kurbağa boş bir taş buluncaya kadar zıplar. Bulamadığı sürece sonsuza kadar bunu tekrarlar. Fonksiyon tanımında t değişkeni kullanılabilir. O ≤ t ≤ 8, bulunulan taşın numarasını gösterir. Başlangıç noktasında t = O olarak kabul edilir. M ifadesi zıplamadan önce, N ifadesi zıplanan yerde (kurbağa bulunan) hesaplanır.
Kurbağalar geri zıplayamaz. Dolayısıyla zıplama sonucu O ya da daha küçük bir sayı geldiğinde kurbağa bulunduğu taşta (başka kurbağa olsa da) kalır, bir daha zıplayamaz.
## AÇIKLAMA
Kurbağaların başlangıç pozisyonu ve zıplama fonksiyonu soruya göre değiştiğinden; bu pakette soru çözümünü kolaylaştırıcı genel yolu bulmaktansa, soruları çözmeye başlayıp fonksiyonun adımlarını hızlıca uygulamak daha mantıklı olur.
• % işaretini mod olarak kullanacağız (I, n) aralığında değer veren özel mod diyelim), her atlamada
(taşın numarası+zıplama miktarı) %8 yeni taşın numarası olur.
28. 2., 5. ve 7. taşlarda kurbağalar varken: zıpla(x) = (x + 1| zıpla(x + 1)) tanımına göre kurbağa zıpla(1) ile başlarsa hangi taşa yerleşir?
A) 1          B) 6          C) 8          D) 3          E) 4
Fonksiyonumuza göre kurbağa önce x+1 kadar zıplar. Eğer taş doluysa zıpla(x+1) fonksiyonuna göre tekrar zıplar. Şimdi başlayalım:
• Kurbağa O. taşta. zıpla(l) gelir, 1+1 = 2 kadar zıplar ve 2.taş dolu olduğundan zıpla(l+1) çağrılır.
• Kurbağa 2. taşta. zıpla(2) gelir, 2+1 = 3 kadar zıplar ve 5.taş dolu olduğundan zıpla(2+1) çağrılır.
• Kurbağa 5. taşta. zıpla(3) gelir, 3+1 = 4 kadar zıplar ve 1.taşa gelir.
• 1.taş boş olduğundan kurbağa bu taşa yerleşir.

---

1., 2., ve 6. taşlarda kurbağalar varken zıpla(x) =(2 - x | zıpla(t)) tanımına göre kurbağa zıpla(3) ile başlarsa hangi taşa yerleşir?

text<|/ref|><|/det|>[[130, 697, 780, 713]]<|/det|>

Şıklar:
A) 3 | B) 4 | C) 5 | D) 8 | E) Sonsuza kadar zıplar.

Cevap: E Sonsuza kadar zıplar.

Çözüm:
Fonksiyonumuza göre kurbağa önce x kadır zıplar. Eğer taş doluysa zıpla(x-ı) fonksiyonuna göre tekrar zıplar. Şimdi başılayalım:
• Kurbağa O. taşta. zıpla(3) gelir, 2*x = 2*3 = 6 kadar zıplar ve 6.taş dolu olduğundan zipla(6) çağrılır. (zipla(t) yazılmadan önce t=6 olmuştu)
• Kurbağa 6. taşta. zıpla(6) gelir, 2*6 %8 = 4 kadar zıplar ve 2.taş dolu olduğundan zipla(2) çağrılır.
• Kurbağa 2. taşta. zıpla(3) gelir, 2*2 = 4 kadar zıplar ve 6.taş dolu olduğundan ziple(6) çağrılır.
• Kurbağa 6. taşta. zıpla(5) gelir, bu işlem ise 2.işlem ile aynı olduğundan kurbağa sonsuza kadar zıplar.