10.10 Özyineleme Kullanımı – Sonuçlar
Labirentin çıkış yollarının aranması probleminden çıkarılan genel sonuç hali hazırda ifade edilebilir: Eğer özyinelemenin nasıl çalıştığını çok iyi anlamakta güçlük yaşıyorsanız, kullanmayınız!
Özyinelemeli metotları yazarken dikkatli olunuz. Özyineleme en çok kombinasyon problemlerini çözmek için elverişli güçlü bir programlama tekniğidir; fakat yanlışlara neden olunabilir ve dikkatsiz kullanma nedeniyle herkese önerilmez. Programın sonlanamaması ve yığın taşmasına neden olması durumlarında, yinelemeli yaklaşımlarla probleme bir çözüm geliştirmeye, problemin tanımı analiz edildikten sonra karar verilmelidir.
Örneğin, labirentte en kısa çıkış yolunu bulmak ile tanımlı problemi analiz ederseniz özyineleme kullanmadan, sadece (BFS) Breadth-First Search yardımıyla çözebilirsiniz. Kuyruk (queue) veri yapısı ile uygulamaları bulunan "BFS" algoritması Wavefront algoritması olarak bilinir. Daha fazla okumanız için başvuru yapılması önerilen link: http://en.wikipedia.org/wiki/Breadth-first_search.
10.11 Alıştırmalar
-
n iç içe döngüyü simüle eden bir program geliştirin.
-
k sınıfından n eleman için tüm çeşitlemeleri tekrarlarıyla listeleyen bir özyinelemeli program geliştirin. Örnek girdi:
-
Çıktısı:
-
(1 1), (1 2), (1 3), (2 1), (2 2), (2 3), (3 1), (3 2), (3 3)
|
Aynı görev için yinelemeli algoritma uygulayın.
-
n elemanlı bir küme içinden k elemanlı tüm kombinasyonları tekrarlarıyla listeleyen bir özyinelemeli program geliştirin. Örnek girdi:
-
Çıktısı:
-
(1 1), (1 2), (1 3), (2 2), (2 3), (3 3)
|
Aynı görev için yinelemeli algoritma uygulayın.
-
Verilen bir sözcük dizisi ve k değeri için, sözcük dizisinin k elemanlı tüm öz alt kümelerini listeleyen özyinelemeli program geliştirin. Örnek girdi:
-
strings = {'test', 'rock', 'fun'}
k = 2
|
Çıktısı:
-
(test rock), (test fun), (rock fun)
|
Aynı görev için yinelemeli bir algoritma uygulayın.
-
Verilen bir sözcük dizisi için, sözcük dizisinin tüm alt kümelerini listeleyen özyinelemeli program geliştirin. Örnek girdi:
-
strings = {'test', 'rock', 'fun'}
k = 2
|
Çıktısı:
-
(), (test), (rock), (fun), (test rock), (test fun),
(rock fun), (test rock fun)
|
Aynı görev için yinelemeli algoritma uygulayın.
-
Birleştirme-sıralama (merge-sort) algoritmasını özyinelemeli uygulayın. Bu algoritmaya girdi olarak verilen bir dizi önce iki eşit parçaya bölünür ve özyinelemeli olarak sıralanır. Sonrasında sıralanan parçalar bütün diziyi oluşturmak üzere birleştirilir.
-
Verilen bir n tamsayısı için 1, 2, …, n sayılarının tüm permütasyonlarını listeleyen özyinelemeli program geliştirin. Örnek girdi:
-
Çıktısı:
-
(1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), (3, 2, 1)
|
Aynı görev için yinelemeli algoritma uygulayın.
-
Verilen bir tamsayı dizisi ve N sayısı için, dizideki sayıların toplamı N olan tüm alt kümelerini bulan özyinelemeli program geliştirin. Örneğin {2, 1 , 3 , -1} dizisi ve N=4 için, toplamı N=4 olan sayılar şöyle elde edilir: 4=2+3-1; 4=3+1.
-
Verilen bir pozitif tamsayı dizisi için, elemanları toplamı S olan herhangi bir alt kümesinin olup olmadığını hesaplayan bir program geliştirin. Büyük diziler için program verimli çalışabilir mi?
-
Verilen iki pozisyon için, geçerli ve geçersiz kapıları olan bir labirent üzerinde iki pozisyon arasında bulunan tüm yolları hesaplayan bir program geliştirin.
-
Labirentin en kısa yolunu bulmak için BFS (breadth-first search) algoritmasını uygulayan bir program geliştirin.
-
İki pozisyon arasındaki tüm yolları hesaplayan bir önceki alıştırmada istenen programı iki pozisyon arasında bir yol olup olmadığını kontrol edecek şekilde değiştirin.
-
Geçerli ve geçersiz kapıları olan verilen bir labirent için tek doğrultuda yol dönüş yapmaksızın, başka tarafa sapmaksızın, komşu ve ardışık pozisyonlardan oluşan en büyük alanı hesaplayan program geliştirin.
-
C:\ hard diski içindeki tüm klasör ve dosyaları ziyaret eden ve özyinelemeli listeleyen bir program geliştirin.
Dostları ilə paylaş: |
