Calcolo eq. ricorrenza stringa
Ciao 
dopo aver "seguito" un corso rapido con apatriarca, mi sono buttato a fare gli esercizi che chiedono di trovare un'equazione di ricorrenza. Come al solito, sto andando in confusione...
"Determinare un'equazione di ricorrenza per il numero di stringhe decimali di lunghezza n che contengono un numero dispari di zeri".
Di seguito illustro il mio ragionamento. Sono gradite critiche e suggerimenti al fine di migliorare e capire come vanno fatti questi esercizi (non nascondo che mi mettono in ampia difficoltà).
- numero di stringhe decimali di lunghezza n ==> $10^n$
Uso la formula $S(n) = 10^n - T(n)$ partendo da T(n)
Stringhe che non contengono un numero dispari di zeri: 1,2,3,4,5,6,7,8,9
Calcolo T(n):
$T(n) = T(n-1) + T(n-2) + T(n-3) + T(n-4) + T(n-5) + T(n-6) + T(n-7) + T(n-8) + T(n-9)$
$S(n) = 10^n - T(n) = 10^n - T(n-1) - T(n-2) - T(n-3) - T(n-4) - T(n-5) - T(n-6) - T(n-7) - T(n-8) - T(n-9)$
$S(n) = 10^n - (10^(n-1) - S(n-1)) - (10^(n-2) - S(n-2)) - (10^(n-3) - S(n-3)) - (10^(n-4) - S(n-4)) - (10^(n-5) - S(n-5)) - (10^(n-6) - S(n-6)) - (10^(n-7) - S(n-7)) - (10^(n-8) - S(n-8)) - (10^(n-9) - S(n-9))$
Uhm, non so quanto possa essere giusto...spero che qualcuno mi aiuti a capire se sia corretto o meno (l'unico esercizio fatto considerava stringhe binarie...forse là la questione era più semplice
)
dopo aver "seguito" un corso rapido con apatriarca, mi sono buttato a fare gli esercizi che chiedono di trovare un'equazione di ricorrenza. Come al solito, sto andando in confusione...
"Determinare un'equazione di ricorrenza per il numero di stringhe decimali di lunghezza n che contengono un numero dispari di zeri".
Di seguito illustro il mio ragionamento. Sono gradite critiche e suggerimenti al fine di migliorare e capire come vanno fatti questi esercizi (non nascondo che mi mettono in ampia difficoltà).
- numero di stringhe decimali di lunghezza n ==> $10^n$
Uso la formula $S(n) = 10^n - T(n)$ partendo da T(n)
Stringhe che non contengono un numero dispari di zeri: 1,2,3,4,5,6,7,8,9
Calcolo T(n):
$T(n) = T(n-1) + T(n-2) + T(n-3) + T(n-4) + T(n-5) + T(n-6) + T(n-7) + T(n-8) + T(n-9)$
$S(n) = 10^n - T(n) = 10^n - T(n-1) - T(n-2) - T(n-3) - T(n-4) - T(n-5) - T(n-6) - T(n-7) - T(n-8) - T(n-9)$
$S(n) = 10^n - (10^(n-1) - S(n-1)) - (10^(n-2) - S(n-2)) - (10^(n-3) - S(n-3)) - (10^(n-4) - S(n-4)) - (10^(n-5) - S(n-5)) - (10^(n-6) - S(n-6)) - (10^(n-7) - S(n-7)) - (10^(n-8) - S(n-8)) - (10^(n-9) - S(n-9))$
Uhm, non so quanto possa essere giusto...spero che qualcuno mi aiuti a capire se sia corretto o meno (l'unico esercizio fatto considerava stringhe binarie...forse là la questione era più semplice
)
Risposte
Qui credo che l'idea migliore sia quella di calcolare in contemporanea il numero di stringhe con un numero pari di zeri \(P(n)\) e quello con un numero dispari di zeri \(D(n)\). Ogni stringa con un numero dispari di zeri può infatti essere costruita aggiungendo uno zero alla fine di una stringa con un numero pari di zeri oppure aggiungendo un numero diverso da zeri ad una stringa che contiene già un numero dispari di zeri. Lo stesso discorso vale per le stringhe che contengono un numero pari di zeri. La stringa nulla ha un numero pari di zeri, per cui \(P(0) = 1\) e \(D(0) = 0\). Per cui hai qualcosa come il seguente:
\[ D(n) = P(n-1) + 9\,D(n-1), \quad P(n) = D(n-1) + 9\,P(n-1). \]
A seconda di quello che il tuo professore desidera da te questo potrebbe già essere un punto di arrivo. Alternativamente puoi sempre osservare che la somma dei due insiemi è il numero totale di stringhe decimali di \(n\) caratteri e quindi \( P(n) = 10^n - D(n)\) da cui
\[ D(n) = 10^{n-1} - D(n-1) + 9\,D(n-1) = 8\,D(n-1) + 10^{n-1}. \]
\[ D(n) = P(n-1) + 9\,D(n-1), \quad P(n) = D(n-1) + 9\,P(n-1). \]
A seconda di quello che il tuo professore desidera da te questo potrebbe già essere un punto di arrivo. Alternativamente puoi sempre osservare che la somma dei due insiemi è il numero totale di stringhe decimali di \(n\) caratteri e quindi \( P(n) = 10^n - D(n)\) da cui
\[ D(n) = 10^{n-1} - D(n-1) + 9\,D(n-1) = 8\,D(n-1) + 10^{n-1}. \]
Oh, cavolo...ero proprio fuori strada 
comunque noto che non c'é un metodo generale, bisogna fare esperienza 
mi toccheranno un sacco di esercizi XD
Non mi faccio mancare una piccola domandina (te pareva, dirai XD)
A cosa é dovuto $-D(n-1)$? non capisco perché lo sottrai ne cosa rappresenta... Mentre invece $9D(n-1)$ rappresenta i caratteri...
NB. forse $-D(n-1)$? Rappresenta la stringa nulla, ma attendo chiarimenti
Intanto grazie per il tuo tempo e la spiegazione
Comunque si, la soluzione che desidera il mio prof é la seconda...quella di cui ti chiedo sopra chiarimenti!!
comunque noto che non c'é un metodo generale, bisogna fare esperienza mi toccheranno un sacco di esercizi XDNon mi faccio mancare una piccola domandina (te pareva, dirai XD)
A cosa é dovuto $-D(n-1)$? non capisco perché lo sottrai ne cosa rappresenta... Mentre invece $9D(n-1)$ rappresenta i caratteri...
"apatriarca":
\[ D(n) = 10^{n-1} - D(n-1) + 9\,D(n-1) = 8\,D(n-1) + 10^{n-1}. \]
NB. forse $-D(n-1)$? Rappresenta la stringa nulla, ma attendo chiarimenti
Intanto grazie per il tuo tempo e la spiegazione
Comunque si, la soluzione che desidera il mio prof é la seconda...quella di cui ti chiedo sopra chiarimenti!!
Siccome \(D(n-1) + P(n-1) = 10^{n-1},\) puoi fare la sostituzione \( P(n-1) = 10^{n-1} - D(n-1). \) Non esiste infatti un metodo generale (e molti esercizi possono essere risolti con metodi e probabilmente anche risultati diversi).
Grazie, ora è più chiaro 
Appena riesco faccio un altro esercizio e vedo cosa mi esce fuori XD
Appena riesco faccio un altro esercizio e vedo cosa mi esce fuori XD
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo