Homework2 < Programmazione1

Homework 2

Implementare una funzione int *findwords(int n, char L[n][n], char *W[], int nw) che prende in input una matrice L di nxn caratteri alfabetici maiuscoli ('A','B',...,'Z') e un vettore W di nw stringhe (ognuna delle quali contiene una parola in lettere maiuscole), e ritorna un vettore C, allocato dinamicamente, che per ogni parola del vettore W conta il numero di volte che appare nella matrice L scritta in orizzontale o in verticale. Quindi, il vettore ritornato C deve avere dimensione nw e per ogni i, C[i] deve essere uguale al numero di volte che la parola W[i] appare in L. Ad esempio, se n = 10, la matrice L e il vettore W (nw = 4) sono:
```
    matrice L                       vettore W
L B A R B A R B A C                 0 "LUNA"
G U O V B L U N A L                 1 "BARBA"
C H N N D U B N T R                 2 "BARBE"
B A R A I N H T U V                 3 "LUNARE"
W B A R B A I U V X
Y Z Z A V I L L M Y
N N T L R M M C C B
K J L U N A R E D G
J G H N N M I U T R
B B R A D O A N U L
```
allora la funzione ritorna il vettore C = [4, 3, 0, 1]. Qui sotto le occorrenze delle parole di W in L sono evidenziate in grassetto:
```
L B A R B A R B A C
G U O V B L U N A L
C H N N D U B N T R
B A R A I N H T U V
W B A R B A I U V X
Y Z Z A V I L L M Y
N N T L R M M C C B
K J L U N A R E D G
J G H N N M I U T R
B B R A D O A N U L
```
Domande & risposte

Le parole vanno cercate anche da destra verso sinistra e dal basso verso l'alto?

No, le parole vanno cercate (come nei tradizionali cruciverba) disposte solo da sinistra a destra e dall'alto verso il basso.
La figura sopra ha anche un esempio di questo: si consideri la sequenza "LUNA" che inizia nell'angolo inferiore destro della matrice e si sviluppa verso sinistra. Questa sequenza non va considerata una occorrenza della parola "LUNA" nella matrice.

Nel 1982 Albert Wilansky, un matematico della Lehigh University, notò che il numero di telefono (4937775) di suo genero Harold Smith aveva una sorprendente proprietà: la somma delle cifre del numero era uguale alla somma delle cifre dei suoi fattori primi. Infatti, 4 + 9 + 3 + 7 + 7 + 7 + 5 = 42, i fattori primi di 4937775 sono 3, 5, 5 e 65837 (cioè, 74937775 = 3x5x5x65837) e la somma delle loro cifre è 3 + 5 + 5 + 6 + 5 + 8 + 3 + 7 = 42. Wilansky fu così colpito da questa scoperta che decise di chiamare numeri di Smith i numeri che hanno questa sorprendente proprietà. Ecco altri esempi di numeri di Smith: 4, 22, 27, 58, 85, 94, 121, 166, 202, 265 (4 = 2 + 2, 2 + 2 = 2 + 1 + 1, 2 + 7 = 3 + 3 + 3, 5 + 8 = 2 + 2 + 9, 8 + 5 = 5 + 1 + 7, 9 + 4 = 2 + 4 + 7, 1 + 2 + 1 = 1 + 1 + 1 + 1, ecc.). Per saperne di più si può consultare la pagina di wikipedia sui numeri di Smith.
Implementare una funzione int issmithnumber(long long n) che controlla se n è un numero di Smith. Se lo è ritorna la somma delle sue cifre, altrimenti ritorna 0.

Domande & risposte

I numeri primi sono numeri di Smith?

I numeri primi soddisfano banalmente la proprietà descritta sopra. Tuttavia, secondo la definizione ufficiale (e proprio per questo) i numeri primi non sono considerati numeri di Smith (v. ad es., Wikipedia).
Ad esempio: 13 è è un numero primo, quindi la somma delle sue cifre (1+3=4) è uguale (banalmente) alla somma delle cifre della sua fattorizzazione, visto che quest'ultima (essendo 13 primo) è 13 stesso!
Tuttavia, 13, essendo numero primo, non è considerato numero di Smith.

Si chiarisce quindi di fare in modo che la funzione prodotta restituisca 0 in caso il numero in input n sia un numero primo.

Una stringa ha periodo k se è uguale alla concatenazione di una o più ripetizioni di una stringa di lunghezza k. Ad esempio, "tramtram" ha periodo 4 e anche periodo 8. Ovviamente, una qualsiasi stringa ha almeno un periodo che è uguale alla sua lunghezza. Alcune hanno anche altri periodi. La stringa abcabcabcabc ha periodi 3, 6 e 12.
Implementare una funzione int strperiod(char *str) che ritorna il più piccolo periodo della stringa str. Ecco i periodi ritornati dalla funzione su acune stringhe:
```
"periodo"     7
"AAAA"        1
"Ah Ah Ah"    8
"01010101"    2
```

Una regione di forma rettangolare di territorio è stata suddivisa in settori quadrati di eguale dimensione e per ognuno di essi è stato valutato il rischio sismico misurato da un opportuno indice di rischio sismico. Quindi, l'intera valutazione è stata sintetizzata in una matrice rettangolare S che per ogni settore di coordinate (i, j) riporta l'indice di rischio sismico S[i][j] di quel settore. Una sottoregione formata da uno o più settori contigui ha indice di rischio sismico dato dalla media degli indici dei suoi settori. Si è interessati a determinare la più grande sottoregione costituita da un gruppo contiguo di settori formanti un quadrato o un rettangolo che ha l'indice di rischio sismico non oltre una certa soglia M. Ciò equivale a determinare la più grande sottomatrice della matrice S la cui media dei valori dei suoi elementi non eccede la soglia M. Una sottomatrice è determinata da un insieme di righe e colonne consecutive.
Implementare una funzione int bestsubmatrix(int nr, int nc, double S[nr][nc], double m) che ritorna l'area (cioè il numero di elementi) della più grande sottomatrice quadrata o rettangolare della matrice S (avente nr righe e nc colonne) con indice di rischio sismico non superiore a m. Ecco alcuni esempi di input e output (in grassetto sono evidenziate alcune sottomatrici di massima area):
```
  nr = 6, nc = 8, m = 3.7         
  6.46  3.36  4.29  3.64  5.97  3.15  5.66  3.20
  3.40  6.22  2.44  6.66  5.55  6.83  1.44  7.70
  4.73  3.52  5.87  7.52  2.96  7.20  6.24  0.72
  3.34  1.65  7.81  3.57  2.25  3.52  0.89  7.02
  5.93  2.19  5.87  3.38  7.01  7.73  7.66  4.11
  7.72  7.07  7.04  1.66  0.64  2.05  7.84  6.60
La funzione ritorna 9

  nr = 5, nc = 5, m = 2.4
  1.84  3.68  4.31  4.39  4.59
  6.75  5.89  6.83  6.18  6.49
  4.22  1.64  2.15  4.94  1.61
  3.68  1.18  6.19  4.30  5.01
  3.91  6.57  1.15  4.39  5.89
La funzione ritorna 2

nr = 5, nc = 4, m = 2.6
  5.69  1.42  2.70  2.17
  2.07  4.01  2.78  2.88
  6.84  2.94  2.96  1.85
  1.83  1.76  5.64  5.51
  6.31  5.50  4.26  6.10
La funzione ritorna 6
```