106 lines
2.2 KiB
C
106 lines
2.2 KiB
C
#include <stdio.h>
|
|
#include <stdlib.h>
|
|
#include <pthread.h>
|
|
#include <assert.h>
|
|
#include <time.h>
|
|
|
|
#define ELIMINE -1
|
|
|
|
typedef struct duel{
|
|
int* liste;
|
|
int debut;
|
|
int tailleGroupe;
|
|
} duel;
|
|
|
|
void affichage(int* liste, int capacite){
|
|
int i;
|
|
for(i=0; i<capacite; i++){
|
|
if (liste[i] != ELIMINE){
|
|
printf("%d ",liste[i]);
|
|
}
|
|
}
|
|
printf("\n");
|
|
}
|
|
|
|
int* creerListe(int taille){
|
|
int* liste = (int*) malloc(taille*sizeof(int));
|
|
int i;
|
|
for (i=0; i<taille; i++){
|
|
liste[i] = (rand()%100);
|
|
}
|
|
return liste;
|
|
}
|
|
|
|
int plusPetit(int* liste, int debut, int nb){
|
|
int plusGrand = -1;
|
|
int i;
|
|
int participant1 =- 1;
|
|
int indiceParticipant1;
|
|
for (i=0; i<nb; i++){
|
|
if (liste[debut+i] != ELIMINE){
|
|
if (participant1 == -1){
|
|
participant1 = liste[debut+i];
|
|
indiceParticipant1 = i;
|
|
}
|
|
else{
|
|
if (liste[debut+i] > participant1){
|
|
return debut + indiceParticipant1;
|
|
}
|
|
else{
|
|
return debut + i;
|
|
}
|
|
}
|
|
}
|
|
}
|
|
return -1;
|
|
}
|
|
|
|
void *tournois(void *argument) {
|
|
duel duo = *((duel*) argument);
|
|
int i;
|
|
int perdant = plusPetit(duo.liste, duo.debut, duo.tailleGroupe);
|
|
duo.liste[perdant] = -1;
|
|
return NULL;
|
|
}
|
|
|
|
int puissance2(int n){
|
|
int p;
|
|
for (p=1; p<n; p*=2){}
|
|
if (p==n){
|
|
return 1;
|
|
}
|
|
return 0;
|
|
}
|
|
|
|
int main(int argc, char** argv[]) {
|
|
int nbParticipant = argc-1;
|
|
int nbDuel = nbParticipant/2;
|
|
int* listeParticipant;
|
|
|
|
assert(puissance2(nbParticipant)==1);
|
|
srand(time(NULL));
|
|
listeParticipant = creerListe(nbParticipant);
|
|
affichage(listeParticipant, nbParticipant);
|
|
|
|
while (nbDuel>=1){
|
|
pthread_t threads[nbDuel];
|
|
duel argument[nbDuel];
|
|
int i;
|
|
for (i=0; i<nbDuel; i++){
|
|
argument[i].liste = listeParticipant;
|
|
argument[i].debut = i*(nbParticipant/nbDuel);
|
|
argument[i].tailleGroupe = nbParticipant/nbDuel;
|
|
}
|
|
for (i=0; i<nbDuel; i++){
|
|
assert( pthread_create(&threads[i], NULL, tournois, &argument[i]) == 0);
|
|
}
|
|
for (i=0; i<nbDuel; i++){
|
|
assert( pthread_join(threads[i], NULL) == 0);
|
|
}
|
|
affichage(listeParticipant, nbParticipant);
|
|
nbDuel /= 2;
|
|
}
|
|
|
|
return EXIT_SUCCESS;
|
|
}
|