TD 04 - Parcours de tableau 1

1 Parcours simples

1.1 Exercice 1

On considère un nombre \(N\) écrit en base 2 sous la forme d’un tableau. Par exemple le nombre 13 s’écrit \((1101)\) en base 2 car \(1\times2^0+0\times2^1+1\times 2^2 +1\times2^3=13\).

Dans notre exercice, nous représenterons ce nombre avec le tableau :

1 0 1 1

Écrire un algorithme qui à partir d’un tel tableau renvoie l’écriture de cet entier en base 10.

1.2 Exercice 2 🏠

Pour chaque question on considère un tableau de taille \(n\).

  1. Écrire un algorithme affichant les éléments d’un tableau de façon alternée en commençant par le premier élément, puis le dernier, puis le second etc. Par exemple, pour le tableau [1,2,3,4,5] il affichera 1,5,2,4,3.
  2. Écrire un algorithme affichant les éléments d’un tableau de façon alternée en commençant par l’élément du milieu, puis en alternant les éléments à droite et à gauche. Par exemple, pour le tableau [1,2,3,4,5] il affichera 3,4,2,5,1.

1.3 Exercice 3

On considère un tableau T de \(n+1\) entiers compris entre 1 et \(n\). Chaque entier n’apparait qu’une fois dans le tableau sauf l’un d’eux, apparaissant deux fois, noté x.

  1. Écrire une relation simple entre la somme des éléments du tableau et x.
  2. En déduire un algorithme permettant de trouver l’élément en double en effectuant un seul parcours de tableau.

1.4 Exercice 4

Soit \(T\) un tableau d’entiers tous distincts de taille \(n\). Soient deux entiers \(1\leq i < j \leq n\), on dit que la paire d’indices \((i,j)\) est en inversion pour \(T\) si \(T[i] > T[j]\).

Écrire un algorithme NbInversion(T) qui renvoie le nombre de paire d’indices en inversion pour \(T\).

2 Recherche et vérifications

2.1 Exercice 5

On dit qu’un tableau est trié en vague si tout élément du tableau (à l’exception du premier et du dernier) est soit plus grand soit plus petit que ses deux voisins. Par exemple les tableaux [2,4,1,3,0] et [1,1,1,1] sont triés en vague mais pas le tableau [2,3,4,1].

  1. Écrire un algorithme EstTrie(T) qui retourne VRAI si le tableau T (de taille \(n\)) est trié en vague et FAUX sinon.
  2. Faire une analyse en meilleur et pire cas de la complexité de l’algorithme et donner sa complexité générale.
NoteExemples de tableaux triés en vague
  • [2,4,1,3,0] : 4 > 2 et 4 > 1 ✓, 1 < 4 et 1 < 3 ✓, 3 > 1 et 3 > 0 ✓
  • [1,1,1,1] : tous égaux à leurs voisins (condition satisfaite)
  • [2,3,4,1] : 3 > 2 mais 3 < 4 (ni max ni min local) ✗

2.2 Exercice 6

Écrire un algorithme itératif qui retourne VRAI si une chaîne de caractères est un palindrome et FAUX sinon. Analyser sa complexité en meilleur et pire cas.

2.3 Exercice 7

Écrire un algorithme qui retourne VRAI si les entiers du tableau T sont triés dans l’ordre croissant et FAUX sinon où T est vu comme un tableau circulaire. Par exemple, pour l’instance \(T=[4,5,1,2,3]\) l’algorithme renverra VRAI.

AstuceIndication

Commencer par rechercher l’élément le plus petit du tableau, puis vérifier la croissance des éléments suivants.

3 En plus

3.1 Exercice 8 🏠

On représente un entier positif en base 2 par un tableau de 0 et de 1. Pour se simplifier l’écriture des algorithmes on décide de placer le chiffre des unités à la première case du tableau.

Adapter l’algorithme d’addition classique à deux entiers binaires de \(n\) bits.

NoteRappel : Addition binaire
  • 0 + 0 = 0
  • 0 + 1 = 1
  • 1 + 0 = 1
  • 1 + 1 = 10 (0 avec retenue 1)
  • 1 + 1 + 1 (avec retenue) = 11 (1 avec retenue 1)

Exemple : 13 + 5 = 18 en binaire

  1101  (13)
+ 0101  (5)
------
 10010  (18)