Recursion C l'image algorithme de compression

Question

Je suis en train de terminer un programme de base simple qui imite un algorithme qui est utilisé dans la compression d'image en utilisant la récursivité. J'ai une matrice n x n où n est toujours une puissance de deux. C'est parce que nous pouvons diviser la matrice en 4 n/2 * n/2 autre matrice. Il existe deux cas de base:

• lorsqu'une matrice est 1x1, il suffit de renvoyer la valeur à l'intérieur de cet emplacement.
• lorsque toutes les valeurs à l'intérieur d'un bloc de nxn sont égaux alors imprimer 1x, où x est la valeur commune

Le cas récursif est différent lorsque nous avons values.In ce cas, on imprime 0 et on divise la matrice dans les quatre autres matrices n/2 xn/2.

Ces régions sont traitées de manière récursive dans le sens des aiguilles d'une montre, en commençant par la zone supérieure gauche.

Exemple:

8 
..**.... 
..**.... 
**...... 
**...... 
........ 
........ 
......*. 
......*. 

Réponse: 001,1 * 1,1 * 1.01.1.0 * .. * 1.1.

Mon problème est que je manque un cas dans mon code si ma réponse ne correspond pas vraiment tout à fait avec le résultat attendu.

Voici mon code:

void computeComressor(char** arr,int m,int x,int y){ 
    int i,j; 
    int flag=1; 
    char c=arr[x][y]; 
    if(m==1){ 
     printf("%c",c); 
     return; 
    } 
    for(i=x;i<m-x*y;i++){ 
     for(j=y;j<m-x*y;j++){ 
      if(arr[i][j]==c){ 
       continue; 
      } 
      else{ 
       flag=0; 
       break; 
      } 
     } 
    } 

    if(flag==1){ 
     printf("1%c",c); 
    } 
    else{ 
     printf("0"); 
     computeComressor(arr,m/2,x,y); 
     computeComressor(arr,m/2,x,m/2); 
     computeComressor(arr,m/2,m/2,m/2); 
     computeComressor(arr,m/2,m/2,y); 
    } 
} 

Answer 1

Vos arguments sur computeCompressor() récursion semble mal. Si vous passez m/2 pour l'argument x ou y, il en résultera 4, 2 et 1 en fonction du niveau de récursivité qui ne correspond pas au coin supérieur gauche des sous-matrices. Vous devez ajouter x et y valeurs de la sous-matrice actuelle à m/2. Mais même dans ce cas, votre code parcourt la sous-matrice dans le sens inverse des aiguilles d'une montre.

Voici la solution que je propose pour computeCompressor() avec quelques modifications supplémentaires:

void computeComressor(char** arr, int m, int x, int y){ 
    int  i,j; 
    char c = arr[x][y]; 
    int  hm = m/2; 

    if (m==1) { 
     printf("%c", c); 
     return; 
    } 

    for (i=x; i<x+m; i++) { 
     for (j=y; j<y+m; j++) { 
      if (arr[i][j] != c) { 
       printf("1%c", c); 
       return; 
      } 
     } 
    } 

    printf("0"); 
    computeComressor(arr, hm, x + 0, y + 0); 
    computeComressor(arr, hm, x + hm, y + 0); 
    computeComressor(arr, hm, x + hm, y + hm); 
    computeComressor(arr, hm, x + 0, y + hm); 
}