Algoritmalar - İkili Arama Algoritması - Sayı Tahmin Örneği

İkili arama algoritması için yapılabilecek en güzel örneklerden biri sayı tahmin oyunudur. Sayı tutma oyununu bu makalemizde binary search ile birlikte inceleyeceğiz.

Sayı tutma oyunu, temelde bilgisayar tarafından belirlenen bir aralıkta tutulan sayıyı tahmin etme oyunudur.

Bu oyunun ikili arama algoritması ile bağlantısı nedir?

İkili arama algoritması, her adımda ihtimali %50 indirerek yeni aralıkta arama yapmaktadır. Sayı tutma oyununun temel mantığı da aynıdır. Örneğin 0-100 aralığında belirlenen bir sayıyı en hızlı şekilde bulmak için yapmanız gereken ilk olarak 50 değerini denemektir. Bunun sebebini şu görselde açıklayabiliriz;

Bu arama yöntemi ile sayıyı tahmin ederek bulmaktan çok daha az adımda bulmuş oluruz. Çünkü ihtimalleri her seferinde %50 indiriyoruz. İşte matematikte bu işlemin karşılığı log₂100'dür.

log2(100) = 6,64385618977473

Yani biz bu işlemi her adımda %50 indirgeyerek en fazla 6,64385618977473 adımda bitiririz. Örneğimizi incelersek 6 adımda bitirdiğimizi göreceksiniz. Şimdi aşağıdaki örneğimize bakalım.

ÖRNEK

Sayı oyununu 1-128 aralığında gerçekeştirelim.

ÇÖZÜM

#include <iostream>
#include <cstdlib>
#include <ctime>
using namespace std;

int main() {
	int sayi, tahmin, kacincida = 0;
	srand(time(0));
	
	sayi = 1 + rand() % 128;
	
	do {
		cout << "Tutulan Sayi Kac Olabilir? (1-128): ";
		cin >> tahmin;
		kacincida++;
		
		if(tahmin > sayi) {
			cout << "Tutulan Sayi Daha KUCUK!";
		} else if(tahmin < sayi) {
			cout << "Tutulan Sayi Daha BUYUK!";
		} else {
			cout << "Bravo! Tutulan Sayi: " << sayi << endl;
			cout << "Sayiya " << kacincida << " adimda ulastin!";
		}
		
	} while(tahmin!=sayi);
	
}

ANALİZ

Bu işlemi mantıksal olarak minimum 7 adımda gerçekleştirebiliriz. Yani 128 sayı içerisinde kaba tabiriyle sallayarak bulmaya çalışırsak bile ihtimalimiz 128'dir. Fakat mantıksal olarak gidersek ihtimalleri hep yarıya indirgeyerek sonuca ulaşabiliriz. Bu da log₂128 = 7 olduğu için minimum 7 adım olacaktır.

SONUÇ

ÖRNEK

Sayı oyununu 1-256 aralığında gerçekeştirelim.

ÇÖZÜM

#include <iostream>
#include <cstdlib>
#include <ctime>
using namespace std;

int main() {
	int sayi, tahmin, kacincida = 0;
	srand(time(0));
	
	sayi = 1 + rand() % 256;
	
	do {
		cout << "Tutulan Sayi Kac Olabilir? (1-256): ";
		cin >> tahmin;
		kacincida++;
		
		if(tahmin > sayi) {
			cout << "Tutulan Sayi Daha KUCUK!";
		} else if(tahmin < sayi) {
			cout << "Tutulan Sayi Daha BUYUK!";
		} else {
			cout << "Bravo! Tutulan Sayi: " << sayi << endl;
			cout << "Sayiya " << kacincida << " adimda ulastin!";
		}
		
	} while(tahmin!=sayi);
	
}

ANALİZ

Bu işlemi mantıksal olarak minimum 8 adımda gerçekleştirebiliriz. Yani 256 sayı içerisinde kaba tabiriyle sallayarak bulmaya çalışırsak bile ihtimalimiz 256'dır. Fakat mantıksal olarak gidersek ihtimalleri hep yarıya indirgeyerek sonuca ulaşabiliriz. Bu da log₂256 = 8 olduğu için minimum 8 adım olacaktır.

SONUÇ