L08 E02 - Programmazione dinamica

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

#define FILESRC "sequenza.txt"
#define DBG 0

typedef struct soluzione{
    int nscambi;
    int *indici;
}sol;

void leggiSequenze(int **seq, int *dim);
void stampaSol(int i, int j, sol *sol, int *seq, int dim, int **indici);
void costoScambi(int i, int j, int*seq, sol *sol);
void scambioFrecceDP(int *seq, int dim);
void stampaSoluzioneR(int i, int j,int *seq, sol *sol, int dim, int **indici);

int main()
{
    int *seq, dim=0;
    leggiSequenze(&seq,&dim);
    for(int i=0;i<dim;i++)
        printf("%d ",seq[i]);
    printf("\n\n");

    scambioFrecceDP(seq,dim);

    return 0;
}

void leggiSequenze(int **seq, int *dim){
    FILE *fsrc;
    int i;

    fsrc=fopen(FILESRC,"r");
    if(fsrc==NULL){
        printf("Errore apertura file...\n");
        exit(-1);
    }
    fscanf(fsrc," %d",dim);
    *seq=(int*)malloc(*dim*sizeof(int));
    for(i=0;i<*dim;i++){
        fscanf(fsrc," %d",*seq+i);
    }
    return;
}

void scambioFrecceDP(int *seq, int dim){
    int **cost,**indici;
    int dim_matrix=dim/2+1;
    int i,j,c;
    sol costo;
    int riga,colonna;
    int traccia;

    cost=(int**)calloc(dim_matrix,sizeof(int*));
    indici=(int**)calloc(dim_matrix,sizeof(int*));
    for(i=0;i<dim_matrix;i++){
        cost[i]=calloc(dim_matrix,sizeof(int));
        indici[i]=calloc(dim_matrix,sizeof(int));
    }

    costo.indici=malloc(dim*sizeof(int));

    //inizio il lavoro vero
    for(i=1;i<dim_matrix;i++){
        for(j=1;j<(dim_matrix-i+1);j++){//devo escludere le ultime colonne quando il range relativo ala riga i-esima sforerebbe il vettore delle frecce
            cost[i][j]=INT_MAX;
            #if DBG==1
            printf("Intervallo %d %d\n",(j-1)*2,(i+j)*2-3);
            #endif // DBG
            //righe prec
            for(c=1;c<=i;c++){//c scorre le righe tra 1 ed i
                costo.nscambi=0;
                if(c!=i){//calcolo dei costi in base alla somma di due costi precedenti
                    //assegno il costo del mattoncino a
                    costo.nscambi=cost[c][j];
                    //calcolo le coordinate del mattoncino b
                    riga=i-c;
                    colonna=j+c;
                    costo.nscambi=costo.nscambi+cost[riga][colonna];
                    traccia=c;//salvo la riga del rimo mattoncino
                    #if DBG==1
                    //stampo la somma dei due 'mattoncini', ossia gli intervalli accorpati e verifico che la somma dei fue intervalli coincida con quello che sto studiando
                    printf("%d,%d + %d,%d\n",(j-1)*2,(c+j)*2-3,(colonna-1)*2,(riga+colonna)*2-3);
                    if((c+j)*2-3-(j-1)*2+(riga+colonna)*2-3-(colonna-1)*2!=(i+j)*2-3-(j-1)*2 -1){
                        printf("errore estremi..\n");
                        exit(-1);
                    }
                    #endif // DBG
                }
                else{//calcolo diretto dei costi
                    costoScambi((j-1)*2,(i+j)*2-3,seq,&costo);//a partire dagli indici della matrice ricavo gli estremi dell'intervallo su cui calcolare il costo
                    traccia=-1;//il costo è calcolato direttamente e non deriva da mattoncini
                    #if DBG==1
                    printf("Diretto: %d,%d\n",(j-1)*2,(i+j)*2-3);
                    #endif // DBG
                }

                //prendo il costo minore
                if(costo.nscambi<cost[i][j]){
                    cost[i][j]=costo.nscambi;
                    indici[i][j]=traccia;
                }
            }
        }
    }

    #if DBG==1
    //verifica matrici
    for(i=1;i<dim_matrix;i++){
        for(j=1;j<dim_matrix;j++){
            printf("%2d ",cost[i][j]);
        }
        printf("\n");
    }
    printf("\n\n");
    for(i=1;i<dim_matrix;i++){
        for(j=1;j<dim_matrix;j++){
            printf("%2d ",indici[i][j]);
        }
        printf("\n");
    }
    #endif // DBG
    costo.nscambi=0;
    stampaSol(dim/2,1,&costo,seq,dim,indici);

    //libero memoria
    for(i=0;i<dim_matrix;i++){
        free(cost[i]);
        free(indici[i]);
    }
    free(indici);
    free(cost);
    free(costo.indici);

    return;
}

void costoScambi(int i, int j, int*seq, sol *sol){
    int start=i;
    sol->nscambi=0;
    for(;i<=(j-start)/2+start;i++){
        if(seq[i]){//se nella prima metà c'è un 1
            sol->indici[sol->nscambi]=i;
            sol->nscambi++;
        }
    }
    for(;i<=j;i++){
        if(!seq[i]){//se nella seconda metà c'è uno 0
            sol->indici[sol->nscambi]=i;
            sol->nscambi++;
        }
    }
    return;
}

void stampaSoluzioneR(int i, int j, int *seq, sol *soluz, int dim, int **indici){
    sol tmp;
    int k, a=0;
    int riga, colonna;
    //terminazione
    if(indici[i][j]==-1){
        //calcolo il costo dell'intervallo
        tmp.indici=malloc(dim*sizeof(int));
        costoScambi((j-1)*2,(i+j)*2-3,seq,&tmp);
        for(k=soluz->nscambi;k<tmp.nscambi+soluz->nscambi;k++){
            soluz->indici[k]=tmp.indici[a];//k-soluz->nscambi+1
            a++;
        }
        soluz->nscambi=soluz->nscambi+tmp.nscambi;
        free(tmp.indici);
        return;
    }

    //elaborazione: divide and conquer
    //calolo i mattoncini di origine
    //mattoncino a:
    riga=indici[i][j];
    colonna=j;
    stampaSoluzioneR(riga,colonna,seq,soluz,dim,indici);

    //mattoncino b:
    riga=i-indici[i][j];
    colonna=j+indici[i][j];
    stampaSoluzioneR(riga,colonna,seq,soluz,dim,indici);

    return;
}

void stampaSol(int i, int j, sol *sol, int *seq, int dim, int **indici){
    int k=0;

    stampaSoluzioneR(i,j,seq,sol,dim,indici);

    printf("\n");
    for(i=0;i<dim;i++){
        if(i==sol->indici[k]){
            printf("%d ",!seq[i]);
            k++;
        }
        else
            printf("%d ", seq[i]);
    }
    printf("\nGli scambi effettuati sono: %d\n",sol->nscambi);
    printf("Indice/i modificato/i:\n");
    for(i=0;i<sol->nscambi;i++){
        printf("%d ",sol->indici[i]);
    }
    return;
}