Fichier de rejeu Close
Indication Close
A propos de... Close
Commentaire Close
Téléchargements
Aide
Récursivité - Exercices de programmation
-
Longueur d'une chaîne
- Définir une fonction récursive
lgr(s)qui détermine la longueur d'une chaîne de caractèress. - Vérifier la fonction précédente en la comparant à la fonction
prédéfinie
len(s).
Votre réponse :
AAV4_REC: Résultat
Utiliser l'interpréteur Python ci-dessous pour programmer les fonctions demandées.
python : essai.pyOutputAAV4_REC: Vérification
Appliquer cette technique au résultat proposé.
Si cette technique nécessite d'être implémentée en Python, le faire dans l'interpréteur Python ci-dessus (cf. Résultat), sinon développer la technique de vérification dans l'éditeur de texte ci-dessous.
Zone de saisie de texte
Clavier Action F1 Afficher une aide technique F2 Afficher une aide pédagogique Ctrl-A Tout sélectionner Ctrl-C Copier la sélection dans le presse-papier Ctrl-V Copier le presse-papier dans la sélection Ctrl-X Couper la sélection et la copier dans le presse-papier Ctrl-Z Annuler la modification Maj-Ctrl-Z Rétablir la modification
Menu Action Ré-initialiser les sorties Faire apparaître le menu d'aide Valider la zone de saisie Initialiser la zone de saisie Charger le contenu d'un fichier dans la zone de saisie Sauvegarder le contenu de la zone de saisie dans un fichier Imprimer le contenu de la zone de saisie
Une solution possible :
AAV4_REC: Répondre explicitement à la question posée
Les fonctions demandées sont définies ci-dessous.
python : recursivite-type-string-1.pyOutputAAV4_REC: Choisir et appliquer une technique de vérification
Une vérification par jeux de tests est proposée dans l'énoncé:
tests = ["","z","bonjour","anticonstitutionnellement"] for t in tests : r = lgr(t) verif = (r == len(t)) print t,r,verif
- Définir une fonction récursive
-
Palindrome
Définir une fonction récursive qui détermine l'inverse d'une chaîne de caractères
s.En utilisant la fonction récursive précédente, définir une fonction qui teste si une chaîne de caractères est un palindrome.
Exemples de palindromes :
"kayak","laval","mon nom","non","ressasser","serres"
Votre réponse :
AAV4_REC: Résultat
Utiliser l'interpréteur Python ci-dessous pour programmer les fonctions demandées.
python : essai.pyOutputAAV4_REC: Vérification
Appliquer cette technique au résultat proposé.
Si cette technique nécessite d'être implémentée en Python, le faire dans l'interpréteur Python ci-dessus (cf. Résultat), sinon développer la technique de vérification dans l'éditeur de texte ci-dessous.
Zone de saisie de texte
Clavier Action F1 Afficher une aide technique F2 Afficher une aide pédagogique Ctrl-A Tout sélectionner Ctrl-C Copier la sélection dans le presse-papier Ctrl-V Copier le presse-papier dans la sélection Ctrl-X Couper la sélection et la copier dans le presse-papier Ctrl-Z Annuler la modification Maj-Ctrl-Z Rétablir la modification
Menu Action Ré-initialiser les sorties Faire apparaître le menu d'aide Valider la zone de saisie Initialiser la zone de saisie Charger le contenu d'un fichier dans la zone de saisie Sauvegarder le contenu de la zone de saisie dans un fichier Imprimer le contenu de la zone de saisie
Une solution possible :
AAV4_REC: Répondre explicitement à la question posée
Les fonctions demandées sont définies ci-dessous.
python : recursivite-type-string-2.pyOutputAAV4_REC: Choisir et appliquer une technique de vérification
Une vérification par jeux de tests est proposée dans l'énoncé:
tests = [("oui",False),("non",True),("kayak",True), ("bonjour",False),("laval",True),("mon nom",True)] for (e,s) in tests : r = palindrome(e) verif = (r == s) print e,r,verif
-
Recherche séquentielle
- Définir une fonction récursive
recherche(t,x,d,f)qui retourne le rang de la première occurrence dexdans la séquencetentre les indicesdinclus etfexclu, -1 si pas d'occurrence dexdanst. - Proposer une version itérative de la recherche séquentielle.
- Vérifier le fonctionnement des fonctions précédentes avec l'appel
prédéfini
t.index(x,d,f)qui retourne le rang de la première occurrence dexdans la séquencetsixest danst.
Votre réponse :
AAV4_REC: Résultat
Utiliser l'interpréteur Python ci-dessous pour programmer les fonctions demandées.
python : essai.pyOutputAAV4_REC: Vérification
Appliquer cette technique au résultat proposé.
Si cette technique nécessite d'être implémentée en Python, le faire dans l'interpréteur Python ci-dessus (cf. Résultat), sinon développer la technique de vérification dans l'éditeur de texte ci-dessous.
Zone de saisie de texte
Clavier Action F1 Afficher une aide technique F2 Afficher une aide pédagogique Ctrl-A Tout sélectionner Ctrl-C Copier la sélection dans le presse-papier Ctrl-V Copier le presse-papier dans la sélection Ctrl-X Couper la sélection et la copier dans le presse-papier Ctrl-Z Annuler la modification Maj-Ctrl-Z Rétablir la modification
Menu Action Ré-initialiser les sorties Faire apparaître le menu d'aide Valider la zone de saisie Initialiser la zone de saisie Charger le contenu d'un fichier dans la zone de saisie Sauvegarder le contenu de la zone de saisie dans un fichier Imprimer le contenu de la zone de saisie
Une solution possible :
AAV4_REC: Répondre explicitement à la question posée
Les fonctions demandées sont définies ci-dessous.
python : recursivite-type-list-1.pyOutputAAV4_REC: Choisir et appliquer une technique de vérification
Une vérification par jeux de tests est proposée dans l'énoncé:
tests = [("bonjour","o",0,5,1),("","e",2,7,-1),("test","x",0,3,-1), ((),"e",2,7,-1),((1,2,3,2,1),2,0,5,1),(('2','1'),1,0,2,-1), ([],[],0,1,-1),([1,2,3,3,2,1],3,1,5,2),([[],[1,2]],1,0,2,-1)] for (e1,e2,e3,e4,s1) in tests : r1 = recherche(e1,e2,e3,e4) r2 = recherche_iteratif(e1,e2,e3,e4) verif1 = (r1 == s1) verif2 = (r2 == s1) if e2 in e1 : verif1 = verif1 and r1 == e1.index(e2,e3,e4) verif2 = verif2 and r2 == e1.index(e2,e3,e4) else : verif1 = verif1 and (r1 == -1) verif2 = verif2 and (r2 == -1) print e1,e2,e3,e4,r1,r2,verif1,verif2
- Définir une fonction récursive
-
Recherche dichotomique
Définir une fonction récursive
recherche_dichotomique(t,x,d,f)qui retourne le rang de la première occurrence dexdans la séquence déjà triée par ordre croissanttentre les indicesdinclus etfexclu, -1 si pas d'occurrence dexdanst.On utilisera une méthode par dichotomie pour profiter du fait que la liste
test triée.Proposer une version itérative de la recherche dichotomique.
Vérifier le fonctionnement des fonctions précédentes avec l'appel prédéfini
t.index(x,d,f)qui retourne le rang de la première occurrence dexdans la séquencetsixest danst.
Votre réponse :
AAV4_REC: Résultat
Utiliser l'interpréteur Python ci-dessous pour programmer les fonctions demandées.
python : essai.pyOutputAAV4_REC: Vérification
Appliquer cette technique au résultat proposé.
Si cette technique nécessite d'être implémentée en Python, le faire dans l'interpréteur Python ci-dessus (cf. Résultat), sinon développer la technique de vérification dans l'éditeur de texte ci-dessous.
Zone de saisie de texte
Clavier Action F1 Afficher une aide technique F2 Afficher une aide pédagogique Ctrl-A Tout sélectionner Ctrl-C Copier la sélection dans le presse-papier Ctrl-V Copier le presse-papier dans la sélection Ctrl-X Couper la sélection et la copier dans le presse-papier Ctrl-Z Annuler la modification Maj-Ctrl-Z Rétablir la modification
Menu Action Ré-initialiser les sorties Faire apparaître le menu d'aide Valider la zone de saisie Initialiser la zone de saisie Charger le contenu d'un fichier dans la zone de saisie Sauvegarder le contenu de la zone de saisie dans un fichier Imprimer le contenu de la zone de saisie
Une solution possible :
AAV4_REC: Répondre explicitement à la question posée
Les fonctions demandées sont définies ci-dessous.
python : recursivite-type-list-2.pyOutputAAV4_REC: Choisir et appliquer une technique de vérification
Une vérification par jeux de tests est proposée dans l'énoncé:
tests = [("abcdef","b",0,5,1),("","e",2,7,-1),("aeiou","x",0,3,-1), ((),"e",2,7,-1),((1,2,2,3),2,0,5,1),(('1','2'),1,0,2,-1), ([],[],0,1,-1),([1,2,3,3,4,5],3,1,5,2),([[],[1,2]],1,0,2,-1)] for (e1,e2,e3,e4,s1) in tests : r1 = recherche_dichotomique(e1,e2,e3,e4) r2 = recherche_dichotomique_iteratif(e1,e2,e3,e4) verif1 = (r1 == s1) verif2 = (r2 == s1) if e2 in e1 : verif1 = verif1 and r1 == e1.index(e2,e3,e4) verif2 = verif2 and r2 == e1.index(e2,e3,e4) else : verif1 = verif1 and (r1 == -1) verif2 = verif2 and (r2 == -1) print e1,e2,e3,e4,r1,r2,verif1,verif2
-
Tri par sélection
Le tri par sélection d'une liste consiste à rechercher le minimum de la liste à trier, de le mettre en début de liste en l'échangeant avec le premier élément et de recommencer sur le reste de la liste.
- Définir une fonction récursive
qui détermine le minimum de la liste
tentre les indicesdinclus etfexclu. - Définir une fonction récursive
tri_selection(t,d,f)qui trie « sur place » la listetpar ordre croissant entre les indicesdinclus etfexclu. - Proposer une version itérative du minimum et du tri par sélection.
- Vérifier le fonctionnement des fonctions précédentes avec les appels
prédéfinis
min(t)qui retourne le minimum de la listetett.sort()qui trie la listet« sur place ».
Tris d'une liste4 Tris1. tri par sélection
2. tri par insertion
3. tri fusion
4. tri rapide
Votre réponse :
AAV4_REC: Résultat
Utiliser l'interpréteur Python ci-dessous pour programmer les fonctions demandées.
python : essai.pyOutputAAV4_REC: Vérification
Appliquer cette technique au résultat proposé.
Si cette technique nécessite d'être implémentée en Python, le faire dans l'interpréteur Python ci-dessus (cf. Résultat), sinon développer la technique de vérification dans l'éditeur de texte ci-dessous.
Zone de saisie de texte
Clavier Action F1 Afficher une aide technique F2 Afficher une aide pédagogique Ctrl-A Tout sélectionner Ctrl-C Copier la sélection dans le presse-papier Ctrl-V Copier le presse-papier dans la sélection Ctrl-X Couper la sélection et la copier dans le presse-papier Ctrl-Z Annuler la modification Maj-Ctrl-Z Rétablir la modification
Menu Action Ré-initialiser les sorties Faire apparaître le menu d'aide Valider la zone de saisie Initialiser la zone de saisie Charger le contenu d'un fichier dans la zone de saisie Sauvegarder le contenu de la zone de saisie dans un fichier Imprimer le contenu de la zone de saisie
Une solution possible :
AAV4_REC: Répondre explicitement à la question posée
Les fonctions demandées sont définies ci-dessous.
python : recursivite-type-list-3.pyOutputOn constate que les fonctions
tri_selection(t,d,f)ettri_selection_iteratif(t,d,f)partage évidemment la même spécification, seules les implémentations diffèrent : l'une est récursive, l'autre itérative.AAV4_REC: Choisir et appliquer une technique de vérification
Une vérification par jeux de tests est proposée dans l'énoncé:
print 'test minimum et minimum_iteratif' tests = [([1,2,3],0,2,0),([3,2,1],1,3,2), (['r','e','d','a'],0,3,2)] for (e1,e2,e3,s1) in tests : r1 = minimum(e1,e2,e3) r2 = minimum_iteratif(e1,e2,e3) verif1 = (r1 == s1 and e1[r1] == min(e1[e2:e3])) verif2 = (r2 == s1 and e1[r2] == min(e1[e2:e3])) print e1,e2,e3,r1,r2,verif1,verif2 print '\ntest tri_selection' tests = [([],-2,-5,[]),([1,2,3],0,3,[1,2,3]),([3,2,1],1,25,[3,1,2]), (['r','e','d','a'],0,3,['d','e','r','a'])] for (e1,e2,e3,s1) in tests : e10 = e1[e2:e3] e10.sort() e10 = e1[0:e2] + e10 + e1[e3:] print e1,e10, tri_selection(e1,e2,e3) verif1 = (e1 == s1 and e10 == s1) print e1,verif1 print '\ntest tri_selection_iteratif' tests = [([],-2,-5,[]),([1,2,3],0,3,[1,2,3]),([3,2,1],1,25,[3,1,2]), (['r','e','d','a'],0,3,['d','e','r','a'])] for (e1,e2,e3,s1) in tests : e10 = e1[e2:e3] e10.sort() e10 = e1[0:e2] + e10 + e1[e3:] print e1,e10, tri_selection_iteratif(e1,e2,e3) verif2 = (e1 == s1 and e10 == s1) print e1,verif2
- Définir une fonction récursive
qui détermine le minimum de la liste
-
Tri par insertion
Dans le tri par insertion, on trie successivement les premiers éléments de la liste : à la \(i^{\grave eme}\) étape, on insère le \(i^{\grave eme}\) élément à son rang parmi les \(i-1\) éléments précédents qui sont déjà triés entre eux.
- Définir une fonction récursive
inserer(t,d,f)qui déplace l'élémentt[f]d'une listetentre les indicesdetfen conservant l'ordre croissant au sein de la listetdéjà triée entre les indicesdinclus etfexclu. - Définir une fonction récursive
tri_insertion(t,d,f)qui trie « sur place » la listetpar ordre croissant entre les indicesdinclus etfexclu. - Proposer une version itérative de l'insertion et du tri par insertion.
- Vérifier le fonctionnement du tri en comparant à l'appel prédéfini
t.sort()qui trie la listet« sur place ».
Tris d'une liste4 Tris1. tri par sélection
2. tri par insertion
3. tri fusion
4. tri rapide
Votre réponse :
AAV4_REC: Résultat
Utiliser l'interpréteur Python ci-dessous pour programmer les fonctions demandées.
python : essai.pyOutputAAV4_REC: Vérification
Appliquer cette technique au résultat proposé.
Si cette technique nécessite d'être implémentée en Python, le faire dans l'interpréteur Python ci-dessus (cf. Résultat), sinon développer la technique de vérification dans l'éditeur de texte ci-dessous.
Zone de saisie de texte
Clavier Action F1 Afficher une aide technique F2 Afficher une aide pédagogique Ctrl-A Tout sélectionner Ctrl-C Copier la sélection dans le presse-papier Ctrl-V Copier le presse-papier dans la sélection Ctrl-X Couper la sélection et la copier dans le presse-papier Ctrl-Z Annuler la modification Maj-Ctrl-Z Rétablir la modification
Menu Action Ré-initialiser les sorties Faire apparaître le menu d'aide Valider la zone de saisie Initialiser la zone de saisie Charger le contenu d'un fichier dans la zone de saisie Sauvegarder le contenu de la zone de saisie dans un fichier Imprimer le contenu de la zone de saisie
Une solution possible :
AAV4_REC: Répondre explicitement à la question posée
Les fonctions demandées sont définies ci-dessous.
python : recursivite-type-list-4.pyOutputOn constate que les fonctions
tri_insertion(t,d,f)ettri_insertion_iteratif(t,d,f)partage évidemment la même spécification, seules les implémentations diffèrent : l'une est récursive, l'autre itérative.AAV4_REC: Choisir et appliquer une technique de vérification
Une vérification par jeux de tests est proposée dans l'énoncé:
print 'test inserer' tests = [([],-2,-5,[]),([1,2,3],0,2,[1,2,3]),([3,2,1],1,2,[3,1,2]), (['r','e','d','a'],1,2,['r','d','e','a'])] for (e1,e2,e3,s1) in tests : print e1, inserer(e1,e2,e3) verif = (e1 == s1) print e1,verif print '\ntest tri_insertion' tests = [([],-2,-5,[]),([1,2,3],0,3,[1,2,3]),([3,2,1],1,25,[3,1,2]), (['r','e','d','a'],0,3,['d','e','r','a'])] for (e1,e2,e3,s1) in tests : e10 = e1[e2:e3] e10.sort() e10 = e1[0:e2] + e10 + e1[e3:] print e1,e10, tri_insertion(e1,e2,e3) verif1 = (e1 == s1 and e10 == s1) print e1,verif1 print '\ntest tri_insertion_iteratif' tests = [([],-2,-5,[]),([1,2,3],0,3,[1,2,3]),([3,2,1],1,25,[3,1,2]), (['r','e','d','a'],0,3,['d','e','r','a'])] for (e1,e2,e3,s1) in tests : e10 = e1[e2:e3] e10.sort() e10 = e1[0:e2] + e10 + e1[e3:] print e1,e10, tri_insertion_iteratif(e1,e2,e3) verif2 = (e1 == s1 and e10 == s1) print e1,verif2
- Définir une fonction récursive
-
Tri fusion
Dans le tri fusion, on partage la liste à trier en deux sous-listes que l'on trie séparément, et on interclasse (on fusionne) ces deux sous-listes triées.
La fusion consiste donc à construire, à partir des deux sous-listes triées (la première de l'indice
dinclus à l'indicemexclu, la deuxième de l'indiceminclus à l'indicefexclu) une liste elle-même triée des indicesdinclus àfexclu et contenant l'ensemble des éléments des deux sous-listes d'origine.
- Définir une fonction récursive
fusion(t,d,m,f)qui fusionne les deux parties triées de la listet(entredinclus etmexclu d'une part, etminclus etfexclu d'autre part) de telle manière que la listetsoit triée entre les indicesdinclus etfexclu. - Définir une fonction récursive
tri_fusion(t,d,f)qui trie « sur place » la listetpar ordre croissant entre les indicesdinclus etfexclu. - Vérifier le fonctionnement du tri fusion en le comparant à l'appel
prédéfini
t.sort()qui trie la listet« sur place ».
Tris d'une liste4 Tris1. tri par sélection
2. tri par insertion
3. tri fusion
4. tri rapide
Votre réponse :
AAV4_REC: Résultat
Utiliser l'interpréteur Python ci-dessous pour programmer les fonctions demandées.
python : essai.pyOutputAAV4_REC: Vérification
Appliquer cette technique au résultat proposé.
Si cette technique nécessite d'être implémentée en Python, le faire dans l'interpréteur Python ci-dessus (cf. Résultat), sinon développer la technique de vérification dans l'éditeur de texte ci-dessous.
Zone de saisie de texte
Clavier Action F1 Afficher une aide technique F2 Afficher une aide pédagogique Ctrl-A Tout sélectionner Ctrl-C Copier la sélection dans le presse-papier Ctrl-V Copier le presse-papier dans la sélection Ctrl-X Couper la sélection et la copier dans le presse-papier Ctrl-Z Annuler la modification Maj-Ctrl-Z Rétablir la modification
Menu Action Ré-initialiser les sorties Faire apparaître le menu d'aide Valider la zone de saisie Initialiser la zone de saisie Charger le contenu d'un fichier dans la zone de saisie Sauvegarder le contenu de la zone de saisie dans un fichier Imprimer le contenu de la zone de saisie
Une solution possible :
AAV4_REC: Répondre explicitement à la question posée
Les fonctions demandées sont définies ci-dessous.
python : recursivite-type-list-5.pyOutputAAV4_REC: Choisir et appliquer une technique de vérification
Une vérification par jeux de tests est proposée dans l'énoncé:
print 'test fusion' tests = [([],0,0,0,[]),([4,5,1,2,3],0,2,5,[1,2,3,4,5]), ([9,7,4,6,8,10,3,5,2,0],2,6,8,[9,7,3,4,5,6,8,10,2,0])] for (e1,e2,e3,e4,s1) in tests : print e1,e2,e3,e4, fusion(e1,e2,e3,e4) verif = (e1 == s1) print e1,verif print '\ntest tri_fusion' tests = [([],-2,-5,[]),([1,2,3],0,3,[1,2,3]), ([3,2,1],1,25,[3,1,2]),([1,1,1],0,3,[1,1,1]), (['d','c','b','a'],0,4,['a','b','c','d']), (['r','e','d','a'],0,3,['d','e','r','a'])] for (e1,e2,e3,s1) in tests : e10 = e1[e2:e3] e10.sort() e10 = e1[0:e2] + e10 + e1[e3:] print e1,e10, tri_fusion(e1,e2,e3) verif1 = (e1 == s1 and e10 == s1) print e1,verif1
- Définir une fonction récursive
-
Parcours d'arbres
On considère ici la notion d'arbre binaire. Un arbre binaire est soit vide, soit composé de 3 éléments : une racine, un arbre binaire
Gaucheet un arbre binaireDroite. L'arbre binaire vide sera représenté ici par la liste vide ([]), l'arbre binaire non vide par une liste de 3 éléments ([racine,Gauche,Droite]) oùGaucheetDroitesont eux-mêmes des arbres binaires etracinede type quelconque.Ainsi, l'arbre binaire ci-dessous est représenté par la liste :
[1,[2,[4,[],[]],[]],[3,[5,[],[]],[6,[],[7,[],[]]]]].
On a souvent besoin de parcourir les éléments d'un arbre binaire pour effectuer un traitement. On distingue alors 3 types de parcours d'arbre :
parcours en notation préfixée : on considère d'abord la racine de l'arbre avant de traiter le sous-arbre de gauche puis le sous-arbre de droite (l'arbre vide est affiché à l'aide d'un 0).
Exemples de parcours préfixé :
[1,[2,[],[]],[3,[],[4,[],[]]]]: 1 2 0 0 3 0 4 0 0[1,[2,[4,[],[]],[]],[3,[5,[],[]],[6,[],[7,[],[]]]]]: 1 2 4 0 0 0 3 5 0 0 6 0 7 0 0
parcours en notation infixée : on traite d'abord le sous-arbre de gauche, puis la racine de l'arbre avant de passer au sous-arbre de droite (l'arbre vide est affiché à l'aide d'un 0).
Exemples de parcours infixé :
[1,[2,[],[]],[3,[],[4,[],[]]]]: 0 2 0 1 0 3 0 4 0[1,[2,[4,[],[]],[]],[3,[5,[],[]],[6,[],[7,[],[]]]]]: 0 4 0 2 0 1 0 5 0 3 0 6 0 7 0
parcours en notation postfixée : on traite d'abord le sous-arbre de gauche, puis le sous-arbre de droite et enfin la racine de l'arbre (l'arbre vide est affiché à l'aide d'un 0).
Exemples de parcours postfixé :
[1,[2,[],[]],[3,[],[4,[],[]]]]: 0 0 2 0 0 0 4 3 1[1,[2,[4,[],[]],[]],[3,[5,[],[]],[6,[],[7,[],[]]]]]: 0 0 4 0 2 0 0 5 0 0 0 7 6 3 1
- Définir une fonction récursive
isBinaryTree(t)qui teste sitest un arbre binaire. - Définir une fonction récursive
prefix(a)qui affiche les éléments d'un arbre binaireaen notation préfixée. - Définir une fonction récursive
infix(a)qui affiche les éléments d'un arbre binaireaen notation infixée. - Définir une fonction récursive
postfix(a)qui affiche les éléments d'un arbre binaireaen notation postfixée.
Votre réponse :
AAV4_REC: Résultat
Utiliser l'interpréteur Python ci-dessous pour programmer les fonctions demandées.
python : essai.pyOutputAAV4_REC: Vérification
Appliquer cette technique au résultat proposé.
Si cette technique nécessite d'être implémentée en Python, le faire dans l'interpréteur Python ci-dessus (cf. Résultat), sinon développer la technique de vérification dans l'éditeur de texte ci-dessous.
Zone de saisie de texte
Clavier Action F1 Afficher une aide technique F2 Afficher une aide pédagogique Ctrl-A Tout sélectionner Ctrl-C Copier la sélection dans le presse-papier Ctrl-V Copier le presse-papier dans la sélection Ctrl-X Couper la sélection et la copier dans le presse-papier Ctrl-Z Annuler la modification Maj-Ctrl-Z Rétablir la modification
Menu Action Ré-initialiser les sorties Faire apparaître le menu d'aide Valider la zone de saisie Initialiser la zone de saisie Charger le contenu d'un fichier dans la zone de saisie Sauvegarder le contenu de la zone de saisie dans un fichier Imprimer le contenu de la zone de saisie
Une solution possible :
AAV4_REC: Répondre explicitement à la question posée
Les fonctions demandées sont définies ci-dessous.
python : recursivite-type-tree-1.pyOutputAAV4_REC: Choisir et appliquer une technique de vérification
On procède par jeux de tests pour retrouver les exemples d'affichages proposés dans l'énoncé:
tests = [ [1,[2,[],[]],[3,[],[4,[],[]]]], [1,[2,[4,[],[]],[]],[3,[5,[],[]],[6,[],[7,[],[]]]]] ] for t in tests : print t,isBinaryTree(t) prefix(t) print infix(t) print postfix(t) print
-
Cercles
Un « bubble » est une figure formée d’un cercle et de deux copies de ce cercle ayant subies une réduction d’un facteur 2, ces deux petits cercles étant tangents extérieurement au cercle initial tels que les lignes des centres soient parallèles aux axes du repère. Ces deux petits cercles deviennent à leur tour « cercle initial » pour poursuivre le dessin.
La figure ci-dessous illustre de gauche à droite des bubbles de profondeur 1 à 4.
- Définir une fonction
circle(t,x,y,r)où la tortuetdessine un cercle de centre(x,y)et de rayonr. - Définir une fonction récursive
bubble(t,n,x,y,r)où la tortuetdessine un bubble de profondeurnà partir d'un cercle de centre(x,y)et de rayonr. A chaque étape, le rayon est divisé par 2.
aide Pythontortue Logo : (documentation Python)
import turtlemodule Python à importer pour manipuler la tortue Logo.
t = turtle.Turtle()crée une tortue
t.t.setheading(a)oriente la tortue
tdans une direction qui fait l'anglea(en degrés) avec l'axe horizontal (sens trigonométrique).t.forward(d)fait avancer la tortue
td'une distanceddans la direction courante.t.backward(d)fait reculer la tortue
td'une distanceddans la direction courante.t.left(a)fait tourner sur la gauche (sens trigonométrique) la tortue
t(sans avancer, ni reculer) d'un angleapar rapport à la direction courante.t.right(a)fait tourner sur la droite (sens horaire) la tortue
t(sans avancer, ni reculer) d'un angleapar rapport à la direction courante.t.goto(x,y)fait aller la tortue au point de coordonnées
(x,y)quelle que soit son orientation.Votre réponse :
AAV4_REC: Résultat
Utiliser l'interpréteur Python ci-dessous pour programmer les fonctions demandées.
python : essai.pyOutputAAV4_REC: Vérification
Appliquer cette technique au résultat proposé.
Si cette technique nécessite d'être implémentée en Python, le faire dans l'interpréteur Python ci-dessus (cf. Résultat), sinon développer la technique de vérification dans l'éditeur de texte ci-dessous.
Zone de saisie de texte
Clavier Action F1 Afficher une aide technique F2 Afficher une aide pédagogique Ctrl-A Tout sélectionner Ctrl-C Copier la sélection dans le presse-papier Ctrl-V Copier le presse-papier dans la sélection Ctrl-X Couper la sélection et la copier dans le presse-papier Ctrl-Z Annuler la modification Maj-Ctrl-Z Rétablir la modification
Menu Action Ré-initialiser les sorties Faire apparaître le menu d'aide Valider la zone de saisie Initialiser la zone de saisie Charger le contenu d'un fichier dans la zone de saisie Sauvegarder le contenu de la zone de saisie dans un fichier Imprimer le contenu de la zone de saisie
Une solution possible :
AAV4_REC: Répondre explicitement à la question posée
La fonction demandée est définie ci-dessous.
python : recursivite-logo-1.pyOutputAAV4_REC: Choisir et appliquer une technique de vérification
On procède par simple comparaison de figures : on retrouve bien les figures de l'énoncé.
- Définir une fonction
-
Arbres
On considère un arbre composé d'un tronc de hauteur \(h\), de 2 branches principales (la gauche et la droite) qui font respectivement un angle \(a_g\) et \(a_d\) avec l'axe du tronc. Chaque branche se décompose elle-même de la même façon jusqu'à une « profondeur » \(p\) comme le montre la figure ci-dessous pour différentes valeurs de \(p\) (de gauche à droite : \(p =\) 0, 2, 4, 6).
Définir une fonction récursive
arbre(t,h,p,rg,ag,rd,ad)où la tortuetdessine un arbre de hauteurhet de profondeurp. A chaque nouvelle étape, la longueur d'une branche gauche est multipliée parrg(\(0 < r_g < 1\)), celle de la branche droite parrd(\(0 < r_d < 1\)). La branche gauche fait un angleagpar rapport à la branche précédente, la branche droite un anglead.aide Pythontortue Logo : (documentation Python)
import turtlemodule Python à importer pour manipuler la tortue Logo.
t = turtle.Turtle()crée une tortue
t.t.setheading(a)oriente la tortue
tdans une direction qui fait l'anglea(en degrés) avec l'axe horizontal (sens trigonométrique).t.forward(d)fait avancer la tortue
td'une distanceddans la direction courante.t.backward(d)fait reculer la tortue
td'une distanceddans la direction courante.t.left(a)fait tourner sur la gauche (sens trigonométrique) la tortue
t(sans avancer, ni reculer) d'un angleapar rapport à la direction courante.t.right(a)fait tourner sur la droite (sens horaire) la tortue
t(sans avancer, ni reculer) d'un angleapar rapport à la direction courante.t.goto(x,y)fait aller la tortue au point de coordonnées
(x,y)quelle que soit son orientation.Votre réponse :
AAV4_REC: Résultat
Utiliser l'interpréteur Python ci-dessous pour programmer les fonctions demandées.
python : essai.pyOutputAAV4_REC: Vérification
Appliquer cette technique au résultat proposé.
Si cette technique nécessite d'être implémentée en Python, le faire dans l'interpréteur Python ci-dessus (cf. Résultat), sinon développer la technique de vérification dans l'éditeur de texte ci-dessous.
Zone de saisie de texte
Clavier Action F1 Afficher une aide technique F2 Afficher une aide pédagogique Ctrl-A Tout sélectionner Ctrl-C Copier la sélection dans le presse-papier Ctrl-V Copier le presse-papier dans la sélection Ctrl-X Couper la sélection et la copier dans le presse-papier Ctrl-Z Annuler la modification Maj-Ctrl-Z Rétablir la modification
Menu Action Ré-initialiser les sorties Faire apparaître le menu d'aide Valider la zone de saisie Initialiser la zone de saisie Charger le contenu d'un fichier dans la zone de saisie Sauvegarder le contenu de la zone de saisie dans un fichier Imprimer le contenu de la zone de saisie
Une solution possible :
- AAV4_REC: Répondre explicitement à la question posée
La fonction demandée est définie ci-dessous.
python : recursivite-logo-3.pyOutputAAV4_REC: Choisir et appliquer une technique de vérification
On procède par simple comparaison de figures : on retrouve bien les figures de l'énoncé.
-
Dragons
La courbe du dragon est obtenue à partir d'un segment sur lequel on construit 2 autres segments de façon à former un triangle rectangle isocèle. A chaque étape, on alterne le sens de construction des triangles.
Définir une fonction récursive
dragon(t,n,s)où la tortuetdessine la courbe du dragon à l'ordrenen initialisant les rotations sur la droite (s = -1) ou sur la gauche (s = 1).aide Pythontortue Logo : (documentation Python)
import turtlemodule Python à importer pour manipuler la tortue Logo.
t = turtle.Turtle()crée une tortue
t.t.setheading(a)oriente la tortue
tdans une direction qui fait l'anglea(en degrés) avec l'axe horizontal (sens trigonométrique).t.forward(d)fait avancer la tortue
td'une distanceddans la direction courante.t.backward(d)fait reculer la tortue
td'une distanceddans la direction courante.t.left(a)fait tourner sur la gauche (sens trigonométrique) la tortue
t(sans avancer, ni reculer) d'un angleapar rapport à la direction courante.t.right(a)fait tourner sur la droite (sens horaire) la tortue
t(sans avancer, ni reculer) d'un angleapar rapport à la direction courante.t.goto(x,y)fait aller la tortue au point de coordonnées
(x,y)quelle que soit son orientation.Votre réponse :
AAV4_REC: Résultat
Utiliser l'interpréteur Python ci-dessous pour programmer les fonctions demandées.
python : essai.pyOutputAAV4_REC: Vérification
Appliquer cette technique au résultat proposé.
Si cette technique nécessite d'être implémentée en Python, le faire dans l'interpréteur Python ci-dessus (cf. Résultat), sinon développer la technique de vérification dans l'éditeur de texte ci-dessous.
Zone de saisie de texte
Clavier Action F1 Afficher une aide technique F2 Afficher une aide pédagogique Ctrl-A Tout sélectionner Ctrl-C Copier la sélection dans le presse-papier Ctrl-V Copier le presse-papier dans la sélection Ctrl-X Couper la sélection et la copier dans le presse-papier Ctrl-Z Annuler la modification Maj-Ctrl-Z Rétablir la modification
Menu Action Ré-initialiser les sorties Faire apparaître le menu d'aide Valider la zone de saisie Initialiser la zone de saisie Charger le contenu d'un fichier dans la zone de saisie Sauvegarder le contenu de la zone de saisie dans un fichier Imprimer le contenu de la zone de saisie
Une solution possible :
- AAV4_REC: Répondre explicitement à la question posée
La fonction demandée est définie ci-dessous.
python : recursivite-logo-4.pyOutputAAV4_REC: Choisir et appliquer une technique de vérification
On procède par simple comparaison de figures : on retrouve bien les figures de l'énoncé.
-
Distribuer les cartes
Définir une fonction récursive
distribuer(jeu,mains)qui retourne la liste des cartes dujeu(un jeu est une liste de cartes) non distribuées (la pioche) entrenjoueurs (n = len(mains));mainsest la liste des mains (une main est une liste de cartes) de chaque joueur.Votre réponse :
AAV4_REC: Résultat
Utiliser l'interpréteur Python ci-dessous pour programmer les fonctions demandées.
python : essai.pyOutputAAV4_REC: Vérification
Appliquer cette technique au résultat proposé.
Si cette technique nécessite d'être implémentée en Python, le faire dans l'interpréteur Python ci-dessus (cf. Résultat), sinon développer la technique de vérification dans l'éditeur de texte ci-dessous.
Zone de saisie de texte
Clavier Action F1 Afficher une aide technique F2 Afficher une aide pédagogique Ctrl-A Tout sélectionner Ctrl-C Copier la sélection dans le presse-papier Ctrl-V Copier le presse-papier dans la sélection Ctrl-X Couper la sélection et la copier dans le presse-papier Ctrl-Z Annuler la modification Maj-Ctrl-Z Rétablir la modification
Menu Action Ré-initialiser les sorties Faire apparaître le menu d'aide Valider la zone de saisie Initialiser la zone de saisie Charger le contenu d'un fichier dans la zone de saisie Sauvegarder le contenu de la zone de saisie dans un fichier Imprimer le contenu de la zone de saisie
Une solution possible :
AAV4_REC: Répondre explicitement à la question posée
La fonction demandée est définie ci-dessous.
python : recursivite-jeux-2.pyOutputAAV4_REC: Choisir et appliquer une technique de vérification
On procède par jeux de tests:
import random n = random.choice([32,52,78]) jeu = range(n) r = random.randint(2,9) mains = [] for k in range(r) : mains.append([]) pioche = distribuer(jeu,mains) print n,r,pioche for j in mains : print len(j),j
-
Compter les points
- Définir une fonction récursive
compter(t)qui retourne la somme des éléments de la listetoùtreprésente la main d'un joueur de cartes. On supposera que chaque carte est représentée par un entier qui est aussi sa valeur. - Ecrire une version itérative de cette fonction.
Votre réponse :
AAV4_REC: Résultat
Utiliser l'interpréteur Python ci-dessous pour programmer les fonctions demandées.
python : essai.pyOutputAAV4_REC: Vérification
Appliquer cette technique au résultat proposé.
Si cette technique nécessite d'être implémentée en Python, le faire dans l'interpréteur Python ci-dessus (cf. Résultat), sinon développer la technique de vérification dans l'éditeur de texte ci-dessous.
Zone de saisie de texte
Clavier Action F1 Afficher une aide technique F2 Afficher une aide pédagogique Ctrl-A Tout sélectionner Ctrl-C Copier la sélection dans le presse-papier Ctrl-V Copier le presse-papier dans la sélection Ctrl-X Couper la sélection et la copier dans le presse-papier Ctrl-Z Annuler la modification Maj-Ctrl-Z Rétablir la modification
Menu Action Ré-initialiser les sorties Faire apparaître le menu d'aide Valider la zone de saisie Initialiser la zone de saisie Charger le contenu d'un fichier dans la zone de saisie Sauvegarder le contenu de la zone de saisie dans un fichier Imprimer le contenu de la zone de saisie
Une solution possible :
AAV4_REC: Répondre explicitement à la question posée
La fonction demandée est définie ci-dessous.
python : recursivite-jeux-3.pyOutputAAV4_REC: Choisir et appliquer une technique de vérification
On procède par jeux de tests : les versions récursive et itérative donnent bien les mêmes résultats.
- Définir une fonction récursive
-
Elévation à la puissance
- Définir une fonction récursive qui calcule l'élévation d'un nombre à une puissance entière (\(p = x^n\)).
- Vérifier le bon fonctionnement de la fonction précédente avec
l'opérateur prédéfini
**.
Votre réponse :
AAV4_REC: Résultat
Utiliser l'interpréteur Python ci-dessous pour programmer les fonctions demandées.
python : essai.pyOutputAAV4_REC: Vérification
Appliquer cette technique au résultat proposé.
Si cette technique nécessite d'être implémentée en Python, le faire dans l'interpréteur Python ci-dessus (cf. Résultat), sinon développer la technique de vérification dans l'éditeur de texte ci-dessous.
Zone de saisie de texte
Clavier Action F1 Afficher une aide technique F2 Afficher une aide pédagogique Ctrl-A Tout sélectionner Ctrl-C Copier la sélection dans le presse-papier Ctrl-V Copier le presse-papier dans la sélection Ctrl-X Couper la sélection et la copier dans le presse-papier Ctrl-Z Annuler la modification Maj-Ctrl-Z Rétablir la modification
Menu Action Ré-initialiser les sorties Faire apparaître le menu d'aide Valider la zone de saisie Initialiser la zone de saisie Charger le contenu d'un fichier dans la zone de saisie Sauvegarder le contenu de la zone de saisie dans un fichier Imprimer le contenu de la zone de saisie
Une solution possible :
AAV4_REC: Répondre explicitement à la question posée
La fonction demandée est définie ci-dessous.
python : recursivite-elem-1.pyOutputAAV4_REC: Choisir et appliquer une technique de vérification
Une vérification par jeux de tests est proposée dans l'énoncé:
import random for i in range(1,10) : x = random.randint(0,20) n = random.randint(0,10) r = puissance(x,n) verif = (r == x**n) print x,n,r,verif
-
Fonction d'Ackermann
Définir une fonction récursive qui calcule la fonction d'Ackermann.
\[f(m,n) = \left\{\begin{array}{ll} n + 1 & \mathrm{\ si\ } m = 0 \\ f(m-1,1) & \mathrm{\ si\ } m > 0 \mathrm{\ et\ } n = 0 \\ f(m-1,f(m,n-1)) & \mathrm{\ si\ } m > 0 \mathrm{\ et\ } n > 0 \end{array}\right.\]Votre réponse :
AAV4_REC: Résultat
Utiliser l'interpréteur Python ci-dessous pour programmer les fonctions demandées.
python : essai.pyOutputAAV4_REC: Vérification
Appliquer cette technique au résultat proposé.
Si cette technique nécessite d'être implémentée en Python, le faire dans l'interpréteur Python ci-dessus (cf. Résultat), sinon développer la technique de vérification dans l'éditeur de texte ci-dessous.
Zone de saisie de texte
Clavier Action F1 Afficher une aide technique F2 Afficher une aide pédagogique Ctrl-A Tout sélectionner Ctrl-C Copier la sélection dans le presse-papier Ctrl-V Copier le presse-papier dans la sélection Ctrl-X Couper la sélection et la copier dans le presse-papier Ctrl-Z Annuler la modification Maj-Ctrl-Z Rétablir la modification
Menu Action Ré-initialiser les sorties Faire apparaître le menu d'aide Valider la zone de saisie Initialiser la zone de saisie Charger le contenu d'un fichier dans la zone de saisie Sauvegarder le contenu de la zone de saisie dans un fichier Imprimer le contenu de la zone de saisie
Une solution possible :
AAV4_REC: Répondre explicitement à la question posée
La fonction demandée est définie ci-dessous.
python : recursivite-prop-0.pyOutputAAV4_REC: Choisir et appliquer une technique de vérification
Une vérification par jeux de tests suffit:
tests = [(0,5,6),(1,0,2),(1,1,3),(3,5,253)] for (e1,e2,s1) in tests : r = ackermann(e1,e2) verif = (r == s1) print e1,e2,r,verif