Merhaba bugün çok güzel bir algoritma sorusundan ve çözümünden bahsedeceğim.
Problem: 100 Adam ve 100 kapımız var. 1. adam 1’in katları olan kapılardan, 2. adam 2’nin katları olan kapılardan, …., N. Adam N’in katları olan kapılardan, … , 100. Adam 100’ün katları olan kapılardan geçerek kapıların konumlarını değiştiriyor. (Kapı açıksa kapatıyor, kapalıysa açıyor).
En başta bütün kapıların kapalı olduğunu kabul edersek, 100. adam da geçtikten sonra hangi kapıların açık olduğunu bulan programı yazınız.
Java programlama dili ile yazılmış çözümü aşağıdaki gibidir.
public static void main(String[] args) {
//100 kapı için durumlari kaydedecegimiz bir int dizisi acikladik.
int[] kapiDurumu = new int[100];
// Bu dizide kayitli deger 1 ise o kapi acik, 0 ise kapali.
// Dizilerde ilk degerin 0 ile adreslendigini unutmayalim.
// Yani ilk kapi icin kapiDurumu[0] son kapi icin kapiDurumu[99] kullanacagiz.
// Böyle sorularda genelde for döngüsü yapmak gerekir. Biz de öyle yapacagiz.
// Adamlar ve kapilar icin iki ayri döngü gerekecek.
// Döngülerde sayac olarak kullanacagimiz degiskenleri deger atayarak acikliyoruz.
int siradakiAdam = 1;
int siradakiKapi = 1;
// 1'den 100'e kadar bir döngü kurarak kapı durumlarına baslangiç durumu olan sıfır atıyoruz
for (siradakiKapi = 1; siradakiKapi <= 100; siradakiKapi = siradakiKapi + 1) {
// döngü 1'den 100'e ve kapiDurumu indeksleri 0'dan 99'a kadar oldugundan kapi indeksleri hep döngü degerinin bir eksigidir.
// Yani 1. kapinin durumu kapiDurumu[0]'da; 100. kapinin durumu kapiDurumu[99]'da kayitlidir.
kapiDurumu[siradakiKapi - 1] = 0;
}
// siradakiAdam = 1; ===> siradakiAdam degerini 1'den ba$latarak
// siradakiAdam <= maksimumAdamSayisi; ===> siradakiAdam degeri 100'den kücük ve 100'e esit oldugu sürece
// siradakiAdam=siradakiAdam+1 ===> siradakiAdam degeri bir sonraki döngüde siradakiAdam+1 olacak sekilde arttir.
for (siradakiAdam = 1; siradakiAdam <= 100; siradakiAdam = siradakiAdam + 1) {
// Simdi o adamin kendi sirasina ait kapidan ve o siranin katlarindan gecmesi icin ikinci döngüyü yapiyoruz.
// Ilk kapi siradakiAdam'in o anki degeri olacak, sonra döngüyü 100'e kadarki katlarini alarak kuracagiz
for (siradakiKapi = siradakiAdam; siradakiKapi <= 100; siradakiKapi = siradakiKapi + siradakiAdam) {
// Kapi kapaliysa ac
if (kapiDurumu[siradakiKapi - 1] == 0) {
kapiDurumu[siradakiKapi - 1] = 1;
} else {
// Aciksa kapat{
kapiDurumu[siradakiKapi - 1] = 0;
}
}
}
for (siradakiKapi = 1; siradakiKapi <= 100; siradakiKapi = siradakiKapi + 1) {
if (kapiDurumu[siradakiKapi - 1] == 1) {
System.out.println(siradakiKapi + ". kapi durumu acik");
}
}
// Sonuclar dogru mu diye basit bir saglama yapalim:
// 1. kapi sadece 1. adam tarafindan acilacagi icin mutlaka acik olmali.
// 2. kapi 1.'de acilacak, 2.'de kapanacak
// 3. kapi 1.'de acilacak, 3.'de kapanacak
// 4. kapi 1'de acik, 2'de kapali, 4'de acik
// ...
// ...
// son olarak da 100. kapiyi inceleyelim:
// 1 acar
// 2 kapatir
// 4 acar
// 5 kapatir
// 10 acar
// 20 kapatir
// 25 acar
// 50 kapatir
// 100 acar
}C programlama dili ile yazılmış çözümü aşağıdaki gibidir.
//100 kapı için durumlari kaydedecegimiz bir int dizisi acikladik.
int kapiDurumu[100];
// Bu dizide kayitli deger 1 ise o kapi acik, 0 ise kapali.
// Dizilerde ilk degerin 0 ile adreslendigini unutmayalim.
// Yani ilk kapi icin kapiDurumu[0] son kapi icin kapiDurumu[99] kullanacagiz.
// Böyle sorularda genelde for döngüsü yapmak gerekir. Biz de öyle yapacagiz.
// Adamlar ve kapilar icin iki ayri döngü gerekecek.
// Döngülerde sayac olarak kullanacagimiz degiskenleri deger atayarak acikliyoruz.
int siradakiAdam = 1;
int siradakiKapi = 1;
// 1'den 100'e kadar bir döngü kurarak kapı durumlarına baslangiç durumu olan sıfır atıyoruz
for (siradakiKapi = 1; siradakiKapi <= 100; siradakiKapi = siradakiKapi + 1) {
// döngü 1'den 100'e ve kapiDurumu indeksleri 0'dan 99'a kadar oldugundan kapi indeksleri hep döngü degerinin bir eksigidir.
// Yani 1. kapinin durumu kapiDurumu[0]'da; 100. kapinin durumu kapiDurumu[99]'da kayitlidir.
kapiDurumu[siradakiKapi - 1] = 0;
}
// siradakiAdam = 1; ===> siradakiAdam degerini 1'den ba$latarak
// siradakiAdam <= maksimumAdamSayisi; ===> siradakiAdam degeri 100'den kücük ve 100'e esit oldugu sürece
// siradakiAdam=siradakiAdam+1 ===> siradakiAdam degeri bir sonraki döngüde siradakiAdam+1 olacak sekilde arttir.
for (siradakiAdam = 1; siradakiAdam <= 100; siradakiAdam = siradakiAdam + 1) {
// Simdi o adamin kendi sirasina ait kapidan ve o siranin katlarindan gecmesi icin ikinci döngüyü yapiyoruz.
// Ilk kapi siradakiAdam'in o anki degeri olacak, sonra döngüyü 100'e kadarki katlarini alarak kuracagiz
for (siradakiKapi = siradakiAdam; siradakiKapi <= 100; siradakiKapi = siradakiKapi + siradakiAdam) {
// Kapi kapaliysa ac
if (kapiDurumu[siradakiKapi - 1] == 0) {
kapiDurumu[siradakiKapi - 1] = 1;
} else {
// Aciksa kapat{
kapiDurumu[siradakiKapi - 1] = 0;
}
}
}
for (siradakiKapi = 1; siradakiKapi <= 100; siradakiKapi = siradakiKapi + 1) {
if (kapiDurumu[siradakiKapi - 1] == 1) {
printf("kapi%3i = acik\n", siradakiKapi);
}
}
// Sonuclar dogru mu diye basit bir saglama yapalim:
// 1. kapi sadece 1. adam tarafindan acilacagi icin mutlaka acik olmali.
// 2. kapi 1.'de acilacak, 2.'de kapanacak
// 3. kapi 1.'de acilacak, 3.'de kapanacak
// 4. kapi 1'de acik, 2'de kapali, 4'de acik
// ...
// ...
// son olarak da 100. kapiyi inceleyelim:
// 1 acar
// 2 kapatir
// 4 acar
// 5 kapatir
// 10 acar
// 20 kapatir
// 25 acar
// 50 kapatir
// 100 acarProblemin çözümü için yardımlarını eksik etmeyen Mustafa Akın Akalın’a teşekkür ediyorum.