C# İle biLGİsayar programlama temelleri (C# Programlama Kitabı) Svetlin Nakov & Co

10.9 İç içe N Döngünün Simülasyonu

Sık sık iç içe döngüler yazmak zorundayız. İki, üç adet veya daha önceden belirli bir sayı kadar döngünün kodlanması kolaydır. Ancak sayılar önceden bilinmiyorsa, farklı bir yaklaşım düşünmekte fayda var.

N sayısının 1..K defa tekrarlanarak gösterimini gerçekleştiren aşağıdaki örneği göz önüne alınız: N ve K kullanıcı tarafından girilmelidir.

for (a1 = 1; a1 <= K; a1++) for (a2 = 1; a2 <= K; a2++) for (a3 = 1; a3 <= K; a3++) … for (aN = 1; aN <= K; aN++) Console.WriteLine("{0} {1} {2} … {N}", a1, a2, a3, …, aN);

Örneğin N=2 ve K=3 için (1..3 defa tekrarlanarak gösterimi), ve N=3 ve K=2 için (1..2 defa tekrarlanarak gösterimi), çıktılar aşağıdaki gibidir:

Bu problemi çözen algoritmayı önceki örnekte olduğu gibi açıkça anlayamayabilirsiniz. Bunun için biri özyinelemeli, diğeri yinelemeli iki çözüm geliştirebiliriz.
Sonucun her satırında, N adet sayının bir sıralı dizilimini görüyorsunuz. Birinci değişken birinci döngü sayacının geçerli değerini temsil eder. İkinci değişken – ikinci döngü sayacının geçerli değerini temsil eder, vs. Her sayı 1 ve K arasında değer alabilir. N ve K verildiğinde görevimiz, N elemanın sıralı dizilimlerini bulmaktır.

10.9.1 İç içe Döngüler – Özyinelemeli Yaklaşım

Eğer problem için özyinelemeli çözüm arıyorsanız, ilk yaklaşımınız özyinelemeli bağlılık bulmaktır. Örnekte tanımlı olan probleme biraz daha dikkatli bakalım.

N=2 için cevabı hesaplasaydık, birinci sayı olarak K koyarak (örneğimizde K=3) N=3 için de cevabı elde edecektik, çünkü diğer sayılar N=2 için hali hazırda yazılı olacaktı. Bu sonlanma koşulu N>3 için de geçerlidir.

Bu şekilde aşağıdaki bağlılığı yakaladık – ilk pozisyondan itibaren geçerli her konuma 1..K arası değerleri sırasıyla yerleştirdikten sonra bir sonraki pozisyon için özyinelemeli olarak kendimizi çağırdık. Özyineleme N defa kendisini çağırdığında sonlanır ve sayılar K değerine kadar sıralı bir şekilde ard arda yazılır. C# metotu aşağıda gösterilmiştir:

static void NestedLoops(int currentLoop) { if (currentLoop == numberOfLoops) { PrintLoops(); return; } for (int counter=1; counter<=numberOfIterations; counter++) { loops[currentLoop] = counter; NestedLoops(currentLoop + 1); } }

Sayı dizisi loops adlı bir dizide saklanırken, PrintLoops() metoduyla özyineleme sonlandığında bu sayılar basılacaktır.

NestedLoops(…) metotu sayıların yerleştirileceği pozisyonları belirten bir parametre almaktadır.

Bir sonraki pozisyon için NestedLoops(…) metotunu özyinelemeli olarak çağırdıktan sonra döngü içinde adlandırdığımız olası her değer yazdırılır. numberOfIterations değişkeni kullanıcı tarafından girilen K değeri için oluşturulmuştur.

Geçerli konum N olduğunda en son satır yazılmıştır ve özyineleme sonlanır. numberOfLoops değişkeni kullanıcı tarafından girilen N değeri için oluşturulmuştur.

Özyinelemeli olarak iç içe döngü ile ilgili çözümün tam bir uygulaması aşağıda verilmiştir:

RecursiveNestedLoops.cs

using System; class RecursiveNestedLoops { static int numberOfLoops; static int numberOfIterations; static int[] loops; static void Main() { Console.Write("N = "); numberOfLoops = int.Parse(Console.ReadLine()); Console.Write("K = "); numberOfIterations = int.Parse(Console.ReadLine()); loops = new int[numberOfLoops]; NestedLoops(0); } static void NestedLoops(int currentLoop) { if (currentLoop == numberOfLoops) { PrintLoops(); return; } for (int counter=1; counter<=numberOfIterations; counter++) { loops[currentLoop] = counter; NestedLoops(currentLoop + 1); } } static void PrintLoops() { for (int i = 0; i < numberOfLoops; i++) { Console.Write("{0} ", loops[i]); } Console.WriteLine(); } }

N=2 ve K=4 için uygulama çıktısı aşağıdaki gibidir:

N = 2 K = 4 1 1 1 2 1 3 1 4 2 1 2 2 2 3 2 4 3 1 3 2 3 3 3 4 4 1 4 2 4 3 4 4

Main() metotu içinde N ve K için değerler girilir, sayı dizilerini tutan bir dizi oluşturulur, daha sonra birinci pozisyon için NestedLoops(…) metot çağrısı ile tüm çıktı sonucu üretilir ve konsolda gösterilir.

Dikkat etmelisiniz ki, dizinin parametresi olarak 0 veriyoruz, çünkü sayı dizisini tuttuğumuz dizinin endeksi 0’dan başlar. PrintLoops() metotu dizinin tüm elemanlarını ziyaret ederek konsolda onları basar.

10.9.2 İç içe Döngüler – Yinelemeli Yaklaşım

Eğer problem için yinelemeli çözüm arıyorsanız, her yinelemede bir sonraki sayı dizisini bulan ve basan aşağıdaki algoritmayı kullanabilirsiniz:

1. 
   Her pozisyon başına 1 sayısını yerleştirin.
   
2. 
   Mevcut sayı dizisini bastırın.
   
3. 
   N pozisyon numarasını 1 artırdıktan sonra elde ettiğiniz değer K’yı aşmışsa, onu tekrar 1’e eşitleyin ve N-1 pozisyonundaki değeri 1 ile artırın. Bu değer de K’yı aşmışsa, onu tekrar 1’e eşitleyin ve N-2 pozisyonundaki değeri 1 ile artırın, ve bu böyle devam eder.
   
4. 
   İlk pozisyon değeri K’yı aştığı takdirde, algoritma sonlanır.
   
5. 
   Adım 2 ile devam edin.
   

Açıkladığımız yinelemeli iç içe döngüler algoritmasın uygulaması aşağıda sunulmuştur:

IterativeNestedLoops.cs

using System; class IterativeNestedLoops { static int numberOfLoops; static int numberOfIterations; static int[] loops; static void Main() { Console.Write("N = "); numberOfLoops = int.Parse(Console.ReadLine()); Console.Write("K = "); numberOfIterations = int.Parse(Console.ReadLine()); loops = new int[numberOfLoops]; NestedLoops(); } static void NestedLoops() { InitLoops(); int currentPosition; while (true) { PrintLoops(); currentPosition = numberOfLoops - 1; loops[currentPosition] = loops[currentPosition] + 1; while (loops[currentPosition] > numberOfIterations) { loops[currentPosition] = 1; currentPosition--; if (currentPosition < 0) { return; } loops[currentPosition] = loops[currentPosition] + 1; } } } static void InitLoops() { for (int i = 0; i < numberOfLoops; i++) { loops[i] = 1; } } static void PrintLoops() { for (int i = 0; i < numberOfLoops; i++) { Console.Write("{0} ", loops[i]); } Console.WriteLine(); } }

Main() ve PrintLoops() metotları özyinelemeli uygulamadaki gibidir.

NestedLoops() metotu yinelemeli ve parametresiz olarak çalıştığı için farklı uygulanmalıdır.

Metotun en başında, InitLoops() metotuna bir çağrı yapılarak dizinin her pozisyonu için 1 atanır.

Algoritmanın adımları çalışırken sonsuz döngüden metotların return deyimi ile çıkar.

Algoritmanın 3.adımını uygulamak oldukça ilginçtir. K’nın üzerindeki değerlerin kontrolü, 1’e eşitlenmeleri, ve bir önceki pozisyonun değerinin 1 ile artırılması (aynı kontrolü onun için de gerçekleştirdikten sonra) ardından K’yı aşan değerler için while döngüsüne girilir.

Mevcut pozisyon değeri bu amaçla 1’e eşitlenir. Bunun sonrasında bir önceki pozisyon geçerli olur. Ardından geçerli pozisyonun değeri 1’e eşitlenir ve döngünün başlangıcına dönülür. Bu eylemler mevcut pozisyon değeri K veya daha az iken devam eder. K’yı aşınca (numberOfIterations değişkeni K değerine erişince) sona erer.

İlk pozisyon değeri K’yı aşınca, döngü K defa çalışmıştır. Çıktının devamlılığını sağlayabilmek için (sonsuz döngüye devam etmek için) sayı dizisinin bir sonraki elemanı tekrar 1’e eşitlenir ve bu anda bu alt döngünün yinelenme sayısı K’yı tükettiği için geçerli pozisyon (currentPosition) 0’dan az ve negatif bir değer almıştır. Dizi endeksi negatif değer alamayacağı için bir if-kontrol deyimi içindeki return ile alt döngüden çıkılır.

N=3 ve K=2 için uygulamayı test edebiliriz:

N = 3 K = 2 1 1 1 1 1 2 1 2 1 1 2 2 2 1 1 2 1 2 2 2 1 2 2 2

10.9.3 Hangisi Daha İyi: Özyineleme veya Yineleme?

Eğer problem çözme algoritması özyinelemeli ise, özyinelemeli çözüm uygulaması aynı problem için geliştirilebilecek bir yinelemeli çözüm uygulamasından çok daha okunaklı ve tercih edilirdir.

Eşdeğer bir algoritmanın tanımlanması ve algoritmaların eşdeğerliliklerini kanıtlamak zor da olabilir.

Özyineleme kullanarak belirli durumlarda çok daha basit, daha kısa ve kolay çözümler sunmayı başarabiliriz.

Öte yandan, özyinelemeli çağrılar çok daha fazla kaynak tüketebilir (CPU zamanı ve bellek). Her özyinelemeli çağrı için ayrıca yığında, metota giren ve/veya çıkan argümanlar, yerel değişkenler ve döndürülen değerleri saklayan yeni bellek alanları ayrılmalıdır. Çok fazla özyinelemeli çağrılar bir yan etki olarak bellek akıntısına neden olabilir.

Özyinelemeli çözümler, bazı durumlarda, eşdeğer yinelemeli çözümlerinden daha zor okunabilir ve anlaşılabilir.

Özyineleme güçlü bir programlama tekniğidir, ancak dikkatli analiz edilmelidir. Yanlış kullanımında, çözümlerin anlaşılması ve bakımı zorlaşır.

Eğer özyineleme kullanarak daha basit, daha kısa ve daha kolay bir çözüme varırsanız tercih edilebilir. Aksi takdirde, yinelemeli bir çözüm düşününüz.

10.9.4 Fibonacci Sayıları – Özyinelemenin Yanlış Kullanımı

Bir Fibonacci dizisinin n.elemanını bulduğumuz örneğe yeniden göz atalım ve özyinelemeli çözüme daha dikkatli olarak yaklaşalım.

static long Fib(int n) { if (n <= 2) { return 1; } return Fib(n - 1) + Fib(n - 2); }

Bu çözüm, sezgisel, kısa ve anlaşılırlığı yüksektir. İlk bakışta özyinelemenin iyi uygulanabileceği bir örnekmiş gibi görünüyor. Ancak gerçekte, özyinelemenin kullanımına dair doğru olmayacak bir örnektir. Nedenini açıklamak gerekirse, özyinelemeli uygulamayı aşağıdaki şekilde geliştirdiğimizi düşünelim:

RecursiveFibonacci.cs

using System; class RecursiveFibonacci { static void Main() { Console.Write("n = "); int n = int.Parse(Console.ReadLine()); long result = Fib(n); Console.WriteLine("fib({0}) = {1}", n, result); } static long Fib(int n) { if (n <= 2) { return 1; } return Fib(n - 1) + Fib(n - 2); } }

n=100 için, hesaplamalar kimsenin beklemeyi göze almayacağı kadar uzun süreceği için uygulama son derece verimsiz olacaktır. Özyinelemeli her çağrı için iki özyinelemeli çağrı daha yapılıyor. Çağrılar, bu nedenle, aşağıdaki şekilde gösterildiği gibi katlanarak büyümektedir.

fib(100) hesaplanması için gerekli adımlar 100 üssü 1,6 mertebesindedir, matematiksel olarak bu sayı kanıtlanmıştır. Buna rağmen, çözüm doğrusal olsaydı, bu sayı 100 olacaktı.

Nedeni, çok fazla hesap gerektirmesindendir. Aşağıdaki Fibonacci ağacından da görülebileceği gibi, fib(2) sayısı birden fazla yerde göze çarpmaktadır.

10.9.5 Fibonacci Sayıları – Özyinelemenin Doğru Kullanımı

Fibonacci sayılarının hesaplanması için özyinelemeli metotu optimize etmenize yardımcı olabiliriz. Dizide zaten hesaplanan sayıları hatırlayarak (saklayarak) ve ancak eğer sayı henüz hesaplanmamışsa özyinelemeli çağrıyı yapmaya hazırlanmakla optimizasyon sağlanabilir. Bilgisayar bilimlerinde dinamik optimizasyon veya memoizasyon olarak bilinen bu optimizasyon tekniği sayesinde (hafıza teknikleri ile karıştırmayınız), özyinelemeli çözüm adımları doğrusal bir sayı kadar yinelendikten sonra sona erer.

Aşağıda özyinelemenin doğru kullanımını gösteren bir uygulama verilmiştir:

RecursiveFibonacciMemoization.cs

using System; class RecursiveFibonacciMemoization { static long[] numbers; static void Main() { Console.Write("n = "); int n = int.Parse(Console.ReadLine()); numbers = new long[n + 2]; numbers[1] = 1; numbers[2] = 1; long result = Fib(n); Console.WriteLine("fib({0}) = {1}", n, result); } static long Fib(int n) { if (0 == numbers[n]) { numbers[n] = Fib(n - 1) + Fib(n - 2); } return numbers[n]; } }

Gözle görülür bir fark vardır. Önceki örnekte n=100 için sonsuza giden bir hesaplama nedeniyle sonuç uzun zaman sonra hesaplanırken, optimize edilmiş çözüm ile sonuç hemen hesaplanıyor. Daha sonraki “Veri Yapıları ve Algoritma Karmaşıklığı” Bölümü’nde not edileceği üzere, birinci çözüm üssel, ikinci çözüm doğrusal zamanda çalışmaktadır.

n = 100 fib(100) = 3736710778780434371

10.9.6 Fibonacci Sayıları – Yinelemeli Çözüm

Fibonacci sayılarının ardışık hesaplanmasıyla özyineleme kullanmadan problemi çözmenin de mümkün olabileceğini fark etmişsinizdir. Bu amaçla dizinin sadece son iki elemanı saklanır ve bir sonraki elemanın değerini hesaplamak için saklanan değerler kullanılır. Fibonacci sayılarını yinelemeli hesaplayan algoritmanın bir uygulaması aşağıda verilmiştir:

IterativeFibonacci.cs

using System; class IterativeFibonacci { static void Main() { Console.Write("n = "); int n = int.Parse(Console.ReadLine()); long result = Fib(n); Console.WriteLine("fib({0}) = {1}", n, result); } static long Fib(int n) { long fn = 0; long fnMinus1 = 1; long fnMinus2 = 1; for (int i = 2; i < n; i++) { fn = fnMinus1 + fnMinus2; fnMinus2 = fnMinus1; fnMinus1 = fn; } return fn; } }

Bu çözüm kısa ve zarif görünüyor, verimlidir ve fazla bellek gerektirmez, ancak yine de özyineleme için varolan riskleri tamamen yok etmiyor.

Bir başka öneriyle önceki örnekleri sonuçlandıralım:

Özyineleme güçlü bir programlama tekniğidir, fakat çalışması ve etki alanı hakkında yeterli bilgiye sahip olunmadığı sürece ne olduğunu fark edemeyebilir ve kendi bindiğiniz dalı kesebilirsiniz. Bu da yanlış programlamaya neden olacağı için dikkatle kullanmalısınız!

Eğer bu kuralı uygularsanız, özyinelemenin yanlış kullanım olasılığı azalır ve sonuçlarından etkilenmezsiniz.

10.9.7 Özyineleme ve Yineleme – Daha Fazlası

Doğrusal hesaplama gerektiren süreçler için özyineleme kullanmak genellikle zorunlu değildir, çünkü yinelemeyle sonuçlar kolayca bir araya getirilebilir, bu basit ve etkili bir hesaplama tekniğidir. Örneğin, doğrusal işlem gerektiren faktöriyel hesaplama probleminde, bir sonraki elemanın değeri sadece önceki gelen tüm elemanlara bağlıdır.

Doğrusal hesaplama işlemlerinin karakteristik özelliği, her adımda sadece bir kere özyineleme çağrısı ile hesabın sadece bir yönde ilerlenerek tamamlanabilmesidir. Doğrusal hesaplama sürecini şematik olarak şu şekilde tanımlayabiliriz:

void Recursion(parameters) { do some calculations; Recursion(some parameters); do some calculations; }

Metot gövdesinde sadece bir kere özyinelemeli çağrı yapılmışsa özyineleme kullanmak gerekli değildir, çünkü yineleme anlaşılır ve barizdir.

Mantıksal ve/veya kontrol edilmesi gerekli kod dalları içeren hesaplama süreçleri varsa özyineleme kullanabilirsiniz. Örneğin, yinelemeli çözümlerle iç içe N döngüyü temsil etmek zordur.Metot gövdesinde birden fazla özyinelemeli çağrı, ağaç benzeri bir hesaplama düzenini ortaya çıkarır. Ağaç dallarına benzer bu kod hesaplama süreçleri için özyinelemenin her adımı birkaç özyineleme çağrısına girer (doğrusal hesaplamalarda bu bir listeye benzer).

Ağaç benzeri dallara sahip bir hesaplama sürecinin şematik gösterimi aşağıdaki gibidir:

void Recursion(parameters) { do some calculations; Recursion(some parameters); … Recursion(some other parameters); do some calculations; }

Özyinelemeli çağrıları programın çalışmasıyla yığıtta (stack) simüle edebilirsiniz, ancak bu yinelemelere inmek karışık ve gereksizdir. Fibonacci sayılarını hesaplarken gerekli hesap çağrılarını hatırlayın. Her bir sonraki sayı, önceden hesaplanabilir önceki iki sayı üzerinden hesaplandı. Özyineleme, bu örnekteki gibi, probleme basit, kolay anlaşılır ve verimli bir çözüm sunuyorsa tercih edilmelidir.

Ancak, sonraki sayı önceki değil sonraki sayılar üzerinden hesaplanıyorsa, özyinelemeli bağımlılık tanımı kolay değil, zor analiz edilir. Bu durumda memoizasyon tekniğini uygulayarak yinelenen hesaplamalardan kaçındığınız takdirde özyineleme doğru bir şekilde uygulanırsa çok verimli olabilir.

Dallı yinelemeli hesaplamalar için özyineleme kullanabilirsiniz (fakat her değerin sadece bir kez hesaplanması şartını aramalısınız). Doğrusal özyinelemeli hesaplamalar için yineleme kullanmayı tercih edin.

10.9.8 Labirentte İz Sürmek – Örnek

N x M kapıdan oluşan dikdörtgen şekilli bir labirent veriliyor. Kapıların her biri geçilir veya geçilmez özelliklidir. Sol üst köşesinden labirente giren bir kimse, sağ alt köşeye ulaşmak istiyor. Kişi yukarı, aşağı, sağa veya sola yöne bir seferde bir kapı hareket edebilir. Bir kapıdan geçildiğinde, geri dönüş yapılmaksızın tekrar aynı kapıdan geçilmesi yasaktır. Ancak kapı serbest hale gelebilirse geçilebilir. Sağ alt köşeye ulaşıldığına yol tamamlanıyor.

Labirente giren bir kişinin girişten çıkışa kadar izlediği tüm yolları görüntülemek istiyoruz.

Özyineleme kullanılarak çözülebilen problemlere tipik bir örnektir. Bu problemin yineleme ile çözümü daha karmaşık ve uygulaması zor olacaktır.

Şekiller üzerinden problemi anlamaya çalışınız:

Belirtimleri yerine getiren girişten çıkışa 3 ayrı yol olduğunu görebilirsiniz. (sadece geçerli kapılardan geçilmiştir ve aynı kapıdan iki kere geçilmemiştir). Bu 3 yol aşağıda izlenmiştir:

Yukarıdaki şekillerde sayılar yolu izlerken kaç defa dönüş yapıldığına işaret ediyor.

10.9.9 Labirent Yolları – Özyinelemeli Algoritma

Bu problemi nasıl çözeriz? Labirentin herhangi bir pozisyonundan sonuna kadar arama işlemini bir özyinelemeli süreç olarak aşağıda gibi tanımlayabiliriz:

1. 
   Başlangıç pozisyonu (0,0) olmak üzere, labirentin geçerli konumu (row, col) olsun.
   
2. 
   Mevcut konum (N-1, M-1) ise hedefe varılmıştır. Aranan çıkış sağlanmıştır.
   
3. 
   Kapı geçilmezse, geri gideriz (durma hakkımız yoktur).
   
4. 
   Pozisyon daha önce ziyaret edilmişse, geri gideriz (iki kere geçme hakkımız yoktur).
   
5. 
   Bunların dışında, 4 özyineleme sözkonusudur:
   

• 
  Sağa gidiş: (row, col + 1)
  
• 
  Aşağı gidiş: (row + 1, col)
  
• 
  Yukarı gidiş: (row – 1, col)
  
• 
  Sola gidiş: (row, col - 1)
  

Bu algoritma çözümünü analiz ederken özyinelemeli düşünmeliyiz. Problem cümlesi “verilen bir pozisyondan çıkışa giden yolu bulmaktır”. Alt problemlere bölünmesi gerekirse:

• 
  geçerli konumun bir sağındaki pozisyondan çıkışa giden yolu aramak
  
• 
  geçerli konumun bir aşağısındaki pozisyondan çıkışa giden yolu aramak
  
• 
  geçerli konumun bir yukarısındaki pozisyondan çıkışa giden yolu aramak
  
• 
  geçerli konumun bir solundaki pozisyondan çıkışa giden yolu aramak
  

Ulaştığımız herhangi bir pozisyonundan, dört yönde de gitmek fakat dairesel bir yol rotası içinde olmamamız şartı iki kere aynı kapıdan geçmemek koşulu ile ve (eğer varsa) son kapıya (çıkışa) ulaşarak yol bulmayı da hesaplar.

Bu problem için özyineleme, daha önceki örneklerden daha zordur. Her adımda çıkışa ulaşıp ulaşmadığımız kontrol edilmeli veya geçilmez kapıda (yasak pozisyon) olup olmadığımız bilinmelidir. Bunun sonrasında, bulunduğumuz pozisyonu ziyaret edilmiş sayıp dört tarafta arayış için özyinelemeli çağrı vardır. İlerlemeye izin vermeyip de geri gidilen kapılar serbest bırakılmalıdır (backtracking).

10.9.10 Labirent Yolları – Uygulama

Algoritma uygulaması için uygun bir şekilde labirenti temsil etmeliyiz. İki boyutlu bir karakter dizisi kullanacağız. Geçilir pozisyonlar ' ' boşluk karakteri ile, çıkış pozisyonu 'e ' ile, geçilmez pozisyonlar '*' yıldız karakteri ile gösterilecek. Başlangıç pozisyonu geçilir pozisyondur. Ziyaret ettiğimiz pozisyonları 's' ile işaretleyeceğiz. Bir labirent temsili aşağıda verilmiştir:

static char[,] lab = { {' ', ' ', ' ', '*', ' ', ' ', ' '}, {'*', '*', ' ', '*', ' ', '*', ' '}, {' ', ' ', ' ', ' ', ' ', ' ', ' '}, {' ', '*', '*', '*', '*', '*', ' '}, {' ', ' ', ' ', ' ', ' ', ' ', 'e'}, };

Labirent yollarının bulunması için özyinelemeli metotun uygulaması şöyle olacaktır:

static char[,] lab = { {' ', ' ', ' ', '*', ' ', ' ', ' '}, {'*', '*', ' ', '*', ' ', '*', ' '}, {' ', ' ', ' ', ' ', ' ', ' ', ' '}, {' ', '*', '*', '*', '*', '*', ' '}, {' ', ' ', ' ', ' ', ' ', ' ', 'e'}, }; static void FindPath(int row, int col) { if ((col < 0) || (row < 0) || (col >= lab.GetLength(1)) || (row >= lab.GetLength(0))) { // We are out of the labyrinth return; } // Check if we have found the exit if (lab[row, col] == 'e') { Console.WriteLine("Found the exit!"); } if (lab[row, col] != ' ') { // The current cell is not free return; } // Mark the current cell as visited lab[row, col] = 's'; // Invoke recursion to explore all possible directions FindPath(row, col - 1); // left FindPath(row - 1, col); // up FindPath(row, col + 1); // right FindPath(row + 1, col); // down // Mark back the current cell as free lab[row, col] = ' '; } static void Main() { FindPath(0, 0); }

Uygulama yukarıdaki tanımı aynen gerçekleştirir. Bu durumda labirentin boyutları N ve M değişkenlerinde saklanmaz, ancak iki-boyutlu bir lab dizisi yardımıyla, labirentin sütun sayısı lab.GetLength(1) ve satır sayısı lab.GetLength(0) olmak üzere elde edilir.

Arama yapan özyinelemeli metotun girişinde ilk koşul labirentin dışına çıkıp çıkmadığımızın kontrolüdür. Bu yasak durumda, labirentin sınırları dışına çıkılmaması için metot sonlandırıldı.

Çıkış bulup bulmadığımız kontrol edilmelidir. Bulduysak uygun bir mesaj yazıyoruz ve bulunduğunuz konumdan ileriye doğru arama sonlandırıyoruz.

Daha önce ziyaret etmediğimiz geçerli ve geçilir bir pozisyon (labirentin geçerli pozisyonundan itibaren geçerli yolun bir parçası değilse) arıyoruz.

Bir pozisyon bulursak ziyaret ediyoruz. Tanım gereği bu hücreyi 's' ile işaretleyerek ziyaret etmeliyiz. Sonrasında özyinelemeli olarak dört olası yönde bir yol aramalıyız. Bu dört özyinelemeli çağrıdan dönüldüğünde geçerli hücre ' ' ile işaretlenerek serbest bırakılır.

Geçerli konumun serbest bırakılması önemlidir, çünkü geri döndüğümüzde mevcut yolun bir parçası değildir. Bu belirtimi atlarsanız, yolların hepsi değil, ancak bazıları bulunmuş olabilir.

Labirentin çıkış yollarını bulmak için uygulanan özyinelemeli metot bu şekilde özetlenmiştir. Şimdi sadece bu metotu (0, 0) başlangıç pozisyonundan başlatarak Main() metotu içinden çağırmalıyız.

Bu sonuç aşağıdaki sonucu döndürür:

Found the exit! Found the exit! Found the exit!

Çıkışın tam üç kez bulunduğunu görebilirsiniz. Algoritma düzgün çalışıyor gibi görünüyor; ancak daha anlamlı olabilmesi için çıkış yolunu yazdırmamız gerekiyor.

10.9.11 Labirent Yolları – İz Kayıtları

Özyinelemeli algoritma ile bulduğumuz yolları yazdırmak için, her adımda atılan adım yönünü saklayacak bir diziye ihtiyacımız var: sağ – R (right), aşağı – D (down), yukarı – U (up), sol – L (left). Bu dizi her an için labirentin başından itibaren geçerli yolu tutacak.

Bir karakter dizisi ve sayaç yardımıyla, şu anki özyineleme derinliğini, yani özyinelemeli olarak kaç pozisyon ilerlediğimizi tutabiliriz. Özyinelemeye her girişte sayaç 1 artırılmalıdır. Dönüşte 1 azaltılmalıdır. Çıkış yolu bulunduğunda, yazdırılması için gerekli veriler hazırdır (0 ile başlayan ve sayaç endeksine kadar olan dizinin tüm karakterleri).

Dizinin boyutları ne olmalıdır? Bu sorunun cevabı kolaydır; bir hücreye en fazla bir kere girilebildiğine göre en uzun yol N * M kadardır. Örneğimizdeki labirent 7 * 5 boyutlarında olduğu için dizinin en fazla uzunluğu 35 kabul edilmelidir.

Not: List veri yapısını biliyorsanız, karakter dizisi yerine List kullanmanız daha uygun olabilir. Listeleri daha detaylı olarak "Doğrusal Veri Yapıları" Bölümü’nde öğreneceksiniz.

Açıklanan fikrin uygulanması aşağıda verilmiştir:

static char[,] lab = { {' ', ' ', ' ', '*', ' ', ' ', ' '}, {'*', '*', ' ', '*', ' ', '*', ' '}, {' ', ' ', ' ', ' ', ' ', ' ', ' '}, {' ', '*', '*', '*', '*', '*', ' '}, {' ', ' ', ' ', ' ', ' ', ' ', 'e'}, }; static char[] path = new char[lab.GetLength(0) * lab.GetLength(1)]; static int position = 0; static void FindPath(int row, int col, char direction) { if ((col < 0) || (row < 0) || (col >= lab.GetLength(1)) || (row >= lab.GetLength(0))) { // We are out of the labyrinth return; } // Append the direction to the path path[position] = direction; position++; // Check if we have found the exit if (lab[row, col] == 'e') { PrintPath(path, 1, position - 1); } if (lab[row, col] == ' ') { // The current cell is free. Mark it as visited lab[row, col] = 's'; // Invoke recursion to explore all possible directions FindPath(row, col - 1, 'L'); // left FindPath(row - 1, col, 'U'); // up FindPath(row, col + 1, 'R'); // right FindPath(row + 1, col, 'D'); // down // Mark back the current cell as free lab[row, col] = ' '; } // Remove the last direction from the path position--; } static void PrintPath(char[] path, int startPos, int endPos) { Console.Write("Found path to the exit: "); for (int pos = startPos; pos <= endPos; pos++) { Console.Write(path[pos]); } Console.WriteLine(); } static void Main() { FindPath(0, 0, 'S'); }

Labirentin çıkış yolunu arayan özyinelemeli metota bir parametre daha ekledik: geçerli konuma ulaşmak için kullandığımız yönü belirtir imleç : R, D, U, L. Bu parametre başlangıç pozisyonundan geçerken S değerine sahiptir. Ancak bu bir anlam taşımaz. Yolu yazdırırken, bu ilk elemanı atlarız.

Programı başlatırsak, labirentin başından sonuna kadar üç yol bulunur:

Found path to the exit: RRDDLLDDRRRRRR Found path to the exit: RRDDRRUURRDDDD Found path to the exit: RRDDRRRRDD

10.9.12 Labirent Yolları – Programın Test Edilmesi

Algoritma düzgün çalışıyor gibi görünüyor. Biraz daha fazla örnek ile test etmek hatasız çalıştığını gösterecektir.

1x1 boş labirent ile programı test edebilirsiniz, 3 x 3 boş labirent ile, yada çıkış yolu olmayan bir labirent ile ve birçok yola sahip boyutları büyük bir labirent ile test edebilirsiniz.

Bu testler her durumda programın düzgün çalıştığına sizi ikna edecektir.

Örnek girdi ( 1 x 1 boş labirenti):

static char[,] lab = { {'e'}, };

Örnek çıktı:

Found path to the exit:

Çıktıdaki yol beklendiği gibi boştur (uzunluğu 0’dır), çünkü başlangıç pozisyonu çıkışla aynıdır. Bu durumda görselleştirmeyi geliştirmek isteyebilirsiniz (“Yol boştur” yazdırmak, vs.)

Örnek girdi ( 3 x 3 boş labirenti):

static char[,] lab = { {' ', ' ', ' '}, {' ', ' ', ' '}, {' ', ' ', 'e'}, };

Yukarıdaki örnek labirentin çıktısı:

Found path to the exit: RRDLLDRR Found path to the exit: RRDLDR Found path to the exit: RRDD Found path to the exit: RDLDRR Found path to the exit: RDRD Found path to the exit: RDDR Found path to the exit: DRURDD Found path to the exit: DRRD Found path to the exit: DRDR Found path to the exit: DDRUURDD Found path to the exit: DDRURD Found path to the exit: DDRR

Bunlar tüm çıkış yollarıdır.

Bir başka örnek girdi (çıkışı olmayan 5 x 3 labirenti):

static char[,] lab = { {' ', '*', '*', ' ', ' '}, {' ', ' ', ' ', '*', ' '}, {'*', ' ', ' ', '*', 'e'}, };

Çıktısı:

(çıkış yok)

Şimdi çok büyük bir labirent için programa bakalım: Örnek girdi ( 15 x 9 labirenti):

static char[,] lab = {{' ','*',' ',' ',' ',' ','*',' ',' ',' ',' ','*','*',' ',' '}, {' ',' ','*',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' '}, {' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' '}, {' ',' ',' ',' ',' ',' ','*',' ',' ',' ',' ',' ',' ',' ',' '}, {' ',' ',' ',' ',' ','*',' ',' ',' ',' ',' ',' ',' ',' ',' '}, {' ',' ',' ',' ',' ','*',' ',' ',' ',' ',' ',' ',' ',' ',' '}, {' ','*','*','*',' ','*',' ',' ',' ',' ',' ','*','*','*','*'}, {' ',' ',' ',' ',' ','*',' ',' ',' ',' ',' ',' ',' ',' ',' '}, {' ',' ',' ',' ',' ','*',' ',' ',' ',' ',' ',' ',' ',' ','e'}};

Program çalıştırıldığında çıkış yollarını yazdırmaya başlar, ancak sonlanmaz çünkü çıkış yolları oldukça fazladır. Birkaç yol çıktısı aşağıda verilmiştir:

Found path to the exit: DRDLDRRURUURRDLDRRURURRRDLLDLDRRURRURRURDDLLDLLDLLLDRRDLDRDRRURDRR Found path to the exit: DRDLDRRURUURRDLDRRURURRRDLLDLDRRURRURRURDDLLDLLDLLLDRRDLDRDRRRURRD Found path to the exit: DRDLDRRURUURRDLDRRURURRRDLLDLDRRURRURRURDDLLDLLDLLLDRRDLDRDRRRURDR …

Şimdi, son bir örnek için programı çalıştıralım:

Örnek girdi (çıkışı olmayan 15 x 9 labirenti):

static char[,] lab = { {' ','*',' ',' ',' ',' ','*',' ',' ',' ',' ','*','*',' ',' '}, {' ',' ','*',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' '}, {' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' '}, {' ',' ',' ',' ',' ',' ','*',' ',' ',' ',' ',' ',' ',' ',' '}, {' ',' ',' ',' ',' ','*',' ',' ',' ',' ',' ',' ',' ',' ',' '}, {' ',' ',' ',' ',' ','*',' ',' ',' ',' ',' ',' ',' ',' ',' '}, {' ','*','*','*',' ','*',' ',' ',' ',' ',' ','*','*','*','*'}, {' ',' ',' ',' ',' ','*',' ',' ',' ',' ',' ','*','*',' ',' '}, {' ',' ',' ',' ',' ','*',' ',' ',' ',' ',' ',' ',' ','*','e'}, };

Program çalıştırıldığında çıktı yazdırmadan kilitleniyor. Çok uzun zamandır çalıştığı için sorun olabilir.

Sorun nedir? Ortalama boyutu 20 olan bir labirent için 4 kere özyinelemeli çağrı vardır. Bunun anlamı 420 kere özyineleme çağrılır. Bu da programın aramasını tamamlayıp sonlanması için oldukça büyük bir rakamdır. Belki sayılar tam kesinlikte değildir, ancak programın çalışma zamanı hakkında bize bir fikir veriyor.

Bu sorun labirentin tüm çıkış yollarını bulma problemi için geçerlidir. Çalışma zamanı sorununu çözmek için daha fazla enerji tüketmenizi istemeyeceğiz. Ancak şunu belirtmekte fayda vardır ki, problem tanımımızı çok az değiştirerek, yani örneğin sadece bir yol bulunmasını isteyerek, çalışma zamanı sorunundan sizi kurtarabiliriz. Programda geri dönülen yollar için özyinelemenin mevcut geçerli pozisyonunu serbest bırakmayarak bu değişikliği gerçekleştirebiliriz.

// Mark back the current cell as free lab[row, col] = ' ';

Bunun için yukarıdaki satır silinmelidir. Bunun sonrasında program çıkış olup olmadığına karar verir ve varsa onu çabucak bulur. Kısa ya da uzun farketmez, sadece ilk yolu muhakkak bulacaktır.