Durée : 2 h

1- OBJECTIFS

• Savoir concevoir de façon intuitive des petits algorithmes itératifs sur des tableaux
• Connaître quelques algorithmes élémentaires solutionnant des problèmes classiques
• Savoir programmer en Java de tels algorithmes

• Consignes générales :
• Recommandation : concevoir d'abord les algorithmes en pseudo-langage avant de les exprimer en Java
• On s'interdit l'emploi de la méthode des bibliothèques Java qui solutionnerait d'emblée le problème posé
• Il est attendu des solutions itératives, non pas récursives
• Le travail demandé doit être terminé, en séance ou hors séance
• Le niveau de difficulté de chaque exercice (algorithme ou/et programmation) est spécifié par un nombre d'étoiles :
          *    facile
          **   peu difficile
          ***  assez difficile
          **** difficile ou assez long à réaliser

Ecrire en Java une méthode inversant un tableau d'entiers :
• paramètre : un tableau t d'entiers
• valeur de retour : aucune
• exemple :
    t = [ 12  15  50  0  100  200  0  0  4 ] devient t =  [ 4  0  0  200  100  0  50  15  12 ]
• contraintes de réalisation : pas d'utilisation d'autre tableau que le tableau fourni ; ne visiter chaque case du tableau qu'une fois au plus.
  

Ecrire en Java une méthode recherchant l'élément d'un tableau le plus proche d'une valeur donnée :
• paramètres : un tableau t de réels et une valeur x
• valeur de retour : l'élément de t le plus proche de x
  
• contrainte de réalisation : pas d'utilisation d'autre tableau que le tableau fourni

Un palindrome est un mot, une phrase, un nombre, ..., qui peut se lire à l'identique dans les deux sens (abstraction faite de la ponctuation, des accents, des espaces entre les mots). Exemples :
     Radar
     Esope reste ici et se repose
     Elu par cette crapule
     2112
     A reveler mon nom, mon nom relevera
     Dot saw I was Tod

Ecrire en Java une méthode déterminant si tableau de caractères est un palindrome :
• paramètre : un tableau de caractères (les lettres seront supposées non accentuées et en minuscules)
  
• valeur de retour : un booléen, true ssi la chaîne de caractères est un palindrome
• nota 1 : pour simplifier, on pourra supposer qu'il n'y a pas de signes de ponctuation ni d'espaces entre les mots (exemple : esoperesteicietserepose)
  
• nota 2 : si l'on souhaitait passer en paramètre une donnée de type String, on pourrait faire appel aux utilitaires de la classe String :  la fonction char charAt(int index)  ou  la fonction char[] toCharArray( )
• contrainte de réalisation : pas d'utilisation d'autre tableau que le tableau fourni

Soit à calculer la valeur d'un polynôme quelconque P(x), P étant un polynôme d'une variable et à coefficents réels, pour une valeur de x donnée. Les coefficients a_i du polynôme sont stockés dans un tableau.

Pour l'évaluation, on utilisera la forme de Horner :

P(x) = ( ... ( ( a_n x + a_n-1) x + a_n-2 ) x + ... a₁) x + a₀
Quel est l'intérêt de cette forme ?

Ecrire en Java une méthode évaluant le polynôme P(x) :
• paramètres : le tableau des coefficients a_i et la valeur de la variable x
• valeur de retour : valeur de P(x)
• contraintes de réalisation : utiliser la forme de Horner pour l'évaluation ; ne visiter chaque case du tableau qu'une fois au plus.

Le crible d'Eratosthène est une méthode pour déterminer les nombres premiers. Le principe de la méthode est illustré ci-après : on considère a priori que chaque nombre est un nombre premier potentiel ; à chaque étape, on raye des nombres qui sont multiples de la valeur courante ; in fine, tous les nombres non rayés sont les nombres premiers :

• 1 et 2 sont les deux premiers nombres premiers
  
• étape 1 : 2 n'est pas "rayé" => sont "rayés" tous les multiples de 2
• étape 2 : 3 n'est pas "rayé" => sont "rayés" tous les multiples de 3
• étape 3 : 5 n'est pas "rayé" => sont "rayés" tous les multiples de 5
• ...

Exemple ('V' pour "est premier", 'F' pour "n'est pas premier") :

        2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 ...
Etape1  V   F   F   F    F     F     F     F     F     F   
Etape2    V     F     F        F        F        F        F
Etape3        V          F              F              F   
...

Ecrire en Java une méthode déterminant par la méthode d'Erathostène tous les nombres premiers inférieurs à une valeur n donnée :
• paramètre : un entier naturel n non nul
• valeur de retour : un tableau p de booléens tel que p[i] = true ssi i est un nombre premier

Ecrire en Java une méthode déterminant si une matrice carrée est symétrique (M_ij = M_ji pour tout i et j) :
• paramètre : une matrice carrée d'entiers
• valeur de retour : un booléen, true ssi cette matrice est symétrique
• contrainte de réalisation : générer la réponse dès que possible

Le tri à bulles est un algorithme pour ordonner un tableau par valeurs croissantes (resp. décroissantes) d'éléments. L'opération élémentaire du tri à bulles consiste à comparer deux éléments d'indices consécutifs et à échanger ces éléments s'ils ne sont pas dans l'ordre voulu. Une phase de tri consiste à appliquer cette opération élémentaire successivement à tous les couples d'éléments d'indices consécutifs. Cela a pour effet de faire "remonter" vers le début du tableau les éléments "légers", d'où de nom de la méthode. On répète cette phase de tri jusqu'à ce que le tableau soit trié.

Ecrire en Java une méthode triant un tableau de réels par ordre croissant avec un tri à bulles :
• paramètre : un tableau de réels
• valeur de retour : aucune
• comportement : trie le tableau par ordre croissant d'éléments
• contraintes de réalisation :
• pas d'utilisation de tableau autre que celui donné
• pas de parcours inutile du tableau
  

Ecrire en Java une méthode convertissant en entier un tableau de caractères représentant un entier :
• paramètre : un tableau  de caractères représentant un entier
  
• valeur de retour : l'entier défini par cette chaîne
• exemple : appliquée à la chaîne "-457", la méthode renverra -457
• contraintes de réalisation : minimiser le nombre d'opérations de façon que le nombre de multiplications soit au plus égal au nombre de chiffres