Lista esercizi algo2
ESERCIZIO 1 Dato un intero n con n 2 vogliamo contare il numero di modi in cui possibile ottenere n partendo dal numero 2 e potendo effettuare le sole 3 operazioni di incremento di 1 prodotto per 2 e prodotto per 3 Ad esempio per n 10 la risposta 9 Infatti le sequenze possibili sono 2345678910 234510 2348910 23678910 23910 24510 245678910 248910 2678910 Progettare un algoritmo che risolve il problema in tempo On Motivare BENE la correttezza e la complessit dellalgoritmo proposto
ESERCIZIO 2 Progettare un algoritmo che dato un intero n stampa tutte le matrici binarie quadrate n n dove il numero di zeri presenti in ciascuna colonna minore o uguale al numero di uni della colonna
Lalgoritmo proposto deve avere complessit On2Sn
ESERCIZIO 1 Data una sequenza S crescente di n interi vogliamo trovare la lunghezza massima per le sottosequenze di S dove ciascun elemento divisore del successivo Ad esempio per S 351020 la risposta 3 la sottosequenza pi lunga 51020 Per S 136131718 la risposta 4 la sottosequenza pi lunga 13618 Progettare un algoritmo che risolve il problema in tempo On2
ESERCIZIO 2 Progettare un algoritmo che data una stringa X lunga n sullalfabeto 012 stampa tutte le stringhe lunghe n sullalfabeto 012 che differiscono da X in ciascuna posizione e non hanno simboli adiacenti uguali Ad esempio per X 2001 lalgoritmo deve stampare non necessariamente nello stesso ordine le seguenti 5 stringhe 0210 0212 0120 1210 1212 Lalgoritmo proposto deve avere complessit OnSn dove Sn il numero di stringhe da stampare
ESERCIZIO 1 Data una sequenza S di n cifre decimali vogliamo calcolare la lunghezza massima per una sottosequenza non decrescente che contiene i tre simboli 0 1 e 2 Ad esempio per S 506722101 la risposte deve essere 0 non esistono infatti in S sottosequenze nondecrescenti che contengono i tre simboli 0 1 e 2 per S 01256141222152 la risposta deve essere 8 infatti la sottosequenza non decrescente pi lunga con tutti e tre i simboli 01 11222 2 Progettare un algoritmo che risolve il problema in tempo On Motivare BENE la correttezza e la complessit dellalgoritmo proposto
ESERCIZIO 2 Progettare un algoritmo che dato un intero n stampa tutte le matrici binarie n ncon la propriet che nella riga i 0 i n della matrice sono presenti esattamente i uni Lalgoritmo proposto deve avere complessit On2 Sn dove Sn il numero di matrici da stampare
n 3 9
ESERCIZIO 1 Abbiamo due interi k ed n con 1 k n Vogliamo sapere quanti diversi modi ci sono di partizionare linsieme dei primi n interi in k sottoinsiemi Ad esempio per k 2 ed n 3 lalgoritmo deve restituire 3 possiamo infatti partizionare i 3 interi in due sottoinsiemi nei modi seguenti 12 3 1 23 13 2 Progettare un algoritmo che risolve il problema in tempo On k
ESERCIZIO 2 Progettare un algoritmo che dato un intero n stampa tutte le stringhe binarie di lunghezza 2 n tali che il numero di uni presenti nella prima met della stringa lo stesso del numero di uni presenti nella seconda met Ad esempio per n 2 lalgoritmo ordine le seguenti 6 stringhe deve stampare non necessariamente nello stesso 1111 1010 1001 0110 0101 0000 Lalgoritmo proposto deve avere complessit OnSn dove Sn il numero di stringhe da stampare
ESERCIZIO 1 Data una stringa binaria presenti nella sequenza S vogliamo contare il numero di diverse coppie 01 Ad esempio per S 1110100 la risposte deve essere 1 abbiamo infatti 01 p e r S 010010 l a r i s p o s t a d e v e e s s e r e 8 a b b i a m o i n f a t t i 01 01 01 e 01 Progettare un algoritmo che risolve il problema in tempo On Motivare BENE la correttezza e la complessit dellalgoritmo proposto
ESERCIZIO 2 Progettare un algoritmo che dati due interi n e k stampa tutte le stringhe binarie di lunghezza n in cui siano presenti almeno k zeri consecutivi Utilizziamo un algoritmo di backtracking per la stampa di tutte le stringhe binarie sol di lunghezza n con laggiunta di funzioni di taglio Ad esempio per n 4 e k 2 lalgoritmo deve stampare non necessariamente nello stesso ordine le seguenti 8 stringhe 0000 0001 0010 0011 0100 1000 1001 11001 Lalgoritmo proposto deve avere complessit OnSn k dove Sn k il numero di stringhe da stampare Motivare BENE la correttezza e la complessit dellalgoritmo proposto
ESERCIZIO 1 Un numero intero positivo pu sempre essere rappresentato come somma di quadrati di altri numeri interi Ad esempio il generico numero n pu scomporsi come somma di n addendi tutti uguali a 12 vale a dire sommda i1 a n 12 Dato un intero positivo n vogliamo scoprire qual il numero minimo di quadrati necessari ad ottenere n Ad esempio a per n 100 la risposta 1 infatti 100 102 Nota che vale anche 100 52 52 52 52 ma questa scomposizione usa 4 quadrati e non minimale Analogamente non minimale la scomposizione 100 82 62 che usa 2 quadrati b per n 6 la risposta 3 infatti 6 22 12 12 e non difficile vedere che 6 non pu esprimersi come somma di due soli quadrati Scrivere lo pseudocodice di un algoritmo che risolve il problema in tempo On32
ESERCIZIO 2 Progettare un algoritmo che dati tre interi positivi n m e k con 1 m k n stampa tutte le stringhe ternarie lunghe n sullalfabeto 012 dove il numero di occorrenze di 1 non supera m ed il numero di occorrenze di 2 non supera k Lalgoritmo proposto deve avere complessit On Sn m k dove Sn n k il numero di stringhe da stampare Ad esempio per n 3 m 1 e k 2 lalgoritmo deve stampare non necessariamente nello stesso ordine le seguenti 19 stringhe 000 001 002 010 012 020 021 022 100 102 120 122 200 201 202 210 212 220 221
ESERCIZIO 2 Progettare un algoritmo che dato un intero n stampa tutte le stringhe binarie di lunghezza 2n tali che il numero di zeri presenti nella prima met della stringa inferiore o uguale al numero di uni presenti nella seconda met Lalgoritmo proposto deve avere complessit OnSn dove Sn il numero di stringhe da stampare Ad esempio per n 2 lalgoritmo deve stampare non necessariamente nello stesso ordine le seguenti 11 stringhe 0011 0101 0110 0111 1001 1010 1011 1100 1101 1110 1111 Motivare BENE la correttezza e la complessit del vostro algoritmo
ESERCIZIO 1 Dati tre interi positivi n m e k con 1 m k n vogliamo calcolare il numero di stringhe lunghe n sullalfabeto 012 dove il numero di occorrenze di 1 non supera m ed il numero di occorrenze di 2 non supera k Ad esempio per n 3 m 1 e k 2 il numero 19 ternarie lunghe 3 con al pi un 1 ed al pi due 2 sono Infatti le sole stringhe 000 001 002 010 012 020 021 022 100 102 120 122 200 201 202 210 212 220 221 Progettare un algoritmo che risolve il problema in tempo On m k
ESERCIZIO 2 Progettare un algoritmo che dato un intero n stampa tutte le stringhe di lunghezza 2 n sullalfabeto 123 tali che il numero di cifre dispari presenti nella prima met della stringa lo stesso del numero di cifre dispari presenti nella seconda met Ad esempio per n 2 lalgoritmo ordine le seguenti 33 stringhe deve stampare non necessariamente nello stesso 1111 1113 1131 1133 1221 1223 1212 1232 1311 1313 1331 1333 2121 2123 2112 2132 2222 2321 2323 2312 2332 3111 3113 3131 3133 3221 3223 3212 3232 3311 3313 3331 3333 Lalgoritmo proposto deve avere complessit OnSn dove Sn il numero di stringhe da stampare
ESERCIZIO 2 Progettare un algoritmo che data una stringa X lunga n sullalfabeto 012 stampa tutte le stringhe lunghe n sullalfabeto 012 che concordano con la stringa X in esattamente una posizione Ad esempio per X 200 lalgoritmo deve stampare non necessariamente nello stesso ordine le seguenti 12 stringhe 110 101 102 120 010 001 002 020 211 212 221 222 Lalgoritmo proposto deve avere complessit OnSn dove Sn il numero di stringhe da stampare