22 NİSAN 2017
CUMARTESİ
13.52
Youtube
Youtube kanalım açıldı! Daha detaylı ve güncel konu anlatımları için takip etmeyi unutmayın.
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ığı log2100'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 log2128 = 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 log2256 = 8 olduğu için minimum 8 adım olacaktır.

SONUÇ

YORUMLAR 2
0
Mert Topuz
24 NİSAN 2017 - 20.40
Teşekkürler :) Akılda ve arşive kalması gereken minik ayrıntılar aslında hepsi :) Mantığı bir kez kavradıktan sonra nerede ne kullanman gerektiğini görmüş oluyorsun :) Hadi bakalım, seriye devam o zaman :)
CEVAPLA
0
MertTest
01 NİSAN 2020 - 10.42
Test Yorumu
0
Yunus Emre Geldegül
23 NİSAN 2017 - 23.45
Kardeşim seriyi büyük bir iştah ile okuyorum, hakkını vermeliyim çok güzel konular gerçekten. Okulda öğretilen başla, dışarı çık, yumurta al mevzularında sıkıldığım kadar burada tat alıyorum. Vakti zamanında bende bir forumda python ile çeşitli algoritmaları anlatmıştım, kendi blogumda yayımlamak nasip olmamıştı. Burada görmek güzel oldu :)
CEVAPLA
YORUM BIRAK
Şuanda bu yoruma cevap yazıyorsunuz:
İptal Et