Homework2 < Programmazione1

Tags: view all tags

<H2>Homework 2</H2>

<DIV ALIGN="justify" style="margin-left:5%; margin-right:10%">
<OL>
<LI>Implementare una funzione <code>int *findwords(int n, char L[n][n], char *W[], int nw)</code>
che prende in input una matrice <code>L</code> di <code>nxn</code>  caratteri 
alfabetici maiuscoli (<code>'A','B',...,'Z'</code>) e un vettore <code>W</code> 
di <code>nw</code> stringhe (ognuna delle quali contiene una parola in lettere maiuscole),
e ritorna un vettore <code>C</code>, allocato dinamicamente, che per ogni parola del 
vettore <code>W</code> conta il numero di volte che appare nella matrice <code>L</code>
scritta in orizzontale o in verticale. Quindi, il vettore ritornato <code>C</code>
deve avere dimensione <code>nw</code> e per ogni <code>i</code>, <code>C[i]</code>
deve essere uguale al numero di volte che la parola <code>W[i]</code> appare
in <code>L</code>. Ad esempio, se <code>n = 10</code>, la matrice <code>L</code> e il vettore
<code>W</code> (<code>nw = 4</code>) sono:
<pre>
    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
</pre>
allora la funzione ritorna il vettore <code>C = [4, 3, 0, 1]</code>. Qui sotto
le occorrenze delle parole di <code>W</code> in <code>L</code> 
sono evidenziate in grassetto:
<pre>
L <b>B A R B A R B A</b> C
G U O V B <b>L U N A</b> L
C H N N D <b>U</b> B N T R
B A R A I <b>N</b> H T U V
W <b>B A R B A</b> I U V X
Y Z Z A V I L L M Y
N N T <b>L</b> R M M C C B
K J <b>L U N A R E</b> D G
J G H <b>N</b> N M I U T R
B B R <b>A</b> D O A N U L
</pre>

<p>
<div style="background: #DDDDDD; padding:6pt;">
<b>Domande & risposte</b>
   <dl>
   <dt><i>Le parole vanno cercate anche da destra verso sinistra e dal basso verso l'alto?</i></dt>
   <dd><b>No</b>, le parole vanno cercate (come nei tradizionali cruciverba) disposte solo da sinistra a destra e dall'alto verso il basso.
      <br>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 <b>non</b> va considerata una occorrenza della parola "LUNA" nella matrice. 
   </dd>
</div>

</LI>
<BR>
<LI>
Nel 1982 Albert Wilansky, un matematico della Lehigh University, not&ograve;
che il numero di telefono (4937775) di suo genero Harold Smith aveva una sorprendente 
propriet&agrave;: 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&egrave;, 74937775 = 3x5x5x65837) e la somma 
delle loro cifre &egrave; 3 + 5 + 5 + 6 + 5 + 8 + 3 + 7 = 42. Wilansky fu cos&igrave; 
colpito da questa scoperta che decise di chiamare <em>numeri di Smith</em> 
i numeri che hanno questa sorprendente propriet&agrave;. 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&ugrave; si pu&ograve; consultare la pagina di wikipedia sui
<a href="http://it.wikipedia.org/wiki/Numero_di_Smith">numeri di Smith</a>.
<br>
Implementare una funzione <code>int issmithnumber(long long n)</code> che controlla
se <code>n</code> &egrave; un numero di Smith. Se lo &egrave; ritorna la
somma delle sue cifre, altrimenti ritorna <code>0</code>.

<p>
<div style="background: #DDDDDD; padding:6pt;">
<b>Domande & risposte</b>
   <dl>
   <dt><i>I numeri primi sono numeri di Smith?</i></dt>
   <dd>I numeri primi soddisfano banalmente la propriet&agrave; descritta sopra. Tuttavia, secondo la definizione ufficiale
      (e proprio per questo) i numeri primi <b>non sono considerati</b> numeri di Smith (v. ad es., <a href="http://it.wikipedia.org/wiki/Numero_di_Smith">Wikipedia</a>).   
      <br>
      Ad esempio: 13 &egrave; &egrave; un numero primo, quindi la somma delle sue cifre (1+3=4) &egrave; uguale (banalmente)
      alla somma delle cifre della sua fattorizzazione, visto che quest'ultima (essendo 13 primo) &egrave; 13 stesso!
      <br>
      <b>Tuttavia, 13, essendo numero primo, non &egrave; considerato numero di Smith</b>.

      <p>Si chiarisce quindi di fare in modo che la funzione prodotta restituisca <code>0</code> in caso il numero in input <code>n</code> sia un numero primo.
    </dd>
</div>

</LI>
<br>
<LI>Una stringa ha periodo <code>k</code> se &egrave; uguale alla concatenazione 
di una o pi&ugrave; ripetizioni di una stringa di lunghezza <code>k</code>. Ad esempio,
<code>"tramtram"</code> ha periodo 4 e anche periodo 8. Ovviamente, una qualsiasi
stringa ha almeno un periodo che &egrave; uguale alla sua lunghezza. Alcune hanno 
anche altri periodi. La stringa <code>abcabcabcabc</code> ha periodi 3, 6 e 12.
<br>
Implementare una funzione <code>int strperiod(char *str)</code> che ritorna il pi&ugrave;
piccolo periodo della stringa <code>str</code>. Ecco i periodi 
ritornati dalla funzione su acune stringhe:
<pre>
"periodo"     7
"AAAA"        1
"Ah Ah Ah"    8
"01010101"    2
</pre>
</LI>
<br>
<li>Una regione di forma rettangolare di territorio &egrave; stata suddivisa in 
settori quadrati di eguale dimensione e per ognuno di essi &egrave; stato valutato
il rischio sismico misurato da un opportuno indice di rischio sismico. 
Quindi, l'intera valutazione &egrave; stata sintetizzata in una matrice rettangolare <em>S</em> che
per ogni settore di coordinate (<em>i</em>, <em>j</em>) riporta l'indice di 
rischio sismico <em>S</em>[<em>i</em>][<em>j</em>] di quel settore. Una sottoregione 
formata da uno o pi&ugrave; settori
contigui ha indice di rischio sismico dato dalla media degli indici dei
suoi settori. Si &egrave; interessati a determinare
la pi&ugrave; 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 <em>M</em>. Ci&ograve; equivale
a determinare la pi&ugrave; grande sottomatrice della matrice <em>S</em> la cui media 
dei valori dei suoi elementi non eccede la soglia <em>M</em>. Una sottomatrice &egrave;
determinata da un insieme di righe e colonne consecutive.
<br>
Implementare una funzione <code>int bestsubmatrix(int nr, int nc, double S[nr][nc], double m)</code>
che ritorna l'area (cio&egrave; il numero di elementi) della pi&ugrave; grande 
sottomatrice quadrata o rettangolare della matrice <code>S</code> (avente <code>nr</code>
righe e <code>nc</code> colonne) con indice di rischio sismico non superiore
a <code>m</code>. Ecco alcuni esempi di input e output (in grassetto sono evidenziate 
alcune sottomatrici di massima area):
<pre>
  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  <b>3.57  2.25  3.52</b>  0.89  7.02
  5.93  2.19  5.87  <b>3.38  7.01  7.73</b>  7.66  4.11
  7.72  7.07  7.04  <b>1.66  0.64  2.05</b>  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  <b>1.64  2.15</b>  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  <b>2.70  2.17</b>
  2.07  4.01  <b>2.78  2.88</b>
  6.84  2.94  <b>2.96  1.85</b>
  1.83  1.76  5.64  5.51
  6.31  5.50  4.26  6.10
La funzione ritorna 6
</pre>
</li>
</OL>
</DIV>