Algorithme

Algorithme: Exercice R0120112016

Un cours complet pour maîtriser Algorithme: Exercice R0120112016.

0 chapitres 0 QCM Accès gratuit

Commencer Retour aux cours

Objectif :

Définir la récursivité.
Reconnaître et identifier des algorithmes récursifs.
Faire appel à des fonctions récursives pour résoudre certains problèmes.

Pour chacun des exercices suivants :

Proposer une analyse modulaire au problème.
Analyser chacun des modules envisagés précédemment.
Déduire les algorithmes correspondants.
Traduire la solution en un programme Pascal.

Exercice 01

Convertir, en Pascal, la procédure itérative ci-dessous en une procédure récursive :

Procedure Compter ;
Var i : integer ;
Begin
    For i := 1 to 10 do
        Writeln('Bac 2011') ;
End;

Exercice 02

Ecrire une fonction récursive nommée Somme_Chiffre qui retourne la somme des chiffres d’un nombre N donné.

Exemple : 417 → 4 + 1 + 7 = 12

Exercice 03

Ecrire une fonction récursive nommée Chiffre_Droite qui détermine le K^ième chiffre à partir de la droite d’un entier n > 0.

Exemples :

Le 3^ème chiffre de 89752 est 7
Le 5^ème chiffre de 21327 est 2

Exercice 04

On appelle palindrome une chaîne de caractères qui donne la même chaîne selon que l’on la lise de gauche à droite ou inversement. Autrement dit, le premier caractère est égal au dernier, le deuxième caractère est égal à l’avant dernier, etc.

Une définition récursive d’un palindrome est :

La chaîne vide est un palindrome ;
La chaîne constituée d’un seul caractère est un palindrome ;
aXb est un palindrome si a = b et si X est un palindrome. (Exemple : "ABCBA" ; A=A et "BCB" est un palindrome).

Écrire une fonction récursive nommée Palindrome qui vérifie si une chaîne donnée est palindrome.

Exercice 05

Écrire une fonction récursive Inverse qui permet de lire une phrase ou un mot et de l’écrire à l’envers, à partir du dernier caractère rentré.

Exemple : Miroir, qui est la plus belle ? ? → elleb sulp al tse iuq ,rioriM

Exercice 06

Écrire une fonction récursive nommée anag qui détermine si deux chaînes sont anagrammes.

Deux chaînes ch1, ch2 sont dites anagrammes, si les lettres qui composent la 1^er chaîne existent toutes dans la 2^ème chaîne.

Exemple : ch1 = chien et ch2 = niche

Exercice 07

La fonction d’Ackermann f est définie, pour x et y entiers naturels, par :

[latex] f(x,y) =\left \{ \begin{array}{r c l} y+1 & si&x=0 \ f(x − 1, 1) & si&y = 0 \ f(x-1,f(x,y− 1))& si&x e y e 0 nd{array} ight. [/latex]

Calculer f(2,3).

Ecrire une fonction récursive qui permet de calculer f pour x et y donnés.

Exercice 08

La suite de Fibonnacci est définie par :

[latex] f_{n} =\left \{ \begin{array}{r c l} 1 & si&n=0 \ 1 &si&n = 1 \ f_{n-1}+f_{n-2} & pour& n>2 nd{array} ight. [/latex]

Calculer f(7).

Ecrire une fonction récursive qui permet de déterminer la valeur retournée par la fonction f pour un entier n donné.

Exercice 09

Transformer la procédure suivante en une procédure récursive :

0/ Début Procédure Calcul (N : entier, var P : réel)
1/ P ← 1
2/ Pour i de 1 à N faire
      P ← P * i
   Fin Pour
3/ Fin Calcul

Exercice 10

Écrire un programme récursif qui affiche tout le contenu d'un tableau T de taille n.

Cours Algorithmique