Forum Informatica Unict

LAUREA TRIENNALE (D.M. 270/04) => Programmazione 2, 9 CFU => Topic started by: rox on 10-08-2014, 12:31:14



Title: funzione ricorsiva sui naturali
Post by: rox on 10-08-2014, 12:31:14
cose si potrebbe risolvere questo esercizio?
Scrivere una funzione ricorsiva  reverse_int che dato in input SOLO n,restituisca il naturale ottenuto invertendo l'ordine delle cifre di n. Ovvero reverse_int(1234)=4321.
Una cosa che potrebbe aiutare è che se abbiamo il numero 1234, allora 4=1234%10, mentre 123=1234/10... ma anche avendo questi dettagli non riesco a trovare una soluzione ...

il mio problema sta in questo:
quando io prendo l'ultimo elemento del numero, come faccio a sapere se è un'unità, decina, centinaia, ecc?? utilizzando solo un input come argomento è possibile fare questa funzione secondo voi?  :-)|


Title: Re:funzione ricorsiva sui naturali
Post by: ɹǝǝuıƃuǝsɹǝʌǝɹ on 10-08-2014, 16:46:22
Certo che è possibile.

inizializzi il risultato R da calcolare su 0, poi
puoi fare un ciclo (while)
Ad ogni iterazione, tu
- verifichi che il numero N trattato sia > 0 (condizione di entrata del while)
- in questo caso, si entra nel ciclo e tu giustamente prima trovi C := N%10
- inserisci C in coda ad R tramite R := R*10 + C
- togli C da N tramite N := N/10 (divisione intera!)

Questo codice JavaScript può aiutarti a comprendere, e lo puoi provare nel browser! (apri la console javascript, in Chrome con F12) e usalo:
Code:
function reverse_int (n) {var r=0; while (n>0) {c=n%10; r=r*10+c; n=parseInt(n/10);} return r;}

n=parseInt (Math.random () * Math.pow (10, 10)); console.log (" numero=" + n + "\ninverso=" + reverse_int (n));


Title: Re:funzione ricorsiva sui naturali
Post by: rox on 11-08-2014, 10:28:24
mmm si! ma questa è una funzione iterativa! non ricorsiva come volevo farla io!  :[Emoticon] Asd: il problema (secondo me è che questa variabile r che tu usi dovrei metterla come parametro di input della funzione ricorsiva... ) .


Title: Re:funzione ricorsiva sui naturali
Post by: ɹǝǝuıƃuǝsɹǝʌǝɹ on 17-08-2014, 23:50:22
Scusa, hai ragione, avevo proprio confuso il concetto di ricorsione :-)|.

Allora, prova questa metodologia:

caso base - il numero ha una sola cifra: in questo caso, banalmente reverse_int (n):=n
caso iterativo - il numero ha più cifre:
   idea: prendo la cifra più a destra (la meno significativa) e la pongo a sinistra concatenandovi dopo il reverse_int del numero che ottengo rimuovendo tale cifra dal numero:
Code:
function reverse_int (n) {if ((n%10)==n) return n; else return (n%10) * Math.pow(10, Math.floor (Math.log (n)/Math.log (10))) + reverse_int (Math.floor (n/10));}

Una condizione sufficiente per verificare che un numero ha una sola cifra è il fatto che esso coincide con il resto della divisione dello stesso per 10.

Per rimuovere l'ultima cifra, è sufficiente fare la divisone del numero con 10 (se il linguaggio usato non supporta la divisione tra interi, ma fa sempre quella tra numeri decimali, sarà necessario fare poi il floor di tale numero, come ho fatto io perché uso JS).
Per concatenare tale numero a destra di un altro, posso fare la somma di questo numero con quello che ottengo moltiplicando per una opportuna potenza di 10 dell'altro.
Per conoscere quante cifra usa la rappresentazione decimale del numero intero n, è sufficiente fare questo calcolo:
\fs{4}c(n)=\lfloor{\log_{10}{\({n}\)}}\rfloor+1

Siccome io devo spostare a sinistra il numero ottenuto come ultima cifra di n (cioè n%10), devo moltiplicare questa ultima cifra per \fs{3}10^{c(\lfloor{\frac{n}{10}}\rfloor)}=10^{\lfloor{\log_{10}{\({\lfloor{\frac{n}{10}}\rfloor}\)}}\rfloor+1}=10^{\lfloor{\log_{10}{n}\rfloor} (da non confondere con \fs{3}10^{\log_{10}{n}}=n), e poi aggiungerla al reverse_int del numero a cui ho tolto l'ultima cifra (cioe del numero \fs{3}\lfloor{\frac{n}{10}\rfloor.

In linguaggio matematico la funzione è definita così:

\fs{4}\text{reverseint}(n)=\{\begin{matrix}n&&\text{se }n\% 10=n\\(n\% 10)\cdot 10^{\lfloor{\frac{n}{10}}\rfloor}+\text{reverseint}({\lfloor{\frac{n}{10}}\rfloor})&&\text{altrimenti}\end{matrix}