Ricerca di una sequenza all'interno di una matrice

di il
4 risposte

Ricerca di una sequenza all'interno di una matrice

Salve! sono nuovo tanto nel forum che nell'utilizzo di C e infatti vi scrivo per affrontare un problema che da giorni non trova soluzione . Vi ripropongo la traccia e successivamente il mio tentativo di soluzione (sperando di non aver fatto stupidaggini troppo gravi)

"Si scriva un programma C che:
- legga da tastiera (per righe o per colonne, a scelta) una matrice quadrata di dimensione uguale a 5 righe e 5 colonne;
- rintracci se tale matrice contiene delle sequenze di elementi adiacenti uguali a zero di lunghezza uguale o maggiore di 3;
- visualizzi l'indice di riga in cui tali sequenze si presentano.

Esempio. Sia la matrice seguente:
0 0 0 4 5
1 2 0 4 5
1 0 0 4 0
1 2 3 4 5
1 0 0 0 0
La sequenza di valori '0 0 0' compare nella prima e nell'ultima riga."

Dopo aver caricato la matrice, ho cercato di risolvere il secondo punto attraverso l'utilizzo di cicli for. Purtroppo credo di aver fatto fesserie:

#include <stdio.h>

int main ()
{   int v[5][5];
    int i,j,k,u=0;
    printf("Carica la matrice di numeri:\n");
    for (i=0; i<5; i++)
    {
        for (j=0; j<5; j++)
        {
            scanf("%d ",&v[i][j]);
        }
    }
for (i=0; i<5; i++)
    {
        for (j=0; j<3; j++)
        {
            for (k=j; k<2+j; k++)
            {
                if (v[i][k]==0)
                {
                    u++;
                }
            }
            if (u>=3)
            {
                printf("\nLa sequenza compare nella riga %d",i+1);
            }
        }
    }
    return 0;
    }
Ora...il programma non restituisce ciò che mi aspetto...potreste consigliarmi un percorso logico da seguire per la risoluzione?

Inoltre...
Nel tentativo di elaborare una soluzione alternativa o almeno più compatta, ho pensato di utilizzare (giacchè la traccia non me lo vieta) una matrice di caratteri avente per righe delle stringhe. In questo modo potrei sfruttare, attraverso l'header file string.h, la funzione strstr per cercare la sottostringa '0,0,0' all'interno del vettore riga. Credete che come soluzione possa funzionare?

Grazie per l'attenzione

4 Risposte

  • Re: Ricerca di una sequenza all'interno di una matrice

    1) per la risposta direi che ti serviranno principalmente dei cicli while, o dei for con dei break.
    a grandi linee il tuo ragionamento è giusto, per l'approccio naive o banale al problema (che penso proprio sia quello che ti viene chiesto)
    2) l'uso di una funzione strstr è meraviglioso, io ti avrei dato il voto massimo per l'impegno.
    le prestazioni sarebbero modeste, ma il "problem solving" mostra un livello incoraggiante di inclinazione per la materia.

    3) un vero metodo "furbo" sarebbe molto più complicato, e te lo accenno solo (livello: professionale avanzato)
    se stai cercando stringhe uguali di lunghezza 3 non ha senso verificare sequenzialmente se sono tutte uguali.
    ad esempio nella sequenza a[] 1234000567 potresti pensare di testarle a coppie.
    Cioè se a=a[i+1] allora inizi a contare: se a[i+1]=a[i+2] allora continui eccetera
    In realtà potresti prima verificare se a=a[i+3]. Perchè se alla fine della sequenza il carattere è diverso, allora sai già
    che è inutile controllare quelli intermedi 1234009567
    in questo esempio quando arrivi al primo 0, è inutile testare il secondo, perchè al terzo posto c'è un 9 e non uno zero.
    ovviamente questa è una introduzione molto banale (e molto imprecisa) al pattern matching "serio".
    diciamo che magari nel futuro arriverai agli algoritmi professionali per questi problemi.

    4) consiglio finale: invece di mettere la procedura di caricamento da tastiera, cabla (cioè inserisci nel sorgente) la matrice di prova e commenta il caricamento.
    in questo modo sarà 1000 volte più veloce provare i tuoi programmi senza dover ogni volta riscrivere tutti i valori
  • Re: Ricerca di una sequenza all'interno di una matrice

    Grazie innanzitutto per l'attenzione un secondo grazie per le dritte che mi hai fornito . Ho provato a implementare il programma con due cicli for e, come da te suggerito, degli if per controllare l'uguaglianza tra gli elementi adiacenti, a loro volta uguali a 0 (quei tre "impossibili" cicli for proposti all'inizio non hanno fatto altro che confondermi le idee). Adesso sembra funzionare perfettamente . Grazie infinite per la disponibilità e per il massimo voto datomi almeno per l'impegno!
  • Re: Ricerca di una sequenza all'interno di una matrice

    Anche se ormai l'esercizio è risolto, vorrei far notare che strstr non avrebbe funzionato perché anche il terminatore di stringa è 0.
  • Re: Ricerca di una sequenza all'interno di una matrice

    dvaosta ha scritto:


    Anche se ormai l'esercizio è risolto, vorrei far notare che strstr non avrebbe funzionato perché anche il terminatore di stringa è 0.
    avrebbe funzionato, al contrario, perchè i codici ASCII delle cifre non sono 0.
    Comunque, in questi casi, si giustappone un carattere delimitativo (è la tecnica per le colonne virtuali nei db, o per i json dei pover in altri termini).
Devi accedere o registrarti per scrivere nel forum
4 risposte