Tüm Sorularımız
Soruda bizden kısaca matrisin sol üst köşesinden, sağ alt köşesine en fazla sayıda çiçek toplayarak gitmemizi istiyordu.
Her adımda yolu kısaltarak gidiyor denmesi ile de her adımda aşağı veya sağa gitmesi sağlanıyordu Abidin’in.
Matriste herhangi bir (x,y) elemanından (N,M) e giderken toplanabilecek olan maksimum çiçek sayısı f(x,y) olsun.
Sadece sağa ve aşağı gidilebildiğinden (x,y) den sadece (x,y+1) e ve (x+1,y) ‘ye erişim vardır.
f(x,y) = matris[x][y] + max ( f(x,y+1) , f(x+1,y) ) şeklinde fonksiyonu ifade edebiliriz.
Base caselerimiz (x>N veya y>M) ise f(x,y)=0.
Çoğu programlama dillerinde bu fonksiyonu implement ettiğimizde exponential sürede sonlanacaktır çünkü her aşamada fonksiyon 2’ye dallanıyor.
Baktığımızda f(x,y) asla kendisini çağırmıyor, her seferinde ya x ya da y azalıyor. Bu özelliği kullanarak herhangi bir aşamada f(x,y) ‘yi hesapladığımızda, hesaplanmış olarak işaretleyip, eğer bir fonksiyon hesaplanmış olarak işaretlenmişse, önceki hesaplanmış değerini kullanırsak sadece N*M fonksiyon hesaplayarak sonuca ulaşabiliriz.
Complexity exponential’dan O(N*M)’e düştü.
Bu yöntem bilgisayar bilimi camiyasında Dynamic Programming olarak adlandırılmış olup, birçok soruda ve problemde karşılaşılmakta/kullanılmaktadır. Eğer mümkünse hesaplanan bir değerin tekrar hesaplanmayıp kullanılmasına denir.
Küçük bir örnek vermek gerekirse fibonnaci sayılarını f(x)=f(x-1)+f(x-2) şeklinde direkt olarak hesaplarsak complexity si O(2^N) olacaktır, fakat O(N)’de hesaplanabilmektedir. Her fibonnaci yi hesapladığımızda değeri kaydedersek, aynı fonksiyon ile O(N)’de hesaplayabiliriz.
Yollanan çözümler arasında bu yöntemi başarılı bir şekilde uygulayan Lütfi Altın’ı tebrik ediyoruz. Çözüm yollayan diğer arkadaşlarımızı da kutluyoruz. Kendisi aynı yöntemi recursive kodlamak yerine iteratif olarak kodlamıştır. Recursive versiyonundan daha hızlı çalışmaktadır. Kendinin çözümüne bu bağlantıyı takip ederek ulaşabilirsiniz. Ayrıca, çalıştırıldığında çözüm ve input üreten deneme koduna ise, bu bağlantıyı takip ederek ulaşabilirsiniz.
Çözüm yollayan arkadaşlarımıza tekrardan teşekkür ediyoruz ve Nisan ayı programlama sorumuza geçiyoruz. Pdf versiyonuna bu bağlantıyı takip ederek ulaşabilirsiniz. Sorumuz aşağıda açıklanmıştır.
Abidin bir altyapı firmasında amelelik yapmaktadır. On senedir bu firmada çalıştığından artık bir terfiyi hak ettiğini düşünmektedir.
Bu firmanın görevi bir noktadan diğerine su taşımaktır. Fakat yüksek taşıma kapasiteli borular pahalı olduğundan bu firma düşük kapasiteli boruları birbirine bağlayarak amacına ulaşmaktadır. Bazen binlerce boruyu, değişik şekillerde birleştirerek hedeflerine ulaşmaktadırlar. Bir örnek vermek gerekirse:
A noktasından B noktasına su aktarılmaktadır. Firma C ve D noktalarında boruları birleştirmiştir. 5 boru vardır:
A dan C’ye 3 kapasiteli
A dan D’ye 2 kapasiteli
C den D’ye 5 kapasiteli
C den B’ye 2 kapasiteli
D den B’ye 3 kapasiteli
A dan verilen su C ve D’ye doğru 2 ye ayrılmıştır. C den B’ye doğru 2 kapasiteli borudan 2 miktar su aktarılabilmiştir fakat 1 miktar su artmıştır. O 1 miktar su D noktasında A’dan gelen 2 miktar su ile birleşerek B ye akmıştır. Sonuç olarak sistemin kapasitesi 5’dir.
C den D’ye olan 5 kapasiteli borudan sadece 1 miktar su geçmektedir.
Abidin’in çalıştığı firmada bir sistemin kapasitesini belirlemek çok zaman almaktadır. Toplanıp uzun süreler bunu hesaplamaya çalışmaktadırlar. Eğer Abidin verilen bir sistemin kapasitesini hesaplayan bir program bulabilirse istediği terfiye sonunda kavuşacağını düşünmektedir.
Sizden istenen verilen bir boru sisteminden geçebilecek maksimum su miktarını bulmanız.
4 5
1 2 3
1 3 2
2 3 5
2 4 2
3 4 3
(Örnekte verilen sistem, A:1 C:2 D:3 B:4 numaralıdır.)
5
Bu derginin içeriği, Creative Commons lisansı ile korunmaktadır.
Kaynak göstermek ve link vermek şartıyla ticari olmayan amaçlarla yazılarımızı kullanabilirsiniz.
©2007-2008 ODTÜ Bilgisayar Topluluğu