Bunich

L08 E02 - Programmazione dinamica

Dec 24th, 2017
106
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <limits.h>
  4.  
  5. #define FILESRC "sequenza.txt"
  6. #define DBG 0
  7.  
  8. typedef struct soluzione{
  9.     int nscambi;
  10.     int *indici;
  11. }sol;
  12.  
  13. void leggiSequenze(int **seq, int *dim);
  14. void stampaSol(int i, int j, sol *sol, int *seq, int dim, int **indici);
  15. void costoScambi(int i, int j, int*seq, sol *sol);
  16. void scambioFrecceDP(int *seq, int dim);
  17. void stampaSoluzioneR(int i, int j,int *seq, sol *sol, int dim, int **indici);
  18.  
  19. int main()
  20. {
  21.     int *seq, dim=0;
  22.     leggiSequenze(&seq,&dim);
  23.     for(int i=0;i<dim;i++)
  24.         printf("%d ",seq[i]);
  25.     printf("\n\n");
  26.  
  27.     scambioFrecceDP(seq,dim);
  28.  
  29.     return 0;
  30. }
  31.  
  32. void leggiSequenze(int **seq, int *dim){
  33.     FILE *fsrc;
  34.     int i;
  35.  
  36.     fsrc=fopen(FILESRC,"r");
  37.     if(fsrc==NULL){
  38.         printf("Errore apertura file...\n");
  39.         exit(-1);
  40.     }
  41.     fscanf(fsrc," %d",dim);
  42.     *seq=(int*)malloc(*dim*sizeof(int));
  43.     for(i=0;i<*dim;i++){
  44.         fscanf(fsrc," %d",*seq+i);
  45.     }
  46.     return;
  47. }
  48.  
  49. void scambioFrecceDP(int *seq, int dim){
  50.     int **cost,**indici;
  51.     int dim_matrix=dim/2+1;
  52.     int i,j,c;
  53.     sol costo;
  54.     int riga,colonna;
  55.     int traccia;
  56.  
  57.     cost=(int**)calloc(dim_matrix,sizeof(int*));
  58.     indici=(int**)calloc(dim_matrix,sizeof(int*));
  59.     for(i=0;i<dim_matrix;i++){
  60.         cost[i]=calloc(dim_matrix,sizeof(int));
  61.         indici[i]=calloc(dim_matrix,sizeof(int));
  62.     }
  63.  
  64.     costo.indici=malloc(dim*sizeof(int));
  65.  
  66.     //inizio il lavoro vero
  67.     for(i=1;i<dim_matrix;i++){
  68.         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
  69.             cost[i][j]=INT_MAX;
  70.             #if DBG==1
  71.             printf("Intervallo %d %d\n",(j-1)*2,(i+j)*2-3);
  72.             #endif // DBG
  73.             //righe prec
  74.             for(c=1;c<=i;c++){//c scorre le righe tra 1 ed i
  75.                 costo.nscambi=0;
  76.                 if(c!=i){//calcolo dei costi in base alla somma di due costi precedenti
  77.                     //assegno il costo del mattoncino a
  78.                     costo.nscambi=cost[c][j];
  79.                     //calcolo le coordinate del mattoncino b
  80.                     riga=i-c;
  81.                     colonna=j+c;
  82.                     costo.nscambi=costo.nscambi+cost[riga][colonna];
  83.                     traccia=c;//salvo la riga del rimo mattoncino
  84.                     #if DBG==1
  85.                     //stampo la somma dei due 'mattoncini', ossia gli intervalli accorpati e verifico che la somma dei fue intervalli coincida con quello che sto studiando
  86.                     printf("%d,%d + %d,%d\n",(j-1)*2,(c+j)*2-3,(colonna-1)*2,(riga+colonna)*2-3);
  87.                     if((c+j)*2-3-(j-1)*2+(riga+colonna)*2-3-(colonna-1)*2!=(i+j)*2-3-(j-1)*2 -1){
  88.                         printf("errore estremi..\n");
  89.                         exit(-1);
  90.                     }
  91.                     #endif // DBG
  92.                 }
  93.                 else{//calcolo diretto dei costi
  94.                     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
  95.                     traccia=-1;//il costo è calcolato direttamente e non deriva da mattoncini
  96.                     #if DBG==1
  97.                     printf("Diretto: %d,%d\n",(j-1)*2,(i+j)*2-3);
  98.                     #endif // DBG
  99.                 }
  100.  
  101.                 //prendo il costo minore
  102.                 if(costo.nscambi<cost[i][j]){
  103.                     cost[i][j]=costo.nscambi;
  104.                     indici[i][j]=traccia;
  105.                 }
  106.             }
  107.         }
  108.     }
  109.  
  110.     #if DBG==1
  111.     //verifica matrici
  112.     for(i=1;i<dim_matrix;i++){
  113.         for(j=1;j<dim_matrix;j++){
  114.             printf("%2d ",cost[i][j]);
  115.         }
  116.         printf("\n");
  117.     }
  118.     printf("\n\n");
  119.     for(i=1;i<dim_matrix;i++){
  120.         for(j=1;j<dim_matrix;j++){
  121.             printf("%2d ",indici[i][j]);
  122.         }
  123.         printf("\n");
  124.     }
  125.     #endif // DBG
  126.     costo.nscambi=0;
  127.     stampaSol(dim/2,1,&costo,seq,dim,indici);
  128.  
  129.     //libero memoria
  130.     for(i=0;i<dim_matrix;i++){
  131.         free(cost[i]);
  132.         free(indici[i]);
  133.     }
  134.     free(indici);
  135.     free(cost);
  136.     free(costo.indici);
  137.  
  138.     return;
  139. }
  140.  
  141. void costoScambi(int i, int j, int*seq, sol *sol){
  142.     int start=i;
  143.     sol->nscambi=0;
  144.     for(;i<=(j-start)/2+start;i++){
  145.         if(seq[i]){//se nella prima metà c'è un 1
  146.             sol->indici[sol->nscambi]=i;
  147.             sol->nscambi++;
  148.         }
  149.     }
  150.     for(;i<=j;i++){
  151.         if(!seq[i]){//se nella seconda metà c'è uno 0
  152.             sol->indici[sol->nscambi]=i;
  153.             sol->nscambi++;
  154.         }
  155.     }
  156.     return;
  157. }
  158.  
  159. void stampaSoluzioneR(int i, int j, int *seq, sol *soluz, int dim, int **indici){
  160.     sol tmp;
  161.     int k, a=0;
  162.     int riga, colonna;
  163.     //terminazione
  164.     if(indici[i][j]==-1){
  165.         //calcolo il costo dell'intervallo
  166.         tmp.indici=malloc(dim*sizeof(int));
  167.         costoScambi((j-1)*2,(i+j)*2-3,seq,&tmp);
  168.         for(k=soluz->nscambi;k<tmp.nscambi+soluz->nscambi;k++){
  169.             soluz->indici[k]=tmp.indici[a];//k-soluz->nscambi+1
  170.             a++;
  171.         }
  172.         soluz->nscambi=soluz->nscambi+tmp.nscambi;
  173.         free(tmp.indici);
  174.         return;
  175.     }
  176.  
  177.     //elaborazione: divide and conquer
  178.     //calolo i mattoncini di origine
  179.     //mattoncino a:
  180.     riga=indici[i][j];
  181.     colonna=j;
  182.     stampaSoluzioneR(riga,colonna,seq,soluz,dim,indici);
  183.  
  184.     //mattoncino b:
  185.     riga=i-indici[i][j];
  186.     colonna=j+indici[i][j];
  187.     stampaSoluzioneR(riga,colonna,seq,soluz,dim,indici);
  188.  
  189.     return;
  190. }
  191.  
  192. void stampaSol(int i, int j, sol *sol, int *seq, int dim, int **indici){
  193.     int k=0;
  194.  
  195.     stampaSoluzioneR(i,j,seq,sol,dim,indici);
  196.  
  197.     printf("\n");
  198.     for(i=0;i<dim;i++){
  199.         if(i==sol->indici[k]){
  200.             printf("%d ",!seq[i]);
  201.             k++;
  202.         }
  203.         else
  204.             printf("%d ", seq[i]);
  205.     }
  206.     printf("\nGli scambi effettuati sono: %d\n",sol->nscambi);
  207.     printf("Indice/i modificato/i:\n");
  208.     for(i=0;i<sol->nscambi;i++){
  209.         printf("%d ",sol->indici[i]);
  210.     }
  211.     return;
  212. }
RAW Paste Data