Programim dhe zhvillim, javascript, python, php, html

Python - konverto rekursionin në një rekursion të bishtit

Për të gjetur numrin e mënyrave për të shkuar nga një cep i një rrjeti në këndin e kundërt, duke zbritur vetëm poshtë ose djathtas. Unë dal me një ide fillestare për të përdorur rekursionin për të zgjidhur problemin:

def find_num_of_ways(x: int, y: int):
    if x == 0 or y == 0:
        return 1
    return find_num_of_ways(x - 1, y) + find_num_of_ways(x, y - 1)

Kjo mund të jetë tejmbushje e pirgut kur x dhe y rriten. Dëshironi të gjeni një mënyrë më të mirë për të rifaktoruar këtë, njëra është konvertimi në rekursion të bishtit. Por duke pasur parasysh 2 variabla në nënshkrim, atëherë si të grumbullohet rezultati në mënyrë që të bëhet rekursion i bishtit?

python recursion tail-recursion
11.09.2020

  • kjo do të ndihmojë të konvertojë rekursionin në "rekursion bisht" 11.09.2020
  • Rekursioni i bishtit nuk ekziston në Python. Nëse nuk ka ndonjë pengesë, mund ta llogaritni këtë matematikisht (Projekti Euler 15). Nëse ka pengesa, përdorni DP nga poshtë lart. 11.09.2020
  • @ggorlen mirë, sigurisht që rekursioni i bishtit ekziston në python, por nuk ka optimizim të thirrjes së bishtit në CPython. 11.09.2020
  • OK, kjo tingëllon më e saktë teknikisht, por qëllimi im është që pirgu do të fryhet pavarësisht se si e vendosni kodin në CPython. Ndoshta një zbatim tjetër e optimizon atë si një lak. 11.09.2020

Përgjigjet:


1

Analiza ime për këtë është se kërkon kaq shumë kohë për të llogaritur një përgjigje, saqë do të largoheni shumë përpara se pirgja të tejmbushet. Unë do të sugjeroj që të heqim rekursionin fare dhe ta bëjmë këtë si një problem kombinimi kuti dhe topa

(x + y - 1)!
------------
 y!(x - 1)!

plus anasjelltas:

(y + x - 1)!
------------
 x!(y - 1)!

domethënë, në kuptimin Python:

from math import factorial as f

def find_num_of_ways(x, y):
    return f(x + y - 1) // (f(y) * f(x - 1)) + f(y + x - 1) // (f(x) * f(y - 1)) 

print(find_num_of_ways(10, 10))

OUTPUT

> python3 test.py
184756
>

Për sa i përket performancës, për argumentet:

find_num_of_waysTail(13, 14)

Në makinën time, zgjidhja origjinale rekursive e OP zgjat 9 sekonda, zgjidhja kundërvlerësuese e @Mike67 zgjat rreth 12 sekonda dhe zgjidhja ime e mësipërme zgjat rreth 0,05 sekonda. Të gjitha japin rezultatin 20058300.

11.09.2020

2

Meqenëse të gjitha shtigjet përfundojnë në të njëjtën pikë, thjesht mund të numëroni sa herë është prekur pika e fundit.

#### Recursion ####
def find_num_of_ways(x: int, y: int):
    if x == 0 or y == 0:
        return 1
    return find_num_of_ways(x - 1, y) + find_num_of_ways(x, y - 1)

ttl = find_num_of_ways(10,10)
print("Recursion", ttl)


#### Counter ####
ttl = 0
def find_num_of_waysCtr(x: int, y: int):
    global ttl
    if x == 0 or y == 0:
        ttl += 1
        return
    find_num_of_waysCtr(x - 1, y)
    find_num_of_waysCtr(x, y - 1)

find_num_of_waysCtr(10,10)
print("Counter  ", ttl)

Prodhimi

Recursion 184756
Counter   184756
11.09.2020
Materiale të reja
Masterclass Coroutines: Kapitulli-3: Anulimi i korutinave dhe trajtimi i përjashtimeve.
Mirë se vini në udhëzuesin gjithëpërfshirës mbi Kotlin Coroutines! Në këtë seri artikujsh, unë do t'ju çoj në një udhëtim magjepsës, duke filluar nga bazat dhe gradualisht duke u thelluar në..
Faketojeni derisa ta arrini me të dhënat false
A e gjeni ndonjëherë veten duke ndërtuar një aplikacion të ri dhe keni nevojë për të dhëna testimi që duken dhe duken më realiste ose një grup i madh të dhënash për performancën e ngarkesës...
Si të përdorni kërkesën API në Python
Kërkesë API në GitHub për të marrë depot e përdoruesve duke përdorur Python. Në këtë artikull, unë shpjegoj procesin hap pas hapi për të trajtuar një kërkesë API për të marrë të dhëna nga..
Një udhëzues hap pas hapi për të zotëruar React
Në këtë artikull, do të mësoni se si të krijoni aplikacionin React, do të mësoni se si funksionon React dhe konceptet thelbësore që duhet të dini për të ndërtuar aplikacione React. Learning..
AI dhe Psikologjia — Pjesa 2
Në pjesën 2 të serisë sonë të AI dhe Psikologji ne diskutojmë se si makineritë mbledhin dhe përpunojnë të dhëna për të mësuar emocione dhe ndjenja të ndryshme në mendjen e njeriut, duke ndihmuar..
Esencialet e punës ditore të kodit tim VS
Shtesat e mia të preferuara - Git Graph 💹 Kjo shtesë është vërtet e mahnitshme, e përdor përpara se të filloj të punoj për të kontrolluar dy herë ndryshimet dhe degët më të fundit, mund të..
Pse Python? Zbulimi i fuqisë së gjithanshme të një gjiganti programues
Në peizazhin gjithnjë në zhvillim të gjuhëve të programimit, Python është shfaqur si një forcë dominuese. Rritja e tij meteorike nuk është rastësi. Joshja e Python qëndron në thjeshtësinë,..