Tahmin Oyunu

Şimdi aynı problem için geliştirilen farklı algoritmaların ne derece farklı verimliliklerinin olabileceği hakkında bize fikir veren bir oyun oynayalım. Bilgisayar 1'den 16'ya kadar rastgele bir tam sayı seçecek. Bu sayıyı buluncaya kadar sayı tahmin edeceksiniz ve bilgisayar, her seferinde tahmininizin büyük yada küçük olduğunu söyleyecek.

Sayıyı bulduğunuzda, her tahmininizden sonra gelecek olan yeni tahmininiz için izlediğiniz yolu bir düşünün.

Belki doğru sayıyı buluncaya kadar 1, sonra 2, sonra 3, sonra 4 ve bu şekilde devam ederek tahmin etmiş olabilirsiniz. Bu yaklaşıma doğrusal arama denir, çünkü sayıları sıraya dizilmiş gibi tahmin ettiniz. Bu işe yarardı fakat en çok kaç tahmin hakkına ihtiyacınız olurdu? Eğer bilgisayar 16'yı seçseydi 16 kere tahmin etmek zorunda kalacaktınız. Eğer şansınıza bilgisayar 1'i seçseydi, o zaman ilk tahmininizde sayıyı bulmuş olacaktınız. Peki ortalama hakkında ne söyleyebiliriz? Eğer bilgisayar 1'den 16'ya kadar herhangi bir sayıyı eşit ihtimalle seçecek olursa, ortalama 8 tahmine ihtiyacınız olacaktır.

Fakat 1, 2, 3, 4 gibi sıralı şekilde tahmin etmekten daha verimli bir şey yapabilirsiniz, değil mi? Bilgisayar size tahmin ettiğiniz sayının büyük, küçük,yada eşit olduğunu belirttiği için tahmin etmeye 8'den başlayabilirsiniz. Eğer bilgisayarın seçtiği sayı 8'den küçükse 8'den 16'ya kadar bütün sayıları eleyebilirsiniz; çünkü biliyorsunuz ki 8 üst limittir. Eğer bilgisayarın seçtiği sayı 8'den büyükse, 1'den 7'ye kadar bütün sayıları eleyebilirsiniz. İki şekilde de sayıların yarısını eleyebilirsiniz. Bir sonraki tahminde kalan sayıların yarısını eleyin. Bu şekilde her seferinde kalan sayıların yarısını eleyin. Bu yarılama yaklaşımına ikili arama denir ve bu yöntemle bilgisayarın 1'den 16'ya kadar seçtiği sayıya bağlı olmaksızın, sayıyı en fazla 4 tahminde bulabilirsiniz.

Şimdi 1'den 300'e kadar olan bir sayı için anlattığımız yöntemi deneyin. Bunun için 9'dan fazla tahmine ihtiyacınız olmayacak.

Bu sefer kaç tahminde sayıyı buldunuz? Neden hiçbir zaman 9 tahminden fazlasına ihtiyacınız olmaz? (Matematiksel bir açıklama bulabilir misiniz)?

İkili aramaya tekrar döneceğiz ve onu bir JavaScript dizisindeki bir elemanı aramak için nasıl kullanabileceğimizi göreceğiz. Ama ilk önce daha zor bir problem için hazırlanan bir algoritmaya bakalım.

Bu içerik Dartmouth Bilgisayar Bilimleri öğretim görevlileri Thomas Cormen ve Devin Balkcom ile Khan Academy bilgisayar bölümü içeriklerini hazırlayan takımın işbirliği ile hazırlanmıştır. İçerik CC-BY-NC-SA lisanslıdır.