Equazione di ricorrenza
ciao tutti,
sto continuando a fare esercizi sulle equazioni di ricorrenza, ma continuo a riscontrare problemi. Pazzesco!! Sembra che non ci sia modo di farle entrare in testa XD Non so cosa dire
ve la sottopongo nella speranza di uscirne e arrivare a una soluzione.
"determinare una eq. Di ricorrenza per il numero delle stringhe decimali prive di zeri consecutivi".
Mio ragionamento: la stringa può iniziare con un qualsiasi valore (0/1). Uno zero può essere seguito sia da 1 che da un altro zero...il caso che interessa a noi!!
É giusto questo ragionamento?
io poi sono arrivato alla conclusione che la stringa da me cercata é $S(n) = 10^n + T(n-1)$ dove $t(n-1)$ é il caso in cui la stringa abbia due zeri consecutivi.
Cosa ne pensate? Spero non sia sbagliato come sempre...XD
spero in un aiutino e una spiegazione sugli eventuali errori commessi
grazie
sto continuando a fare esercizi sulle equazioni di ricorrenza, ma continuo a riscontrare problemi. Pazzesco!! Sembra che non ci sia modo di farle entrare in testa XD Non so cosa dire
ve la sottopongo nella speranza di uscirne e arrivare a una soluzione.
"determinare una eq. Di ricorrenza per il numero delle stringhe decimali prive di zeri consecutivi".
Mio ragionamento: la stringa può iniziare con un qualsiasi valore (0/1). Uno zero può essere seguito sia da 1 che da un altro zero...il caso che interessa a noi!!
É giusto questo ragionamento?
io poi sono arrivato alla conclusione che la stringa da me cercata é $S(n) = 10^n + T(n-1)$ dove $t(n-1)$ é il caso in cui la stringa abbia due zeri consecutivi.Cosa ne pensate? Spero non sia sbagliato come sempre...XD
spero in un aiutino e una spiegazione sugli eventuali errori commessi
grazie
Risposte
Non mi sembra che il tuo ragionamento abbia senso.. Stiamo parlando di stringhe decimali, per cui di certo il primo valore non è limitato a 0 e 1. E se ti interessano le stringhe senza zeri consecutivi, che vuol dire "Uno zero può essere seguito sia da 1 che da un altro zero..." ? Questa non è di certo una descrizione adatta al problema. Infine immagino che nella tua formula ci debba essere una sottrazione e non una somma. Se devo essere sincero, l'impressione è che tu stia cercando di applicare in modo meccanico uno dei metodi che hai visto fino ad ora senza ragionare più di tanto.
L'idea di base di dividere la prima lettera dal resto va bene, ma non è ovviamente corretto il ragionamento su quali valori può avere. Che valori può assumere il primo simbolo di una stringa decimale? Se questo simbolo è uguale a zero, cosa puoi dire del simbolo successivo se non ci possono essere due zeri adiacenti? Cosa puoi dire del resto della stringa? E se invece il primo simbolo è diverso da zero? Cosa puoi dire del resto della stringa?
uhm, effettivamente sto applicando un ragionamento meccanico...osservando e cercando di capire gli esercizi (e i pochi appunti) precedenti.
Uhm, hai ragione. Allora considerando una stringa decimale, posso dire che i valori iniziali possono andare da 0 a 9. Ecco che quindi mi si presenta un bivio: nel caso in cui il valore iniziale sia zero e venga seguito da un altro zero ho il caso che mi interessa non si verifichi. Piu complesso se la stringa inizia per un valore diverso da zero...in quel caso puo' essere seguita da un valore diverso o uguale a zero (e in questo caso si ricade nel caso precedente, con la possibilità dopo ci sia uno zero o un valore differente). Ora mi sembra più corretto
quindi potrei dire che nel caso in cui considero un valore iniziale diverso da zero, ottengo $S(n) = 10^n -T(n-1) - T(n-2)$. Mi sono basato sul fatto che la stringa può essere composta da 10 valori diversi (da qui il $10^n$ e che due di questi sono da scartare. In questo caso ho considerato $t(n-1)$ il caso in cui mi capiti uno zero e $t(n-2)$ il caso in cui mi capiti lo zero consecutivo.
Cosa ne pensi ora? Non mi aspetto sia totalmente corretto, ma almeno di aver centrato il problema
Uhm, hai ragione. Allora considerando una stringa decimale, posso dire che i valori iniziali possono andare da 0 a 9. Ecco che quindi mi si presenta un bivio: nel caso in cui il valore iniziale sia zero e venga seguito da un altro zero ho il caso che mi interessa non si verifichi. Piu complesso se la stringa inizia per un valore diverso da zero...in quel caso puo' essere seguita da un valore diverso o uguale a zero (e in questo caso si ricade nel caso precedente, con la possibilità dopo ci sia uno zero o un valore differente). Ora mi sembra più corretto
quindi potrei dire che nel caso in cui considero un valore iniziale diverso da zero, ottengo $S(n) = 10^n -T(n-1) - T(n-2)$. Mi sono basato sul fatto che la stringa può essere composta da 10 valori diversi (da qui il $10^n$ e che due di questi sono da scartare. In questo caso ho considerato $t(n-1)$ il caso in cui mi capiti uno zero e $t(n-2)$ il caso in cui mi capiti lo zero consecutivo.
Cosa ne pensi ora? Non mi aspetto sia totalmente corretto, ma almeno di aver centrato il problema
Che cosa sono esattamente \(T(n-1)\) e \(T(n-2)\) ? Nella tua descrizione non è molto chiaro. Inoltre non credo che in questo caso ci sia bisogno di riscrivere l'equazione "in negativo" (nel senso di togliere i casi in cui ci sono almeno due zeri consecutivi). Considera infatti che se la stringa non inizia con uno zero, il resto è di nuovo una stringa che non contiene due zeri consecutivi, ma di lunghezza \(n-1\). Se invece c'è uno zero, il secondo simbolo deve essere un numero da uno a nove e il resto sarà di nuovo una stringa senza zeri consecutivi qualsiasi, ma di lunghezza \(n-2\). Per cui alla fine puoi scrivere qualcosa come \( S(n) = 9\,(S(n-1) + S(n-2)) \).
uhm, credo di aver capito. In effetti il tuo ragionamento é molto piu semplice e funzionale. Non ci avevo pensato
ma se volessi per esempio riscrivere l'equazione trovata in maniera diversa? Magari evidenziando il fatto che sia decimale (es. Mettendo $10^n)... Un po' come abbiamo fatto quando mi hai spiegato i casi con stringhe binarie...mettavamo sempre “2^n”. É possibile anche con questo caso fare qualcosa di simile? In quella forma si riesce a capirle meglio queste eq...
ma se volessi per esempio riscrivere l'equazione trovata in maniera diversa? Magari evidenziando il fatto che sia decimale (es. Mettendo $10^n)... Un po' come abbiamo fatto quando mi hai spiegato i casi con stringhe binarie...mettavamo sempre “2^n”. É possibile anche con questo caso fare qualcosa di simile? In quella forma si riesce a capirle meglio queste eq...
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo