Forum >> Principianti >> Problema python in algoritmica

Pagina: 1

salve a tutti sto studiando algoritmica per un esame universitario e mi sono trovato un po in difficolta con questa semplice ricorsione che ora vi mostro: so che ci sono delle librerie per fare lo stesso ma non è quello il punto, mi serve riuscire a capire bene un algoritmo :question: :question:
def binario(n):

if n == 0 : #condizione

return ' ' #non so cosa sia forse una sorta di pass o rende stringa il numero :question:

return binario(n//2)+str(n%2) #richiama la funzione e quindi divide escludendo i decimali n finche non diventa = 0 salva il modulo 2 di ogni n che viene diviso come stringa. non capisco bene il +str forse perche non si sommano i valori dato che è diventato una str




print(binario(353646545521))

allora io interpreto questa funzione in questo modo, utilizzo if per controllare che n non sia 0 se non lo è mi divide il numero messo in in input(353646545521) escludendo i decimali e sommando il modulo dello stesso numero come stringa, essendo richiamata la funzione divide il numero n volte finche n non torna 0, a quel punto non capisco che cosa ci sta a fare il return ' ' , so cosa fa la funzione stampa il binario del numero facendo il modulo di n piu il modulo di n//2 ecc finche non viene 0 e considera il risultato come stringa ma non riesco proprio a capire bene se è essenziale return o funge come una sorta di condizione passiva che serve solo a fermare la funzione, qualcuno che mi delucidi un po?

grazie mille in anticipo
Non ci sono molte soluzioni per capire la ricorsione: bisogna mettersi lì con carta e penna e fare il conto, e poi rifarlo e rifarlo ancora finché non capisci come funziona. Per prima cosa, riscriviamo la funzione formattandola con l'apposito pulsante "code" (quello con il simbolo "<>") in modo che si capisca di che cosa parliamo:

def binario(n):
    if n==0:
        return ''
    return binario(n//2) + str(n%2)
Ora, è chiaro che se ti metti con carta e penna a calcolare "binario(353646545521)" non ne esci vivo. Però carta e penna è l'unico modo, fidati. Proviamo insieme a calcolare cosa succede quando scrivi


binario(5)  # dà "101", ovviamente
Allora, sei pronto? Via:


PRIMO PASSAGGIO: "binario(5)"
- 5 è uguale a 0? No, andiamo avanti
- 5%2 è uguale a 1. Quindi la stringa finale terminerà per "1"
- 5//2 è uguale a 2. Quindi dobbiamo calcolare binario(2)
- stato attuale: la stringa è "....1", e dobbiamo calcolare binario(2)

SECONDO PASSAGGIO: "binario(2)"
- 2 è uguale a 0? No, andiamo avanti
- 2%2 è uguale a 0. Quindi aggiungiamo a sinistra uno "0" alla stringa finale
- 2//2 è uguale a 1. Quindi dobbiamo calcolare binario(1)
- stato attuale: la stringa è "...01", e dobbiamo calcolare binario(1)

TERZO PASSAGGIO: "binario(1)"
- 1 è uguale a 0? No, andiamo avanti
- 1%2 è uguale a 1. Quindi aggiungiamo a sinistra un "1" alla stringa finale
- 1//2 è uguale a 0. Quindi dobbiamo calcolare binario(0)
- stato attuale: la stringa è "...101", e dobbiamo calcolare binario(0)

QUARTO PASSAGGIO: "binario(0)"
- 0 è uguale a 0? Sì, quindi aggiungiamo una stringa vuota ("") a sinistra alla stringa finale, e usciamo
- stato attuale: la stringa è "101", e non dobbiamo calcolare più nessuna ricorsione.

Risultato: "101"

Se non sei riuscito a seguire questi passaggi, ripetili con carta e penna finché non ci riesci. Se ci sei riuscito, prova almeno altre cinque volte con carta e penna a fare altri calcoli semplici (binario(3), binario(7), binario(9)...) finché non hai interiorizzato come funziona. Purtroppo la ricorsione funziona così, devi trovare il modo di immaginarti nella testa lo stack delle chiamate successive e i risultati parziali.




--- Ultima modifica di RicPol in data 2018-11-20 21:49:07 ---
https://leanpub.com/capirewxpython: Capire wxPython, il mio libro
https://pythoninwindows.blogspot.com: Python in Windows, il mio blog e le mie guide
Non ci sono molte soluzioni per capire la ricorsione: bisogna mettersi lì con carta e penna e fare il conto, e poi rifarlo e rifarlo ancora finché non capisci come funziona. Per prima cosa, riscriviamo la funzione formattandola con l'apposito pulsante "code" (quello con il simbolo "<>") in modo che si capisca di che cosa parliamo:

def binario(n):
    if n==0:
        return ''
     
Ora, è chiaro che se ti metti con carta e penna a calcolare "binario(353646545521)" non ne esci vivo. Però carta e penna è l'unico modo, fidati. Proviamo insieme a calcolare cosa succede quando scrivi


binario(5)  # dà "101", ovviamente
Allora, sei pronto? Via:


PRIMO PASSAGGIO: "binario(5)"
- 5 è uguale a 0? No, andiamo avanti
- 5%2 è uguale a 1. Quindi la stringa finale terminerà per "1"
- 5//2 è uguale a 2. Quindi dobbiamo calcolare binario(2)
- stato attuale: la stringa è "....1", e dobbiamo calcolare binario(2)

SECONDO PASSAGGIO: "binario(2)"
- 2 è uguale a 0? No, andiamo avanti
- 2%2 è uguale a 0. Quindi aggiungiamo a sinistra uno "0" alla stringa finale
- 2//2 è uguale a 1. Quindi dobbiamo calcolare binario(1)
- stato attuale: la stringa è "...01", e dobbiamo calcolare binario(1)

TERZO PASSAGGIO: "binario(1)"
- 1 è uguale a 0? No, andiamo avanti
- 1%2 è uguale a 1. Quindi aggiungiamo a sinistra un "1" alla stringa finale
- 1//2 è uguale a 0. Quindi dobbiamo calcolare binario(0)
- stato attuale: la stringa è "...101", e dobbiamo calcolare binario(0)

QUARTO PASSAGGIO: "binario(0)"
- 0 è uguale a 0? Sì, quindi aggiungiamo una stringa vuota ("") a sinistra alla stringa finale, e usciamo
- stato attuale: la stringa è "101", e non dobbiamo calcolare più nessuna ricorsione.

Risultato: "101"

Se non sei riuscito a seguire questi passaggi, ripetili con carta e penna finché non ci riesci. Se ci sei riuscito, prova almeno altre cinque volte con carta e penna a fare altri calcoli semplici (binario(3), binario(7), binario(9)...) finché non hai interiorizzato come funziona. Purtroppo la ricorsione funziona così, devi trovare il modo di immaginarti nella testa lo stack delle chiamate successive e i risultati parziali.




--- Ultima modifica di RicPol in data 2018-11-20 21:49:07 ---
grazie mille una risposta molto esaudiente e completa complimenti hai dato un significato ad ogni concetto espresso e mi hai "passato" un po del tuo ragionamento, in questo caso ho capito quasi tutto escluso <code> return binario(n//2) + str(n%2)
non capisco perche invece di fare la somma fra n//2 +stri(n%2) salva str(n%2) in una stringa prima di fare n//2, piu che non ho capito diciamo che non ho ben chiaro forse riguardandolo un po' potrei trovarci una logica. Visto che sei stato molto bravo hai dei consigli o delle guide per quanto riguarda queste cose ?
Eh, diciamo che non hai capito la cosa fondamentale. Mettiamola così: a ogni iterazione, quella funzione restituisce un "coso" nella forma:

R + S

dove "S" è una stringa, e "R" è il risultato di un'altra ricorsione. Quindi, dopo un po' di volte che ripeti la ricorsione, hai un "coso" di questo tipo:

(((((...) + S) + S) + S) + S)

dove "..." rappresenta il livello di ricorsione che hai raggiunto attualmente. Arrivati all'ultima ricorsione, la funzione restituisce una stringa vuota e si ferma (cioè non chiama più se stessa). Quindi, dopo l'ultima ricorsione, tu avrai un "coso" finale di questo tipo:

(((((("") + S) + S) + S) + S) + S)

che è ovviamente la somma di varie stringhe, ossia una stringa. In altre parole, la stringa finale è il risultato dell'accumulo progressivo delle "stringhe-resto" prodotte a ogni successiva ricorsione, più l'ultima stringa vuota di chiusura. (Le "stringhe-resto", come spero avrai capito, sono i resti convertiti in stringa: questo algoritmo mappa la procedura che faresti con carta e penna per convertire un intero decimale in binario).





Esercizio numero 1: che cosa garantisce che a un certo punto la funzione "esca", e non continui a ricorrere all'infinito? Ovvero, che cosa garantisce che si arrivi sempre, a un certo punto, allo zero e quindi a chiamare "binario(0)"?

Esercizio numero 2: che cosa succede se, arrivati a zero, la funzione non esce restituendo la stringa vuota, ma qualsiasi altra cosa? Cioè, per esempio, se scrivo:
def binario(n):
    if n==0:
        return None # o "return 42", o "return False", qualunque cosa
    etc etc etc come sopra
La funzione "funziona" ancora? E perché?

Esercizio numero 3: scritta in questo modo la funzione ha un piccolo baco: se chiami "binario(0)" il risultato è una stringa vuota, cosa ovviamente sbagliata. Il binario di 0 invece è "0", ovviamente. Il problema è che quando la funzione testa "if n==0" non riesce a distinguere se sta parlando proprio del numero originale oppure del numero che riceve a una ricorsione successiva. Cioè non riesce a distinguere se in quel momento sta eseguendo la prima ricorsione, o è già arrivata a una ricorsione successiva. Bisognerebbe correggere la funzione con qualcosa del genere:
# pseudo-codice
def binario(n):
    if n==0 and siamo-alla-prima-ricorsione:
        return "0"
    if n==0 and siamo-oltre-la-prima-ricorsione:
        return ""
    etc etc come sopra
C'è un modo per fare questo? (questo esercizio è un po' più difficile. Forse puoi usarlo per fare l'ingenuo e trollare il tuo prof. C'è una discreta possibilità che così su due piedi non lo sappia fare neanche lui).





Detto questo, il tuo problema resta lo stesso: posso guidarti per mano, centimetro dopo centimetro; posso farti un milione di esempi e di metafore; ma se non ci ragioni sopra con la tua testa, perderndoci una giornata (ma una giornata seria, intendo: col telefonino spento, senza distrazioni, senza musica... come si faceva una volta) non ci riuscirai mai. E' proprio qualcosa che ti scatta nella testa, e deve scattarti perché riesci a visualizzarlo alla tua maniera. Poi prova con gli esercizi che ti ho proposto, poi prova altre funzioni ricorsive, eccetera.


La ricorsione non è difficile di per sé: tuttavia è oggettivamente difficile visualizzare il flusso del programma ricorsivo nella testa. C'è solo da mettersi lì con pazienza e carta e penna.
















https://leanpub.com/capirewxpython: Capire wxPython, il mio libro
https://pythoninwindows.blogspot.com: Python in Windows, il mio blog e le mie guide
ciao andredatto,

cerco se riesco a spiegarti il ragionamento che ho fatto: in pratica a grandi linee "ovviamente" dovresti considerare il 'return' come un accumulatore di risultato

quindi se binario è 5 la ricorsione si ripeterà per 3 volte, quindi avrai una situazione come questa:

return = (none) + ricorsione + risultato

return = (risultato) + ricorsione + risultato

return = (risultato + risultato) + ricorsione + risultato

return = (risultato + risultato + risultato) + ''




per lo meno questo è quello che da profano a grandi somme ho visualizzato il funzionamento

ovviamente non saprei fino a che punto il ragionamente vada bene o i termini tecnici siano giusti....

nel caso sicuramente Ric o altri potranno darti maggiori chiarimenti nello specifico. un saluto :ok:

Eh, diciamo che non hai capito la cosa fondamentale. Mettiamola così: a ogni iterazione, quella funzione restituisce un "coso" nella forma:

R + S

dove "S" è una stringa, e "R" è il risultato di un'altra ricorsione. Quindi, dopo un po' di volte che ripeti la ricorsione, hai un "coso" di questo tipo:

(((((...) + S) + S) + S) + S)

dove "..." rappresenta il livello di ricorsione che hai raggiunto attualmente. Arrivati all'ultima ricorsione, la funzione restituisce una stringa vuota e si ferma (cioè non chiama più se stessa). Quindi, dopo l'ultima ricorsione, tu avrai un "coso" finale di questo tipo:

(((((("") + S) + S) + S) + S) + S)

che è ovviamente la somma di varie stringhe, ossia una stringa. In altre parole, la stringa finale è il risultato dell'accumulo progressivo delle "stringhe-resto" prodotte a ogni successiva ricorsione, più l'ultima stringa vuota di chiusura. (Le "stringhe-resto", come spero avrai capito, sono i resti convertiti in stringa: questo algoritmo mappa la procedura che faresti con carta e penna per convertire un intero decimale in binario).





Esercizio numero 1: che cosa garantisce che a un certo punto la funzione "esca", e non continui a ricorrere all'infinito? Ovvero, che cosa garantisce che si arrivi sempre, a un certo punto, allo zero e quindi a chiamare "binario(0)"?

Esercizio numero 2: che cosa succede se, arrivati a zero, la funzione non esce restituendo la stringa vuota, ma qualsiasi altra cosa? Cioè, per esempio, se scrivo:
def binario(n):
    if n==0:
        return None # o "return 42", o "return False", qualunque cosa
    etc etc etc come sopra
La funzione "funziona" ancora? E perché?

Esercizio numero 3: scritta in questo modo la funzione ha un piccolo baco: se chiami "binario(0)" il risultato è una stringa vuota, cosa ovviamente sbagliata. Il binario di 0 invece è "0", ovviamente. Il problema è che quando la funzione testa "if n==0" non riesce a distinguere se sta parlando proprio del numero originale oppure del numero che riceve a una ricorsione successiva. Cioè non riesce a distinguere se in quel momento sta eseguendo la prima ricorsione, o è già arrivata a una ricorsione successiva. Bisognerebbe correggere la funzione con qualcosa del genere:
# pseudo-codice
def binario(n):
    if n==0 and siamo-alla-prima-ricorsione:
        return "0"
    if n==0 and siamo-oltre-la-prima-ricorsione:
        return ""
    etc etc come sopra
C'è un modo per fare questo? (questo esercizio è un po' più difficile. Forse puoi usarlo per fare l'ingenuo e trollare il tuo prof. C'è una discreta possibilità che così su due piedi non lo sappia fare neanche lui).





Detto questo, il tuo problema resta lo stesso: posso guidarti per mano, centimetro dopo centimetro; posso farti un milione di esempi e di metafore; ma se non ci ragioni sopra con la tua testa, perderndoci una giornata (ma una giornata seria, intendo: col telefonino spento, senza distrazioni, senza musica... come si faceva una volta) non ci riuscirai mai. E' proprio qualcosa che ti scatta nella testa, e deve scattarti perché riesci a visualizzarlo alla tua maniera. Poi prova con gli esercizi che ti ho proposto, poi prova altre funzioni ricorsive, eccetera.


La ricorsione non è difficile di per sé: tuttavia è oggettivamente difficile visualizzare il flusso del programma ricorsivo nella testa. C'è solo da mettersi lì con pazienza e carta e penna.
--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------



Dovresti fare il professore nella mia università, oltre ad essere molto preparato sei anche molto gentile e disponibile ti ringrazio per il tempo dedicatomi, salvo inconvenevoli.
Ho provato a fare gli esercizi in 30 minuti sono riuscito a ponderare queste soluzioni
1= la condizione if n==0 si verifica sempre perche u numero fratto 2 per "n" volte alla fine torna 0 e quindi essendo una ricorsione prima o poi arriva a zero e fa verificare la condizione che fa uscire dal ciclo e attiva il return

2= inizialmente pensavo che avrebbe funzionato sia che al posto di '' ci sia stati caratteri che numeri, invece provando ho visto che i numeri a meno che non metta <code> str(numero) </code> non funziona, a livello logico però ho compreso che in effetti python non permette di addizionare numeri e stringhe quindi okei. per quanto riguarda il none essendo una key in python non penso possa farlo
3= in 20 minuti nella pausa pranzo ho pensato che un modo sarebbe :calcolare il LEN della str e mettere che se il len della str è =0 ti return '0' elif ti return ' ' , senno avevo anche pensati di printare un count ad ogni ciclo e se il count era a 0 e n==0 allora return '0'
<code>





def bin (n):
if n==0 and len(str(n))==1:
return '0'
elif n==0:
return ''

return bin(n//2)+str(n%2)
</code>
pero non penso vada bene dopo trovo una soluzione e modifico il post se non mi hai ancora risposto.
ancora grazie comunque













--- Ultima modifica di andredatto in data 2018-11-21 13:39:34 ---



--- Ultima modifica di andredatto in data 2018-11-21 13:41:21 ---


--- Ultima modifica di andredatto in data 2018-11-21 13:41:53 ---
1. Esatto.La risposta è: solo la meccanica di questo algoritmo specifico garantisce che si finirà per uscire, ma non c'è nulla, in generale, che garantisca che una ricorsione prima o poi finisca. Quando si progetta una funzione ricorsiva è anzi facilissimo cascare in ricorsioni infinite. A lato pratico, in questi casi Python si accorge del problema ed emette un errore prima che il computer fonda. Però occorre prestare molta attenzione alla robustezza dell'algoritmo, prima di trasformarlo in codice vero e proprio.

2. Proprio così. E questo insegna che anche ingegnerizzare la "via di uscita" dalla ricorsione richiede qualche attenzione architetturale. Non basta dire "ok, quando si verifica questa condizione esco". E' come un giocoliere con le palle: puoi continuare ad aggiungere palle, finché restano in aria. Ma a un certo punto l'esercizio finisce e devi fare attenzione che tutte le palle che tenevi in aria finiscano esattamente nel cestino ai tuoi piedi, nell'ordine giusto.


3. L'idea di calcolare la lunghezza della stringa non funziona perché in nessun momento la stringa binaria è esplicitamente collegata a una variabile che puoi raggiungere. Ti ricordo che "n" non è la stringa binaria, ma il numero decimale di partenza. Se tu testi per str(n)==1, allora la tua funzione esce subito anche quando chiami binario(7), per dire. Ovviamente puoi cercare il modo per tenere traccia della stringa binaria a ogni passaggio... Ma direi che invece la strada con il contatore è più saggia... però devi implementare questo contatore... provaci... e se ci pensi su vedrai che in effetti un contatore è perfino eccessivo... in realtà basta un flag... ma prova a pensarci per conto tuo.



--- Ultima modifica di RicPol in data 2018-11-21 18:35:27 ---
https://leanpub.com/capirewxpython: Capire wxPython, il mio libro
https://pythoninwindows.blogspot.com: Python in Windows, il mio blog e le mie guide


Pagina: 1



Esegui il login per scrivere una risposta.