R1.01 – Prog#9 – Exercice 1

Ecrivez la procédure triSelection () de signature

void triSelection (vector<unsigned> & vUint);

Cette procédure trie le vecteur en paramètre selon la méthode du tri par sélection / échange (cf. R1.01 – Algo8 – eox2).

Afin d’initialiser votre vecteur, ajouter ces lignes dans le main () :

#include <cstdlib>
#include <ctime>
...
srand (time(NULL));
vector<unsigned> vUInt (XXX);

for (auto & val : vUInt)
     val = rand () % (vUInt.size() * 10);

Pour finir, écrivez la fonction testVecteurTrie () de signature

void testVecteurTrie (const vector<unsigned> & vUint);

Cette fonction doit tester si le vecteur qui lui est passé en paramètre est trié. Cette vérification doit de faire à l’aide de la fonction assert ().

NB : pensez à mettre un message à la fin de votre fonction testVecteurTrie () pour vous assurer que vous passez tous les tests.

R1.01 – Prog#9 – Exercice 5

Insérer dans le code suivant vos algorithmes de tri.
Modifier le .pro en ajoutant la ligne LIBS += -pthread

Puis faite divers tests en faisant varier les paramètres d’entrée :

  1. la taille des vecteurs;
  2. le nombre de vecteurs différents;
  3. nombre d’itérations par vecteur;
#include <iostream>
#include <vector>
#include <iomanip>
#include <cstdlib>
#include <ctime>
#include <algorithm>
#include <thread>
#include <cassert>

using namespace std;
typedef vector <vector<double>> CMatrix;

CMatrix Mat;

void selectSort (vector <unsigned> & tab){
    //TODO
}

void insertSort (vector <unsigned> & vUint)
{
//TODO
}

void bubbleSort (vector <unsigned> & vUint)
{
//TODO
}

void countingSort (vector <unsigned> & vUint)
{
//TODO
}

void languageSort (vector<unsigned> & VUint)
{
    sort (VUint.begin(), VUint.end());
}

void initMat (unsigned NbColumns)
{
    Mat.resize(5, vector <double> (NbColumns));
}

//http://stackoverflow.com/questions/2962785/c-using-clock-to-measure-time-in-multi-threaded-programs
void protoGenericSort(void (*mySort) (vector <unsigned> & vUint), const vector <unsigned> & vUint, unsigned NbFois, unsigned PosMat, unsigned VectNum)
{
    for (unsigned i (0); i < NbFois; ++i)
    {
        vector <unsigned> copyVUint (vUint);
        struct timespec start, finish;
        double elapsed;
        clock_gettime(CLOCK_MONOTONIC, &start);
        mySort (copyVUint);
        clock_gettime(CLOCK_MONOTONIC, &finish);
        elapsed = (finish.tv_sec - start.tv_sec);
        elapsed += (finish.tv_nsec - start.tv_nsec) / 1000000000.0;
        Mat [PosMat][i + NbFois * VectNum] = elapsed;
    }
}

void traiterResultats (const unsigned & nbElemAEnlever)
{
    for (vector <double> & UneLigne : Mat)
    {
        //tri
        sort (UneLigne.begin(), UneLigne.end());
        //suppresion des éléments non significatifs
        UneLigne = vector <double> (UneLigne.begin() + nbElemAEnlever / 2, UneLigne.end() - nbElemAEnlever / 2 );
        //plus petit temps
        double min (UneLigne[0]);
        //plus grand temps
        double max (UneLigne[UneLigne.size()-1]);
        //temps median
        double med (UneLigne[UneLigne.size()/2]);

        //On assigne les valeurs memorisees aux 3 premières cases
        UneLigne[0] = min;
        UneLigne[1] = med;
        UneLigne [2] = max;
    }
    //Affichage
    cout << setw (20) << "Tri" << setw (10) << "Min" << setw (10) << "Med" << setw (10) << "Max" << endl;
    vector<string> VMetode {"Selection", "Insertion", "Bulles", "comptage", "Langage"};
    for (unsigned i (0); i < VMetode.size(); ++i)
        cout << setw (20) << VMetode[i] << setw (10) << setprecision(6) << Mat[i][0] << setw (10) << setprecision(6) << Mat[i][1] << setw (10) << setprecision(6) << Mat[i][2] << endl;

}

int main(int argc, char *argv[])
{
    if (argc != 4)
    {
        cerr << "boulette !\n utilisation : " << argv [0] << " (1) NbElem par vecteur (2) Nb de vecteurs differents (3) Nb itérations par vecteur" << endl;
        return 1;
    }

    unsigned NbElem (stoul(argv[1]));
    unsigned NbVecteurs (stoul(argv[2]));
    unsigned NbFois (stoul(argv[3]));

    srand (time(NULL));
    vector <unsigned> VUInt (NbElem);
    initMat (NbFois * NbVecteurs);


    for (unsigned i (0); i < NbVecteurs; ++i)
    {
        for (auto & Val : VUInt)
            Val = rand () % (VUInt.size() * 10);

        thread th1 (protoGenericSort, selectSort, VUInt, NbFois, 0, i);
        thread th2 (protoGenericSort, insertSort, VUInt, NbFois, 1, i);
        thread th3 (protoGenericSort, bubbleSort, VUInt, NbFois, 2, i);
        thread th4 (protoGenericSort, countingSort, VUInt, NbFois, 3, i);
        thread th5 (protoGenericSort, languageSort, VUInt, NbFois, 4, i);
        th1.join();
        th2.join();
        th3.join();
        th4.join();
        th5.join();
        cout << i << "fini" << endl;
    }

    cout << "Taille des vecteurs : " << NbElem << "\nNb de vecteurs : " << NbVecteurs << "\nNb iterations par vecteur : " << NbFois << endl;
    //On traite les résultats en supprimant 10% des éléments
    traiterResultats (NbFois * NbVecteurs / 10);
    return 0;
}

R1.01 – Prog#10 – Exercice 1

Mettre de la couleur dans le terminal sous GNU / Linux

Puisque les cours d’IHM (Interface Homme Machine) ne commencent qu’au second semestre, nous allons voir comment nous pouvons spécifier, dans un programme, la couleur des caractères ainsi que celle du fond d’une console, mais aussi effacer son contenu.
Puisque la console est une émulation d’un terminal VT100, toutes les instructions que nous allons lui donner commencent par \033[. Ensuite, une autre séquence d’instruction, concaténée à la première, provoque l’effacement de l’écran, le changement de la couleur de la police ou du fond.

Remarque : les informations évoquées dans cette partie fonctionnent aussi sous Mac OS-X, mais pas sous Windows.

Effacer l’écran

Afin d’effacer l’écran, la seconde séquence est : H\033[2J. En conséquence, la fonction suivante permet d’effacer l’écran :

void clearScreen () {
    cout << "\033[H\033[2J";
}

Copiez la.

Changer la couleur

Afin de changer la couleur, la seconde séquence est : XXm, où m est le code de la couleur souhaitée. Ce code est constitué de 2 chiffres comme le montre le tableau suivant :

Couleur Code associé
0 réinitialise le système de couleur à la valeur par défaut du shell
30 Noir
31 Rouge
32 Vert
33 Jaune
34 Bleu
35 Magenta
36 Cyan

 

Copiez le code suivant :

const unsigned KReset   (0);
const unsigned KNoir    (30);
const unsigned KRouge   (31);
const unsigned KVert    (32);
const unsigned KJaune   (33);
const unsigned KBleu    (34);
const unsigned KMAgenta (35);
const unsigned KCyan    (36);
	
void couleur (const unsigned & coul) {
    cout << "\033[" << coul <<"m";
}

Le code suivant :

couleur (KRouge);
cout << "Rouge" << endl;
couleur (KVert);
cout << "Vert" << endl;
couleur (KReset);
cout << "Retour à la normale" << endl;

provoquera l’affichage :
Rouge
Vert
Retour à la normale

Changer le fond

Pour changer le fond, c’est exactement la même séquence d’instructions que pour changer la couleur. La seule différence provient du fait que les couleurs associées voient leur code respectif augmenté de 10.

Pour des informations complémentaires quant à la gestion du terminal (sous GNU / Linux), vous pouvez visiter cette page.

R1.01 – PROG#10 – Exercice 2 – Candy Crush

Gestion de la grille

Le but du projet est de réaliser une version simplifiée du célèbre jeu “Candy Crush” (pour plus d’informations voir ici).

Les règles du jeu sont les suivantes :

  1. Contrairement aux règles du jeu originel, on va essayer de faire des combinaisons de nombres et non de sucreries;
  2. Un joueur à KMaxTimes coups pour réaliser le meilleur score;
  3. A chaque tour, il choisit les corrodées d’un numéro de la grille et un déplacement (horizontal ou vertical). Les touches valides de déplacement sont ‘A’ (gauche),
    ‘Z’ (haut), ‘E’ (droit), ‘S’ (bas).
  4. S’il réussit à faire une combinaison d’au moins 3 chiffres identiques :
    1. ceux-ci sont supprimés;
    2. on fait monter les chiffres du dessous;
    3. Les nouvelles cases vides ne sont plus utilisables;
    4. le score est cumulé avec le score courant. Le score est la somme du nombre de cases supprimées (par exemple, si on fait une combinaison de 3 chiffres ‘2’ à la suite, le score est augmenté de 6).
  5. Le but est donc de vider la grille le plus rapidement possible.

La grille est représentée par une matrice de taille NxN.
En conséquence, nous pouvons définir les alias suivants :

typedef vector <unsigned> line; // un type représentant une ligne de la grille
typedef vector <line> mat; // un type représentant la grille
struct maPosition { 
unsigned abs;
unsigned ord
}; // une position dans la girlle

Initialisation de la grille

Ecrire la fonction initGrid () de profil :

void initGrid (mat & grid, const size_t & matSize)

Cette fonction a pour but d’initialiser toutes les cases de la grille des nombres tirés au hasard entre 1 et une constante KNbCandies à définir.

Affichage de la grille

Travail à effectuer : écrivez le corps de la fonction displayGrid () de profil :

void  displayGrid (const mat & grid)

Cette fonction doit :

  1. faire appel à la fonction clearScreen ();
  2. remettre la couleur des caractères à sa valeur par défaut;
  3. afficher case / case le contenu de la case courante. Si la case n’est pas occupé par un nombre compris entre 1 et KNbCandies, on affiche une case vide, sinon, on affiche le nombre courant.

R1.01 – PROG#10 – Exercice 3 – Candy Crush

Le jeu

Placement d’un jeton au bon endroit

Ecrire la fonction makeAMove () de profil :

void makeAMove (mat & grid, const maPosition & pos, const char & direction)

Cette fonction permute, dans la grille, le nombre situé initialement à la position pos (aux coordonnées pos.abs, pos.ord)
avec la case de destination selon
la valeur du caractère direction.

Detection d’une suite de nombres identiques sur la même colonne

Ecrire le corps de la fonction  atLeastThreeInAColumn () de profil :

bool atLeastThreeInAColumn (const mat & grid, maPosition & pos, unsigned & howMany);

Cette fonction parcourt la grille afin de trouver une suite d’au moins 3 nombres identiques sur la même colonne. Elle renvoie vrai si une telle suite a été trouvée, faux sinon.
Si elle a renvoyée vrai, on a une suite de howMany tous égaux à partir des coordonnées pos.

Detection d’une suite de nombres identiques sur la même ligne

Ecrire le corps de la fonction atLeastThreeInARow () de profil :

bool atLeastThreeInARow (const mat & grid, maPosition & pos, unsigned & howMany);

Cette fonction parcours la grille afin de trouver une suite d’au moins 3 nombre identiques sur la même ligne. Elle renvoie vrai si une telle suite a été trouvée, faux sinon.
Si elle a renvoyée vrai, on a une suite de howMany tous égaux à partir des coordonnées pos.

Suppression dans une colonne

Ecrire le corps de la fonction removalInColumn () de profil :

	void removalInColumn (mat & grid, const maPosition & pos, unsigned  howMany);

Cette fonction supprime les howMany nombres identiques de la colonne pos.abs à partir de la ligne pos.ord, remonte ceux qui sont en dessous et complète la ligne avec la constante KImpossible.

Suppression dans une ligne

Ecrire le corps de la fonction removalInRow () de profil :

	void removalInRow (mat & grid, const maPosition & pos, unsigned  howMany);

Cette fonction supprime les howMany nombres identiques de la ligne pos.ord à partir de la colonne pos.abs, remonte ceux qui sont en dessous et complète la ligne avec la constante KImpossible. Pour écrire cette fonction, on doit s’appuyer sur la fonction removalInColumn ().

L’algorithme principal

Le but de cette partie est d’écrire la fonction main () .
Cette fonction :

  1. initialise la grille du jeu ainsi que le nombre de coup maximal;
  2. entre dans une boucle tant qu’on n’a pas atteint le nombre maximal de coups :
    1. affiche la grille;
    2. affiche un petit menu donnant les consignes de déplacement;
    3. saisit les coordonnées du nombre à deplacer ainsi que le déplacement souhaité;
    4. fait les tests de suppression en ligne / colonne;
    5. fait les suppression si besoin;
    6. met à jour le score si besoin;
  3. affiche le score final.