Kahve otomatlarıyla ilgili soruları nasıl çözmeli: Tipik şemalar ve örnekler

Bir kahve otomatı sorusunu çözmek için, onun işleyişini sonlu bir otomat olarak modellemeniz gerekir: durumları belirleyin (örneğin, "para haznesi boş", "5 ruble biriktirildi"), madeni paraların atılması sırasındaki olası geçişleri ve kahvenin verildiği hedef durumu tanımlayın. Çözümün anahtarı, ne kadar para biriktirildiğini ve ne kadar para üstü iade edilmesi gerektiğini net bir şekilde gösteren bir durum grafiği veya geçiş tablosu oluşturmaktır.

Bilişim alanındaki Yükseköğretim Kurumları Sınavı görevlerinde (genellikle bu, 6. soru veya açık uçlu cevap bölümündeki varyasyonlardır) "kahve otomatı", klasik bir yürütücü modelidir. Genellikle otomat belirli nominal değerlerdeki madeni paraları (1, 2, 5, 10 ruble) kabul eder, sınırlı bir belleğe sahiptir (veya hiç belleği yoktur, sadece mevcut toplam tutarla çalışır) ve rezervde varsa para üstü verir.

Temel kavram: Sonlu Otomat

Eğitim amaçlı sorular bağlamında kahve otomatı, deterministik sonlu otomat (DSO) prensibine göre çalışır.

Çalışması üç bileşenle tanımlanır:

1. Giriş alfabesi: Atılabilecek madeni para seti (örneğin, {1, 2, 5}).
2. Durumlar kümesi: Mevcut biriktirilen toplam tutar veya cihazın durumu (örneğin, S0 — 0 ruble, S1 — 1 ruble, S2 — 2 ruble vb.).
3. Geçiş fonksiyonu: Otomatın yeni bir madeni para aldığında durumunu değiştirdiği kural.

Tipik çözüm şeması

Başarılı bir çözüm için şu algoritmayı izleyin:

1. Parametreleri belirleyin:

   • Kahvenin fiyatı ($C$).
   • Kabul edilen madeni paraların nominal değerleri.
   • Para üstü mekanizmasının varlığı/yokluğu (ve belirtilmişse, para üstü için başlangıç madeni para stoğu).
   • Sıfırlama koşulu (satın alma işleminden sonra para haznesinin sıfırlanıp sıfırlanmadığı).

2. Durum grafiğini oluşturun:

   • İçlerine biriktirilen toplam tutarı yazarak daireler (durumlar) çizin.
   • Başlangıç durumu her zaman 0'dır.
   • Bir durumdan diğerine oklar (geçişler) çizin ve okların üzerine madeni paranın nominal değerini yazın.

3. Hedef durumları belirleyin:

   • Bunlar, biriktirilen toplam tutarın $\ge C$ olduğu durumlardır.
   • Bu durumlardan "kahve verme" ve "para üstü iadesi" geçişleri çıkmalıdır.

4. Süreci modelleyin:

   • Sorunun koşuluna göre (atılan madeni paraların sırasına göre) graf üzerinde ilerleyin.
   • Son durumu veya verilen kahve miktarını kaydedin.

Örnek 1: Para üstü vermeyen otomat (biriktirmeli)

Koşul: Otomat 10 rubleye kahve satıyor. 1, 2 ve 5 rublelik madeni paraları kabul ediyor. Para üstü vermiyor. 10 rubleden fazla atılırsa, fazlası yanar (veya bir sonraki satın alma için saklanır; koşulda belirtilir, basitlik adına modelimizde yandığını varsayalım, ancak YKS sorularında genellikle aksi belirtilmedikçe fazlası bir sonraki satın alma için haznede kalır. En yaygın durumu ele alalım: fazla kaybolur, çünkü otomat "aptal"dır).

Not: Gerçek YKS sorularında daha sık karşılaşılan model, otomatın sadece toplam tutarı biriktirdiğidir. Toplam >= 10 ise, kahve verir ve sayacı 0'a sıfırlar, kalanı yok sayar veya kalanı taşır. En sık görülen durumu inceleyelim: kalan taşınır.

Soru: Kullanıcı şu madeni paraları attı: 5, 2, 2, 1, 5. Kaç fincan kahve alır?

Durum tablosu ile çözüm:

Cevap: 1 fincan kahve.

Örnek 2: Para üstü veren otomat (daha karmaşık)

Koşul: Kahve fiyatı — 15 ruble. Otomat şu madeni paraları kabul eder: 1, 5, 10. Otomat, rezervde varsa 1 ve 5 rublelik madeni paralarla para üstü verir. Başlangıç para üstü rezervi: beş adet 1 rublelik ve iki adet 5 rublelik madeni para. Tam para üstü yoksa, otomat son madeni parayı kabul etmez ve hemen iade eder, para haznesinin durumu değişmez.

Soru: Madeni para sırası: 10, 5, 1, 1, 1. Ne olur?

Çözüm:

1. 10 atıldı.

   • Biriktirilen: 10.
   • Hedefe kalan: 5 ruble.
   • Para üstü rezervi: değişmedi.

2. 5 atıldı.

   • Biriktirilen: 10 + 5 = 15.
   • Toplam tutar fiyata eşit.
   • Eylem: Kahve ver. Para haznesini 0'a sıfırla. Para üstü gerekmez.
   • Para üstü rezervi: aynı (5x1r, 2x5r).

3. 1 atıldı.

   • Biriktirilen: 1.

4. 1 atıldı.

   • Biriktirilen: 2.

5. 1 atıldı.

   • Biriktirilen: 3.

Sonuç: 1 fincan kahve alındı, haznede 3 ruble kaldı. Para üstü gerekmedi.

Soruyu zorlaştıralım: Sıra: 10, 10.

1. 10 atıldı. Biriktirilen 10.
2. 10 atıldı. Biriktirilen 20.
   • Fazla: $20 - 15 = 5$ ruble.
   • 5 ruble para üstü verilmesi gerekiyor.
   • Rezervi kontrol et: 5 rublelik madeni para veya beş adet 1 rublelik madeni para var mı?
   • Rezervde iki adet 5 rublelik madeni para var.
   • Eylem: Kahve ver, para üstü olarak bir adet 5 rublelik madeni para ver.
   • Para haznesi 0'a sıfırlanır.
   • Yeni rezerv: beş adet 1 rublelik, bir adet 5 rublelik madeni para.

Çözüm sırasında yapılan yaygın hatalar

1. Para üstü sınırının göz ardı edilmesi. Öğrenciler genellikle otomatın her zaman para üstü verebileceğini düşünür. Koşulda "para üstü sadece mevcut madeni paralarla" deniyorsa, rezervin takibini yapmanız gerekir.

2. Yanlış işlem sırası. Önce toplam tutarın yeterliliği kontrol edilir, ardından kahve verilir, sonra para üstü hesaplanır ve verilir ve en sonunda para haznesinin durumu sıfırlanır (veya düzeltilir).

3. "Takılma" ile ilgili kafa karışıklığı. Bazı sorularda, para üstü yoksa otomat kilitlenir veya biriktirilen tüm tutarı iade eder. Para üstü verme hatasındaki davranışı dikkatlice okuyun.

4. Graf üzerindeki aritmetik hatalar. Çok sayıda küçük madeni para olduğunda toplam tutarda hata yapmak kolaydır. Zihinden hesaplamak yerine tablo yöntemini kullanın.

SSS

Bellekli ve belleksiz otomat arasındaki fark nedir? Belleksiz (kombinasyonel) otomat sadece mevcut madeni paraya tepki verir (nadiren karşılaşılır). Bellekli (sıralı) otomat, mevcut toplam tutarı saklayarak yatırılan tüm geçmiş hesaba katar. YKS sorularında neredeyse her zaman ikinci türden bahsedilir.

Soruda fazla ile ne olacağı belirtilmemişse ne yapmalı? Okul soruları standardına göre, "fazla yanar" denmemişse, bir sonraki satın alma için haznede kaldığı kabul edilir. Ancak, otomat kahve verdiyse, hazne genellikle sıfırlanır ve fazla para üstü olarak iade edilir.

25 rublelik fiyat için grafiği hızlıca nasıl oluştururum? Tüm 25 durumu çizmek gerekli değildir. Sadece mevcut madeni paralarla ulaşılabilen tutarları ve önemli (kilit) noktaları çizin: 0, nominal değerlerin katları olan ara toplamlar ve hedef tutar.

Otomat aynı anda birden fazla madeni para kabul edebilir mi? YKS modellerinde giriş akışı her zaman sıralıdır. Eşzamanlı atma durumu değerlendirilmez.

"Otomat döngüye girdi" ne demektir? Bu, mantık hatası nedeniyle (örneğin, para üstü verememe ve madeni paraları iade edememe) otomatın çıkış yolu olmayan bir duruma geçtiği durumdur. Sorularda bu durum genellikle doğru koşullarla engellenir.

Sonuç

Kahve otomatları ile ilgili soruların çözümü, sistem durumunun disiplinli bir şekilde takip edilmesine dayanır. Tüm rakamları zihninizde tutmaya çalışmayın. Basit bir şema çizin: "Önce -> Atılan -> Sonra -> Eylem". Bu görsel yaklaşım, aritmetik hataları ortadan kaldırır ve para üstü verme mantığını doğru bir şekilde hesaba katmanıza yardımcı olur. Unutmayın, otomat, sorunun koşullarında kesin olarak programlandığı şeyi yapan resmi bir yürütücüdür.