Nippolo ha scritto:
Mi sono cimentato anche io
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <time.h>
#include <windows.h>
#define N 13
#define RED 12
#define DEFAULT_COLOUR 7
void set_position(const COORD xy)
{
SetConsoleCursorPosition(GetStdHandle(STD_OUTPUT_HANDLE), xy);
}
void set_colour(int colour)
{
SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE), colour);
}
void scambia_valori(unsigned int *a, unsigned int *b)
{
unsigned int temp = *a;
*a = *b;
*b = temp;
}
void ordina_array(unsigned int v[N], unsigned int u[N])
{
for(unsigned int i = 0; i < N - 1; ++i)
{
for(unsigned int j = 0; j < N - i - 1; ++j)
{
if(v[j] < v[j + 1])
{
scambia_valori(v + j, v + (j + 1));
scambia_valori(u + j, u + (j + 1));
}
}
}
}
bool inizializza_array(unsigned int u[N], const unsigned int dim)
{
for(unsigned int i = 0; i < dim; ++i)
{
u[i] = i;
}
return true;
}
bool combinazione_successiva(unsigned int u[N], const unsigned int n, const unsigned int k)
{
for(unsigned int i = 0; i < k; ++i)
{
if(u[k - i - 1] < n - i - 1)
{
++u[k - i - 1];
if(i && u[k - i] - u[k - i - 1] > 1)
{
for(unsigned int j = k - i; j < k; ++j)
{
u[j] = u[j - 1] + 1;
}
}
return true;
}
}
return false;
}
void riempi_matrice_casuale(int m[N][N], const int min, const int max)
{
for(unsigned int i = 0; i < N; ++i)
{
for(unsigned int j = 0; j < N; m[i][j++] = rand() % (max - min + 1) + min);
}
}
void normalizza_matrice(bool m_[N][N], int m[N][N])
{
for(unsigned int i = 0; i < N; ++i)
{
for(unsigned int j = 0; j < N; ++j)
{
m_[i][j] = m[i][j] < 0;
}
}
}
void stampa_matrice(int m[N][N])
{
for(unsigned int i = 0; i < N; ++i)
{
for(unsigned int j = 0; j < N; printf("% d ", m[i][j++]));
printf("\n");
}
}
bool verifica_sottomatrice(bool m[N][N], unsigned int rig_2[N], unsigned int col_2[N], unsigned int u_rig[N], unsigned int u_col[N], const unsigned int k)
{
for(unsigned int i = 0; i < k; ++i)
{
for(unsigned int j = 0; j < k; ++j)
{
if(!m[rig_2[u_rig[i]]][col_2[u_col[j]]])
{
return false;
}
}
}
return true;
}
void evidenzia_sottomatrice(int m[N][N], unsigned int rig_2[N], unsigned int col_2[N], unsigned int u_rig[N], unsigned int u_col[N], const unsigned int k)
{
set_colour(RED);
for(unsigned int i = 0; i < k; ++i)
{
for(unsigned int j = 0; j < k; ++j)
{
set_position((COORD){3 * col_2[u_col[j]], rig_2[u_rig[i]]});
printf("% d ", m[rig_2[u_rig[i]]][col_2[u_col[j]]]);
}
}
set_position((COORD){0, N});
set_colour(DEFAULT_COLOUR);
}
int main()
{
int m[N][N];
srand(time(0));
riempi_matrice_casuale(m, -5, 5);
stampa_matrice(m);
bool m_[N][N];
normalizza_matrice(m_, m);
unsigned int rig_1[N] = {0};
unsigned int col_1[N] = {0};
unsigned int rig_2[N];
unsigned int col_2[N];
unsigned int rig_3[N + 1] = {0};
unsigned int col_3[N + 1] = {0};
unsigned int u_rig[N];
unsigned int u_col[N];
for(unsigned int i = 0; i < N; ++i)
{
for(unsigned int j = 0; j < N; ++j)
{
rig_1[i] += m_[i][j];
col_1[j] += m_[i][j];
}
}
for(unsigned int k = 0; k < N; ++k)
{
rig_2[k] = col_2[k] = k;
++rig_3[rig_1[k]];
++col_3[col_1[k]];
}
ordina_array(rig_1, rig_2);
ordina_array(col_1, col_2);
for(unsigned int k = N; k; --k)
{
if(rig_3[k] >= k && col_3[k] >= k)
{
inizializza_array(u_rig, k);
inizializza_array(u_col, k);
do
{
if(verifica_sottomatrice(m_, rig_2, col_2, u_rig, u_col, k))
{
evidenzia_sottomatrice(m, rig_2, col_2, u_rig, u_col, k);
return 0;
}
}
while(combinazione_successiva(u_rig, rig_3[k], k) || combinazione_successiva(u_col, col_3[k], k) && inizializza_array(u_rig, k));
}
rig_3[k - 1] += rig_3[k];
col_3[k - 1] += col_3[k];
}
}
L'ho testato poco e nulla, ma sembra funzionare.
Con matrici di ordine 13 impiega qualche centesimo di secondo.
Adesso non riesco, ma domani con calma cerco di spiegare il ragionamento che ho adottato ...
Il ragionamento di fondo è piuttosto semplice:
- innanzitutto, affinché possa esistere una sottomatrice valida m di ordine k, la matrice completa M deve avere un numero n_rig di righe e un numero n_col di colonne, che presentino un numero di elementi validi (ossia di valori negativi in questo caso) maggiore o uguale a k, almeno pari a k;
- in questo modo è possibile individuare un valore massimo di k da cui iniziare la ricerca delle sottomatrici. Se la ricerca per il valore attuale di k dà esito negativo, allora si diminuisce k di un'unità e si ripete la ricerca;
- una volta definito il valore attuale di k, basta generare le sequenze date dalle combinazioni semplici degli n_rig elementi (costituiti dagli indici delle righe della matrice completa M con numero di elementi validi maggiore o uguale a k) di classe k, e quelle date dalle combinazioni semplici degli n_col elementi di classe k;
- ogni possibile coppia tra combinazioni su riga e combinazioni su colonna definirà una sottomatrice facilmente verificabile.
Questo per quanto riguarda l'algoritmo generale, relativamente al codice invece mi limiterò a spiegare cosa rappresentano rig_1, rig_2, rig_3 e u_rig:
- rig_1 è un array di dimensione N (pari all'ordine della matrice completa M) i cui elementi rappresentano il numero di elementi validi nella corrispettiva riga di M.
Discorso analogo vale per col_1 relativamente alle colonne;
- rig_2 è un array di dimensione N, ricavato a partire da rig_1, i cui elementi rappresentano gli indici delle righe di M ordinati in senso decrescente relativamente al numero di elementi validi in esse contenuti.
Discorso analogo vale per col_2 relativamente alle colonne;
- rig_3 è un array di dimensione N+1, ricavato a partire da rig_1, i cui elementi rappresentano il numero di righe di M con numero di elementi validi pari all'indice in rig_3. Tale array viene utilizzato per ricavare i valori di k e n_rig menzionati in precedenza.
Discorso analogo vale per col_3 relativamente alle colonne;
- u_rig è un array intermedio utilizzato per generare le sequenze relative alle combinazioni semplici degli n_rig elementi di classe k.
Discorso analogo vale per u_col relativamente alle colonne.
Secondo voi quest'algoritmo in generale presenta ulteriori margini di ottimizzazione?
P.S.
@HATFIELD sarà contento che non sono "ricorso alla ricorsione"!