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 O(n)
Motivare BENE la correttezza e la complessità dell'algoritmo 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
L'algoritmo proposto deve avere complessità O(n^2) * S(n)
ESERCIZIO 3
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 e la sottosequenza più lunga è 51020
Per S = 136131718 la risposta è 4 e la sottosequenza più lunga è 13618
Progettare un algoritmo che risolve il problema in tempo O(n^2)
ESERCIZIO 4
Progettare un algoritmo che data una stringa X lunga n sull'alfabeto 012 stampa
tutte le stringhe lunghe n sull'alfabeto 012 che differiscono da X in ciascuna
posizione e non hanno simboli adiacenti uguali
Ad esempio per X = 2001 l'algoritmo deve stampare non necessariamente nello stesso
ordine le seguenti 5 stringhe:
0210 0212 0120 1210 1212
L'algoritmo proposto deve avere complessità O(n)S(n) dove S(n) è il numero di stringhe
da stampare.
ESERCIZIO 5
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 risposta 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 O(n)
Motivare BENE la correttezza e la complessità dell'algoritmo proposto
ESERCIZIO 5
Progettare un algoritmo che dato un intero n stampa tutte le matrici binarie nxn con
la proprietà che nella riga i_0... i_n della matrice sono presenti esattamente i uni
L'algoritmo proposto deve avere complessit O(n^2) S(n) dove S(n) è il numero di matrici
da stampare
n = 3 -> 9
ESERCIZIO 6
Abbiamo due interi k ed n con 1 < k < n Vogliamo sapere quanti diversi modi ci sono di
partizionare l'insieme dei primi n interi in k sottoinsiemi
Ad esempio per k = 2 ed n = 3 l'algoritmo 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
O(n)(k)
ESERCIZIO 7
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 l'algoritmo
ordine le seguenti 6 stringhe
deve stampare non necessariamente nello stesso
1111 1010 1001 0110 0101 0000
L'algoritmo proposto deve avere complessit O(n)S(n) dove S(n) è il numero di stringhe
da stampare
ESERCIZIO 8
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
per S = 010010 la risposta deve essere 8
Progettare un algoritmo che risolve il problema in tempo O(n)
Motivare BENE la correttezza e la complessità dell'algoritmo proposto
ESERCIZIO 9
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 l'algoritmo deve stampare non necessariamente nello stesso ordine le seguenti 8 stringhe
0000 0001 0010 0011 0100 1000 1001 11001
L'algoritmo proposto deve avere complessit O(n)S(n) k dove S(n) k il numero di
stringhe da stampare
Motivare BENE la correttezza e la complessità dell'algoritmo proposto
ESERCIZIO 10
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 somma da i=1 a n=12
Dato un intero positivo n vogliamo scoprire qual il numero minimo di quadrati
necessari ad ottenere n
Ad esempio
- per n = 100 la risposta è 1 infatti 10^2 Nota che vale anche
100 = 5^2 + 5^2 + 5^2 + 5^2 ma questa scomposizione usa 4 quadrati e non
minimale Analogamente non è minimale la scomposizione 10 = 8^2 + 6^2
che usa 2 quadrati
Scrivere lo pseudocodice di un algoritmo che risolve il problema in tempo ...
ESERCIZIO 11
Progettare un algoritmo che dato un intero n stampa tutte le stringhe binarie
di lunghezza 2^n tali che il numero di zeri presenti nella prima metà della stringa
è inferiore o uguale al numero di uni presenti nella seconda metà
L'algoritmo proposto deve avere complessit O(n)S(n) dove S(n) è il numero
di stringhe da stampare
Ad esempio per n = 2 l'algoritmo 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 12
Dati tre interi positivi n m e k con 1 < m < k < n vogliamo calcolare il numero di
stringhe lunghe n sull'alfabeto 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
O(n*m*k)
ESERCIZIO 13
Progettare un algoritmo che dato un intero n stampa tutte le stringhe di lunghezza 2^n
sull'alfabeto 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 l'algoritmo ordine le seguenti 33 stringhe deve stampare non necessariamente nello stesso ordine
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
L'algoritmo proposto deve avere complessit O(n)S(n) dove S(n) è il numero di stringhe
da stampare
ESERCIZIO 14
Progettare un algoritmo che data una stringa X lunga n sull'alfabeto 012 stampa
tutte le stringhe lunghe n sull'alfabeto 012 che concordano con la stringa X in
esattamente una posizione
Ad esempio per X = 200 l'algoritmo deve stampare non necessariamente nello stesso
ordine le seguenti 12 stringhe
110 101 102 120 010 001 002 020 211 212 221 222
L'algoritmo proposto deve avere complessit O(n)S(n) dove S(n) è il numero di stringhe
da stampare