Tableaux: implantation de fonctions classiques

#include <iostream>
#include <vector>
using namespace std;

Exercice: fonctions max et min

On a vu en TD comment calculer le maximum d’un tableau d’entiers. On va maintenant aborder des variantes, comme calculer le maximum d’un tableau de chaînes de caractères. On appellera nos fonctions monMax et monMin afin d’éviter des conflits avec les fonctions préexistantes de C++.

Comme les exemples suivants l’illustrent, la comparaison de deux chaînes de caractères se fait – en C++ comme dans la plupart des langages – selon l’ordre lexicographique (celui du dictionnaire):

string("alice") < string("bob")
string("alice") < string("alain")
  1. Implanter la fonction monMax dont la documentation est donnée ci-dessous, qui prend en entrée un tableau d’entiers et renvoie le plus grand.
    Indication: Si besoin, inspirez vous de la fonction mystere de l’exercice 2 du TD (mais le mieux est de savoir le faire seul).

/** Maximum d un tableau d entiers
 * @param t un tableau d entiers
 * @return l élément le plus grand du tableau
 **/
int monMax(vector<int> t) {
    /// BEGIN SOLUTION
    int m = t[0];
    for ( int i = 1; i < t.size(); i++ ){
        if ( t[i] > m ) {
            m = t[i];
        }
    }
    return m;
    /// END SOLUTION
}
  • Vérifier que la fonction se comporte comme prévu :

monMax( { 5, -1, 3, 7, -4, 8, 4 } )
CHECK( monMax( { 5 }) == 5 );
CHECK( monMax({ 5, -1, 3, 7, -4, 8, 4 }) == 8 );
  1. Écrire la documentation puis implanter la fonction monMin qui prend en entrée un tableau de chaînes de caractères et renvoie la plus petite pour l’ordre lexicographique :

/// BEGIN SOLUTION
/** Minimum d un tableau de chaînes de caractères
 * @param t un tableau de string
 * @return l élément le plus petit du tableau
 **/
 /// END SOLUTION
string monMin(vector<string> t) {
    /// BEGIN SOLUTION
    string m = t[0];
    for ( int i = 1; i < t.size(); i++ ){
        if ( t[i] < m ) {
            m = t[i];
        }
    }
    return m;
    /// END SOLUTION
}
monMin( { "bonjour", "allo", "xylophone", "fonction", "schtroumpf" } )
  • Le test précédent était manuel. Transformer le en test automatique équivalent, en utilisant CHECK :

/// BEGIN SOLUTION
CHECK( monMin({ "bonjour", "allo", "xylophone", "fonction", "schtroumpf" }) == "allo");
/// END SOLUTION
CHECK( monMin( { "coucou"}) == "coucou" );
CHECK( monMin( { "ok", "bonjour", "quarante-deux", "info-111"}) == "bonjour" );
/// BEGIN HIDDEN TESTS
CHECK( monMin({ "bonjour", "allo", "xylophone", "fonction", "schtroumpf" }) == "allo");
/// END HIDDEN TESTS

Exercice

Compléter chacune des fonctions suivantes:

  • Si il n’y a pas de documentation, l’écrire;

  • Si la fonction est vide, l’implanter;

  • S’il n’y a pas de tests automatiques, en rajouter en utilisant CHECK.

Fonction estPositif :

/** Positivité des éléments d un tableau
 * @param t un tableau de réels
 * @return un booléen qui vaut true ssi tous les éléments du tableau sont positifs
 **/
bool estPositif(vector<float> tab) {
    for(int i=0; i < tab.size(); i++){
        if ( tab[i] < 0. ) {
            return false;
        }
    }
    return true;
 }

Tests:

/// BEGIN SOLUTION
CHECK(     estPositif( {1.25, 4.0001, 2.9} ) );
CHECK( not estPositif( {1.2,    -1.8, 2.8} ) );
/// END SOLUTION

Fonction incremente

La fonction suivante renvoie un tableau. En principe on devrait mettre vector<int> comme type de retour. Pour contourner un bug dans cling (corrigé dans la version de développement), on va mettre le type tableau à la place, après avoir défini ce type comme un alias pour vector<int>.

typedef vector<int> tableau;
/** Fonction incremente
 * @param t un tableau d entiers
 * @return un tableau d entiers obtenu en incrémentant de 1 chaque valeur de t
 **/
tableau incremente(vector<int> t) {
    /// BEGIN SOLUTION
    for ( int i=0; i < t.size(); i++ ) {
        t[i] = t[i] + 1;
    }
    return t;
    /// END SOLUTION
}

Tests:

CHECK( incremente({5,1,3}) == vector<int>({6,2,4}) )

Fonction egale

/** Teste si deux tableaux sont égaux (même longueur, mêmes valeurs)
 * @param t1: un tableau d entiers
 * @param t2: un tableau d entiers
 * @return true si les deux tableaux sont égaux, false sinon
 **/
bool egale(vector<int> t1, vector<int> t2) {
    if( t1.size() != t2.size() ) {
        return false;
    }
    for ( int i=0; i < t1.size(); i++ ) {
        if ( t1[i] != t2[i] ) {
            return false;
        }
    }
    return true;
}

Tests:

/// BEGIN SOLUTION 
CHECK(     egale({1,2,3}, {1,2,3})  );
CHECK( not egale({1,2,3}, {1,2})    );
CHECK( not egale({1,2,3}, {1,-4,3}) );
/// END SOLUTION

Fonction produitTableau

Implanter la fonction documentée ci-dessous.
Indication: Inspirez-vous de la fonction somme du cours.

/** renvoie le produit de tous les éléments d un tableau d entiers
 * @param t un tableau d entiers
 * @return le résultat du calcul de t[0] * t[1] * t[2] * ... 
 **/
/// BEGIN SOLUTION
int produitTableau(vector<int> t) {
    int resultat = 1;
    for ( int i = 0; i < t.size(); i++ ) {
        resultat = resultat * t[i];
    }
    return resultat;
}
/// END SOLUTION
produitTableau({2, 3, 4}) // doit valoir 24
produitTableau({0, 10, 100}) // doit valoir 0

Tests:

/// BEGIN SOLUTION
CHECK( produitTableau({1, 2, 3, 4}) == 24 );
CHECK( produitTableau({0, 42, 42}) == 0   );
/// END SOLUTION

Fonction plusDeVrai

/** Teste si un tableau contient plus de `true` que de `false`
 * @param tab un tableau de booleen
 * @return true si le tableau contient plus de `true`, `false` sinon
 **/
bool plusDeVrai(vector<bool> tab) {
    /// BEGIN SOLUTION
    int nbTrueFalse = 0;
    for ( int i = 1; i < tab.size(); i++ ) {
        if ( tab[i] ) {
            nbTrueFalse++;
        } else {
            nbTrueFalse--;
        }
    }
    return (nbTrueFalse>0);
    /// END SOLUTION
}

Tests:

/// BEGIN SOLUTION
CHECK(     plusDeVrai({true, true, false, true}) );
CHECK( not plusDeVrai({false, true, false})      );
/// END SOLUTION
/// BEGIN HIDDEN TESTS
CHECK(     plusDeVrai({true, true, false, true}) );
CHECK( not plusDeVrai({false, true, false})      );
/// END HIDDEN TESTS

Fonction contient

La fonction contient prend en argument un tableau et un entier et renvoie vrai si le tableau contient l’entier, faux sinon.

/// BEGIN SOLUTION
/** Test de présence d un entier dans un tableau
 *  @param t un tableau d entiers
 *  @param x un entier
 *  @return true si le tableau t contient x, false sinon
 **/
/// END SOLUTION
/// BEGIN SOLUTION
bool contient(vector<int> t, int x) {
    for ( int i=0; i < t.size(); i++ ) {
        if ( t[i] == x ) {
            return true;
        }
    }
    return false;
}
/// END SOLUTION

Tests:

CHECK(     contient( { 5, -1, 8, 4 }, 8) );
CHECK( not contient( { 1, 2 }, 42)       );