Algorithme de sous-groupe

Question

Récemment, quelqu'un m'a demandé de créer un programme C qui «groupait» (ses mots, pas les miens!) Les nombres en paires. Voici comment cela fonctionne. D'abord, l'utilisateur entre la gamme maximale: (disons) 10 Maintenant, l'utilisateur entre un nombre: (disons) 4. Ensuite, les groupes de programmes 4 et 5 ensemble. (c'est-à-dire n et n + 1) Entrée utilisateur suivante: 8 Les groupes de programmes 8 et 9 également. Maintenant, cela continue. Exceptions: Si l'utilisateur entre un nombre qui a déjà été groupé, comme 4,5,8 ou 9. Ensuite, le groupe auquel il appartient est supprimé complètement. En outre, le programme invalide les entrées qui nécessitent un appariement avec des numéros déjà associés. Par exemple. Si 4 et 5 sont appariés, 3 n'est pas une entrée valide. De même, entrer les extrêmes (ici, 1 et 10) n'est pas autorisé.

J'ai créé le programme ci-dessus en C, en utilisant Visual Studio 2013. J'ai fourni le code ci-dessous. Mes questions sont: A) Comment ai-je pu considérablement améliorer mon code (à part initialiser le tableau APRÈS avoir accepté l'entrée maxi) B) Plus important encore, quelqu'un peut-il me dire ce qu'est cet algorithme? Est-ce un problème standard? A-t-il une application/implémentation dans le monde réel? Ou est-ce juste une idée aléatoire?

#include<stdio.h> 
#inlcude<conio.h> 

#define array_size 10 

int group[array_size][2] = { 0 }; 
int n = 0, max=0, search = 0, max_mem = 0; 
int tcount = 2; 
void sort(int x[][2]); 
void print_groups(); 
void test_print(); 

void main() 
{ 
group[0][0] = 0; 
group[0][1] = 1; 

printf("Enter a number:"); 
scanf_s("%d", &max); 

max_mem = (max/2)+1; 
if (max_mem > array_size) 
{ 
    printf("Not enough memory assigned!"); 
    return; 
} 
else 
{ 
    group[max_mem-1][0] = max; 
} 

print_groups(); 
test_print(); 

while (1) 
{ 
    printf("Enter a number:"); 
    scanf_s("%d", &n); 
    if ((n <= 1) || (n >= max-1)) 
    { 
     printf("Invalid entry!"); 
     continue; 
    } 
    search = 0; 
    for (int i = 1; i < max_mem; i++) 
    { 
     for (int j = 0; ((j < 2)&&(search!=1)); j++) 
     { 
      if (n == group[i][j]) 
      { 
       group[i][0] = 0; 
       group[i][1] = 0; 
       search = 1; 
      } 
      if (group[i][0]==n+1) 
      { 
       printf("Already group exists -> (%d,%d)", group[i][0], group[i][1]); 
       //getch(); 
       search = 1; 
      } 

     } 
    } 
    if (search != 1) 
    { 
     group[1][0] = n; 
     group[1][1] = n + 1; 
    } 

    printf("\nSorting!\n"); 
    sort(group); 
    //clrscr(); 
    print_groups(); 
    test_print(); 
} 
} 

void sort(int x[][2]) 
{ 
int i, j, t[1][2]; 
for (i = 1; i <= max_mem - 2; i++) 
for (j = 2; j <= max_mem-1 - i; j++) 
if (x[j - 1][0] >= x[j][0]) 
{ 
    t[0][0] = x[j - 1][0]; 
    x[j - 1][0] = x[j][0]; 
    x[j][0] = t[0][0]; 
    t[0][1] = x[j - 1][1]; 
    x[j - 1][1] = x[j][1]; 
    x[j][1] = t[0][1]; 
} 
} 

void print_groups() 
{ 
    printf("The group is:\n%d ", group[0][1]); 
    for (int i = 1; i < max_mem-1; i++) 
    { 
     if (group[i][0] != 0) 
     { 
      printf("("); 
      printf("%d,", group[i][0]); 
      printf("%d", group[i][1]); 
      printf(")"); 
     } 
    } 
    printf(" %d.", group[max_mem - 1][0]); 
    printf("\n"); 
} 

void test_print() 
{ 
    printf("Array Formation:\n"); 
    for (int i = 0; i < array_size; i++) 
    { 
     printf(" %d,%d ", group[i][0], group[i][1]); 
    } 
    printf("\n"); 
} 

Answer 1

On dirait que c'est juste une idée aléatoire. Vous pouvez simplifier votre code en utilisant un tableau à une dimension, où chaque entrée dans le tableau est

• 0 pour les numéros non dans un groupe
• 1 pour le premier numéro d'un groupe
• 2 pour la deuxième nombre d'un groupe

Par exemple, si array [4] est 1 et array [5] vaut 2, alors 4 et 5 sont un groupe.

Lorsque l'utilisateur entre un nouveau numéro, il est facile de mettre à jour la matrice. Voici un exemple en pseudo-code de la façon dont le tableau sera mis à jour si l'utilisateur entre le numéro 7

if (array[7] == 0 and array[8] == 0) 
    array[7] = 1, array[8] = 2 
else if (array[7] == 0 and array[8] == 1) 
    input is invalid 
else if (array[7] == 1) 
    array[7] = 0, array[8] = 0 
else if (array[7] == 2) 
    array[6] = 0, array[7] = 0