Programma con array bidimensionali!!!!

[giuliomontenero]

salve a tutti gente, avrei bisogno di sapere come si risolve questo esercizio
è un esercizio d'esame
ecco il testo:
Scrivere una funzione C++ che dato un array a due dimensioni N x N di interi a, un intero n>=1 ed un intero k, restituisce TRUE se e solo se in ogni colonna esistono n coppie distinte di elementi la cui somma sia pari a k.

[bandido]

crei un int da utilizzare come contatore, da azzerare ogni volta che inizi una colonna nuova
per ogni colonna prendi il primo elemento, scorri tutta la colonna cercando un altro elemento che sommato ad esso ti dia k, se lo trovi conti +1, prosegui per tutta la colonna finchè il contatore è uguale a n, e ritorni true, oppure finisci la colonna, nel qual caso ricominci da capo prendendo il secondo elemento della colonna, e così via.

poi passi alla colonna successiva ecc.ecc.

[Umby2]

"maschulillo":
Scrivere una funzione C++ che dato un array a due dimensioni N x N di interi a, un intero n>=1 ed un intero k, restituisce TRUE se e solo se in ogni colonna esistono n coppie distinte di elementi la cui somma sia pari a k.

non mi è chiara quel "n coppie".

Facciamo un esempio,
abbiamo una tavola pitagorica 12x12, quindi N = 12
cerchiamo nelle colonne 3 numeri (quindi n=3), la cui sommatoria sia uguale a 30 (quindi k=30).

Quali colonne soddisfano questa condizione ?

Che soluzione proponi ?

[giuliomontenero]

ah gà è vero ecco degli esempi
per n=2 e k=5
se la colonna fosse formata da

3
1
2
4
0
6

restituisce TRUE perchè le coppie sono $(3,2) e (1,4)$

se fosse invece

3
1
2
2
6

retituisce FALSE perchè le coppie $(3,2) e (3,2)$ hanno il 3 in comune

[apatriarca]

Hai qualche idea su come risolverlo? bandido ti ha già dato una mano, anche se non ha considerato le coppie disgiunte. Ma hai in mente una qualche struttura dati aggiuntiva (anche solo un array) che ti possa essere utile a memorizzare le coppie già trovate e forse anche gli elementi già controllati?

[giuliomontenero]

no mi dispiace avrei bisogno del codice della funzione se qualcuno ha qualche idea
proprio non saprei come fare

[apatriarca]

Non è questo il modo per prepararti all'esame.. Se non ci provi nemmeno a risolverlo come pensi di riuscirci quando ti troverai davanti alla prova? Per cui, sei almeno capace di dichiarare una funzione in C++ che restituisce un valore booleano e che ha come parametri una matrice bidimensionale di interi di dimensione NxN (che suppongo essere costanti e conosciuti alla compilazione), che chiami a, e due interi che chiami n e k? Questo è certamente il primo passo da fare. Se non sei capace di fare neanche questo passaggio, allora sarebbe meglio se ti ristudiassi la teoria.

Una volta arrivato a questo punto l'algoritmo da usare è più o meno quello consigliato da bandido. Con l'unica differenza che devi tenere traccia delle coppie già uscite. Il modo più semplice è quello di allocare un array di booleani (che chiamo visitato) lungo quanto la colonna inizializzato con tutti gli elementi uguali a false. Ad ogni elemento della colonna che controllo, mentre cerco l'elemento della coppia nel resto della colonna, segno come visitati tutti gli elementi della colonna uguali all'elemento o a k meno l'elemento. Ma inizia ad impostare il codice di base e poi torniamo sui dettagli.

[giuliomontenero]

ecco una soluzione elaborata da me


Ho utilizzato due funzioni
La prima che mi verifica se le condizioni nel testo vengono verificate nella prima colonna
La seconda funzione che mi verifica invece se la condizione viene verificata per tutte le altre colonne

bool verifica_coppia(int a[N][N], int k, int n){
int i , j;
bool trovata = false;
int cont=0;
i=0;
while(i j=0;
while(j c=0;
if((a[c]+a[i+j][c])==k)
cont++;
j++;
}
i++;
if(cont==n)
trovata=true;
}
return trovata;
}

bool condizione(int a[N][N], int k, int n){
int s=0;
bool condition=true;
while (s verifica_coppia(a,k,n,s);
if(verifica_coppia)
s++;
cout<<”La condizione è verificata”< cout<<”La condizione non è verificata”< }
return condition;
}

[Umby2]

"maschulillo":
......
i=0;
while(i j=0;
while(j c=0;
if((a[c]+a[i+j][c])==k)
cont++;

cosi' facendo oltrepassi il limite massimo della tabella, il secondo ciclo non è corretto.
ti conviene che j parta da i+1 e non da zero...

se, ad esempio, la tabella è 12x12,
quando i=0, j deve posizionarsi a 1 ed arrivare a 11
quando i=1, j parte da 2 ed arriva a 11.... e cosi' via...

poi dovresti fare un ciclo piu esterno per le colonne (la tua variabile [c])

[giuliomontenero]

potresti scrivermi il codice
altrimenti non arriverò mai in tempo alla soluzione
questo errore ora l'ho capito, altrimenti facendo mai l'avrei capito

[apatriarca]

"maschulillo":
bool verifica_coppia(int a[N][N], int k, int n)
{
int i , j;
bool trovata = false;
int cont=0;
i=0;
while(i {
j=0;
while(j {
c=0;
if((a[c]+a[i+j][c])==k)
cont++;
j++;
}
i++;
if(cont==n)
trovata=true;
}
return trovata;
}

bool condizione(int a[N][N], int k, int n)
{
int s=0;
bool condition=true;
while (s {
verifica_coppia(a,k,n,s);
if(verifica_coppia)
s++;
cout<<”La condizione è verificata”< cout<<”La condizione non è verificata”< }
return condition;
}

Visto che non è tanto difficile fare un tentativo.. Non è corretto, ma qualche idea c'è. Coraggio.. non c'è alcun bisogno di buttarsi giù in questo modo. Per prima cosa ti faccio una domanda: hai fatto solo il ciclo while? Conosci il ciclo for? Per cicli di questo tipo lo trovo sicuramente più comodo.

Per la correzione partirei dalla funzione più "esterna" (quella che lavora su tutta la matrice e chiama l'altra). Quella che tu hai deciso di chiamare condizione. È infatti quasi tutta corretta tranne il corpo del ciclo. È cioè giusta l'idea di fare un ciclo su tutte le colonne e mantenere una variabile booleana per sapere se la condizione vale per ogni colonna, ma nel corpo non modifichi questa condizione e incrementi s solo ad una condizione che ha probabilmente un significato molto diverso da quello che immagini. Vediamo quindi come dovresti modificare il corpo della tua funzione:

bool condizione(int a[N][N], int k, int n)
{
    int s=0;
    bool condition = true;

    while (s < N && condition) {
        condition = verifica_coppia(a,k,n,s); // devi memorizzare il valore restituito dalla funzione da qualche parte..
        if (contition) { // utilizzi il valore di ritorno che hai memorizzato come condizione
            s++;
            cout<<”La condizione è verificata”<<endl;
        } else { // attento però alle parentesi
            cout<<”La condizione non è verificata”<<endl;
        }
    }

    return condition;
}

Dovrebbe essere tutto chiaro dai commenti. Il problema più grosso è che per utilizzare il valore restituito da una funzione devi memorizzare tale valore in una qualche variabile. La condizione di prima aveva un significato totalmente diverso ed era soprattutto sempre vera..

L'altra funzione è certamente più problematica. Per prima cosa ti manca un parametro, hai infatti passato 4 argomenti alla funzione nell'altra funzione, mentre hai solo 3 parametri. Il quarto è la colonna da analizzare che dal codice sembra tu abbia deciso di chiamarla c. Per cui inizia a scrivere:

bool verifica_coppia(int a[N][N], int k, int n, int c)
{

A questo punto le variabili locali e il primo ciclo più esterno vanno abbastanza bene. Quello interno deve essere invece corretto e deve andare da i+1 fino a N-1. Devi cioè scrivere

j = i+1;
while (j < N) { // non è necessario verificare che trovato sia false perché è garantito che lo sia sempre
    // c è un parametro.. deve essere proprio così, settarlo a 0 NON va bene
    if ((a[i][c] + a[j][c]) == k) {
        cont++;
    }
    j++;
}

Il resto del codice è abbastanza corretto. Il codice non verifica però che le coppie non siano disgiunte. Qualche idea?

[giuliomontenero]

no è proprio quello il problema
puoi aiutarmi anche in questo
intendo scrivere il codice e ti dirò poi se o capito
visto che su questo non so cosa fare proprio almeno sull'altra parte un pò di codice lo avevo scritto

[apatriarca]

L'idea è quella di tenere traccia delle coppie e in generale dei valori già presi in considerazione. Un metodo è quello di avere un array di dimensione N di booleani. Ogni valore di questo array indica se l'elemento è già stato preso in considerazione in precedenza o se è nuovo. Nel ciclo più esterno ignori gli elementi già visitati in precedenza e in quello più interno setti a true tutti i valori uguale a quello che stai prendendo in considerazione oppure uguale a k meno il numero. Cioè

bool verifica_coppia(int a[N][N], int k, int n, int c)
{
    int i , j;
    bool trovata = false;
    int cont=0;
    bool visitato[N];

    /*
     * Inizializzo l'array visitato, se non conosci il ciclo for
     * ti scrivo poi la versione con il ciclo while..
     */
    for (i = 0; i < N; ++i) {
        visitato[i] = false;
    }

    i=0;
    while(i<N && !trovata)
    {
        if (visitato[i]) continue; // ignora quelli già considerati

        visitato[i] = true;
        j = i+1;
        while (j < N) {
            if (a[i][c] == a[j][c]) {
                visitato[j] = true; // segna come visitati anche gli altri elementi uguali
            } else if ((a[i][c] + a[j][c]) == k) {
                visitato[j] = true; // segna come visitati gli elementi della coppia
                cont++;
            }
            j++;
        }
        i++;
        if(cont==n)
            trovata=true;
    }
    return trovata;
}

Dovrebbe essere corretto ma non l'ho testato e neanche compilato.

[giuliomontenero]

ti ringrazio in questi giorni ci doò un occhiata e lo provo
e poi ti faccio sapere
grazie ancora

[Umby2]

"apatriarca":
Dovrebbe essere corretto ma non l'ho testato e neanche compilato.

Ci sono un paio di cose che non mi quadrano (il C lo conosco pochissimo):

Premessa: se ho ben capito si intende conteggiare solo le coppie "uniche". Quindi se una coppia si ripete più volte si intende conteggiarla una sola volta, scartando tutte le successive.

Primo punto:
se k è un numero pari (esempio 12), tra le varie coppie valide, dovrei considerare anche la coppia 6+6. Questa coppia non verrebbe conteggiata in quanto l'istruzione:

            if (a[i][c] == a[j][c]) { 
                visitato[j] = true; // segna come visitati anche gli altri elementi uguali 

non la fa transitare per l'if successivo utile alla assegnazione di una coppia valida (spero di aver interpretato correttamente il "else if" successivo.

Secondo punto:

se il secondo elemento della coppia si ripete piu volte, le coppie uguali vengono conteggiate piu volte. Infatti l'indice j pur avendo trovato la coppia, continua nella sua marcia.

            } else if ((a[i][c] + a[j][c]) == k) { 
                visitato[j] = true; // segna come visitati gli elementi della coppia 
                cont++; 
            } 
            j++; 

[apatriarca]

Hai perfettamente ragione! Così imparo a non testare i programmi che posto. Propongo allora una versione un po' diversa:

bool verifica_coppia(int a[N][N], int k, int n, int c) 
{ 
    int i , j; 
    bool trovata = false; 
    int cont=0; 
    bool visitato[N]; 

    /* 
     * Inizializzo l'array visitato, se non conosci il ciclo for 
     * ti scrivo poi la versione con il ciclo while.. 
     */ 
    for (i = 0; i < N; ++i) { 
        visitato[i] = false; 
    } 

    i=0; 
    while(i<N && !trovata) 
    {
        if (visitato[i]) continue; // ignora quelli già considerati 

        visitato[i] = true; 
        j = i+1;
        int k = 0;
        while (j < N) { 
            if (a[i][c] == a[j][c]) { 
                visitato[j] = true; // segna come visitati anche gli altri elementi uguali 
            }

            if ((a[i][c] + a[j][c]) == k) { 
                visitato[j] = true; // segna come visitati gli elementi della coppia 
                k = 1; 
            } 
            j++;
        } 
        cont += k;
        i++; 
        if(cont==n) 
            trovata=true; 
    } 
    return trovata; 
}

I due if non sono adesso esclusivi per cui se i due elementi della coppia sono uguali entra anche nel secondo if. Inoltre invece di incrementare direttamente cont setto una variabile k che può assumere solo valore 0 o 1 a seconda se sia stata trovata una coppia. Ora dovrebbe essere corretto.. Ma è meglio se ci date una controllata anche voi..

[Umby2]

"apatriarca":
Ma è meglio se ci date una controllata anche voi..

Mi sembra quasi perfetto.
L'unico punto ancora dubbio è il punto dove è stata posizionata l'istruzione:

 
          if(cont==n) 
             trovata=true; 

mi sembra di capire che sia stata posizionata all'interno del primo ciclo (quello della "i"). Considerato che devo valutare alla fine del ciclo, se il numero di coppie sia uguale o diverso da "n", questa istruzione andrebbe "fuori ciclo". Concordi ?

[apatriarca]

Era stata fatta in questo modo anche nel codice originale e quindi l'ho lasciata. Si tratta comunque dell'ultima istruzione del ciclo e non c'è quindi alcun rischio che si perda una coppia, inoltre permette di uscire prima dal ciclo, facendo quindi meno iterazioni. Forse, scrivendo la funzione da zero, avrei messo il test al di fuori del ciclo per una maggiore leggibilità (ma avrei fatto ad esempio anche uso del ciclo for al posto del while), ma ho preferito seguire la traccia impostata da maschulillo.

[Umby2]

Non sono molto d'accordo, e ti spiego perchè:

se n = 5 (mi interessano che ci siano 5 coppie per ogni colonna), e nella colonna ce ne sono 6 (in generale un numero maggiore di 5), l'indice cont viene posizionato a zero inizialmente, ed incrementato di una unità ad ogni coppia trovata. Quindi quando passerà per il 5, la condizione (cont==n) si verifichera' e la variabile trovata posizionata a true .... ma non abbiamo completato il tutto.
Se, invece, testo (cont==n) esterno al ciclo, posso sapere esattamente dopo della intera elaborazione, quante coppie ho trovato, e quindi stabilire se la colonna soddisfa o meno la condizione ricercata.

[apatriarca]

Ma non ha chiesto che ci siano esattamente k coppie distinte, ma solo l'esistenza di k coppie distinte. Per cui se anche ce ne fossero più di k, la condizione sarebbe comunque verificata. O almeno è come ho interpretato il testo dell'esercizio che posto per comodità:

Scrivere una funzione C++ che dato un array a due dimensioni N x N di interi a, un intero n>=1 ed un intero k, restituisce TRUE se e solo se in ogni colonna esistono n coppie distinte di elementi la cui somma sia pari a k.

[giuliomontenero]

no devono essere esattamente k coppie distinte come ho scritto nell'esempio