Problem i python, för stort tal? (nybörjare)

2013-09-18 17:29

Medlem

Registrerad: Dec 2010

●

Problem i python, för stort tal? (nybörjare)

Hejsan, jag undrar hur man får följande kod att räkna ut factorial på tal högre än 994? Vid 995 och uppåt får jag ett väldigt långt error:

>>> factorial(1000)
Traceback (most recent call last):
File "<pyshell#0>", line 1, in <module>
factorial(1000)
File "G:\factorial.py", line 4, in factorial
a = x*factorial(x-1)
File "G:\factorial.py", line 4, in factorial (detta meddelande kommer ca 100 ggr i rad)
a = x*factorial(x-1)
File "G:\factorial.py", line 2, in factorial
if x == 1:
RuntimeError: maximum recursion depth exceeded in comparison

Dold text

kod:

def factorial(x):
    if x == 1:
        return 1
    a = x*factorial(x-1)
    return a

Koden ska helst inte vara iterativ, så någon fix till min nuvarande kod vore kanon! Tack på förhand!

Senast redigerat 2013-09-18 18:06

Rapportera Redigera

Citera flera Citera

2013-09-18 17:36

Permalänk

MrSir

Medlem

Registrerad: Jul 2013

●

Och vad får du för output på 994! ? Fel blir det ju hur som helst. Låter som en inställning i Python som säger stopp för den tycker du gör något konstigt.

Du vet att du får ett tal som ser ut som 10000000000000000000000000000000000000000000000000000000000000000000... .. 0000000000000000000000... ... 000000000000 ?

Nu vet jag inte vilka python bibliotek som behövs för att räkna ut det där men det är väl inget du behöver bråka med som nybörjare?

edit: Svaret du får måste du ju ta emot i formen av en text, eller som primtalsfaktorer med rest. Så du inte sitter med en Int och undrar.

Rapportera Redigera

Citera flera Citera

2013-09-18 18:10

Permalänk

Monkeyapa

Medlem

Registrerad: Dec 2010

●

Skrivet av MrSir:

Och vad får du för output på 994! ? Fel blir det ju hur som helst. Låter som en inställning i Python som säger stopp för den tycker du gör något konstigt.

Du vet att du får ett tal som ser ut som 10000000000000000000000000000000000000000000000000000000000000000000... .. 0000000000000000000000... ... 000000000000 ?

Nu vet jag inte vilka python bibliotek som behövs för att räkna ut det där men det är väl inget du behöver bråka med som nybörjare?

edit: Svaret du får måste du ju ta emot i formen av en text, eller som primtalsfaktorer med rest. Så du inte sitter med en Int och undrar.

Gå till inlägget

utskrift för x=994:

408479828515489256353474995482408358160497265910659964627093499965899020851244601523057075998189630761571573915775902022827388462056824913280383023299404143746088956859469192805413326179609395288550759267766567778513344579219396409879210452632138317526533536196130411663019544586462612597488979234580446395660782673845444445744446855627291878808156097739274830944977355758443500055387784290059300751838756648811927011205971860183777745097119216518533151831009400768021448911289481662701447360711223209656699002520448639971994566756090610988433892850569176843947513344124003111025471699286332054703221257479803948554799185113770298141157185620393078623204745722963720698814601900758867993711577337192974108712287297749642787549814125573511062877441959959260507852204098837246533731205586429495445967118104588944721998842997546998124028007142174958031760791583183391032548795783726631789230510072791194968120873322260682504816108290276311669974945205102145855184779926222627829030287142693286266992238150977861451748992852206601963644944460140583093508461742609331020447278800834251499762845396883436690995642125377603902309825187631767468294699985328703628219690641217645609747104661139112053822227409417921028438799401282694582506602919442719939153634607083979767632422894489890114396942195858649361345578680339826776670671845270671830154841858480190455309228288644778025813024881155217868366059367507592218734243130726544496608175222147001922603977244134716572158821985549126914876832955809281953139717211726184820291130209183555991241407805122458415669879589475928715662168928321719454680101336064798315065628256548290180972984451059066626333000912556158031738275175386225550858916243728654220881036238065191589359977031741231835062137110163347854168291465847975084637169658768234208654239463025500793325344468514105336014841926266134549270010837172219988723226653082422906138273681658890486944523549522576817468781761838856080901405866957872122666667194108909031450387743075081047741905664955902329075255693536749391178968154378514691238064222302637921456741313279637838800099969604859212696767294670969427836275465208799095194119907852867739507433497693801297921352579298871053850535218508291814815992495163658514825596955670792238036446958964327174516278331545376827058626704243676311184208250168934400000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

Dold text

Nyfiken på varför det fungerar upp till 994 och inte högre, ska tydligen gå att lösa problemet!

Rapportera Redigera

Citera flera Citera

2013-09-18 18:22

Permalänk

MrSir

Medlem

Registrerad: Jul 2013

●

Va ju bara att googla på felmeddelandet.

sys.setrecursionlimit(1500)

Python har bestämt sig för att en funktion inte får kalla på sig själv mer än ca 1000 ggr, du kan ändra det med funktionen ovan. Anledningen är att ditt program inte ska bugga ur eller krascha någon stackares surfplatta. Förövrigt var det ju imponerande att Python spottade ut så många tal ändå.

Rapportera Redigera

Citera flera Citera (1)

2013-09-18 18:23

Permalänk

phz

Hedersmedlem ★

Registrerad: Okt 2002

●

Först och främst så finns fakultetsfunktion redan i `math`, utan dylika problem, men antar att detta är en skoluppgift.

Det existerar en rekursionsgräns för att skydda tolken mot ofrivillig oändlig rekursion. Det går att ändra denna gräns dock:

>>> import sys
>>> sys.getrecursionlimit()
1000
>>> sys.setrecursionlimit(2000)
>>> sys.getrecursionlimit()
2000
>>> def factorial(x):
...     if x == 1:
...         return 1
...     a = x*factorial(x-1)
...     return a
... 
>>> factorial(1000)
402387260077093773543702433923003985719374864210714632543799910429938512398629020592044208486969404800479988610197196058631666872994808558901323829669944590997424504087073759918823627727188732519779505950995276120874975462497043601418278094646496291056393887437886487337119181045825783647849977012476632889835955735432513185323958463075557409114262417474349347553428646576611667797396668820291207379143853719588249808126867838374559731746136085379534524221586593201928090878297308431392844403281231558611036976801357304216168747609675871348312025478589320767169132448426236131412508780208000261683151027341827977704784635868170164365024153691398281264810213092761244896359928705114964975419909342221566832572080821333186116811553615836546984046708975602900950537616475847728421889679646244945160765353408198901385442487984959953319101723355556602139450399736280750137837615307127761926849034352625200015888535147331611702103968175921510907788019393178114194545257223865541461062892187960223838971476088506276862967146674697562911234082439208160153780889893964518263243671616762179168909779911903754031274622289988005195444414282012187361745992642956581746628302955570299024324153181617210465832036786906117260158783520751516284225540265170483304226143974286933061690897968482590125458327168226458066526769958652682272807075781391858178889652208164348344825993266043367660176999612831860788386150279465955131156552036093988180612138558600301435694527224206344631797460594682573103790084024432438465657245014402821885252470935190620929023136493273497565513958720559654228749774011413346962715422845862377387538230483865688976461927383814900140767310446640259899490222221765904339901886018566526485061799702356193897017860040811889729918311021171229845901641921068884387121855646124960798722908519296819372388642614839657382291123125024186649353143970137428531926649875337218940694281434118520158014123344828015051399694290153483077644569099073152433278288269864602789864321139083506217095002597389863554277196742822248757586765752344220207573630569498825087968928162753848863396909959826280956121450994871701244516461260379029309120889086942028510640182154399457156805941872748998094254742173582401063677404595741785160829230135358081840096996372524230560855903700624271243416909004153690105933983835777939410970027753472000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000L
>>>

EDIT: Minuten sen, men låter det stå iom kodexemplet.

EDIT 2: Du bör hantera 0! också, som är definierat till 1. Det räcker med att ändra `if x == 1:` till `if x == 0:`. Sedan kanske ett lite snällare felmeddelande för felaktiga argument än `recursionlimit` stycken felutskrifter kan vara bra .

EDIT 3: Bara för att det är Python:

factorial = lambda n: reduce(lambda x, y: x*y, range(1, n+1))

Det ger en fakultetsfunktion utan rekursionsgränsproblem (som inte funkar för 0). Bättre (typ) variant på samma tema:

def factorial(n):
    if n==0:
        return 1
    try:
        return reduce(lambda x, y: x*y, range(1, n+1))
    except TypeError:
        raise ValueError('argument must be non-negative integer')

Lambdafunktioner och reduce()… Guido skulle inte varit nöjd .

Visa signatur

Nu med kortare användarnamn, men fortfarande bedövande långa inlägg.

Rapportera Redigera

Citera flera Citera (1)

2013-09-18 20:27

Permalänk

Yoshman

Datavetare ★

Plats: Stockholm
Registrerad: Jun 2011

●

Att öka maximalt rekursionsdjup löser tyvärr inte det grundläggande problemet. I vissa språk så "äter" inte svansrekursiva funktioner stack, så man skulle kunna skriva

def factorial(n, acc = 1):
    if n < 2:
        return acc
    return factorial(n - 1, n * acc)

Tyvärr fungerar det inte i Python då man fortfarande allokerar en ny stack även om anropet är i svansrekursion position, något som nog aldrig kommer ändras. Tycker att Guido har en helt rimligt anledning till att aldrig göra denna förändring i Python.

Vad man kan göra i alla språk där funktioner är första ordningens objekt är en s.k. trampolin. Resultatet blir som om språket skriver om svansrekursion till en loop. I Python skulle de kunna se ut så här

def trampoline(fn, *args):
    r = fn(*args)
    while callable(r):
        r = r()
    return r

och enda skillnaden på funktionen ovan är att den ska returnera en anonym funktion utan argument. Den funktionen är då en s.k. closure, anonym funktion + en eller flera inkapslade variabler (det som man "closing over").

def factorial(n, acc = 1):
    if n < 2:
        return acc
    return lambda: factorial(n - 1, n * acc)

Här utnyttjar jag att Python är dynamiskt typat då factorial kan resultera både i ett heltal (och då är vi klar) eller en funktion (och då fortsätter trampoline att anropa funktionen).

Man kan du göra detta

trampoline(factorial, 10000)

utan att få stack-overflow.

Reder man ut vad som händer i fallet trampoline(factorial, 3) så blir det

r = factorial(3, 1) -> lambda: factorial(3 - 1, 3 * 1)
r = r() -> factorial(2, 3) -> lambda: factorial(2 - 1, 3 * 2)
r = r() -> factorial(1, 6) -> 6
# r is no longer callable(), trampoline returns 6

Men i detta fall är det både enklare och betydligt mycket mer effektiv att göra en iterativ implementation, något som väldigt ofta är sant. Rekursion leder ofta till väldigt eleganta lösningar, men i "verkligheten" är det sällan man kan använda det då man inte vet hur stort rekursiondjup funktionen kan orsaka när man inte har total kontroll över indata.

Visa signatur

Care About Your Craft: Why spend your life developing software unless you care about doing it well? - The Pragmatic Programmer

Rapportera Redigera

Citera flera Citera (1)

Problem i python, för stort tal? (nybörjare)

Problem i python, för stort tal? (nybörjare)

Externa nyheter

Spelnyheter från FZ