[PDF] Exemples dalgorithmes récursifs 1 Des exercices sur les suites

View - Download Exemples dalgorithmes récursifs 1 Des exercices sur les suites

Previous PDF

Next PDF

IREM Clermont-Ferrand Philippe Lac

Année 2010-2011 Malika More

Stage d"AlgorithmiqueExemples d"algorithmes récursifs Les programmes sont disponibles dans l"archive associée. Par exemple,algo1Rtrous.scedésigne la traduction de l"algorithme 1 sousSCILAB, en version récursive à compléter. Ainsi lorsque la mentiontrousn"est pas présente, il s"agit alors de la version complète, et lorsque la mentionRn"est pas présente, il s"agit d"une version itérative.

1 Des exercices sur les suites

1.

On considè rel"algorithme sui vant:

Entrée:nun entier

Résultat:? ???

débutDonner àSla valeur0; pouride1anfaireDonner àSla valeurS+i fin retourner:SfinAlgorithme 1: (a)

Quelle v aleurrend-il pour n= 0?

(b) De f açongénérale, quel rés ultatrend-il ? (c) Réécrire ce talgorithme sous forme récursi ve. 2. (a)

Que f aitl"algorithme sui vant:

1

Entrée:nun entier

Résultat:? ???

débutareçoit0; breçoit0; pouride1anfaireareçoita+i; breçoita+b; fin retourner:bfinAlgorithme 2: +aide :(b)Le réécrire sous forme récursi ve. 3.

On considè rel"algorithme sui vant:

Entrée:nun entier

Résultat:? ???

débutsin=0alorsretourner:1 sinonretourner:f(n-1)*2 fin finFonctionf(n)(a)T raduirecet algorithme sous XCASou

SCILAB.

(b)

Dérécursifier cet alogrithme.

4.

On considè rela suite udéfinie par

u0= 5 u n+1=p1 +un (a) Ecrire un algorithme itératif, que l"on traduira sous XCASouSCILAB, qui, pourn donné, retourneun. (b)

Même question, a vecun algo rithmerécursif.

(c) En utilisant les fonction précédentes, écrire un programme qui af fichetous les termes de la suiteuvérifiantjun+1unj>105. Quel problème soulève cette façon de procéder? 2

2 En vrac

1.

On considè rel"algorithme sui vant:

Entrée:aun tableau;

netkdes entiers

Résultat:? ???

débutsik1< n=2alorsretourner:a sinontmpreçoita[k]; a[k]reçoita[nk+ 1]; a[nk+ 1]reçoittmp; retourner:vrac( a,n,k1) fin finFonctionvrac(a,n,k)(a)Si a= [1;2;3;4;5;6], que va rendre l"exécution de vrac(a;6;6)? (b)

Sa traduction peut poser un problème.

De quelle nature?

+paramètres de la fonction et pile d"exé- cution (c)

Comm entremédier simplement à ce pro-

blème? (d)

Ecrire la v ersionitérati vede cet algo-

rithme. 2.

L "algorithmesui vanta été écrit pour réaliser la même tâche que précédemment :

Entrée:aun tableau;

netkdes entiers

Résultat:? ???

débutsik=nalorsretourner:a sinontmpreçoita[n]; a[n]reçoita[k]; a[k]reçoittmp; retourner:vrac2( a,n,k+ 1) fin finFonctionvrac2(a,n,k)

Pourquoi n"est-il pas correct?

3 Des fractales

3.1 Courbe de Péano

Rappelons le principe :

3 on part de la diagonale d"un carréon découpe ce carré en 9 carrés, puis on trace les diagonaleson réitère ce processus sur chaque diagonale Dans la suite, nous réaliserons des algorithmes destinés à être traduits sousXCAS. Pour cela, nous avons utiliserons le modelogo, accessible via les touchesAlt+D. Ce mode met à notre disposition plusieurs commandes permettant de déplacer un curseur gra-

phique, que l"on appellera tortue : à notre disposition plusieurs fonctions, bien pratiques pour ce

que l"on veut faire : avance(n): la tortue avance de n pas (par défaut n=10). tourne_gauche(n): la tortue tourne à gauche de n degrés (par défaut n=90). tourne_droite(n): la tortue tourne à droite de n degrés (par défaut n=90) efface: efface l"écran de la tortue ou recule de n pas en effaçant. saute: La tortue saute (avance sans laisser de traces) de n pas (par défaut n=10). 1. Complét erles séquences sui vantesafin d"obtenir une fonction qui re produitla seconde figure,`désignant la longueur de la diagonale du grand carré : +on suppose que la tortue est déjà dans la bonne direction.

Entrée:un réel `

Résultat:Le déplacement sur une diagonale de longueur ` débutavance(...); tourne_gauche(...); avance(...); ...finFonctionDeplacement(`) 2.

Modifier l"algorithme précédent, pour obtenir un algorithme récursif du tracé de la courbe

de Péano d"ordren:

Entrée:nun entier, un réel`

Résultat:La courbe de Péano d"ordre n sur une diagonale de longueur ` début... ; finFonctionPeano(n,`) 4 +On prendra soin de repérer les points de l"algorithme où doit intervenir la récursivité dans le premier algorithme. On utilisera la variablenpour le contrôle de la terminaison. 3.

T raduirel"algorithme précédent sous XCAS, et réaliser le tracé de la courbe de Péano pour

n= 4et`= 270. Quelles sont les instructions dont on peut changer l"ordre dans l"algorithme sans modifier le résultat?

3.2 D"autre exemples

1. En s"inspirant de la première partie, réaliser un algorithme, et le traduire sous XCAS, afin d"obtenir la courbe du dragon d"ordren. 2.

Réalis erun flocon de V onKoch

4 Problème du labyrinthe

Préléminaires :

Dans le dossierLabyrinthe, charger, sousSCILAB, le fichierBoiteOutils.sceet l"exé- cuter dans la console. Ce fichier fournit 3 programmes : LabC(n) : permet de construire une matricenxnassociée à un labyrinthe; LabA(M,n) : permet d"afficher une matriceMde taillenxnassociée à un labyrinthe; dedale(fi,fj,di,dj) : exploration d"un labyrinthe stocké dans une matriceL(variable globale), dont la sortie est aussi stockée dans une variable globale (sietsj). di,djdésignent la postion de l"entrée etfi;fjla première position explorée. +par convention, la case inférieure gauche a la position 1,1. 1. F aireun ess ai,en utilisant la matrice Msauvegardé dans le fichierM:dat: 2. Construir eun labyrinthe et tester le programme dedale sur ce labyrinthe. 3. Comment modifier l"ordre d"e xplorationdes bifurcations ? 4. La modifica tionde cet ordre peut-il permettre de trouv erle chemin le plus court ? 5. Construir eun labyrinthe mettant en echec le programme dedale (présence d"un c ycle). +Au cas où, un exemple de matrice est sauvegardé dans la variableMcycle(fichier

Mcycle.dat).

6. Modifier l "algorithmede f açonà traiter les c yclesév entuels. +on pourra, par exemple, utiliser un marqueur sur les cases observées, compatible avec le testdeplacement valide 7.

Réfléchi rà un algorithme permettant d"obtenir toutes les solutions, puis la solution la plus

courte. 5

5 Récursivité multiple

1. Ecrire l"algorithme d"une foncton récursi vec(n;p)qui, pour les entiersnetp, retourne le coefficient binomialn p 2. T raduirece talgorithme sous XCASet le tester sur différentes valeurs. 3. Complét erl"algorithme sui vant,sachant qu"il utilise la construction du triangle de P ascal pour obtenir le même résultat.

Entrée:netpdes entiers

variables locales:aun tableau (n+1)x(p+1)

Résultat:pparmin

débuta:= tableau nul de dimension(n+ 1)x(p+ 1); pouride0apfairea[i;i]:=1; fin pouride0anfairea[i;0]:=1; fin pouride1anfairepouride1apfairea[i;j]:= ... ; fin fin retourner:. ..finFonctionc(n,p) 4. Comparer les temps d"e xécutiondes deux fonctions. 5. Réali serune v ersionitérati ve,utilisant un tableau à une seule dimension.

6 Diviser pour régner

1. On se propose de reprendre le jeu du Plus-Moins, et d"en écrire un algorithme récursif. Principe : le joueur choisit mentalement un nombre entier entre deux bornes, fixées préala- blement (netppar exemple), et l"algorithme procède alors par élimination dichotomique. Dans les fichiers mis à disposition, on trouvera dans le dossier PlusMoins des fichiers PMtrousen versionSCILABouXCAS. Compléter ces fichiers afin d"obtenir une ré- ponse au problème posé. 6quotesdbs_dbs45.pdfusesText_45

[PDF] Algorithme DM 2nd 2nde Mathématiques

[PDF] Algorithme DM pour le 13/02 Terminale Mathématiques

[PDF] Algorithme du distributeur (avec une calculatrice TI) 2nde Mathématiques

[PDF] algorithme écrit en langage naturel PDF Cours,Exercices ,Examens

[PDF] Algorithme écrit sur papier et a programmer avec Algobox 2nde Mathématiques

[PDF] algorithme em r PDF Cours,Exercices ,Examens

[PDF] algorithme em sous r PDF Cours,Exercices ,Examens

[PDF] algorithme en langage naturel exemple PDF Cours,Exercices ,Examens

[PDF] algorithme en mathématiques 2nde Mathématiques

[PDF] Algorithme en Seconde 3ème Mathématiques

[PDF] Algorithme en seconde avec calculatrice 3ème Mathématiques

[PDF] algorithme enigma PDF Cours,Exercices ,Examens

[PDF] algorithme equation 1er degré PDF Cours,Exercices ,Examens

[PDF] algorithme equation 2eme degré PDF Cours,Exercices ,Examens

[PDF] ALGORITHME équation de droite 1ère Mathématiques