Licence Informatique - Université de Bordeaux

Cette page est en lecture seule. Vous pouvez afficher le texte source, mais ne pourrez pas le modifier. Contactez votre administrateur si vous pensez qu'il s'agit d'une erreur.
===== Feuille 1 =====

==== Tableaux ====

//Nous supposerons que les tableaux ont déjà été vus et utilisés dans un cadre de programmation.// Pré-requis : le [[http://dept-info.labri.fr/ENSEIGNEMENT/algoprog/|cours d'algorithmique et programmation]] suivi en L1

Un //tableau// est un //type concret// (par opposition à //type abstrait//), puisqu'on précise comment les éléments sont //physiquement// stockés. Dans la plupart des langages, les éléments d'un tableau sont indexés à partir de 0. Ainsi, le premier élément d'un tableau T est T[0], le second est T[1], etc. Avec cette convention de numérotation (le premier élément a l'indice 0), l'indice le plus grand dans le tableau est donc ''len''(T) - 1 où ''len'' désigne la longueur d'un tableau T.

L'accès aux éléments s'effectue directement par l'indice, pour accéder à l’élément d’indice i on écrit T[i].
Le temps de calcul pour accéder à un élément du tableau est constant.


==== Tableaux en langage C ====

La définition et l'utilisation des tableaux varient d'un langage à l'autre, selon que les langages sont typés ou non, par exemple. Ainsi, en C, un tableau contient des éléments de même type -- celui que l'on déclare lorsqu'on introduit le tableau. //Vous en apprendrez plus sur les tableaux en C dans le cours de programmation C.//

<file c ex_tableau.c>
#include <stdio.h>
#include <stdlib.h>

int main() {
	int tab[10];

	for(int i = 0; i < 10; ++i) {
		tab[i] = (i+1)*2;
	}

	printf("Le tableau contient les 10 premiers nombres pairs: \n");
	for(int i = 0; i < 10; ++i) {
		printf("%d ", tab[i]);
	}
	printf("\n");

	return EXIT_SUCCESS;
}
</file>

Ce code utilise un tableau d'entiers de taille 10. On introduit les premiers 10 nombres pairs dans l'ordre croissante et on restitue le contenu du tableau. Vous en apprendrez plus (en cours de programmation) sur la fonction main, sur la déclaration de variables, sur la fonction ''printf'' ou sur la formulation des boucles. 

On compile ce code à l'aide de la commande ''gcc -std=c99 -Wall ex_tableau.c -o ex_tableau''. On l'exécute ensuite depuis le même répertoire avec la commande ''./ex_tableau''.


==== Exercice 1. Décalez les entrées d'un tableau d'entiers ====

Soit T un tableau d'entiers de taille N.

  - Proposez un algorithme qui décale d'une case vers la droite les entrées du tableau T à partir de la position k. Par exemple si T =[b,o,n,j,o,u,r], N=7 et k=3 le décalage donnera T=[b,o,n,j,j,o,u]. 
     * Remarques : On ne se soucie pas ici du fait que la valeur T[k] sera égale à la valeur T[k+1].On ne se soucie pas non plus d'avoir en quelque sorte perdu l'entrée T[N-1] initiale.
  - Dans quel cas l'algorithme de décalage peut-il être utilisé ?

==== Exercice 2. Fusionnez deux tableaux d'entiers triés par ordre croissant ====

Soient deux tableaux d'entiers T, T' de taille N, N' respectivement, qu'on supposera triés par ordre croissant. On souhaite obtenir un nouveau tableau T" de taille N + N' contenant les entrées des tableaux T et T', triées dans l'ordre croissant aussi.

  * Considérons un algorithme (pas très rusé) qui débute par recopier le tableau T au début de T", puis insère une à une les entrées de T'
    * A chaque fois, on recherchera à partir du début de  T" l'endroit où l'entrée T'[i] doit être insérée dans T", puis on décale les entrées au besoin.

  * Considérons maintenant un algorithme plus malin, qui ajoute dans T" //à la position courante//, soit une entrée de T, soit une entrée de T'
    * On tiendra à jour des indices i et i' indiquant le prochain élément de T et T' à ajouter à T"
    * On détermine qui de T[i] ou T'[i'] doit être inséré dans T"
    * On l'insère et on incrémente la position i'' où doit être inséré le prochain élément dans T"
    * On met à jour i ou i'

===== TD machine =====

//Avant de commencer:// [[http://dept-info.labri.fr/ENSEIGNEMENT/algoprog/DocumentsMemoTp/MemoTP.pdf]] 

Le programme suivant est à compléter pour les exercices qui suivent. Il vous permet également de tester vos fonctions.

<file c test_tableaux.c>

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <time.h>

#define N 10
#define N1 5
#define N2 10

bool rechercheElem (int tab[], int elem) {
    bool trouve = false;
    // TO DO
    return trouve;
}

void decaleTab (int tab[], int k, int n) {
    // TO DO
}

void fusionNaive (int tab1[], int tab2[], int newTab[]) {
    // TO DO
}

void fusionMaligne (int tab1[], int tab2[], int newTab[]) {
    // TO DO
}

int main() {
    int tab[N];
    int elem1, elem2;
    
    srand(time(NULL));    

    for(int i = 0; i < N; ++i) {
	tab[i] = rand()%100;
    }
    elem1 = tab[N-1];
    elem2 = 100;

    printf("Le tableau tab a ete initialise avec: \n");
    for(int i = 0; i < N; ++i) {
        printf("%d ", tab[i]);
    }
    printf("\n");
    
    printf("L'element %d se trouve dans le tableau tab. Est-ce le cas?\n", elem1);
    if ( rechercheElem(tab, elem1))
        printf ("vrai\n");
    else
        printf ("faux\n");
    
    printf("L'element %d ne se trouve pas dans le tableau tab. Est-ce le cas?\n", elem2);
    if ( !rechercheElem(tab, elem2))
        printf ("vrai\n");
    else
        printf ("faux\n");
    
    decaleTab(tab, 5, N);
    printf("Le tableau tab obtenu apres le decalage à partir de la position 5 est: \n");
    for(int i = 0; i < N; ++i) {
        printf("%d ", tab[i]);
    }
    printf("\n");
    
    int newN = N1 + N2;
    int tab1[N1], tab2[N2], newTab[newN];
    
    for(int i = 0; i < N1; ++i) {
        tab1[i] = i * 3;
    }
    
    printf("Le tableau tab1 a ete initialise avec: \n");
    for(int i = 0; i < N1; ++i) {
        printf("%d ", tab1[i]);
    }
    printf("\n");
    
    for(int i = 0; i < N2; ++i) {
        tab2[i] = i;
    }
    
    printf("Le tableau tab2 a ete initialise avec: \n");
    for(int i = 0; i < N2; ++i) {
        printf("%d ", tab2[i]);
    }
    printf("\n");
    
    for(int i = 0; i < newN; ++i) {
        newTab[i] = 0;
    }
    fusionNaive(tab1, tab2, newTab);
    printf("Le tableau newTab apres la fusion de tab1 et tab2 avec l'algo naif: \n");
    for(int i = 0; i < newN; ++i) {
        printf("%d ", newTab[i]);
    }
    printf("\n");
    
    for(int i = 0; i < newN; ++i) {
        newTab[i] = 0;
    }
    fusionMaligne(tab1, tab2, newTab);
    printf("Le tableau newTab apres la fusion de tab1 et tab2 avec l'algo malin: \n");
    for(int i = 0; i < newN; ++i) {
        printf("%d ", newTab[i]);
    }
    printf("\n");
    
    return EXIT_SUCCESS;
}

</file>
==== Exercice 3. Recherchez un élément dans un tableau ====

  * Ecrivez la fonction //rechercheElem// qui recherche si un élément donné //elem// est présent dans un tableau //tab//.

==== Exercice 4. Décalez les entrées d'un tableau d'entiers ====

  * Écrivez la fonction //decaleTab// qui implémente l'algorithme décrit dans l'exercice 1.

==== Exercice 5. Fusionnez deux tableaux d'entiers triés par ordre croissant ====

  * Écrivez les fonctions //fusionNaive// et //fusionMaligne//  qui implémentent les algorithmes décrits dans l'exercice 2.