Solution du TD d'informatique No. 3 :
la récursivité
Patrick Gros -- Patrick.Gros@irisa.fr
Didier Le Botlan -- didier.le_botlan@inria.fr
Lundi 27 novembre 2000
1 Écriture d' un nombre en base 2
import java.io.* ;
import java.lang.* ;
import java.util.* ;
public class ecriture_en_base_2 {
// Ecriture d'un nombre en base 2
/////////////////////////////////
static void Base_Deux(int n)
{
if (n >= 2)
Base_Deux(n / 2) ;
System.out.print(n % 2) ;
}
// Programme principal
//////////////////////
public static void main(String[] args) {
// Verifie si les arguments sont la
if (arg.length != 1) {
System.out.println("Utilisation : java ecriture_en_base_2 n") ;
System.exit(0) ;
}
// Recupere le nombre a tester
int n = Integer.parseInt(arg[0]) ;
if (n == 0)
System.out.print(0) ;
else
Base_Deux(n) ;
System.out.println("") ;
}
}
2 Résolution d'une équation par dichotomie
2.1 La dichotomie récursive
import java.io.* ;
import java.lang.* ;
import java.util.* ;
public class dichotomie_recursive {
// Calcul de la fonction
////////////////////////
static double f(double x)
{
return ((((x + 3.0) * x + 2.0) * x + 1.0) * x + 3.0) * x + 1.0 ;
}
// Resolution d'une equation par dichotomie
///////////////////////////////////////////
static double resol_dicho(double min, double max)
{
double mil = (min + max) / 2.0 ;
double ymin = f(min), y = f(mil) ;
if (Math.abs(y) < 1.0e-15)
return mil ;
else if (y < 0 && ymin < 0 || y > 0 && ymin > 0)
return resol_dicho(mil, max) ;
else
return resol_dicho(min, mil) ;
}
// Programme principal
//////////////////////
public static void main(String[] args) {
double x = resol_dicho(-1000.0, + 1000.0) ;
System.out.println("f(" + x + ") = " + f(x)) ;
}
}
2.2 La dichotomie itérative
import java.io.* ;
import java.lang.* ;
import java.util.* ;
public class dichotomie_iterative {
// Calcul de la fonction
////////////////////////
static double f(double x)
{
return ((((x + 3.0) * x + 2.0) * x + 1.0) * x + 3.0) * x + 1.0 ;
}
// Resolution d'une equation par dichotomie
///////////////////////////////////////////
static double resol_dicho(double min, double max)
{
double mil = (min + max) / 2.0 ;
double ymin = f(min), y = f(mil) ;
while (Math.abs(y) > 1.0e-15) {
if (y < 0 && ymin < 0 || y > 0 && ymin > 0) {
min = mil ;
ymin = f(min) ;
}
else {
max = mil ;
}
mil = (min + max) / 2.0 ;
ymin = f(min) ;
y = f(mil) ;
}
return mil ;
}
// Programme principal
//////////////////////
public static void main(String[] args) {
double x = resol_dicho(-1000.0, + 1000.0) ;
System.out.println("f(" + x + ") = " + f(x)) ;
}
}
3 Puissances d'une matrice
import java.io.* ;
import java.lang.* ;
import java.util.* ;
public class calcul_puissance_matrice {
// Interaction avec l'utilisateur
/////////////////////////////////
// Demander un entier a l'utilisateur
static int Lire_Entier(String question) {
System.out.println(question) ;
int reponse= 0 ;
try {
BufferedReader entree = new BufferedReader(new InputStreamReader(System.in)) ;
StringTokenizer st = new StringTokenizer(entree.readLine()) ;
reponse = Integer.valueOf(st.nextToken()).intValue() ;
}
catch(java.io.IOException e) {
System.out.println("Erreur de lecture") ;
System.exit(0) ;
}
return reponse ;
}
// Demander un reel a l'utilisateur
static double Lire_Reel(String question) {
System.out.println(question) ;
double reponse = 0.0 ;
try {
BufferedReader entree = new BufferedReader(new InputStreamReader(System.in)) ;
StringTokenizer st = new StringTokenizer(entree.readLine()) ;
reponse = Double.valueOf(st.nextToken()).doubleValue() ;
}
catch(java.io.IOException e) {
System.out.println("Erreur de lecture") ;
System.exit(0) ;
}
return reponse ;
}
// Exponentiation matricielle
/////////////////////////////
static double [] Mult_Matrice(double [] m1, double [] m2)
{
double [] m = new double [4] ;
m[0] = m1[0] * m2[0] + m1[1] * m2[2] ;
m[1] = m1[0] * m2[1] + m1[1] * m2[3] ;
m[2] = m1[2] * m2[0] + m1[3] * m2[2] ;
m[3] = m1[2] * m2[1] + m1[3] * m2[3] ;
return m ;
}
static double [] Puissance_Matrice(double [] matrice, int n)
{
if (n == 0) {
double [] res = new double [4] ;
res[0] = res[3] = 1.0 ;
res[1] = res[2] = 0.0 ;
return res ;
}
else if (n % 2 == 0) {
double [] mat = Puissance_Matrice(matrice, n / 2) ;
return Mult_Matrice(mat, mat) ;
}
else
return Mult_Matrice(Puissance_Matrice(matrice, n - 1), matrice) ;
}
// Programme principal
//////////////////////
public static void main(String[] args) {
double matrice [] = new double[4], matrice2 [] = new double[4] ;
matrice[0] = Lire_Reel("a11") ;
matrice[1] = Lire_Reel("a12") ;
matrice[2] = Lire_Reel("a21") ;
matrice[3] = Lire_Reel("a22") ;
int n = Lire_Entier("Puissance") ;
matrice2 = Puissance_Matrice(matrice, n) ;
System.out.println("(" + matrice2[0] + " " + matrice2[1] + ")") ;
System.out.println("(" + matrice2[2] + " " + matrice2[3] + ")") ;
}
}
4 Flocon de Von Koch
import java.io.* ;
import java.lang.* ;
import java.util.* ;
import Point ;
import DrawingFrame ;
//import Input ;
//import Output ;
import MacLib ;
public class flocon_von_koch {
// Flocon de Von Koch
/////////////////////
static double x, y;
static final double COTE_MIN = 3.01;
static void flocon(Point centre, Point pointe) {
x = pointe.h;
y = pointe.v;
MacLib.moveTo(pointe.h, pointe.v);
double dx = x - centre.h;
double dy = y - centre.v;
double longueur = Math.sqrt(3 * (dx*dx + dy*dy));
if (longueur < COTE_MIN)
return;
double angle = Math.atan2(-dy, dx) - 5 * Math.PI / 6;
cote(longueur, angle);
cote(longueur, angle - 2 * Math.PI / 3);
cote(longueur, angle + 2 * Math.PI / 3);
}
static void cote(double longueur, double angle) {
if (longueur < COTE_MIN) {
x += longueur * Math.cos(angle);
y -= longueur * Math.sin(angle);
MacLib.lineTo((int)Math.round(x), (int)Math.round(y));
} else {
cote(longueur/3, angle);
cote(longueur/3, angle + Math.PI/3);
cote(longueur/3, angle - Math.PI/3);
cote(longueur/3, angle);
}
}
static void flocon_inverse(Point centre, Point pointe) {
x = pointe.h;
y = pointe.v;
MacLib.moveTo(pointe.h, pointe.v);
double dx = x - centre.h;
double dy = y - centre.v;
double longueur = Math.sqrt(3 * (dx*dx + dy*dy));
if (longueur < COTE_MIN)
return;
double angle = Math.atan2(-dy, dx) - 5 * Math.PI / 6;
cote_inverse(longueur, angle);
cote_inverse(longueur, angle - 2 * Math.PI / 3);
cote_inverse(longueur, angle + 2 * Math.PI / 3);
}
static void cote_inverse(double longueur, double angle) {
if (longueur < COTE_MIN) {
x += longueur * Math.cos(angle);
y -= longueur * Math.sin(angle);
MacLib.lineTo((int)Math.round(x), (int)Math.round(y));
} else {
cote_inverse(longueur/3, angle);
cote_inverse(longueur/3, angle - Math.PI/3);
cote_inverse(longueur/3, angle + Math.PI/3);
cote_inverse(longueur/3, angle);
}
}
// Programme principal
//////////////////////
public static void main(String[] args) {
MacLib.InitQuickDraw() ;
MacLib.showDrawing();
Point centre = new Point(), bout = new Point() ;
MacLib.getClick(centre);
MacLib.getClick(bout);
flocon(centre, bout);
flocon_inverse(centre, bout);
MacLib.getClick(bout);
System.exit(0) ;
}
}
5 La courbe du dragon
class dragon {
static void dragon(int n, int x, int y, int z, int t) {
int u, v ;
if (n == 1) {
MacLib.moveTo(x, y) ;
MacLib.lineTo(z, t) ;
}
else {
u = (x + z + t - y) / 2 ;
v = (y + t - z + x) / 2 ;
dragon(n - 1, x, y, u, v) ;
dragon(n - 1, z, t, u, v) ;
}
}
static void dragon2(int n, int x, int y, int z, int t) {
int u, v ;
if (n == 1) {
MacLib.moveTo(x, y) ;
MacLib.lineTo(z, t) ;
}
else {
u = (x + z + t - y) / 2 ;
v = (y + t - z + x) / 2 ;
dragon2(n - 1, x, y, u, v) ;
dragon3(n - 1, u, v, z, t) ;
}
}
static void dragon3(int n, int x, int y, int z, int t) {
int u, v ;
if (n == 1) {
MacLib.moveTo(x, y) ;
MacLib.lineTo(z, t) ;
}
else {
u = (x + z - t + y) / 2 ;
v = (y + t + z - x) / 2 ;
dragon2(n - 1, x, y, u, v) ;
dragon3(n - 1, u, v, z, t) ;
}
}
static public void main(String arg[]) {
// Verification des parametres
int n ;
if (arg.length == 0)
n = 15 ;
else
n = Integer.parseInt(arg[0]) ;
// Les parametres de base
int largeur = 50, hauteur = 50 ;
// Intialisation du graphique
MacLib.InitQuickDraw() ;
MacLib.ShowDrawing() ;
Rect r = new Rect() ;
r. top = 100 ;
r.left = 100 ;
r.bottom = (short)(r.top + hauteur * 10) ;
r.right = (short)(r.left + largeur * 10) ;
MacLib.SetDrawingRect(r) ;
// Dessin du dragon
MacLib.foreColor(MacLib.yellowColor) ;
dragon2(n, 249, 249, 100, 100) ;
MacLib.foreColor(MacLib.redColor) ;
dragon2(n, 251, 249, 400, 100) ;
MacLib.foreColor(MacLib.blueColor) ;
dragon2(n, 251, 251, 400, 400) ;
MacLib.foreColor(MacLib.magentaColor) ;
dragon2(n, 249, 251, 100, 400) ;
System.out.println("C'est fini") ;
Point bout = new Point() ;
MacLib.getClick(bout);
System.exit(0) ;
}
} ;
This document was translated from LATEX by
HEVEA.