Vecteurs et Tableaux

Objectifs
Exercices sur les tableaux

Exercices simples sur les tableaux

  • Calculer la somme des éléments d’un tableau d’entiers donné.
  • Calculer simultanément la somme des éléments positifs d’un tableau et la somme des éléments négatifs d’un tableau.
  • Écrire une fonction prenant en entrée un tableau de réels et déterminant l’indice d’un élément maximal ?
  • Écrire une fonction prenant en entrée un tableau $t$ non vide, et renvoyant un couple $(i,j)$ tel que $i\geq j$ et $\lvert t_i-t_j \rvert$ est maximal.
  • Écrire une fonction prenant en entrée un tableau $t$ non vide, et renvoyant true si le tableau possède un élément répété au moins deux fois, et false sinon.
  • Écrire une procédure prenant en entrée un tableau $t$ non vide, et affichant la liste (éventuellement vide) des couples $(i,j)$ tels que $i < j$ et $t_i = t_j$.

Conversion décimal vers binaire

On veut automatiser la conversion d’une base vers une autre, pour cela on va faire l’exemple de la traduction d’un nombre en base 10 $M = d_k d_{k-1} \ldots d_2 d_1 d_0$ vers son équivalent en base 2 $a_l d_{l-1} \ldots a_2 a_1 a_0$:

  • On remarque que $a_0$ est le reste de la division euclidienne de $M$ par $2$.
  • Si $M_1 = \frac{M - a_0}{2}$ (nombre entier !), alors $a_1$ est le reste de la division euclidienne de $M’$ par $2$.
  • Si $M_i < 2$, alors $n=i$ et $a_n$ vaut $M_i$.

Questions

  • Concevoir une procédure qui imprime les chiffres de la décomposition en base $2$ d’un entier $x$ passé en paramètre, en imprimant le poids le plus faible à gauche (puisqu’on calcule les poids les plus faibles en premier).
  • Concevoir une procédure qui stocke dans un tableau les chiffres de la décomposition en base $2$ d’un entier $x$ passé en paramètre, puis les imprime les poids les plus faibles à droite.

Évaluation de polynômes

Le polynôme $P=4-3X+X^2+5X^3$ peut être stocké dans un tableau de la forme $[4,-3,1,5]$. D’une manière générale, on stocke le polynôme $p_0+p_1X+…+p_nX^n$ dans un tableau de longueur $n+1$: $[p_0,p_1,…,p_n]$.

  • Écrire une fonction qui pour un $t$ donné évalue $P(t)$
  • Quelle est la complexité de votre fonction pour évaluer un polynôme de degré $d$ ? Essayez de proposer une version optimale de l’évaluation d’un polynôme\ldots en constatant que $P$ peut s’écrire $P = 4 + X \times (-3 + X \times (1 + X \times 5 ))$

Tableau contenu dans un autre

On considère deux tableaux $A$ et $B$ de $N$ entiers. On dit que $A$ est contenu dans $B$ lorsque tous les éléments de $A$ figurent au moins une fois dans $B$.

  • Écrire une fonction qui, étant donné un entier $x$, dit si il apparaît dans un tableau $B$.
  • Écrire une fonction qui sans trier les tableaux, dit si $A$ est contenu dans $B$. On pourra utiliser la fonction précédente.
  • Compter le nombre de comparaisons de votre algorithme.
  • Si le tableau $B$ est trié, peut-on améliorer l’algorithme ?

Maxima dans un tableau

On cherche le deuxième élément le plus grand d’un tableau $t$ de taille $N$ fixée. On suppose que tous les éléments de $t$ sont distincts.

  • Écrire un algorithme qui commence par chercher le maximum, puis refait un parcours pour trouver le deuxième.
  • Écrire un algorithme qui trouve le résultat en un seul parcours.
  • Comparer les deux algorithmes en terme de nombre de comparaisons effectuées.

Produit scalaire de deux vecteurs

Écrire un algorithme qui calcule le produit scalaire de deux vecteurs de même taille passés en paramètre. Rappel~:

La taille commune des deux vecteurs pourra être passée en paramètre.

Factoriel encore !

Écrire un algorithme qui calcule et stocke dans un tableau (vecteur) de taille N les entiers $0!$, $1!$ \ldots $N-1!$, en faisant un minimum de multiplications. Quelle est la complexité de votre algorithme?

On rappelle que $i!=1\times 2\times 3 \times \ldots i$.

Crible d’Ératosthène

Implémenter la méthode du crible dont le principe est le suivant. (\emph{Source: wikipedia}) L’algorithme procède par élimination: il s’agit de supprimer d’une table des entiers de $2$ à $N$ tous les multiples d’un entier. En supprimant tous les multiples, à la fin il ne restera que les entiers qui ne sont multiples d’aucun entier, et qui sont donc les nombres premiers. On commence par rayer les multiples de $2$, puis à chaque fois on raye les multiples du plus petit entier restant. On peut s’arrêter lorsque le carré du plus petit entier restant est supérieur au plus grand entier restant, car dans ce cas, tous les non-premiers ont déjà été rayés précédemment. À la fin du processus, tous les entiers qui n’ont pas été rayés sont les nombres premiers inférieurs à $N$.

Tableaux de mots

Les mots seront supposés codés sour forme d’un d’un tableau de caractères de taille $N$ (fixé, grand) dont le dernier est égal à \0 (caractère spécial de fin de chaîne).

  • Écrire un algorithme pour calculer la taille d’un mot.
  • Écrire un algorithme pour renverser un mot en place. Le mot à inverser et la taille de ce mot seront passés en paramètres.
  • Écrire un algorithme pour dire si un mot donné est un palindrome. On passera la taille de ce mot en paramètre.
  • Soient M1 et M2 deux mots de tailles respectives $l_1$ et $l_2$. Écrire un algorithme permettant de déterminer si le deuxième mot est un anagramme du premier.

Tableaux de mots (bis)

Écrire les programmes suivants:

  • Déterminer et afficher le nombre d’apparitions d’une lettre donnée par l’utilisateur dans un tableau.
  • Déterminer le premier indice d’apparition de chacune des lettres et afficher sous la forme~:
'a' n'apparait jamais
'b' apparait pour la première fois en position 0
'c' apparait pour la première fois en position 35
...

On n’utilisera pas de tableau, et pour chaque lettre on utilisera une boucle while.

  • Déclarer et initialiser un tableau occurrences qui va nous servir à compter le nombre d’apparitions de chaque lettre. De quelle taille est-il ?
  • Remplir le tableau occurrences avec le nombre d’apparition de chaque lettre dans le tableau tab, et afficher le résultat ensuite sous la forme:
'a' apparait 0 fois
'b' apparait 1 fois
'c' apparait 4 fois
...
  • Afficher le contenu du tableau tab dans l’ordre alphabétique. On utilisera le tableau occurrences, et si le caractère 'a' n’apparaît pas, on n’affichera pas 'a'.
  • Utiliser le tableau occurrences pour modifier le tableau tab afin qu’il soit trié par ordre alphabétique, puis afficher le tableau tab afin de vérifier qu’il est trié. Indication~: avec le tableau occurrences, on connaît le nombre d’occurrences de chaque caractères. On peut donc écraser le contenu du tableau tab sans perdre la moindre donnée.

Tableaux de mots (ter)

  • Écrire un programme qui écrit un fichier à l’envers. Indication~: On se demandera comment mémoriser les caractères du fichier
  • Écrire un programme qui dit si un certain mot (un “motif”) est présent dans un fichier.
  • Écrire un programme qui dit si les parenthèses d’un fichier sont bien imbriquées. On ignore les autres caractères. Dans (())() les parenthèses sont bien imbriquées, mais pas dans ((((()(.

Exercice simple sur les matrices

  • Déclarer un tableau à 100 lignes et 200 colonnes, et initialiser le tableau avec des entiers tirés au hasard entre 0 et 50.
  • Écrire une procédure affiche_2d qui prend en paramètre un tableau à CMAX colonnes et LMAX lignes et qui affiche ce tableau en lignes et colonnes.

Exercice simple sur les matrices (bis)

Écrire un algorithme somme_tab2dim qui prend en paramètre un tableau tab à deux dimensions et qui:

  • additionne, colonne par colonne, les lignes du tableau et place le résultat dans un tableau ligne;
  • idem par ligne
  • additionne toutes les cases.
  • Déterminer l’indice de la colonne dont la somme des coefficients est la plus grande.

Relation d’ordre

Soient $n$ un entier et $M[n][n]$ une matrice de booléens représentant une relation $R$ sur les entiers de la façon suivante~: $M[i][j] = true$ si et seulement si $iRj$. Écrire des algorithmes permettant de déterminer si $R$ est réflexive, symétrique, transitive.