Bunich

L08 E02 Dinamic Programmation

Dec 20th, 2017
67
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.  
  7. typedef struct soluzione{
  8.     int nscambi;
  9.     int *indici;
  10. }sol;
  11.  
  12. void leggiSequenze(int **seq, int *dim);
  13. void seq_frecceDP(int *seq, int dim);
  14. void contaScambi(int i, int j, int *seq, sol *sol);
  15. void stampaSol(sol *sol, int *seq, int dim);
  16.  
  17. int main()
  18. {
  19.     int *seq, dim=0;
  20.     leggiSequenze(&seq,&dim);
  21.     for(int i=0;i<dim;i++)
  22.         printf("%d ",seq[i]);
  23.     printf("\n\n");
  24.     seq_frecceDP(seq,dim);
  25.  
  26.     return 0;
  27. }
  28.  
  29. void leggiSequenze(int **seq, int *dim){
  30.     FILE *fsrc;
  31.     int i;
  32.  
  33.     fsrc=fopen(FILESRC,"r");
  34.     if(fsrc==NULL){
  35.         printf("Errore apertura file...\n");
  36.         exit(-1);
  37.     }
  38.     fscanf(fsrc," %d",dim);
  39.     *seq=(int*)malloc(*dim*sizeof(int));
  40.     for(i=0;i<*dim;i++){
  41.         fscanf(fsrc," %d",*seq+i);
  42.     }
  43.     return;
  44. }
  45.  
  46. void seq_frecceDP(int *seq, int dim){
  47.     int i=0,j=dim-1; //estremi sx e dx del vettore di frecce considerato
  48.     int c, k, a;//iterazione
  49.     sol tmp_sol, sol_finale, sol_stampa;
  50.  
  51.     tmp_sol.indici=(int*)malloc(dim*sizeof(int));
  52.     sol_finale.indici=(int*)malloc(dim*sizeof(int));
  53.     sol_stampa.indici=(int*)malloc(dim*sizeof(int));
  54.     tmp_sol.nscambi=0;
  55.     sol_finale.nscambi=0;
  56.     sol_stampa.nscambi=0;
  57.  
  58.     while(i<=j){//poi sarà solo <
  59.  
  60.         sol_finale.nscambi=INT_MAX;
  61.         for(c=i+1;c<=j;c=c+2){
  62.             tmp_sol.nscambi=0;
  63.             //conto scambi necessari su intervallo (i,c), con c variabile nel tempo
  64.             contaScambi(i,c,seq,&tmp_sol);
  65.  
  66.             //salvo la soluzione migliore corrente
  67.             if(tmp_sol.nscambi<=sol_finale.nscambi){
  68.                 sol_finale.nscambi=tmp_sol.nscambi;
  69.                 for(a=0;a<sol_finale.nscambi;a++){
  70.                     sol_finale.indici[a]=tmp_sol.indici[a];
  71.                 }
  72.                 k=c+1;//salvo l'indice dx della sotto soluzione migliore
  73.             }
  74.         }
  75.  
  76.         for(a=sol_stampa.nscambi;
  77.             a<sol_finale.nscambi+sol_stampa.nscambi; //mi sposto di un delta=sol_finale.nscambi
  78.             a++){
  79.                 //accodo gli indici di scambio
  80.                 sol_stampa.indici[a]=sol_finale.indici[a-sol_stampa.nscambi];//a-sol_stampa.nscambi: parto dall'indice 0
  81.             }
  82.         sol_stampa.nscambi=sol_stampa.nscambi+sol_finale.nscambi;
  83.  
  84.  
  85.         i=k;//riparto dall'indice dx della sotto sol. migliore
  86.     }
  87.  
  88.     //stampo
  89.     stampaSol(&sol_stampa,seq,dim);
  90.  
  91.     //libero la memoria
  92.     free(sol_finale.indici);
  93.     free(tmp_sol.indici);
  94.     free(sol_stampa.indici);
  95.     return;
  96. }
  97.  
  98. void contaScambi(int i, int j, int *seq, sol *sol){
  99.     int conta0=0, conta1=0;
  100.     int start, init=i;
  101.  
  102.     for(;i<=j;i++){
  103.         if(!seq[i]){
  104.             //limite:
  105.             if(conta0>(j-init)/2){
  106.                 //ho troppi zeri, registro gli scambi con 1
  107.                 sol->nscambi++;
  108.                 sol->indici[sol->nscambi-1]=i;
  109.                 conta1++;
  110.             }
  111.             else
  112.                 conta0++;
  113.         }
  114.         else{
  115.             if(conta0==0){
  116.                 //non posso iniziare uno sconto con un 1
  117.                 sol->nscambi++;
  118.                 sol->indici[sol->nscambi-1]=i;
  119.                 conta0++;
  120.             }
  121.             else{
  122.                 //verifico che ci siano tanti 1 quanti sono gli zeri appena contati
  123.                 for(start=i;i<start+conta0 && i<=j;i++){
  124.                     if(seq[i]==0){
  125.                         //scambio
  126.                         sol->nscambi++;
  127.                         sol->indici[sol->nscambi-1]=i;
  128.                     }
  129.                     conta1++;
  130.                 }
  131.                 i--;
  132.             }
  133.             //ho passato uno scontro equilibrato
  134.             if(conta0==conta1){
  135.                 conta0=conta1=0;
  136.                 init=i+1;
  137.             }
  138.         }
  139.     }
  140.     return;
  141. }
  142.  
  143. void stampaSol(sol *sol, int *seq, int dim){
  144.     int i, j=0;
  145.     for(i=0;i<dim;i++){
  146.         if(i==sol->indici[j]){
  147.             printf("%d ",!seq[i]);
  148.             j++;
  149.         }
  150.         else
  151.             printf("%d ", seq[i]);
  152.     }
  153.     printf("\nGli scambi effettuati sono: %d\n",sol->nscambi);
  154.     printf("Indici modificati:\n");
  155.     for(i=0;i<sol->nscambi;i++){
  156.         printf("%d ",sol->indici[i]);
  157.     }
  158.     return;
  159. }
RAW Paste Data