Exercices corrigés - LIPN[PDF] exercice statique analytique
[PDF] cours mecanique statique pdf
[PDF] exercice statique graphique
[PDF] cours de statistique appliquée ? l'économie pdf
[PDF] statistiques ? deux variables exercices corrigés b
[PDF] exercice fréquence cumulée croissante
[PDF] suites numériques terminale bac pro
[PDF] suite numérique bac pro cours
[PDF] exercices suites numériques 1 bac pro
[PDF] suites numériques exercices corrigés terminale l p
[PDF] exercices acido basique avec correction
[PDF] exercices corrigés sur l'excrétion urinaire 5eme
[PDF] le role du rein dans l'excrétion urinaire
[PDF] exercices corrigés sur l excrétion urinaire pdf
Universit´e Paris Diderot JAVA
MASS L2 Ann´ee 2007-2008
TD n ◦7 - Correction R´ecursivit´eExercice 1Tableaux bidimensionnels ´Ecrire une m´ethodestatic int minMax(int[][] t)renvoyant le plus petit maximum dechaque ligne de t.Correction :Il est pratique de commencer par ´ecrire une fonction auxiliaire permettant de calculer le
maximum d"une ligne.static int maxLigne(int[] t) int r=t[0]; for (int i=1; iOn peut aussi tout ´ecrire dans une seule m´ethode, mais cel`a va ˆetre moins lisible :static int minMax(int[][] t)
int r=t[0][0]; for (int j=1; jExercice 2R´ecursivit´e
1.´
Ecrire une m´ethode r´ecursivestatic int fact(int n)permettant de calculer la facto- rielle den.Correction :Attention : outre l"appel r´ecursif, toutes les m´ethodes r´ecursives doivent conteinir un crit`ere d"arrˆet.
S"il n"y a pas de crit`ere d"arrˆet ou s"il n"est pas bon, on va avoir une r´ecursion `a l"infini, qui va
provoquer une erreur `a l"ex´ecution. C"est par exemple le cas pour le code suivant :static void stupide()
stupide();o`ustupide()fait des appels en cascade d"elle-mˆeme sans jamais s"arrˆeter.static int fact(int n)
if (n==0) return 1; //crit`ere d"arr^et return n*fact(n-1); //appel r´ecursif2.´
Ecrire une m´ethode r´ecursivestatic binome(int n, int p)permettant de calculer un coefficient binomial.Correction : static int binome(int n, int p) if (n<0 || p<0 || p>n) return 0; if (p==0 || p==n) return 1; return binome(n-1, p-1)+binome(n-1, p);3.En remarquant quexp= (x(p/2))2sipest pair, etxp=x(x(p/2))2sipest impair, ´ecrivez
une m´ethodestatic exp(double x, int n)calculantxnCorrection :On appelle cet algorithmeexponentiation rapide.2
static double exp(double x, int n) if (n==0) return 1; if (n%2==0) double a=exp(x, n/2); return a*a; else double a=exp(x, n-1/2); return a*a*x;Ainsi, pour calculer 2
37, on aura des appels `aexp(2, 37),exp(2, 18),exp(2, 9),exp(2, 4),
exp(2, 2),exp(2, 1),exp(2, 0). En revanche si on utilisait une exponentiation na¨ıve :static double expNaive(double x, int n) if (n==0) return 1; return x*exp(x, n-1);le mˆeme calcul n´ecessiterait des appels `aexp(2, 37),exp(2, 36),exp(2, 35), ...,exp(2, 0), ce
qui est beaucoup plus couteux.Dans le second cas, le calcul dexna une complexit´e lin´eaireO(n), alors que dans le premier cas,
on peut montrer qu"elle est logarithmique (O(log(n))).?Exercice 3R´ecursivit´e et tableaux
1.´
Ecrire une m´ethode r´ecursivestatic int sum(int n, int[] t)calculant la somme desnpremiers ´el´ements det.Correction :Pour faire la somme desnpremiers ´el´ements, on prend la somme desn-1 premiers,
et on lui ajoute le n `eme(c"est-`a-diret[n-1]).static int sum(int n, int[] t) if (n==0) return 0; return t[n-1]+sum(n-1, t);2.En utilisant une m´ethode r´ecursive auxiliaire,´ecrire une m´ethodestatic affiche(int[] t)
permettant d"afficher le tableaut.Correction :Commen¸cons par ´ecrire une m´ethode permettant d"afficher lesnpremiers ´el´ements d"un tableau.
Pour afficher lesnpremiers ´el´ements, on affiche lesn-1 premiers, puis on affiche le n`eme.static void afficheN(int n, int[] t)
if (n==0) return;3 afficheN(n-1, t);System.out.println(t[n-1]);
il ne reste plus alors qu"`a afficher lest.lengthpremiers ´el´ements detpour l"afficher enti`erement.static void affiche(int[] t)
afficheN(t.length, t);3.Modifier la m´ethode pr´ec´edente pour que le tableau soit affich´e dans l"ordre inverse.
Correction :
Il suffit, dansafficheNd"afficher l"´el´ement courantavantd"afficher ce qui pr´ecede :static void afficheN(int n, int[] t)
if (n==0) return;System.out.println(t[n-1]);
afficheN(n-1, t); Exercice 4On parle de r´ecursivit´ecrois´eelorsque deux fonctions s"appellent l"une l"autre r´ecursivement. Les fonctions suivantes sont cens´ees donner la parit´e d"un nombre entier : cela sera-t-il le cas pour toutes les valeurs enti`eres positives?import fr.jussieu.script.Deug; class PairImpair{ static boolean pair (int n){ if (n==0) return true; else return impair(n-1); static boolean impair (int n){ if (n==1) return true; else return pair(n-1); public static void main (String[] args) { int p = Deug.readInt(); Deug.println("pair? "+ pair(p) + " impair? " + impair(p)); }4Correction :Regardons ce qui se passe lors d"un appel `apair(3). En suivant l"ex´ecution du code pas
`a pas, on va avoir les appels suivants : pair(3) impair(2) pair(1) impair(0) pair(-1) impair(-2)La condition d"arrˆet n"est donc pas bonne. Un autre ´el´ement montrant que ce code ne peut pas
marcher est qu"aucune des deux m´ethodes ne peut jamais renvoyerfalse.On pourrait les modifier de la mani`ere suivante pour qu"elles fonctionnent :import fr.jussieu.script.Deug;
class PairImpair{ static boolean pair (int n){ if (n==0) return true; else return impair(n-1); static boolean impair (int n){ if (n==0) return false; else return pair(n-1); public static void main (String[] args) { int p = Deug.readInt(); Deug.println("pair? "+ pair(p) + " impair? " + impair(p));Exercice 5Tours de Hano¨ı
On dispose denplateaux de taille diff´erentes, et de 3 tiges, num´erot´ees de 0 `a 2.Initialement, tous les plateaux sont situ´es sur la tigei. Le but est de les transf´erer sur la
tigej, en respectant les r`egles suivantes :-On ne peux d´eplacer qu"un plateau `a la fois -Les plateaux doivent toujours rang´es par taille d´ecroissante sur une tige.1.R´esolvez le probl`eme `a la main sin= 2,i= 0 etj= 2.Correction :
5 -On transf`ere le petit plateau de 0 `a 1. -On transf`ere le grand plateau de 0 `a 2. -On transf`ere le petit plateau de 1 `a 2. Si vous n"ˆetes pas convaincus, faites un dessin ...?2.R´esolvez le probl`eme `a la main sin= 3,i= 0 etj= 2.Correction :
-On transf`ere le petit plateau de 0 `a 2. -On transf`ere le plateau moyen de 0 `a 1. -On transf`ere le petit plateau de 2 `a 1.(ce faisant, on a d´eplac´e 2 plateaux de 0 vers 1).-On tranf`ere le grand plateau de 0 vers 2.
-On transf`ere le petit plateau de 1 `a 0. -On transf`ere le plateau moyen de 1 `a 2.quotesdbs_dbs4.pdfusesText_8