Recursion veri yapılarındaki en zor konu mu?

4 yıl

Er

Konu Sahibi

Herkese merhaba, uzun süredir veri yapılarıyla uğraşıyorum ancak recursion konusunda fena tosladım. Soruyu çözmek için kendi kurduğum recursive fonksiyonlar eğitmenin kurduklarının yanında 1+1 gibi kalıyor. Ancak sorun bu da değil sorun şu ki: ben eğitmenin yaptığı algoritmayı anlamak için kağıt kalemle sayfalarca adım adım anlamaya çalışıyorum ki bu saatlerimi almakla beraber psikolojimi bozuyor, üstüne anladıktan sonra da "ulan ben hayatta bu kadar soyut düşünüp onlarca adım sonrasını düşünemezdim" diyerek öz güven kaybı yaşıyorum. İstatistik dersleri görücektim ancak şu konu yüzünden malesef bırakamıyorum veri yapıları çalışmayı adeta takıntı oldu. Bir de dediğim gibi bir algoritmayı çözmek için sayfalarca adım adım kalemle hesaplamak gerektiği için çok çok fazla zamanımı alıyor. Ne yapmam lazım bu durumda? Misal verilen bir sayıya verilen bir listedeki sayıları kullanarak en az kaç adımda ulaşabiliriz sorusunun çözümünü böyle vermiş(Listenin küçükten büyüğe değil de karışık olarak verildiği sorunları da çözmeli ayrıca listedeki elemanları küçükten büyüğe (sort()) sıralamak gibi bir trick de yasak) Şahsen bu algoritmayı hayatta kuramazdım ben:

def rec_coin(target,coins,known_results):
    min_coins = target

    if target in coins:
        known_results[target] = 1
        return 1
    elif known_results[target]>0:
        return known_results[target]
    else:

        for i in [c for c in coins if c<=target]:

            num_coins = 1+ rec_coin(target-i,coins,known_results)

            if num_coins < min_coins:
                min_coins = num_coins
                known_results[target] = min_coins
    return min_coins
target = 14
coins = [1,3,5]
known_results = [0]*(target+1)
print(rec_coin(target,coins,known_results))

DH forumlarında vakit geçirmekten keyif alıyor gibisin ancak giriş yapmadığını görüyoruz.

Üye olduğunda özel mesaj gönderebilir, beğendiğin konuları favorilerine ekleyip takibe alabilir ve daha önce gezdiğin konulara hızlıca erişebilirsin.

Üye Ol Şimdi Değil

Bir Daha Gösterme

< Bu mesaj bu kişi tarafından değiştirildi Guest-33247115E -- 21 Haziran 2021; 21:14:44 >

K

Kurtçu Restrop

4 yıl

Yüzbaşı

pseudo code yazmanın ve grafiğe dökmenin önemi burda çıkıyor aslında. onlarca adım sonrasını kimse göremez zaten. fakat grafiğe döktüğünde eksik olan şeyi göreceksin. recursion kısmı tekrar edecek zaten sürekli. matematikteki modüler aritmetikti sanırım ismi onlar gibi kuralı bulduktan sonra yazması da kolay

< Bu ileti iOS uygulamasından atıldı > Bu mesaja 1 cevap geldi.

G

Guest-33247115E

4 yıl

Er

Konu Sahibi

quote:

Orijinalden alıntı: Kurtçu Restrop

pseudo code yazmanın ve grafiğe dökmenin önemi burda çıkıyor aslında. onlarca adım sonrasını kimse göremez zaten. fakat grafiğe döktüğünde eksik olan şeyi göreceksin. recursion kısmı tekrar edecek zaten sürekli. matematikteki modüler aritmetikti sanırım ismi onlar gibi kuralı bulduktan sonra yazması da kolay

Anladım teşekkürler, sana da kolay gelsin yksde:)

Bu mesaja 1 cevap geldi.

K

Kurtçu Restrop

4 yıl

Yüzbaşı

ben de teşekkür ederim bazı şeyleri geride bırakmak gerekiyor

< Bu ileti iOS uygulamasından atıldı > Bu mesaja 1 cevap geldi.

Bu mesajda bahsedilenler: @WhoThisGuy

G

Guest-33247115E

4 yıl

Er

Konu Sahibi

quote:

Orijinalden alıntı: Kurtçu Restrop

ben de teşekkür ederim bazı şeyleri geride bırakmak gerekiyor

HAHAHA, mizaç olarak sen de ben de biraz sertiz sanırım. Yani herhangi bir tartışmada genelde aksini söyleyen taraf olma eğilimi gösteriyoruz, o yüzden geçmişte biraz sürtüşmüş olmamız normal yani :D Yazılımda acemiliğimin yüzüme vurulması sana karşı biraz sert olmama sebep oldu, o yüzden hakkını helal et :) Geçen konunu gördüm ayt mat hakkında, umarım sınavda fullersin :)

T

Tuğkan-0153

4 yıl

Yarbay

Kodu bir deneyim dedim de şöyle gıcık bi hata verdi. Python boşluk/sekme kullandığı için kodu SS ile göndermen gerekli. Bu arada Recursion ile veri yapıları arasında bağlantı yok. Hash, hashmap, associative array gibi veri yapıları 1960'larda geliştirilmeye başlanmış, recursion 1950'lerde vardı, bilg programlama dilleri ortaya cıkmadan yıllar önce de matematikte vardı.

< Resime gitmek için tıklayın >

< Bu ileti mini sürüm kullanılarak atıldı > Bu mesaja 1 cevap geldi.

G

Guest-33247115E

4 yıl

Er

Konu Sahibi

quote:

Orijinalden alıntı: Tuğkan-0153

Kodu bir deneyim dedim de şöyle gıcık bi hata verdi. Python boşluk/sekme kullandığı için kodu SS ile göndermen gerekli. Bu arada Recursion ile veri yapıları arasında bağlantı yok. Hash, hashmap, associative array gibi veri yapıları 1960'larda geliştirilmeye başlanmış, recursion 1950'lerde vardı, bilg programlama dilleri ortaya cıkmadan yıllar önce de matematikte vardı.

< Resime gitmek için tıklayın >

Hocam aslında şu "return min_coins" yazan yeri en baştaki "if" ile aynı hizaya getirirseniz sorun çözülür gibi geldi. Bir de recursion'un zaten matematikte var olduğunu az çok biliyordum da veri yapılarıyla ilgili sizin kadar pek bilgim yok, sadece veri yapılarıyla ilgili kurslarda veya kitaplarda yer aldığı için böyle kaldı aklımda. Bu arada eğitmenin çözümünün linkini atayım hem açıklamalı çözmüş daha kolay olur anlaşılması:

https://github.com/jmportilla/Python-for-Algorithms--Data-Structures--and-Interviews/blob/master/Recursion/Recursion%20Interview%20Problems/Recursion%20Problems%20-%20%20SOLUTIONS/Recursion%20Problem%204%20-%20Coin%20Change%20-%20SOLUTION.ipynb

Bu mesaja 1 cevap geldi.

T

Tuğkan-0153

4 yıl

Yarbay

return min_coins fonksiyonun dönüş degeri old için, dediğin gibi if'le aynı hizada olması gerekli fakat öyle yapsam da aynı satır ve aynı yerde yine indentation/tab hatası verdi. şimdi linkteki kodu kopyaladım hata vermedi.

çözümde fonksiyonun recursive olarak çalıştırıldığı satırdaki şu açıklamada
# Recursive call, note how we include the known results!
target-1 kısmını açıklamamış oysa ki en önemli kısımlardan biri cunku o sayede fonksiyon
elif known_results[target] > 0:
return known_results[target]
ile fonksiyon dönme ihtimalini yakalıyor. Bir önceki "base case" dediği kısımda da dönme ihtimali var tabi ki fakat target, coins içinde zaten varsa dönmek için o örnein hedef 5 ise ve coins içinde 5 varsa tabi ki 1 ile dönecek.

Genel olarak bu problem recursion olayını açıklamak açısından kötü seçim gibi görünüyor. Üstüne de yetersiz açıklamalar eklenince, daha da kötü oluyor. Bu konulara yeni başlayan biri olsam ve böyle bi örnekle karşılaşsam herhalde ben de pek anlayamazdım.

< Bu ileti mini sürüm kullanılarak atıldı > Bu mesaja 2 cevap geldi.

Bu mesajda bahsedilenler: @WhoThisGuy

G

Guest-33247115E

4 yıl

Er

Konu Sahibi

quote:

Orijinalden alıntı: Tuğkan-0153

return min_coins fonksiyonun dönüş degeri old için, dediğin gibi if'le aynı hizada olması gerekli fakat öyle yapsam da aynı satır ve aynı yerde yine indentation/tab hatası verdi. şimdi linkteki kodu kopyaladım hata vermedi.

çözümde fonksiyonun recursive olarak çalıştırıldığı satırdaki şu açıklamada
# Recursive call, note how we include the known results!
target-1 kısmını açıklamamış oysa ki en önemli kısımlardan biri cunku o sayede fonksiyon
elif known_results[target] > 0:
return known_results[target]
ile fonksiyon dönme ihtimalini yakalıyor. Bir önceki "base case" dediği kısımda da dönme ihtimali var tabi ki fakat target, coins içinde zaten varsa dönmek için o örnein hedef 5 ise ve coins içinde 5 varsa tabi ki 1 ile dönecek.

Genel olarak bu problem recursion olayını açıklamak açısından kötü seçim gibi görünüyor. Üstüne de yetersiz açıklamalar eklenince, daha da kötü oluyor. Bu konulara yeni başlayan biri olsam ve böyle bi örnekle karşılaşsam herhalde ben de pek anlayamazdım.

Yok hocam bu recursion açıklamasından ziyade bir mülakat sorusuymuş. Her konu sonrası mülakat soruları çözüyor bu da onlardan biriydi sadece. Yetersiz açıklama kısmında bence de haklısınız, anlatımı baya iyi ancak mülakat sorularını açıklamada çok yetersiz. Zaten genelde çözümlerin üzerinde kendiniz çalışın, eğin bükün vs. vs. diyor yani işi öğrenciye atıyor.

< Bu mesaj bu kişi tarafından değiştirildi Guest-33247115E -- 22 Haziran 2021; 3:31:18 >
Bu mesaja 1 cevap geldi.

T

Tuğkan-0153

4 yıl

Yarbay

Programa bu akşam öylesine bakayım dedim. Ufak bir eksik daha buldum "coins" e 2 ekleyerek [1,3,5,2] yaptım. Bu durumda 14 için yine 4 cıkması gerekirken yanlış şekilde 7 buluyor. 2x5 + 2x2 = 14 ile yine 4 çıkarmalı. Hatanın sebebi cunku algoritma coins 'in artan dizi olduğunu varsayıyor. Bunu açıklamaya eklemesi veya coins = sorted([1,5,3]) gibi tanımlaması gerekirdi

Ancak bu eksiklere ragmen program yine de iyi cunku recursion olayını tam olması gerektiği gibi kullanıyor.

Bu program üzerine bir ek soru daha sorulabilir: En az sayıda coin'in toplam adetiyle birlikte 2 adet 5 kuruş, 2 adet 2 kuruş gibi, kendilerini de listeleyiniz. Programı modifiye ederek bunu yapabilir misin :)

< Bu mesaj bu kişi tarafından değiştirildi Tuğkan-0153 -- 24 Haziran 2021; 23:15:9 >

< Bu ileti mini sürüm kullanılarak atıldı > Bu mesaja 1 cevap geldi.

Bu mesajda bahsedilenler: @WhoThisGuy

G

Guest-33247115E

4 yıl

Er

Konu Sahibi

quote:

Orijinalden alıntı: Tuğkan-0153

Programa bu akşam öylesine bakayım dedim. Ufak bir eksik daha buldum "coins" e 2 ekleyerek [1,3,5,2] yaptım. Bu durumda 14 için yine 4 cıkması gerekirken yanlış şekilde 7 buluyor. 2x5 + 2x2 = 14 ile yine 4 çıkarmalı. Hatanın sebebi cunku algoritma coins 'in artan dizi olduğunu varsayıyor. Bunu açıklamaya eklemesi veya coins = sorted([1,5,3]) gibi tanımlaması gerekirdi

Ancak bu eksiklere ragmen program yine de iyi cunku recursion olayını tam olması gerektiği gibi kullanıyor.

Bu program üzerine bir ek soru daha sorulabilir: En az sayıda coin'in toplam adetiyle birlikte 2 adet 5 kuruş, 2 adet 2 kuruş gibi, kendilerini de listeleyiniz. Programı modifiye ederek bunu yapabilir misin :)

Hocam keşke hatırlatmasaydın ya, neyse ki bu sefer durdurdum kendimi. Ben bu kursu bitirmiştim aslında bu algoritmaya da çok fazla zaman ayırmış kıyısından köşesinden anlayıp bırakmıştım. Baya kafayı takmıştım buna bütün günüm buna gidiyordu. Şu an istatistik dersi alıyorum tekrar bu algoritmayla uğraşırsam bütün plan programım dağılacak. Bu arada kodu kopyalayıp yapıştırdım ancak ben böyle bir hata almadım. Aslında bu algoritmanın böyle kurulmasının sebebi zaten coinslerin random bir sırada verildiği koşullarda da düzgün çalışmasıydı hocanın anlattığına göre. Çünkü çözümüne bakmadan önce kendi geliştirdiğim algoritmada basit düşünüp verilen coinsleri artan sıraya dizip "kalan" üzerinden basit işlemlerle halletmiştim, daha sonra çözüme bakınca ve böyle bir şeyle karşılaşıp kendi yaptığım çözümün basitliğine ve algoritmanın güzelliğine ayrıca böyle bir algoritmayı da henüz kuracak potansiyelimin olmadığını fark etmemle moralim bozulmuştu, zaten konuyu açma sebebim buydu. Belki kodla oynarken unuttuğunuz bir değişiklik yapmış olabilirsiniz hocam, isterseniz kodu baştan yapıştırıp bir deneyin ben de sorunsuz çalıştı.

Sonda sorduğunuz soruyu ise (deneyeyim dedim ama denemek için algoritmayı tam olarak baştan iyi anlamak lazım olduğunu fark edip zaman kaybetmeden bıraktım) sanırım başka bir dictionary oluşturup, coins'e göre sayıyı 1 arttırarak, en az sayılan coin'i bastırmak herhalde doğru olurdu ancak şöyle bir sorun olduğunu fark ettim, algoritmada zaten her coin aslında tek tek kullanılıyor, yani her koşul hesaplanıyor zaten o yüzden o dict'i nereye yazmalıyız daha doğrusu işlem sonunda içerisinde sadece kullanılmış coinlerin olduğu bir dict nasıl oluşturulur biraz uğraşmak gerekiyor sanırım :) Demek istediğim [1,2,3,10] listesinde target 12 iken listedeki tüm coinler algoritma içerisinde doğru coini bulmak için kullanılıyor, ancak asıl coinler burada 10 ve 2 oluyor, işlem sonucunda dict içerisinde sadece 10 ve 2'nin olduğu ve bu 2'sinin adet sayısı karşılaştırılıp az olanın yazıldığı bir kod lazım,Onu da yazmak için şu an çalıştığım dersleri bir kenara bırakıp saatlerce bununla uğraşmam lazım ama kalsın hocam ben almiyim :D Bu arada bu kadar uğraştığınıza göre sizin de baya hoşunuza gitmiş sanırım :D

< Bu mesaj bu kişi tarafından değiştirildi Guest-33247115E -- 24 Haziran 2021; 23:52:43 >
Bu mesaja 1 cevap geldi.

T

Tuğkan-0153

4 yıl

Yarbay

coins'lerin sonuna 2 eklendiğinde 7 bulduğu an.
< Resime gitmek için tıklayın >

bulunan coin'leri listelemek o kadar kolay değil . ancak cok zor da değil.

sorunun ilgimi cekme sebebi, dediğim gibi recursion olayını tam olması gerektiği gibi kullanması. dikkat ettiysen kod yaptığı işe oranla kısa ve net. recursion değil de iterasyon kullansaydı daha uzun ve karışık olurdu. hobi amaçlı ilgilendiğim kodlarda bazen ben de recursion kullanıyorum.

< Bu ileti mini sürüm kullanılarak atıldı > Bu mesaja 1 cevap geldi.

Bu mesajda bahsedilenler: @WhoThisGuy

G

Guest-33247115E

4 yıl

Er

Konu Sahibi

quote:

Orijinalden alıntı: Tuğkan-0153

coins'lerin sonuna 2 eklendiğinde 7 bulduğu an.
< Resime gitmek için tıklayın >

bulunan coin'leri listelemek o kadar kolay değil . ancak cok zor da değil.

sorunun ilgimi cekme sebebi, dediğim gibi recursion olayını tam olması gerektiği gibi kullanması. dikkat ettiysen kod yaptığı işe oranla kısa ve net. recursion değil de iterasyon kullansaydı daha uzun ve karışık olurdu. hobi amaçlı ilgilendiğim kodlarda bazen ben de recursion kullanıyorum.

Hocam kodla oynarken 16.satırda bir değişiklik yapmışsınız, unutmamak için yoruma da almışsınız ama gözden kaçmış :), target yerine min_coins yazınca sorun düzeliyor.

Bu mesaja 1 cevap geldi.

T

Tuğkan-0153

4 yıl

Yarbay

ops aynen, onu yorumdan geri almayı unutmuşum.

sonuçta bu kod, yeni başlayanlar için biraz zor (ve o yüzden biraz isabetsiz seçim) olsa da, tek başına değerlendirildiğinde recursion kullanımına iyi bir örnek. coins listesini cıkaran koda yarın bir bakacağım. dediğm gibi o cok kolay degil, cok zor da değil.

< Bu ileti mini sürüm kullanılarak atıldı >

Bu mesajda bahsedilenler: @WhoThisGuy

S

SonerimSoner

4 yıl

Çavuş

Sen bunu da anlayamazsın ki. Sen necisin ya bu forumda boş boş yorumlar her yerde. Ekran görüntüsüyle paylaş falan :D Tipe gel. Seni iyi maskot yapmamışlar bu foruma ama benim favorim sensin aslanım bundan sonra. Takibindeyim.

Bu mesaja 1 cevap geldi.

Bu mesajda bahsedilenler: @vonderplanitz

T

Tuğkan-0153

4 yıl

Yarbay

Değişik algoritma sorularıyla ilgilenmem ve forumun syntax highlighting'i yeterli olmadığı için bazen kodları SS olarak göndermem neden rahatsız etti ki :)

< Bu mesaj bu kişi tarafından değiştirildi Tuğkan-0153 -- 5 Temmuz 2021; 14:49:3 >

< Bu ileti mini sürüm kullanılarak atıldı >

Bu mesajda bahsedilenler: @SonerimSoner