Polito DSA çalışırken recursion kodunu okuyabiliyor ama çağrı döndüğünde hangi bilginin kaldığını açıklayamıyor musunuz? Backtracking'de de sorun çoğu zaman aynı noktada büyür: bir seçenek denenir, fakat sonraki seçenek önceki denemenin değiştirdiği veriyi yanlışlıkla kullanır. Sağlam çözüm, recursive satırı ezberlemekten önce küçülen problemi ve geri dönüş sözleşmesini tanımlamaktır.
Bu rehber üç özgün, bağımsız C17 programı içerir: sıralı array'de recursive lower_bound, farklı kişilere farklı görev atama ve yan yana iki 1 içermeyen bit dizilerini sayma. Amaç sadece doğru sonuca ulaşmak değil; taban durumunu, korunan kuralı, durma gerekçesini ve bütün dönüşlerde geri alınan değişiklikleri açıklamaktır.
Ders bağlamı: 'da kontrol edilen 01URN Algorithms and Data Structures 2026/27 resmî kılavuzu, recursive programming, backtracking, kombinatorik problemler ve karmaşıklık analizini kapsar. Tam ders kodu ve grup ayrımı için güncel Polito DSA rehberini kullanın. Aşağıdaki görevler bağımsız alıştırmalardır; resmî sınav soruları, teslim çözümleri veya evrensel sınav kuralları değildir.
1. Önce küçülen problemi ve taban durumunu yazın
Recursive fonksiyon için dört cümle hazırlayın: bu çağrı hangi alt problemi çözüyor, girişte hangi kural doğru, bir sonraki çağrıda ne küçülüyor ve çağrı hangi sonucu bırakıyor? “Fonksiyon kendini çağırıyor” cevabı yeterli değildir. Aynı büyüklükteki probleme yeniden çağrı yapmak, bir taban durumu yazmış olsanız bile oraya ulaşmayı garanti etmez.
İlk örnekte küçülen ölçü aralığın uzunluğu; atama probleminde henüz görev verilmemiş kişi sayısı; bit dizisinde doldurulmamış konum sayısıdır. Bunlar negatif olamayan ve her recursive adımda azalan sayılardır. Backtracking'de seçenek sayısı artabilir fakat tek bir çağrı yolu boyunca kalan problem yine küçülmelidir.
Bir de nesneleri ayırın: parametreler ve kaydedilen eski değerler çağrının yerel bilgisidir; used veya bits gibi array'ler ortak çalışma alanıdır. Çağrının bitmesi, bu array'lere yazılan değerleri otomatik geri almaz. Her fonksiyonun hangi veriyi değiştirdiğini ve dönüşte hangisini eski hâliyle bıraktığını açıkça belirleyin.
2. Recursive lower_bound ile yarı açık aralığı koruyun
Sıralı bir array'de hedefe eşit veya hedeften büyük ilk elemanın konumunu arayalım. Böyle bir eleman yoksa sonuç n olur. Bu, “hedef bulundu mu?” sorusuyla aynı değildir: 6 veride bulunmasa da yerleştirilebileceği ilk uygun konum döner. Yinelenen değerlerde ilk eşit elemanı istiyoruz.
Arama alanı [lo, hi): lo dahil, hi hariçtir. Girdi ilk n elemanda azalmayan sırada olmalıdır; fonksiyon sıralılığı denetlemez. En fazla 1024 okunabilir eleman kabul edilir. position geçerli, ayrı bir çıktı nesnesi olmalıdır. Boş girdide values = NULL geçerli; sonuç sıfırdır.
#include <stdbool.h>#include <stddef.h>#include <stdio.h>enum { LOWER_BOUND_MAX = 1024 };static size_t lower_bound_range(const int values[], size_t lo, size_t hi, int target){ if (lo == hi) { return lo; } size_t mid = lo + (hi - lo) / 2; if (values[mid] < target) { return lower_bound_range(values, mid + 1, hi, target); } return lower_bound_range(values, lo, mid, target);}bool lower_bound_bounded(const int values[], size_t n, int target, size_t *position){ if (position == NULL || n > LOWER_BOUND_MAX || (n > 0 && values == NULL)) { return false; } *position = lower_bound_range(values, 0, n, target); return true;}int main(void){ const int values[] = {2, 4, 4, 7, 9}; size_t n = sizeof values / sizeof values[0]; size_t positions[4]; if (!lower_bound_bounded(values, n, 4, &positions[0]) || !lower_bound_bounded(values, n, 6, &positions[1]) || !lower_bound_bounded(values, n, 10, &positions[2]) || !lower_bound_bounded(NULL, 0, 7, &positions[3])) { return 1; } printf("%zu %zu %zu %zu\n", positions[0], positions[1], positions[2], positions[3]); return 0;}Program 1 3 5 0 yazdırır. Hedef 4 için ilk eşit değer indeks birde; 6 için ilk büyük değer indeks üçte; 10 için uygun eleman yoktur. Sonuç n olabilir; bu değeri array indeksi olarak kullanmadan önce sınayın. NULL/uzunluk ön kontrolü başarısız olduğunda fonksiyon false döndürür ve mevcut çıktı değerini korur. Bu kontrol, sarkan pointer'ı veya yanlış bildirilen nesne boyutunu tespit etmez.
3. Çağrı yolunu dönüş değerinden ayrı izleyin
Hedef dört için aralıklar [0,5), [0,2), [0,1) ve [1,1) olur. Son çağrı boş aralıkta biri döndürür; önceki çağrılar bu sonucu geri taşır. Başlangıç ve bitişin hangi dala ait olduğunu her adımda yazın. Eşit değer gördüğümüzde sol aralığa gitmemizin nedeni ilk uygun konumu aramamızdır.
Korunan kural şudur: lo öncesindeki elemanlar hedeften küçük, hi ve sonrasındakiler uygun adaydır. Orta eleman küçükse onu da dışarıda bırakırız; diğer durumda orta konumu aday sınırı olarak koruruz. lo + (hi - lo) / 2, geçerli aralıkta başlangıç ve bitişi doğrudan toplayarak taşma oluşturmaz. Boş aralık kontrolü herhangi bir eleman okumadan önce gelir.
1024 elemanlık sınırda en uzun yol 11 karşılaştırma ve taban çağrısıyla 12 mantıksal fonksiyon çerçevesidir. Bu bir arama ağacının tamamında 1024 çağrı yapılacağı anlamına gelmez: her adım yalnız bir alt problem seçer. Derleyicinin tail-call optimizasyonu yapacağını varsayarak girdi sınırını kaldırmayın; burada sınır ve durma gerekçesi birlikte tasarlanmıştır.
4. Backtracking için seç, çağır, geri al sözleşmesi kurun
Şimdi bir dal başarısız olduğunda başka bir seçenek denememiz gerekecek. Backtracking, aday seçme, daha küçük problemde arama ve seçimi geri alma düzenidir. Kısmi çözümün kurallarını baştan korursanız, geçersiz bir dalı tamamlanmasını beklemeden kapatabilirsiniz. Bunun için hangi koşulun gerçekten devam etmeyi imkânsızlaştırdığını bilmelisiniz.
Dönüş sözleşmesini güçlü tutalım: used ve current, fonksiyonun girişindeki hâline dönecek; bulunan cevap ayrı solution alanına kopyalanacak. “Cevap bulundu, hemen dön” kısayolu da bu sözleşmeye uymalıdır. Geri alma adımından önce dönerseniz çıktı doğru görünürken çağıranın çalışma verisi bozulabilir.
5. Farklı kişilere farklı görev atayın
Üç kişiye, izin tablosuna göre üç farklı görev verelim. allowed[person][task] seçimin izinli olduğunu; used[task] görevin kullanılamadığını belirtir. Adayları artan görev sırasıyla deneriz ve ilk tam atamada dururuz. “İlk” burada bu arama sırasındaki çözümdür; en iyi veya en düşük maliyetli atama değildir.
#include <stdbool.h>#include <stddef.h>#include <stdio.h>enum { MAX_TASKS = 4 };static bool assign_next(const bool allowed[][MAX_TASKS], size_t n, size_t person, bool used[], size_t current[], size_t solution[]){ if (person == n) { for (size_t i = 0; i < n; ++i) { solution[i] = current[i]; } return true; } for (size_t task = 0; task < n; ++task) { if (!allowed[person][task] || used[task]) { continue; } size_t saved = current[person]; used[task] = true; current[person] = task; bool found = assign_next(allowed, n, person + 1, used, current, solution); current[person] = saved; used[task] = false; if (found) { return true; } } return false;}bool find_assignment(const bool allowed[][MAX_TASKS], size_t n, bool used[], size_t current[], size_t solution[], size_t capacity){ if (n == 0) { return true; } if (n > MAX_TASKS || capacity < n || allowed == NULL || used == NULL || current == NULL || solution == NULL) { return false; } return assign_next(allowed, n, 0, used, current, solution);}int main(void){ const bool allowed[3][MAX_TASKS] = { {true, true, false, false}, {true, false, false, false}, {false, true, true, false} }; bool used[MAX_TASKS] = {false}; size_t current[MAX_TASKS] = {99, 99, 99, 99}; size_t solution[MAX_TASKS] = {99, 99, 99, 99}; if (!find_assignment(allowed, 3, used, current, solution, MAX_TASKS)) { return 1; } printf("%zu %zu %zu | %d %zu\n", solution[0], solution[1], solution[2], used[0], current[0]); return 0;}Çıktı 1 0 2 | 0 99'dur. İzin tablosunda ilk n satırın her biri dört sütun taşır. n en fazla dört olabilir; ortak kapasite en az n olmalı, üç çalışma/çıktı array'i de gerçekten o kadar erişilebilir eleman sağlamalıdır. used ve current ilk n elemanda başlatılmış olmalıdır: geri yüklemek için eski değerleri de okuyoruz. Girdi ve bu nesneler birbirleriyle çakışmamalıdır. Bildirilen kapasite, yanlış oluşturulmuş nesneyi kendiliğinden güvenli yapmaz.
Sıfır kişide boş atama vardır: bütün array pointer'ları NULL ve kapasite sıfır olabilir, hiçbir nesneye erişilmez. Pozitif boyutta gerekli pointer'lar geçerli olmalıdır. Baştan true olan bayraklar kapalı görevleri temsil eder ve korunur; ilk n görev arasında böyle bir bayrak varsa bu n-kişilik/n-görevlik model tam atama bulamaz. Bu geçerli fakat çözümsüz bir girdidir.
6. Başarısız dalda ve erken başarıda aynı undo kuralını uygulayın
İlk kişi önce görev sıfırı dener. İkinci kişinin tek izinli görevi de sıfır olduğundan bu dal kapanır. İlk seçimi geri alıp görev biri denediğimizde ikinci kişi sıfırı, üçüncü kişi ikiyi alabilir. Çözüm 1,0,2 ayrı alana kopyalanır; geri dönerken her çağrı kendi yaptığı değişikliği kaldırır.
current[person] için kaydedilen eski değeri geri yazarız. Seçilen görevin bayrağı girişte false olduğu için onu tekrar false yaparız. Önceden true olan başka bayrağa dokunmayız. Kodda if (found) kontrolünün geri alma satırlarından sonra gelmesi önemlidir: erken başarı, cleanup'ı atlamak için izin değildir.
Sadece cevabı sınamayın. Başarıda ve çözümsüz aramada bütün used/current elemanlarını ilk hâliyle karşılaştırın; başarısızlıkta eski solution da değişmemelidir. Aynı çalışma alanıyla ikinci aramayı başlatın. İlk çalışmadan kalan bir işaret ikinci sonucu değiştiriyorsa ortak durumun geri dönüş sözleşmesi bozulmuştur.
7. Yan yana iki 1 içermeyen bit dizilerini sayın
Uzunluğu dört olan sekiz uygun dizi vardır: 0000, 0001, 0010, 0100, 0101, 1000, 1001, 1010. Her konumda sıfırı deneyebiliriz; bir seçmek için önceki konumun bir olmaması gerekir. Yalnız yerleştirdiğimiz prefix incelenir. Tamponun henüz kullanılmayan bölümündeki başlangıç değerleri kararları etkilememelidir.
#include <stdbool.h>#include <stddef.h>#include <stdio.h>enum { MAX_BITS = 12 };static bool count_prefix(unsigned char bits[], size_t n, size_t position, size_t limit, size_t *total){ if (position == n) { if (*total == limit) { return false; } ++*total; return true; } for (unsigned char bit = 0; bit <= 1; ++bit) { if (bit == 1 && position > 0 && bits[position - 1] == 1) { continue; } unsigned char saved = bits[position]; bits[position] = bit; bool ok = count_prefix(bits, n, position + 1, limit, total); bits[position] = saved; if (!ok) { return false; } } return true;}bool count_binary_sequences(unsigned char bits[], size_t capacity, size_t n, size_t limit, size_t *count){ if (count == NULL || n > MAX_BITS || capacity < n || (n > 0 && bits == NULL)) { return false; } size_t total = 0; if (!count_prefix(bits, n, 0, limit, &total)) { return false; } *count = total; return true;}int main(void){ unsigned char bits[] = {9, 9, 9, 9}; size_t count = 999; if (!count_binary_sequences(bits, sizeof bits, 4, 1000, &count)) { return 1; } printf("%zu | %u %u %u %u\n", count, (unsigned)bits[0], (unsigned)bits[1], (unsigned)bits[2], (unsigned)bits[3]); return 0;}Program 8 | 9 9 9 9 yazdırır: uygun diziler sayıldı, çalışma tamponu tamamen geri yüklendi. Tampon bir C string'i değil, unsigned char elemanlarıdır; sonlandırıcı istemiyoruz. Kapasite en az n, uzunluk en fazla 12 olmalı; geri alınacak ilk n eleman başlatılmış olmalıdır. Sıfır uzunlukta tek boş dizi vardır; bits = NULL ve kapasite sıfırla, limit en az birse sonuç birdir. Limit sıfırsa boş dizinin sayımı bile başarısız olur ve çıktı korunur.
limit, sayımın kabul edilen üst sınırıdır. Sekiz sonuç için limit sekiz yeterli, yedi yetersizdir. Artırmadan önce sınır kontrol edilir; bu düzen limit türün en büyük değeri olsa bile taşmayı önler. Limit aşılırsa veya girdi geçersizse count değişmez. Çalışma tamponu ve çıktı ayrı nesneler olmalıdır; tüm başarısız dönüşler de yapılan seçimi geri alır.
8. Pruning, çağrı derinliği ve toplam maliyeti ayırın
Yan yana birler oluştuğunda dalı erken kapatmak güvenlidir: daha fazla bit eklemek mevcut ihlali düzeltemez. Buna pruning denir. Rastgele “bu dal uzun görünüyor” diye durmak aynı şey değildir; geçerli çözümleri kaybedebilir. Bit programının 12 sınırı en fazla 13, atama programının dört sınırı en fazla beş mantıksal açık çerçeve verir.
Genellenmiş lower_bound modelinde süre ve mantıksal çağrı derinliği O(log(n+1)) üst sınırındadır. Atamada farklı görev seçimleri geniş bir arama ağacı oluşturabilir. Genel n-boyutlu modelde k düzeyinde farklı görev prefix'leri ve her iç çağrıda en fazla n aday kontrolü, kaba O(n · n!) üst sınırı verir. İlk çözümde durmak bazı girdileri hızlandırır, her girdiyi ucuz yapmaz. Örneğimiz bilinçli olarak n'i dörtle sınırlar.
Bit dizilerinin sayısı A(0)=1, A(1)=2 ve A(n)=A(n-1)+A(n-2) kuralını izler. Pruning olsa da tüm uygun yaprakları saymak üstel büyür; O(n) derinlik, O(n) toplam süre demek değildir. Yalnız sayım gereken problemde aynı sayıları iterative bir recurrence ile hesaplayabilirsiniz; burada amaç arama ve undo'yu öğrenmektir. Bütün dizileri yazdırırsanız çıktı üretme maliyetini de ekleyin.
9. Bağımsız testleri kendi çözümünüzün kanıtı yapın
Lower_bound'u küçük sıralı array'lerde düz tarama sonucu ile karşılaştırın: boş, tek elemanlı, yinelenen değerli ve hedefin tüm elemanlardan küçük/büyük olduğu girdiler olsun. Atamada küçük izin tablolarını bütün görev permütasyonlarını deneyen ayrı bir yöntemle sınayın. Bit dizilerinde bütün küçük bitmask'leri sayıp yan yana bir içerip içermediğini kontrol edin. Test oracle'ı aynı recursive hatayı kopyalamamalıdır.
Kapasitenin bir eksik olduğu çağrıyı, derinlik sınırının hemen üstünü ve sayım limitinin bir eksik/eşit olduğu durumları ekleyin. Her durumda dönüş değerini, çıktıyı ve değişmemesi gereken çalışma alanını karşılaştırın. Üç dosyayı ayrı derleyin: cc -std=c17 -Wall -Wextra -Wpedantic recursive_lower_bound.c -o recursive_lower_bound. Derleyici uyarılarının olmaması bütün girdileri ispatlamaz; yürütülen testleri ve sözleşmeyi birlikte değerlendirin.
10. Polito DSA'da sonraki adımı hatanıza göre seçin
Recursion Lab rehberindeki çağrı/dönüş gözlem yaklaşımını bir soruyla kullanın: hangi çerçeve bekliyor, hangi değişiklik geri alınmalı? Buradaki üç programın Lab'de hazır bulunduğunu veya oraya yapıştırılıp çalıştırılabildiğini iddia etmiyoruz. Bağımsız C derleyicisi ve kendi testleriniz gerekir; araçların genel girişi Academy Lab sayfasıdır.
Çağrı sonucu karışıyorsa küçük arama trace'ine; durum kirleniyorsa başarı ve başarısızlık sonrası undo testine; süre yorumu yanlışsa ağaç genişliği ile derinlik ayrımına dönün. Ders kodunuz ve hata kaydınızla Polito DSA özel ders sürecini inceleyebilirsiniz. Daha geniş düzen için 12 haftalık çalışma planı ve Polito ders merkezi yol gösterir.
C fonksiyon çağrıları, array erişimi ve nesne yaşam süresi için WG14 N1570 C11 komite taslağının 6.5.2.2, 6.5.2.1 ve 6.2.4 bölümlerine bakabilirsiniz. Bu kamuya açık taslak güncel nihai C standardı olarak sunulmuyor; örneklerimizin derleme hedefi C17'dir.
Websoftik Academy, Politecnico di Torino'dan bağımsızdır. Güncel sınav kuralları için kendi grubunuzun duyuruları esas alınır. Bu özgün alıştırmalar başarı garantisi vermez; değerlendirilecek ödev veya sınav öğrenci yerine çözülmez.
