1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239
| // Pour Zhao par Zavo
// Programme commenté avec visualisation des solutions sous forme de listes
// temps d'exécution: 15 millisecondes
#include <stdio.h>
#include <stdlib.h>
unsigned int * Tab1, *Reste,*Valid; // Les trois tableaux du traitement (algo Zhao)
unsigned int taille; // contiendra la taille de Tab1, Reste et Valid
unsigned char * numeros; // Contiendra tous les numéros possibles (1,2,3,...10,..)
//calcule les puissances de 2
unsigned int power2(unsigned int n)
{
unsigned int result=1;
int i;
for (i=1;i<=n;i++)
result *=2; // multiplier résultat par 2
return result;
}
// calcule le nombre de chiffres de n en binaire
// une expérience récente sur le forum DVP a prouvé que les décalages ne sont pas plus rapides.
unsigned int nbcb(unsigned int n)
{
unsigned int s=0; // totalisateur
while (n) // tantq ue n est non nul
{
s+=n%2; // ajoute le chiffre des unités
n/=2; // divise n par 2
}
return s;
}
// nombre de chiffres comuns à m et n
unsigned int communs(unsigned int m, unsigned int n)
{
return nbcb(m&n); // très rapide car & est un opérateur câblé (le bitwise-AND)
}
// Calcule combien peut supprimer n dans Reste
// sur la base de p éléments communs
unsigned int PeutSupprimer (unsigned int n, unsigned int p )
{
unsigned int s=0; // total mis à zéro au départ
unsigned int i;
for (i=0;i<taille;i++)
{
if (!Reste[i])// si l'élement est déjà supprimé passer immédiatement au suivant
continue;
if (communs(n,Reste[i])>=p) // on en a trouvé un
s++; // on incrémente le total
}
return s;
}
// Elimine de Reste tous les éléments ayant p au moins éléments communs avec n
void eliminer(unsigned int n, unsigned int p)
{
unsigned int i;
for (i=0; i<taille;i++)
if (communs(n,Reste[i])>=p)// plus de p éléments communs ?
Reste[i]=0; // si oui on enlève
}
// Calcule les coefficients Cp,n
unsigned int Cpn(unsigned int p, unsigned int n)
{
unsigned int s=0; // totalisateur
unsigned int i;
for (i=0;i<power2(n);i++)
if (nbcb(i)==p) s++;// Si p chiffres en base 2 on incrémente le compteur
return s;
}
// initialise Tab1 , Reste et Valid
void init(unsigned int p,unsigned int n)
{
unsigned int i,j;
taille=Cpn(p,n); // nombre de combinaisons de p dans n
// on remplit Tab1 à l'envers
Tab1= (unsigned int *) malloc (taille*sizeof(unsigned int));
for (i=0,j=taille-1;i<power2(n);i++)
if (nbcb(i)==p)
Tab1[j--]=i;
// On remplit Reste à l'endroit
Reste= (unsigned int *) malloc (taille*sizeof(unsigned int));
for (i=0,j=0;i<power2(n);i++)
if (nbcb(i)==p)
Reste[j++]=i;
// Valid est initalisé rien qu'avec des zéros ce qui veut dire 'vide'
Valid= (unsigned int *) malloc (taille*sizeof(unsigned int));
for (i=0,j=0;i<power2(n);i++)
if (nbcb(i)==p)
Valid[j++]=0;
// C'est la liste des numéros possibles pour restituer les listes à partir des binaires
numeros=(unsigned char *) malloc (n);
for (i=0;i<n;i++)
numeros[i]=(unsigned char)(i+1);
}
// ajouter un élément à Valid
// on le met au premier emplacement contenant une donnée nulle
void append(unsigned int n)
{
unsigned int i=0;
while (Valid[i])i++; // avancer jusqu'à trouver un zéro
Valid[i]=n;
}
// enlever un élément à un tableau (Tab1 ou Reste)
// On met 0 à sa place
void enleve(unsigned int n, unsigned int * T)
{
unsigned int i;
for (i=0;i<taille;i++)
if (n==T[i])
{
T[i]=0;
break;
}
}
// retourne le premier élément de Tab1 (non nul)
unsigned int firstoftab1()
{
unsigned int i;
for (i=0; i<taille;i++) // on parcourt Tab1
if (Tab1[i]) return Tab1[i]; // On s'arrête sur le premier non nul et on le renvoit.
return 0;
}
// Trouve la combinaison suivante par algorithme Zhao
unsigned int TrouveSuivant(unsigned int p)
{
unsigned int i,s,t,S;
// a priori la prochaine combinaison est la première qui se présente
s=PeutSupprimer(firstoftab1(),p);
S=firstoftab1();
for (i=0;i<taille;i++) // un parcourt Tab1
{
if (Tab1[i]) // seulement si l'élément n'a pas été supprimé
{
t=PeutSupprimer(Tab1[i],p); // on calcule combien il peut en supprimer
if (t>s) // plus que s ?
{
// si oui alors mise à jour de s et S
s=t;
S=Tab1[i];
}
}
}
return S; // retourner le meilleur candidat, celui qui en supprime le plus
}
// Calcule la longueur d'un tableau (le nombre d'éléments non nuls)
unsigned int longueur (unsigned int * T)
{
unsigned int i,s=0;
for (i=0;i<taille;i++)
if (T[i])s++;
return s;
}
// Voir la progression du traitement
void voir()
{
printf("%4d",longueur(Valid)); // pour voir combien d'éléments dans Valid
printf(" - ");
printf("%4d\n",longueur(Reste)); // pour voir combien d'éléments dans Reste
}
// algo proprement dit pour trouver Valid
void traite(unsigned int p)
{
unsigned X ;
printf("Progression:\n");
eliminer (Tab1[0],p); // on commence avec la première combinaison
append(Tab1[0]); // on la met dans Valid
enleve(Tab1[0],Tab1); // On nettoie Reste
voir(); // pour voir l'avancement
while (longueur(Reste)) // tant que Reste n'est pas vide
{
X=TrouveSuivant(p); // Trouver le suivant d'après le critère de Zhao
eliminer(X,p); // nettoyer Reste
append(X); // ajouter la nouvelle combinaison à Valid
enleve(X,Tab1); // retirer de Tab1 cette nouvelle combinaison
voir(); // Pour voir l'avancement
}
}
// reconstitue une liste de numéros à partir d'un nombre binaire
char * restitue (unsigned int n,unsigned int p, unsigned int k)
{
char * r=(char *) malloc(p); // pour p nombres tous <256
unsigned int i,u,v;
i=0;
v=p-1;
while (k) // tant que k n'est pas nul
{
u=k%2; // prendre le chiffre des unités de k
if (u) // est il égal à 1 ?
r[v--]=numeros[n-1-i]; // Si oui placer le numéro correspondant
k=k/2; // diviser k par 2
i++; // incrémenter i
}
return r;
}
// Liste tous les binaires de Valid sous forme de listes
void MontreValid(n,p)
{
unsigned int t= longueur(Valid);
unsigned int i,j; // compteurs de boucles
char * pc; // pour récupérer les listes
printf("Solution:\n");
for (i=0;i<t;i++) // affichage des éléments de Valid
{
pc=restitue(n,p,Valid[i]); // allocation de mémoire et affectation
for (j=0;j<p;j++) // affiche la liste reconstituée
printf("%2d ",pc[j]);
printf("\n");
free(pc); // libération de la mémoire allouée
}
}
//fonction principale
int main()
{
init(6,10); // initialisation
traite(5); // traitement
MontreValid(10,6); // Voir le résultat
return 0;
} |
Partager