Ricavarsi un'equazione di ricorrenza
Ciao a tutti! Tra un mesetto circa ho l'esame di algoritmi in java e mi rimane ancora da capire come posso ricavarmi un'equazione di ricorrenza da un codice Java!
Se c'è qualcuno che può darmi qualche dritta glie ne sarei grato! Ciao!
Se c'è qualcuno che può darmi qualche dritta glie ne sarei grato! Ciao!
Risposte
Normalmente io sono sempre partito dall'equazione di ricorrenza per poi implementarlo nel codice java. Potresti postare un codice dal quale non riesci a trovarla?
Veramente mi servirebbe capire come ricavarmela! Posso postare un codice stupido per esempio così da farmi capire come devo procedere!
Il problema è che a molti testi d'esame ci viene richiesto di ricavarci il miglio upper bound possibile in funzione della dimensione dell'input!
Grazie mille!
public static boolean presente(int a[], int k){
if(a.length <= 7){
for(int i = 0; i<a.length; i++){
if(a[i] == k)return true;
}
return false;
}
return presente(a, k, 0, a.length - 1);
}
private static boolean presente(int a[], int k, int up, int low){
if(up > low)return false;
if(a[up] == k || a[low] == k)return true;
return presente(a, k, up + 1, low - 1);
}
Il problema è che a molti testi d'esame ci viene richiesto di ricavarci il miglio upper bound possibile in funzione della dimensione dell'input!
Grazie mille!
Nella prima funzione se la lunghezza dell'array è minore o uguale a 7 fa una ricerca lineare di k nell'array, in caso contrario richiama la seconda funzione. Questa invece di considerare tutto l'array ne considera solo una parte e cerca il valore negli estremi. Se non viene trovato restringe ulteriormente la parte considerata finché è stato trovato il valore oppure è stato analizzato l'array. Mi viene difficile scrivere un'equazione per questo tipo di funzione che non sia praticamente identico alla funzione originale in Java. Quali sono le difficoltà che incontri esattamente?
Continuo a chiedermi perché quasi tutti gli esercizi che ho visto in giro sono praticamente inutili (come questo) o del tutto elementari (come un fattoriali) o completamente inefficienti (come il calcolo della serie di fibonacci senza memorizzazione dei valori).
Continuo a chiedermi perché quasi tutti gli esercizi che ho visto in giro sono praticamente inutili (come questo) o del tutto elementari (come un fattoriali) o completamente inefficienti (come il calcolo della serie di fibonacci senza memorizzazione dei valori).
Be questo non è un esercizio d'esame l'ho scritto io 5 minuti prima per cercare di capirci su qualcosa sopra e poi passare ad algoritmi complessi tipo quickSort e mergeSort!
La mia difficoltà sta nel ricavarmi il miglior upper bound di un algoritmo e pensavo che avendo una padronanza nello scrivere equazioni di ricorrenza e saperle risolvere sarei riuscito nel mio intento!
La mia difficoltà sta nel ricavarmi il miglior upper bound di un algoritmo e pensavo che avendo una padronanza nello scrivere equazioni di ricorrenza e saperle risolvere sarei riuscito nel mio intento!
Non sono certo che abbia senso parlare di equazione di ricorrenza in un caso come il tuo. Sono solito utilizzarle nel caso di successioni. Ma qui non c'è nessuna successione. Non mi è inoltre del tutto chiaro che cosa intendi con miglior upper bound del tuo algoritmo...
Con upper bound intendiamo l'algoritmo migliore sufficiente per svolgere un compito!
Mi sembra molto strano che venga fatta questa richiesta a partire da un codice Java. Sei certo che la tua definizione sia esatta?
Allora questo è il testo di un esercizio d'esame di Algoritmi e Struture dati! Lo riporto pari pari!
Con riferimento all'algoritmo mistero1, determinare il miglior upper bound possibile, in funzione della dimensione dell'input! Assumere n > 0
qui il testo di un codice!
La definizione di upper bound presa dal libro "Linguaggi, modelli e complessità"
".....quantità di risorse necessarie (lower bound) e/o sufficienti (upper bound) per risolvere i vari problemi!"
Tu per upper bound cosa intendi?
Con riferimento all'algoritmo mistero1, determinare il miglior upper bound possibile, in funzione della dimensione dell'input! Assumere n > 0
qui il testo di un codice!
La definizione di upper bound presa dal libro "Linguaggi, modelli e complessità"
".....quantità di risorse necessarie (lower bound) e/o sufficienti (upper bound) per risolvere i vari problemi!"
Tu per upper bound cosa intendi?
La definizione che avevi dato in precedenza non sembra essere in accordo con quella del tuo libro. Io sono principalmente un matematico e non riuscivo a legare il significato che hanno in matematica con quello da te descritto. Con la definizione del libro ha un po’ più senso anche se avrei preferito poter leggere tutta la frase. Su internet ho comunque trovato altre definizione che secondo me sono migliori (la definizione del tuo libro rimane a mio parere un po’ ambigua).
Se non inserisci l’algoritmo mistero1 al quale l'esercizio fa riferimento non saprei come aiutarti o cosa dirti su quell'esercizio. Riesci a postarlo? Hai degli esercizi già risolti di esempio?
Se non inserisci l’algoritmo mistero1 al quale l'esercizio fa riferimento non saprei come aiutarti o cosa dirti su quell'esercizio. Riesci a postarlo? Hai degli esercizi già risolti di esempio?
public static long mistero1(int n){
return mistero2(n, n);
}
public static long mistero2(int n, int k)}
if(k == 1) return 1;
long c = 0;
for(int i = n - k; i< n; i++){
c += mistero2(n , k-1);
}
return c;
}Questo è un esercizio di un tema d'esame!
Inizio cercando di scrivere l’equazione di ricorrenza. Per comodità indico con $M_{n,k}$ il risultato della funzione mistero2(n,k).
$M_{n,1} = 1$
$M_{n,k} = \sum_{i = n - k}^{n - 1} M_{n,k-1} = k*M_{n,k-1}$
Come si può facilmente osservare la funzione calcola $n!$. L’algoritmo presentato è molto inefficiente e consiste in pratica nel sommare $1$ $n!$ volte. Con dimensione dell’input che intendi in questo caso? Il numero di bit? Il valore di n?
$M_{n,1} = 1$
$M_{n,k} = \sum_{i = n - k}^{n - 1} M_{n,k-1} = k*M_{n,k-1}$
Come si può facilmente osservare la funzione calcola $n!$. L’algoritmo presentato è molto inefficiente e consiste in pratica nel sommare $1$ $n!$ volte. Con dimensione dell’input che intendi in questo caso? Il numero di bit? Il valore di n?
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo