Corrigés des exercices sur les fonctions récursives
Corrigés des exercices sur les fonctions récursives. Exercice 7.1.1 sous-programmes récursifs. Pour chacun des sous-programmes nous donnerons les paramètres
RECURSIVITE Exercices - Corrigés
Exercice 3 – Le compte est-il bon ? Ecrire une fonction Python « compte_a » qui reçoit comme argument une chaîne de caractères (éventuellement vide) et renvoie
TP 2 – Récursivité –Corrigé
Exercice 6 : Diagonale de Cantor. On initialise avec le numéro de (00)
Devoir maison 1 - Corrigé
Devoir maison 1 - Corrigé. M2 AIGEME année 2008-2009. Exercice 1. 1. On souhaite écrire une fonction récursive qui calcule le carré d'un entier. Pour trouver
SUJET + CORRIGE
Récursivité. 9. Le tri par base. 11. Variante tri rapide. 10. Complexité. 10. Total: 40. Exercice 1 : Récursivité. (9 points). Le nombre de combinaisons C p n
TD de Logique 9 (Fonctions récursives)
26/11/2012 Les exercices qui ne sont pas abordés en cours seront (certainement) corrigés sur ma page personelle (voir ci-dessus). (✠) Exercice 1 ( ...
Travaux dirigés 11 : fonctions fonctions récursives 1 Fonctions
l'exercice. 1. 3. Page 4. int McCarthy(int x). { if (x > 100). { return (x-10); Il est nécessaire que ce soit corrigé en TD ou en TP. Si les étudiants sont ...
EXERCICES 1 :
11/04/2021 EXERCICE N°01 : (10.00 POINTS). Soit G une grammaire définie par G= ({A F} ... Gest récursive gauche (cas de la récursivité gauche indirecte).
Travaux Dirigés dalgorithmique no4
Écrire une fonction récursive qui calcule la somme de nombres de 1 a n si n > 0 et renvoie 0 sinon. Exercice 4. Donner un algorithme récursif pour calculer xn
Langage C : énoncé et corrigé des exercices IUP GéniE
Cette f onction donne l e mêm e résu l tat q ue l a f onction est-/acteur m ais est récursive. Exercice 18 On util isera l es t y pes suivants : t y pedef char
Corrigé de la Fiche de TD Récursivité Exercice 1
Exercice 2 a) Écrire une fonction itérative qui renvoie le reste de la division euclidienne d'un entier a par un entier b en utilisant les soustractions
RECURSIVITE Exercices - Corrigés
RECURSIVITE. Exercices - Corrigés. Exercice1 - Un calcul très classique. Ecrire une fonction Python qui calcule la somme des inverses des carrés des n
Corrigés des exercices sur les fonctions récursives
Corrigés des exercices sur les fonctions Exercice 7.1.1 sous-programmes récursifs ... variation qui affecte le paramètre à chaque appel récursif.
Récursivité 1 Exercices
Récursivité. 1 Exercices. 1.1 Généralités sur les algorithmes récursifs. Exercice 2-1 Que calcule fact ? Question 1. Voici quelques lignes de code :.
SUJET + CORRIGE
SUJET + CORRIGE. Avertissement Exercice 1 : Récursivité ... Écrire une fonction python récursive terminale combRecAux(np
Récursivité
RÉCURSIVITÉ. Exercice 6.- (Nombres de Fibonacci). ´Ecrire une fonction C utilisant un algorithme récursif
La récursivité
Cliquez sur l'exercice pour y accéder. Maximum de trois entiers en récursif. Fonction ensureRange. Nombre intermédiaire entre trois entiers. Dis « Bonjour ! ».
TD 1 – Fonctions récursives primitives
Solution de l'exercice 1. On va montrer que les singletons sont récursifs primitifs car leur fonction caractéristique est récursive primitive.
Récursivité 1 Exercices - Nanopdf
Récursivité. 1 Exercices. 1.1 Généralités sur les algorithmes récursifs. Exercice 2-1 Que calcule fact ? Question 1. Voici quelques lignes de code :.
A.1 Quelques exercices corrigés
A.1 Quelques exercices corrigés. 1. 33. Mettre sous forme normale de Chomsky la grammaire définie Eliminer la récursivité gauche de la grammaire ETF.
Corrigés des exercices sur les fonctions récursives
Corrigés des exercices sur les fonctions récursives Exercice 7 1 1 sous-programmes récursifs Pour chacun des sous-programmes nous donnerons les paramètres en précisant le paramètre sur lequel porte la récurrence le cas de base (valeur de ce paramètre pour lequel le calcul s’arrête) et la
Récursivité - Exercices
Récursivité 1 Contenududocumentettravailàréaliser – Le documentprésentedes exemples de fonctionsdé?niesdefaçonrécursive – L’objectifestdecomprendrelaprogrammationrécursivedequelquesfonctionspuisdechercheràen écrirepar vous-mêmesquelques-unes
RECURSIVITE Exercices - Corrigés - PanaMaths
RECURSIVITE Exercices - Corrigés Exercice1 - Un calcul très classique Ecrire une fonction Python qui calcule la somme des inverses des carrés des n premiers entiers naturels non nuls On pourra ensuite écrire un script plus complet qui après le calcul précédent évalue et affiche l’écart (en ) avec la limite de cette somme qui vaut
Searches related to récursivité exercices corrigés PDF
Exercice 3 Fonction binomial(n : entier p : entier) : entier Début Si (p = 0 ou p = n) alors Retourner 1 ; Sinon Retourner binomial(n – 1 p) + binomial(n – 1 p – 1) ; FinSi ; Fin Exercice 4 /*version 1 La forme itérative*/ Fonction premierc(n :entier) :entier Debut Variables i S :entier; S?O; Pour i de 1 à n faire 1er appel
Exercice 1
On cherche à calculer la somme des entiers de 1 à n avec une fonction somme(n). 1. Écrivez une fonction avec la méthode itérative permettant de répondre au problème. 2. Écrivez une fonction récursive permettant de répondre au problème. 3. Écrivez une fonction permettant de calculer directement le résultat sans boucle ni récursion. 4.Faites le bilan...
Exercice 2
On cherche à calculer la somme des éléments d'une liste (un tableau). 1. Écrivez une fonction avec la méthode itérative permettant de répondre au problème. 2.Écrivez une fonction récursive permettant de répondre au problème. On rappelle que le premier élément d'une liste L se note L[0] et que le reste de la liste se note L[1:].
Exercice 3
Ici, on veut savoir si une chaîne de caractère est un palindrome, c'est à dire lue indifféremment de la gauche vers la droite et de la droite vers la gauche. 1. Écrivez une fonction récursive permettant de répondre au problème. On notera qu'on accède au premier élément d'une chaîne s avec s[0] et au dernier avec s[-1]. La chaine amputée de ses deux...
Exercice 5
Nous allons dessiner le fractal de Von Koch avec le module turtle. Nous allons avoir besoin de la récursivité. Nous dessinerons ensuite le flocon de Von Koch. 1. Créez une fonction récursive qui permet de dessiner le fractal de Kosh ci-dessous. Sont dessinés les fractal d'ordre 0, 1 et 2. La fonction de Koch prendra comme argument la longueur du se...
Comment faire une fonction récursive ?
1. Écrivez une fonction récursive donnant le quotient de la division euclidienne de n par d sachant que ce quotient est le même que celui de (n -d) par d, plus 1. Faites attention au cas de base. 2. Écrivez une fonction récursive donnant le reste de la division euclidienne de n par d sachant que ce reste est le même que celui de (n - d) par d.
Comment calculer une somme récursive?
# La fonction récursive pour le calcul de la somme proprement dit. def sum_sq_inv(n): if n == 1: return 1 else: return 1/n**2 + sum_sq_inv(n-1) # DEBUT DU SCRIPT # ===============
Comment résoudre les appels récursifs ?
S’assurer que, dans les appels récursifs, ..les arguments sont plus "simples" queceux avec lesquels la fonction a été appelée (ce qui signi?e essentiellement qu’ils« évoluent vers le cas de base ») Reconstituer correctement la valeur de retour de la fonction à partir du résultatdu ou des appels récursifs.
Université Paris Diderot Année 2016-2017
UFR de mathématiques Logique et complexité
TD 1 - Fonctions récursives primitives
Exercice 1.
Montrer que pour toutn2Nl"ensemblefngest récursif primitif. En déduire que tout sous-ensemble deNqui
est fini ou qui est le complémentaire d"un sous-ensemble fini deNest récursif primitif.Solution de l"exercice 1.
On va montrer que les singletons sont récursifs primitifs car leur fonction caractéristique est récursive primitive.
On sait que l"égalitéfdéfinie parf(x;y) = 1six=yet0sinon est récursive primitive. Si on notecnla fonction
constante égale ànà une variable, on afng=f(11;cn)ce qui montre quefngest bien un ensemble récursif
primitif.L"ensemble des ensembles récursifs primitifs étant clos par opérations booléennes, un sous ensemble fini deN
est la réunion de singletons deNqui sont récursifs primitifs et donc est récursif primitif. De même les ensembles
cofinis deNsont récursifs primitif par passage au complémentaire.Exercice 2.
Montrer que l"ensemble des nombres pairs est récursif primitif.Solution de l"exercice 2.
La fonction caractéristiquefdes nombres pairs se définit de la manière suivante par récurrence :f(0) = 1et
f(n+ 1) = 1f(n); elle est donc bien récursive primitive.Exercice 3.
Soitpun entier non nul. Montrer que la fonction supp:Np!Nqui à(x1;:::;xp)associe le maximum de x1;:::;xpest récursive primitive.
Solution de l"exercice 3.
Soitpun entier non nul , on veut montrer que la fonctionsuppqui aup-uplet(x1;:::;xp)associe le plus grand
desxipouriappartenant àf1;:::;pg. On fait une démonstration par récurrence surp. sup1(x1) =x1;sup1=11(c"est la projection à un argument)
On suppose que les sup
ipouriappartenant àf1;:::;p1g, sont récursives primitives on regarde pour supp+1: sup p+1(x1;:::;xp+1) =sup2(supp(x1;:::;xp);xp+1) où sup2(x;y) =x si x>yetysinon. Ainsi, supp+1est récursive primitive.
Donc la fonction sup
pest récursive primitive pour toutp2N.Exercice 4.
Montrer que les fonctionsquotientetrestesont récursives primitives (par définition, on posex=y= 0siy= 0).
En déduire quef(x;y)jydivisexgest récursif primitif.Solution de l"exercice 4.
Notonsqla fonction quotient. On aq(x;y) =k6x :(k+1)y > x, doncqest récursive primitive. La fonction
reste est égale àr(x;y) =xyq(x;y)l"est également.Exercice 5.
Montrer que l"ensemble des nombre premiers est récursif primitif. En déduire que la fonctionqui ànfait
correspondre le(n+ 1)-ième nombre premier est récursive primitive.Solution de l"exercice 5.
Un entiernest premier ssin >1et pour touta2 f2;n1g,ane divise pasn(qui peut s"écrire : pour touta < n,a <2ouane divise pasn). Ceci montre que l"ensemble des nombre premiers est récursif primitif.
La fonctionfqui ànfait correspondre le(n+ 1)-ième nombre premier est définie par récurrence :f(0) = 2et
f(n+ 1) =a6(f(n)! + 1):(a > f(n) etapremier). 1Exercice 6.
Soitf:N!Nune fonction récursive primitive. Montrer que la fonctiongdéfinie parg(x) =ff:::f|{z} x+1fois(0) est récursive primitive.Solution de l"exercice 6.
On définitgpar schéma de récurrence :(
g(0) =f(0) g(x+ 1) =f(g(x)).Exercice 7.
Montrer que la fonctionx7!xx:::x
, où le nombre dexdans la tour d"exponentielles estx+ 1, est récursive primitive.Solution de l"exercice 7.
On définit d"abord par schéma de récurrence une fonction récursive primitiveF(x;n) =xx:::x
, où le nombre de xdans la tour d"exponentielles estn:(F(x;0) = 1
F(x;n+ 1) =xF(x;n). La fonction cherchée estF(x;x), qui est donc récursive primitive.Exercice 8.
SoitEl"ensemble des entiers naturels qui sont la somme de deux carrés. Montrer queEest récursif primitif.
Solution de l"exercice 8.
x2Es"exprime par9s;t6x(s2+t2=x).Exercice 9.
Soitf:N!Ndéfinie parf(a;b) =2(c;d)oùc=dest l"écriture simplifiée de la fractiona=bsib6= 0, et
c=d= 0sinon. Montrer que la fonctionfest récursive primitive.Solution de l"exercice 9.
Il existe plusieurs solutions. On peut par exemple définirf(a;b)comme le plus petit entierk2(a;b)tel que
12(k)b=22(k)aetk6= 0.
Exercice 10.
Soitula fonction qui àn2Nassocie le(n+1)-ième entier naturel (dans l"ordre croissant) qui est une somme
de deux carrés. Montrer queuest récursive primitive.Solution de l"exercice 10.
On définit la fonctionupar un schéma de récurrence :( u(0) = 0 u(n+ 1) =k6(u(n) + 1)2:k > u(n)et9x;y6k(x2+y2=k)Exercice 11.
Soitfla fonction qui ànassocie le nombre d"entiers premiers inférieurs ou égaux àn. Montrer quefest
récursive primitive.Solution de l"exercice 11.
Deux solutions :
1. On utilise le test de primalité vu dans un exercice précédent :P(k) = 1sikest premier et0sinon. Ce
test est récursif primitif. On a alorsf(n) =Pn k=0P(k)qui est récursive primitive comme somme bornée de fonctions récursives primitives.2. Par schéma de récurrence on pose :(
quotesdbs_dbs2.pdfusesText_2[PDF] algorithme récursif maternelle
[PDF] algorithme récursif factorielle
[PDF] algorithme itératif
[PDF] exercice récursivité algorithme
[PDF] exercices corrigés récursivité python
[PDF] exercices récursivité
[PDF] exercice algorithme avec solution recursivité
[PDF] fonction récursive exercice corrigé python
[PDF] algorithme récursif exemple
[PDF] fonction recursive langage c
[PDF] fonction récursive exercice corrigé
[PDF] recursivite java
[PDF] la récursivité en algorithme exercice corrigé
[PDF] leo traduction
