Discussione Definizioni ricorsive

Ordina per data Ordina commenti per reazioni
J

jr_sottomajor

Utente Silver
2 Luglio 2017
96
33
4
79
Ciao ragazzi, dovrei dare una definizione ricorsiva di 1+(-1)^n per n>=1. In base alle regole che conosco dovrei trovare il passo base che in questo caso è f(0)=2. Ora per il passo ricorsivo mi trovo come f(n)= -f(n-1). Il punto è che quando provo a calcolare un qualunque valore con questa definizione mi escono risultati che non c'entrano proprio nulla. Per esempio f(1) normalmente sarebbe uguale a 0 (in base alla traccia). Calcolandomi f(1) con la definizione ricorsiva invece mi esce -2. Sbaglio io qualcosa o non è possibile definire questa funzione ricorsivamente?
Spero che qualche studente di informatica di università mi sappia rispondere, grazie.
 
fisica-all ha detto:
Ti consiglio di postare il tuo codice cosi' possiamo basarci su quello che hai gia' buttato giu'!
Clicca per espandere...
Nono non si tratta di codice, riguarda metodi matematici per l'informatica.. è solo a livello matematico diciamola così, devo dare una definizione ricorsiva di quella funzione in modo da risolverla in termini del valore della funzione in n-1
 
St3ve ha detto:
Quali sono le regole che conosci?
Clicca per espandere...
ti spiego come ho risolto questo: f(n)= 1+(-1)^n-1+1 ------> 1+(-1)^n-1 * (-1)^1 -------> f(n-1) * (-1)-------> -f(n-1).
In pratica so che al posto di n ci metto n-1+1, il +1 devo cercare di toglierlo per far rimanere solo n-1.. fine.
Non saprei cos'altro devo fare, nelle slide che ho gli esercizi sono semplici e facendo questa operazione di (n-1+1) alla fine la definizione ricorsiva si trova e non ci sono problemi. L'unico problema che ho è questo esercizio, non capisco da dove tirar fuori quel +2.. devo aggiungercelo per via dei calcoli che mi portano a quello o ce lo aggiungo di testa mia? Questo non capisco. Se puoi gentilmente farmi vedere come lo hai risolto tu te ne sarei grato
 
Codice: 
f(n-1) = 1 + (-1)^(n-1)                      | vogliamo scrivere f(n) in funzione di f(n-1)
f(n) = 1 + (-1)^(n-1+1)                      | aggiungo e sottraggo 1 a n 
     = 1 + (-1)^(n-1) * (-1)                 | tiro fuori +1 dall'esponente (moltiplico per la base)
     = 1 + (-1)^(n-1) * (-1) - 1 + 1         | aggiungo e sottrggo 1 all'equazione
     = 1 + (1 + (-1)^(n-1)) * (-1) + 1       | cambio segno al -1 precedente e lo moltiplico per -1
     = 1 + f(n-1) * (-1) + 1                 | ecco che appare f(n-1)
     = 2 - f(n-1)                            | finito
 
  • Mi piace
Reazioni: jr_sottomajor
Ultima modifica:
St3ve ha detto:
Codice: 
f(n-1) = 1 + (-1)^(n-1)                      | vogliamo scrivere f(n) in funzione di f(n-1)
f(n) = 1 + (-1)^(n-1+1)                      | aggiungo e sottraggo 1 a n
     = 1 + (-1)^(n-1) * (-1)                 | tiro fuori +1 dall'esponente (moltiplico per la base)
     = 1 + (-1)^(n-1) * (-1) - 1 + 1         | aggiungo e sottrggo 1 all'equazione
     = 1 + (1 + (-1)^(n-1)) * (-1) + 1       | cambio segno al -1 precedente e lo moltiplico per -1
     = 1 + f(n-1) * (-1) + 1                 | ecco che appare f(n-1)
     = 2 - f(n-1)                            | finito
Clicca per espandere...
Ti ringrazio per la spiegazione.. in pratica hai sottratto e aggiunto 1 per raggirare il problema della soluzione finale che non si trovava (?) ora mi è chiaro
Messaggio unito automaticamente:

gaetanodigenio ha detto:
Ti ringrazio per la spiegazione.. in pratica hai sottratto e aggiunto 1 per raggirare il problema della soluzione finale che non si trovava (?) ora mi è chiaro
Clicca per espandere...
Diciamo che questo passaggio di sottrarre e aggiungere 1 lo si fa solo quando si vede che l'equazione finale non si troverebbe andando a fare i calcoli, nel senso che non è una cosa che si fa sempre giusto?..
 
gaetanodigenio ha detto:
Diciamo che questo passaggio di sottrarre e aggiungere 1 lo si fa solo quando si vede che l'equazione finale non si troverebbe andando a fare i calcoli, nel senso che non è una cosa che si fa sempre giusto?..
Clicca per espandere...
Ho fatto delle semplici manipolazioni algebriche finché non ho ottenuto una funzione ricorsiva. Non è sempre un processo meccanico, basta guardare Fibonacci per rendersene conto. Il tuo procedimento era sbagliato perché il -1 moltiplicava solo la parte destra, 1 + (-1)^(n-1) * (-1)^1 =/= f(n-1) * (-1)
 
Un suggerimento che posso darti, che può tornare utile in alcuni casi e in altri meno, è provare a vedere come si comporta la funzione ovvero vedere che valori assume. In questo particolare caso si nota subito che la funzione alterna per due valori e può portarci a fare delle utili considerazioni su come deve essere scritta la sua definizione ricorsiva.
Questo non è da intendersi come una pratica sistematica da adottare sempre ma come un misto fra euristica ed esperienza e deve essere affiancato e supportato da una buona dimostrazione algebrica.
 
  • Mi piace
Reazioni: jr_sottomajor
Ultima modifica:
Laempo ha detto:
Un suggerimento che posso darti, che può tornare utile in alcuni casi e in altri meno, è provare a vedere come si comporta la funzione ovvero vedere che valori assume. In questo particolare caso si nota subito che la funzione alterna per due valori e può portarci a fare delle utili considerazioni su come deve essere scritta la sua definizione ricorsiva.
Questo non è da intendersi come una pratica sistematica da adottare sempre ma come un misto fra euristica ed esperienza e deve essere affiancato e supportato da una buona dimostrazione algebrica.
Clicca per espandere...
Sisi infatti era quelloche avevo fatto, il mio problema stava nel farlo vedere tramite i vari passaggi..
Messaggio unito automaticamente:

Poi ho fatto un altro esercizio del tipo
F(n)= n(n+1) per n >=1
Passo base : f(1)= 2
Passo ricorsivo: ho riscritto f(n) come n^2+n.
Da cui f(n-1)= (n-1)^2+(n-1).
Quindi svolgendo i calcoli viene n^2 -2n +1 +n -1.
Ora 1 e -1 vanno via, raccolgo (n^2+n)-2n.
(n^2+n) sarebbe il mio f(n). Quindi scrivo f(n)= f(n-1) +2n (ho scritto il tutto in funzione di f(n) semplicemente)...
è giusto aver riscritto f(n) in un modo diverso o è sbagliato far così? Aiutatemi please
 
Ogni manipolazione è consentita finché questa sia corretta. Vorrei solo obiettare su due cose:
- il passaggio n^2 -2n + n --> (n^2 + n) - 2n non è un raccoglimento, semplicemente osservi che quella quantità è proprio f(n) e la riscrivi con quel simbolo;
- potrebbe essere contestato il tuo ultimo passaggio, in cui poni f(n) = f(n-1) + 2n e potrebbe non risultare chiaro il perché il segno di 2n è positivo.
 
Laempo ha detto:
Ogni manipolazione è consentita finché questa sia corretta. Vorrei solo obiettare su due cose:
- il passaggio n^2 -2n + n --> (n^2 + n) - 2n non è un raccoglimento, semplicemente osservi che quella quantità è proprio f(n) e la riscrivi con quel simbolo;
- potrebbe essere contestato il tuo ultimo passaggio, in cui poni f(n) = f(n-1) + 2n e potrebbe non risultare chiaro il perché il segno di 2n è positivo.
Clicca per espandere...
Si intendevo dire quello, non era un raccoglimento ma una sostituzione. L’ultimo passaggio è fatto così come mi è stato spiegato dalla prof, in cui parto da f(n-1)=f(n) + qualsiasi cosa e da lì riscrivo come f(n)= f(n-1) + quello che c’era dall’altro lato cambiato di segno
 
Ragazzi chiedo scusa, devo risolvere questo esercizio :
si consideri il seguente codice ricorsivo.
procedure funz(n)
if n=0 then return 1
else return funz(n-1)+3

a) determinare il valore di funz(5) mettendo in evidenza i passaggi che sono eseguiti nel calcolo ricorsivo.

questo punto è semplice e non ho problemi a farlo

b) Usare l'induzione matematica per provare che funz(n)=3n+1 per ogni intero n>=0.

questo punto non so proprio cosa devo fare.... funz(n) non restituisce funz(n-1)+3 quando n>0? Quindi dovrei porre quella quantità uguale a 3n+1? Non capisco cosa bisogna fare.. se riuscite a darmi una mano.. sicuro sarà una cretinata ma non so come impostarlo, grazie
 
Da quello che scrivi sembra che tu non abbia idea di come procedere a fare una dimostrazione per induzione. È la prima volta che ti è chiesto di farlo?

La dimostrazione per induzione non è assolutamente l'uguaglianza che hai scritto. Trovi abbondante materiale online circa teoria ed esercizi svolti.
Se riscontri problemi dopo aver provato a vedere degli esempi hai ancora difficoltà non esitare a scrivere.
 
Laempo ha detto:
Da quello che scrivi sembra che tu non abbia idea di come procedere a fare una dimostrazione per induzione. È la prima volta che ti è chiesto di farlo?

La dimostrazione per induzione non è assolutamente l'uguaglianza che hai scritto. Trovi abbondante materiale online circa teoria ed esercizi svolti.
Se riscontri problemi dopo aver provato a vedere degli esempi hai ancora difficoltà non esitare a scrivere.
Clicca per espandere...
Allora, io ho iniziato così:
PASSO BASE: funz(0): 3(0)+1=0+1=1
PASSO INDUTTIVO: funz(n) -> funz(n+1)
funz(n+1)= 3(n+1)+1 ......
finite le idee.
Sto procedendo correttamente o ho sbagliato proprio ad impostare?
 
L'impostazione fino ad ora è corretta. Adesso devi trovare un modo per esprimere f(n+1) in funzione di f(n), sapendo che f(n) = 3n + 1.
 
Sì, non mi pare ci sia altro. Questo è il tipo di esercizio che ti mette in difficoltà per la sua semplicità. Focalizzati sulla metodologia di risoluzione e non cadere in perplessità in caso di risultati "banali".
 
Per quanto riguarda invece questo esercizio sulle stringhe:
Si consideri l'insieme S di stringhe sull'alfabeto sigma={0,1} definito ricorsivamente come segue:
PB 1 appartiene a S
PR se w appartiene a S allora 1w0 appartiene a S e 0w1 appartiene a S.

Si definisca ricorsivamente la funzione
u(w)= numero di 1 presenti nella stringa w appartenente a S.

ho iniziato così:
PB u(alfa, cioè stringa vuota)=0
PR non so come impostarlo.
cioè mi verrebbe da scrivere u(w) -> u(1w0) e u(0w1) ma sicuro sto facendo l'ennesima cretinata.. chiedo di essere illuminato
 
Considerando che tutte le stringhe dell'insieme S sono necessariamente nella forma 1w0 e 0w1 direi che la tua idea non è assolutamente una cretinata.
Possiamo, inoltre, considerare interscambiabile la stringa 1w0 con 0w1 poiché contengono lo stesso numero di 1.
A fronte di questo l'impostazione che darei alla funzione u(w) sarebbe u(w) -> u(1s0) o (0s1) -sempre considerando che ai fini del conto in se non cambia nulla-
dove s è una sottostringa di w privata del'estremo sinistro e destro.
A questo punto come pensi di poter continuare se quanto scritto fin'ora ti sembra sensato?
 
È proprio necessario porre u(w)->u(1s0)?
Io ho posto u(w)-> u(1w0) and u(0w1)
Da qui, u(1w0)= u(w)+1 che è uguale a u(0w1).
Cioè, non sarebbe meglio fare un’impostazione più vicina possibile a quella che è la traccia? (Per dirla in altre parole, lasciamo stare le cose così come sono state date senza muovere nulla :D )
 
Per calcolare il numero di 1 nella stringa w immagino che siamo d'accordo che bisogni piano piano ridurla.
Se diciamo che u(w) -> u(1w0) aggiungiamo invece di togliere.

gaetanodigenio ha detto:
u(1w0)= u(w)+1 che è uguale a u(0w1)
Clicca per espandere...
A questo punto come come continui?
Il problema, secondo me, è che usando lo stesso simbolo ritengo difficile rendere l'idea di una diminuzione della lunghezza della stringa.
 

DISCUSSIONI SIMILI

I
Domanda Consiglio programmino
  • 18
  • 645
18
645
Python
luzzi
N
Discussione Process Hollowing + Process Injection con Python su Windows (davvero?)
  • 0
  • 330
0
330
Advanced Hacking
Netcat
G
Discussione Creare una codifica
  • 0
  • 194
0
194
Sicurezza Informatica
Goclau
L
Domanda Programma di gestione autostrada in C
  • 1
  • 394
1
394
C / C++
DispatchCode
B
Terminata Beruby - Fino a 5 euro di bonus benvenuto + cashback da acquisti
  • Chiuso
  • 4
  • 634
4
634
Guadagnare con Promozioni
Bonatz
Top Bottom
Indietro