funzione ricorsiva

[Tony Hak]

ciao raga ! sto impazzendo per questo esericizio ! sapete trovarmi un giusto algoritmo per risolverlo ? l'esercizio è il seguente:

assegnata una matrice M x N di interi e un intero K scrivere una funzione ricorsiva che restituisca True se e solo se esistono esattamente K colonne con la stessa somma

grazie mille

[Scoperchiatore]

Mah, dipende che approccio vuoi usare.

Puoi vederla in 2 modi:
1) ricorsiva pura. Non ottimizzi nulla, ma ha complessità quadratica
2) ricorsiva con array di appoggio. Ottimizzi qualcosa, è meno elegante, ma ha complessità lineare.

Suppongo che la 2) vada oltre gli scopi dell'esercizio, quindi proviamo la 1.

Intanto definisciti la funzione sum(M, j) che trova la somma della colonna j in M

poi

/* Innesco*/
esercizio(Mtrx, K)
find_k_cols(K, Mtrx,0)
find_k_cols(K, Mtrx, this_col)
if (find_k_cols_sum(K, Mtrx, this_col, sum(Mtrx,this_col) )
return true
else if (this_col<N)
return find_k_cols(K, Mtrx, this_col+1)
find_k_cols_sum(K, Mtrx, this_col,cols_found, this_sum)
if (K==0)
return true /*vuol dire che le hai già trovate tutte*/
else if (K>N-this_col)
return false /* stai cercando K colonne, ma te ne sono rimaste K-1*/
else {
if (sum(Mtrx,this_col) == this_sum) 
find_k_cols_sum(K-1, Mtrx, this_col, this_sum)
else 
find_k_cols_sum(K, Mtrx, this_col, this_sum)
}