calcolo possibili combinazioni matrice numerica col limite somma

[Mistico86]

Salve a tutti,

sto cercando di creare un algoritmo che mi consenta di fare quanto segue:

Ho una matrice ad esempio 4x4 con 16 valori numeri generati random compresi da 1 a 9.

Voglio conteggiare tutte le possibili combinazioni di quei numeri che mi dia come somma ad esempio il numero 10.

matrice:

6 5 3 8
6 9 1 2
3 1 2 1
7 5 6 1

generata random. in questo caso ad esempio posso ottenere 10 in vari modi...e il conteggio deve muoversi logicamente anche in diagonale, in avanti e indietro, senza ripetizioni.

Ho provato a vedere ogni posto della matrice come un indice e a sommarlo al successivo finchè non ottengo 10, ma non so proprio come muovermi in tutte le direzioni possibili.

Ho letto che forse serve il backtracking ma non sono riuscito ad usarlo.
Sapreste aiutarmi? Grazie mille :muro:

[misterx]

Salve a tutti,

sto cercando di creare un algoritmo che mi consenta di fare quanto segue:

Ho una matrice ad esempio 4x4 con 16 valori numeri generati random compresi da 1 a 9.

Voglio conteggiare tutte le possibili combinazioni di quei numeri che mi dia come somma ad esempio il numero 10.

matrice:

6 5 3 8
6 9 1 2
3 1 2 1
7 5 6 1

generata random. in questo caso ad esempio posso ottenere 10 in vari modi...e il conteggio deve muoversi logicamente anche in diagonale, in avanti e indietro, senza ripetizioni.

Ho provato a vedere ogni posto della matrice come un indice e a sommarlo al successivo finchè non ottengo 10, ma non so proprio come muovermi in tutte le direzioni possibili.

Ho letto che forse serve il backtracking ma non sono riuscito ad usarlo.
Sapreste aiutarmi? Grazie mille :muro:



Senza voler scomodare altri linguaggi tipo il C ho usato VBA


Dim yy As Integer
Sub calcola()
yy = 1
For y = 1 To 4
For x = 1 To 4
Call pippo(y, x)
Next x, y
End Sub

Sub pippo(x, y)
camp = Cells(y, x)
For colonna = 1 To 4
For riga = 1 To 4
If (riga <> y Or colonna <> x) And Cells(y, x) + Cells(riga, colonna) = 10 Then
tmp$ = Cells(y, x)
tmp$ = tmp$ + ","
tmp$ = tmp$ + Str(Cells(riga, colonna))
Cells(yy, 7) = tmp$
yy = yy + 1
tmp$ = ""
Cells(riga, colonna) = 0
End If
Next riga, colonna
End Sub




basta copiare e incollare i tuoi valori in un foglio di Excel da A1,D4

[Mistico86]

cosi somma solo i numeri vicini 2 a 2. io ho bisogno che continua a sommare in tutte le direzioni. capito che intendo magari parti dal centro va a destra da li può continuare tornando indietro avanti o in diagonale!

[Vincenzo1968]

Salve a tutti,

sto cercando di creare un algoritmo che mi consenta di fare quanto segue:

Ho una matrice ad esempio 4x4 con 16 valori numeri generati random compresi da 1 a 9.

Voglio conteggiare tutte le possibili combinazioni di quei numeri che mi dia come somma ad esempio il numero 10.

matrice:

6 5 3 8
6 9 1 2
3 1 2 1
7 5 6 1

generata random. in questo caso ad esempio posso ottenere 10 in vari modi...e il conteggio deve muoversi logicamente anche in diagonale, in avanti e indietro, senza ripetizioni.

Ho provato a vedere ogni posto della matrice come un indice e a sommarlo al successivo finchè non ottengo 10, ma non so proprio come muovermi in tutte le direzioni possibili.

Ho letto che forse serve il backtracking ma non sono riuscito ad usarlo.
Sapreste aiutarmi? Grazie mille :muro:

Ma i numeri devono essere contigui? Se, per esempio, la matrice fosse:

6 5 3 8
6 9 1 2
3 7 2 1
1 5 6 1

Potrei considerare valida la sequenza di numeri 8 1 1 della seconda diagonale(anche se in mezzo ai due 1 c'è il 7)?

[Mistico86]

Ma i numeri devono essere contigui? Se, per esempio, la matrice fosse:

6 5 3 8
6 9 1 2
3 7 2 1
1 5 6 1

Potrei considerare valida la sequenza di numeri 8 1 1 della seconda diagonale?

no devo essere contigui esatto. per esempio andrebbe bene nella prima colonna... 6-3-1. i numeri da sommare possono essere anche 10 ipotizzando tutti numeri 1. il punto è che devono essere contigui...e si possono contare x ogni lato e direzione, ma non si può tornare indietro.


non ne riesco a venire a capo...

[Vincenzo1968]

Eventualmente in C ti va bene la soluzione?

[Mistico86]

Eventualmente in C ti va bene la soluzione?

si credo di si, eventualmente sarebbe solo un problema di sintassi da cambiare. ora stiamo usando VBA per praticità.

Grazie mille, confido in te! :D

[Vincenzo1968]

si credo di si, eventualmente sarebbe solo un problema di sintassi da cambiare. ora stiamo usando VBA per praticità.

Grazie mille, confido in te! :D

Grazie per la fiducia ;) Ma non è detto che ci riesca. Comunque ci voglio provare, il problema m'acchiappa. :D

Come torno a casa me lo studio un po'.

;)

P.S.: È un problema simile a quello che abbiamo trattato in uno dei nostri contest: il 3 o il 4 mi pare.

EDIT: Si, è il 3: http://www.hwupgrade.it/forum/showthread.php?t=1787500 :D

[misterx]

cosi somma solo i numeri vicini 2 a 2. io ho bisogno che continua a sommare in tutte le direzioni. capito che intendo magari parti dal centro va a destra da li può continuare tornando indietro avanti o in diagonale!

assolutamente no.
Prende un numero, partendo dal primo e lo somma con tutti gli altri della matrice e se soddisfa i requisiti lo azzera.

(x1,y1)+(x2,y2) se = 10(x2,y2)=0 e continua così sino a x4,y4
passa poi a x2,y2 e lo somma con tutti gli altri uno ad uno e se soddisfa i requisiti lo azzera.

Se invece intendevi che 10 può essere formato da più numeri allora non si era capito affatto cosa volevi ottenere oppure, che si può partire da una posizione arbitraria allora è un altro tipo di problema etc....


p.s.
metti sempre degli esempi di output in modo che si ben chiaro cosa vuoi ottenere.

[Vincenzo1968]

Prima mi sono sbagliato. Il problema è simile a quello che abbiamo affrontato nel contest 5:

http://www.hwupgrade.it/forum/showthread.php?t=1799059

;)

[Vincenzo1968]

Ecco questo è il codice che avevo utilizzato per il contest 5:


#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <malloc.h>
#include <time.h>

#define BUFFER_SIZE 4096

typedef enum tagStati
{
S_ERROR = -1, S0, S1, S2
} Stati;

typedef struct tagArray
{
int **m;
int side;
} Array;

typedef struct tagResult
{
int row1;
int col1;
int row2;
int col2;
int sum;
} Result;

int GetArraySize(const char *szFileName)
{
int array_size;
FILE *fp;
char buffer[BUFFER_SIZE + 1];
int numread;
int k;
char c;

fp = fopen(szFileName, "rb");
if ( fp == NULL )
{
printf("Errore nell'apertura del file %s\n", szFileName);
return S_ERROR;
}

numread = fread(buffer, 1, BUFFER_SIZE, fp);
if (numread == 0)
{
fclose(fp);
printf("Errore 4 nella lettura del file %s\n", szFileName);
return S_ERROR;
}
*(buffer + numread + 1) = '\0';

k = 0;
c = *(buffer + k);
array_size = 0;
while ( c != '\n' )
{
if ( c >= '0' && c <= '9' )
{
array_size = array_size * 10 + c - '0';

}
c = *(buffer + k++);
}

fclose(fp);

return array_size;
}

Stati DFA(const char *szFileName, Array *pArray)
{
Stati stato = S0;
FILE *fp;
unsigned char buffer[BUFFER_SIZE + 1];
int numblocks;
int numread;
char c;
int k, x;
int riga, colonna;
int num;
int segno;

pArray->side = GetArraySize(szFileName);
if ( pArray->side <= 0 )
{
printf("Errore nella lettura del file.\n");
return S_ERROR;
}

pArray->m = (int**)calloc(pArray->side + 1, sizeof(int*));
if ( pArray->m != NULL )
{
for ( x = 0; x < pArray->side + 1; x++ )
{
pArray->m[x] = (int*)calloc(pArray->side + 1, sizeof(int));
if ( pArray->m[x] == NULL )
{
printf("Memoria insufficiente.\n");
return S_ERROR;
}
}
}
else
{
printf("Memoria insufficiente.\n");
return S_ERROR;
}

fp = fopen(szFileName, "rb");
if ( fp == NULL )
{
printf("Errore nell'apertura del file %s\n", szFileName);
return S_ERROR;
}

if ( fseek(fp, 0, SEEK_END) )
return 0;

numblocks = ftell(fp)/BUFFER_SIZE;
if ( numblocks == 0 )
{
numblocks = 1;
}
else
{
if ( ftell(fp) % BUFFER_SIZE != 0 )
numblocks++;
}

fseek(fp, 0, SEEK_SET);
numread = fread(buffer, 1, BUFFER_SIZE, fp);
if (numread == 0)
{
fclose(fp);
printf("Errore 1 nella lettura del file %s\n", szFileName);
return S_ERROR;
}

k = 0;
c = *(buffer + k++);
while ( c != '\n' )
{
if (c == '\0')
{
printf("Errore 2 nella lettura del file.\n");
fclose(fp);
return S_ERROR;
}
c = *(buffer + k++);
}

riga = colonna = 0;
num = 0;
x = 0;
while ( x < numblocks )
{
c = *(buffer + k++);

switch ( stato )
{
case S0:
segno = 1;
if ( c >= '0' && c <= '9' )
{
num = c - '0';
stato = S1;
}
else if ( c == '-' )
{
num = 0;
stato = S2;
}
else if ( c == '\r' )
{
}
else if ( c == '\n' )
{
colonna = 0;
riga++;
if (riga >= pArray->side)
return stato;
}
else
{
printf("Automa: Stato S0 errore sul carattere -> '%c' k -> %d\n", c, k);
return S_ERROR;
}
break;
case S1:
if ( c >= '0' && c <= '9' )
{
num = num * 10 + c - '0';
}
else if ( c == ' ' || c == '\r' || c == '\n' )
{
pArray->m[riga + 1][colonna + 1] = num * segno;
num = 0;
colonna++;
stato = S0;
}
else
{
printf("Automa: Stato S1 errore sul carattere -> '%c'\n", c);
return S_ERROR;
}
break;
case S2:
if ( c >= '0' && c <= '9' )
{
num = c - '0';
segno = -1;
stato = S1;
}
else
{
printf("Automa: Stato S2 errore sul carattere -> '%c'\n", c);
return S_ERROR;
}
break;
}

if ( k >= BUFFER_SIZE )
{
numread = fread(buffer, 1, BUFFER_SIZE, fp);
if (numread == 0)
{
fclose(fp);
printf("Errore 3 nella lettura del file %s\n", szFileName);
return S_ERROR;
}
k = 0;
x++;
}
}

fclose(fp);

return stato;
}

int FindKadaneSquareSubmatrix(Array *pArray, Result *pRes)
{
int Somma;
int i, t, m, n, z, x, y, s;

int riga, colonna, dim;

int **column;

column = (int**)calloc(pArray->side + 1, sizeof(int*));
if ( column != NULL )
{
for ( x = 0; x < pArray->side + 1; x++ )
{
column[x] = (int*)calloc(pArray->side + 1, sizeof(int));
if ( column[x] == NULL )
{
printf("Memoria insufficiente.\n");
return S_ERROR;
}
}
}
else
{
printf("Memoria insufficiente.\n");
return S_ERROR;
}

m = pArray->side;
n = pArray->side;

// somma dell'intero array
Somma = 0;
for( y = 1; y <= pArray->side; y++ )
{
for( x = 1; x <= pArray->side; x++ )
{
Somma += pArray->m[y][x];
}
}

pRes->sum = Somma;
pRes->row1 = 1;
pRes->col1 = 1;
pRes->row2 = m;
pRes->col2 = n;

// singoli elememti
for( y = 1; y <= pArray->side; y++ )
{
for( x = 1; x < pArray->side; x++ )
{
s = pArray->m[y][x];
if ( s > Somma )
{
Somma = s;
pRes->row1 = y;
pRes->col1 = x;
pRes->row2 = y;
pRes->col2 = x;
}
}
}

for ( z = 1; z <= m; z++ )
{
for ( i = 1; i <= n; i++ )
{
column[z][i] = column[z - 1][i] + pArray->m[z][i];
}
}

s = 0;
for ( dim = 2; dim <= pArray->side; dim++ )
{
for ( riga = 1; riga <= pArray->side - dim + 1; riga++ )
{
s = 0;
for ( x = 1; x <= dim; x++ )
{
s += column[riga + dim - 1][x] - column[riga-1][x];
}

if ( s > Somma )
{
Somma = s;
pRes->sum = s;
pRes->row1 = riga;
pRes->col1 = 1;
pRes->row2 = dim + 1;
pRes->col2 = dim + 1;
}

for ( colonna = x; colonna <= pArray->side; colonna++ )
{

t = column[riga + dim - 1][colonna - dim] - column[riga - 1][colonna - dim];
s += column[riga + dim - 1][colonna] - column[riga-1][colonna];
s -= t;

if ( s > Somma )
{
Somma = s;
pRes->sum = s;
pRes->row1 = riga;
pRes->col1 = colonna - dim + 1;
pRes->row2 = riga + dim - 1;
pRes->col2 = colonna;
}
}
}
}


return 0;
}


int main()
{
clock_t c_start, c_end;
Array a;
Result res;
Stati stato;

char *szFileName = "C:\\Scaricamenti\\Temp\\Gugo\\Contest5\\matrix1.txt";

c_start = clock();
stato = DFA(szFileName, &a);
if ( stato == S_ERROR )
{
printf("L'automa ha restituito un errore.\n");
return;
}
c_end = clock();
printf("\nTempo impiegato per la lettura del file -> %5.5f secondi\n", (double)(c_end - c_start) / CLOCKS_PER_SEC);

c_start = clock();
FindKadaneSquareSubmatrix(&a, &res);
c_end = clock();
printf("\nRiga1 -> %d\nColonna1 -> %d\n\nRiga2 -> %d\nColonna2 -> %d\n\nSomma -> %d\n\n", res.row1, res.col1, res.row2, res.col2, res.sum);
printf("Tempo impiegato per la ricerca -> %5.5f secondi\n", (double)(c_end - c_start) / CLOCKS_PER_SEC);

return 0;
}


Ovviamente bisogna adattarlo per il tuo problema e alla fine il codice risulterà molto più corto.

;)

[Mistico86]

mmmm difficilotto da adattare x me. non è che mi potresti fare un esempio per quello che serve a me? grazie mille

[Mistico86]

assolutamente no.
Prende un numero, partendo dal primo e lo somma con tutti gli altri della matrice e se soddisfa i requisiti lo azzera.

(x1,y1)+(x2,y2) se = 10(x2,y2)=0 e continua così sino a x4,y4
passa poi a x2,y2 e lo somma con tutti gli altri uno ad uno e se soddisfa i requisiti lo azzera.

Se invece intendevi che 10 può essere formato da più numeri allora non si era capito affatto cosa volevi ottenere oppure, che si può partire da una posizione arbitraria allora è un altro tipo di problema etc....


p.s.
metti sempre degli esempi di output in modo che si ben chiaro cosa vuoi ottenere.


esatto intendo che può essere formato da + combinazioni di numeri de qualsiasi posizione e verso...purchè siano adiacenti.

[Vincenzo1968]

mmmm difficilotto da adattare x me. non è che mi potresti fare un esempio per quello che serve a me? grazie mille

È un po' complicato da adattare si, ma non troppo. La maggior parte del codice che ho postato si occupa di leggere la matrice dal file(la funzione DFA). A noi non serve. A noi serve adattare la funzione con l'algoritmo di Kadane(la funzione FindKadaneSquareSubmatrix).

Potremmo farlo semplicemente con backtracking, ma sarebbe estremamente inefficiente.

[misterx]

esatto intendo che può essere formato da + combinazioni di numeri de qualsiasi posizione e verso...purchè siano adiacenti.

un problema analogo lo avevo risolto con le liste di adiacenza e djikstra

[Vincenzo1968]

Così va bene?

http://img515.imageshack.us/img515/9700/matrixm.jpg

Trova le sequenze di numeri con somma = 10.
Considerando solo le righe. Se va bene lo amplio per la ricerca sulle colonne e sulle diagonali.

[Mistico86]

Va benissimo. Anche io avevo fatto qualcosa del genere ma mi manca proprio la parte per farlo cercare anche in diagonale e colonna. Il punto è che se avanza per riga poi può cambiarepercorso x colonna o x ddiagonale. Da ogni punto della matrice deve poter continuare in ogni direzione. Immaginatevi ruzzle il gioco che va tantodi moda adesso . Uno può comporre la parola in qualsiasi modo purché adiacenti. Dovrei fare la stessa cosa ma con i numeri.
Grazie mille

[Vincenzo1968]

Così?

http://img43.imageshack.us/img43/8926/matrix2p.jpg

Mancano ancora le diagonali.

[Mistico86]

Esatto... Praticament gli stai ffacendo fare tre controlli diversi.. Uno per riga uno per colonna e uno per le diagonali? E se si muove su più direzioni? Se prima scende per colonna poi va per diagonale e poi per riga? Capito che intendo? Ad esempio 4 4 2 Nell angolo in basso a destra è una soluzione valida

[Vincenzo1968]

Esatto... Praticament gli stai ffacendo fare tre controlli diversi.. Uno per riga uno per colonna e uno per le diagonali? E se si muove su più direzioni? Se prima scende per colonna poi va per diagonale e poi per riga? Capito che intendo? Ad esempio 4 4 2 Nell angolo in basso a destra è una soluzione valida

Minnale, allora è più complicato di quel che pensassi. Ci dovrò perdere un po' di tempo in più(forse molto tempo in più).

[misterx]

la strada da seguire è questa http://xoomer.virgilio.it/cmaccher/web_ioi/File/Algoritmo_Dijkstra.htm IMHO matrice di adiacenza e dijkstra, ovviamente l'esempio nel sorgente va adattato al caso specifico.

Buon lavoro

[Mistico86]

ragazzi vi ringrazio ma nessuna di queste è la strada giusta....forse lo è il backtracking....

spero che qualcuno di voi mi possa postare un codice funzionante...per ora non ci riusciamo. grazie

[misterx]

mi chiedo se stati sviluppando per un esame oppure per un gioco/lavoro


altro spunto http://it.wikipedia.org/wiki/Percorso_del_cavallo

secondo me poi non sei stato molto chiaro:

6 5 3 8
6 9 1 2
3 1 2 1
7 5 6 1

partendo dal 9 posso fare:
9+6=15 quello a sx e non va bene
9+6=15 quello in diagonale e non va bene
9+5=14 quello sopra e non va bene
9+3=12 e non va bene
9+1=10 e va bene: quindi considere 9 ed 1 come già visitati e non più usabili?
9+2=11 no
9+1=1 ok
9+3=12 no