Download Algorithmique Techniques Fond Amen Tales de Program Mat Ion com PDF

TitleAlgorithmique Techniques Fond Amen Tales de Program Mat Ion com
File Size2.4 MB
Total Pages221
Table of Contents
                            Algorithmique Techniques fondamentales de programmation ex java.pdf
Algorithmique.pdf
	01-Algorithmique.pdf
		Titre, auteur...
	02-Introduction
		Introduction
	03-Les fondements de l’informatique
		Les fondements de l’informatique
	04-L’algorithmique
		L’algorithmique
	05-Les langages d’implémentation
		Les langages d’implémentation
	06-La variable
		La variable
	07-Opérateurs et Calculs
		Opérateurs et Calculs
	08-Pour aller plus loin
		Pour aller plus loin
	09-Types et langages
		Types et langages
	10-Les tests et conditions
		Les tests et conditions
	11-L’algèbre booléen
		L’algèbre booléen
	12-Les structures itératives
		Les structures itératives
	13-Tant Que
		Tant Que
	14-Répéter … Jusqu’à
		Répéter … Jusqu’à
	15-Pour … Fin Pour
		Pour … Fin Pour
	16-Présentation
		Présentation
	17-Manipulations simples
		Manipulations simples
	18-Algorithmes avancés
		Algorithmes avancés
	19-Structures et enregistrements
		Structures et enregistrements
	20-Présentation
		Présentation
	21-Les sousprogrammes
		Les sous-programmes récursifs
	22-Les différents fichiers
		Les différents fichiers
	23-Les enregistrements
		Les enregistrements
	24-Fichier texte séquentiel
		Fichier texte séquentiel
	25-Les pointeurs et références
		Les pointeurs et références
	26-Les listes chaînées
		Les listes chaînées
	27-Les arbres
		Les arbres
	28-Principe de l’objet, une notion évidente
		Principe de l’objet, une notion évidente
	29-Manipuler les objets
		Manipuler les objets
	30-L’objet en Java
		L’objet en Java
                        
Document Text Contents
Page 2

Ce livre s’adresse à toute personne désireuse de maîtriser les bases essentielles de la programmation. Pour apprendre à programmer, il
faut d’abord comprendre ce qu’est vraiment un ordinateur, comment il fonctionne et surtout comment il peut faire fonctionner des programmes,
comment il manipule et stocke les données et les instructions, quelle est sa logique. Alors, au fur et à mesure, le reste devient évidence :
variables, tests, conditions, boucles, tableaux, fonctions, fichiers, jusqu’aux notions avancées comme les pointeurs et les objets.
Dans ce livre, le langage algorithmique (ou la syntaxe du pseudo-code des algorithmes) reprend celui couramment utilisé dans les écoles
d’informatique et dans les formations comme les BTS, DUT, premières années d’ingénierie à qui ce livre est en partie destiné et
conseillé. Une fois les notions de base acquises, le lecteur trouvera dans ce livre de quoi évoluer vers des notions plus avancées : deux
chapitres, l’un sur les pointeurs et les références, l’autre sur les objets, ouvrent les portes de la programmation dans des langages évolués et
puissants comme le C, le C++ et surtout Java.
Une grande partie des algorithmes de ce livre sont réécrits en Java et les sources, directement utilisables, sont disponibles en téléchargement
sur le site de l’éditeur (www.eni-livres.com).

Ce livre numérique a été conçu et est diffusé dans le respect des droits d’auteur. Toutes les marques citées ont été déposées par leur éditeur respectif. La loi du 11
Mars 1957 n’autorisant aux termes des alinéas 2 et 3 de l’article 41, d’une part, que les “copies ou reproductions strictement réservées à l’usage privé du copiste et non
destinées à une utilisation collective”, et, d’autre part, que les analyses et les courtes citations dans un but d’exemple et d’illustration, “toute représentation ou
reproduction intégrale, ou partielle, faite sans le consentement de l’auteur ou de ses ayants droit ou ayant cause, est illicite” (alinéa 1er de l’article 40). Cette
représentation ou reproduction, par quelque procédé que ce soit, constituerait donc une contrefaçon sanctionnée par les articles 425 et suivants du Code Pénal.
Copyright Editions ENI

Algorithmique 
Techniques fondamentales de programmation



Sébastien ROHAUT  

Résumé

L'auteur

Sébastien ROHAUT a débuté comme Ingénieur de développement en C++. Aujourd’hui Ingénieur Système il intervient sur des missions
régulières pour de grands comptes et continue d’enseigner le développement à des classes d’ingénieur et masters MTIC.

- 1 -© ENI Editions - All rigths reserved

Page 110

● Étape 3 : la plus petite valeur suivante est 25, déjà à la bonne position, on passe à la suivante. 

● Étape 4 : la plus petite valeur suivante est 34, on permute 34 et 48. Le tableau est trié. 

Si le principe est simple, l’algorithme résultant nécessite malheureusement la recherche dans tout ou partie du tableau 
de la plus petite valeur possible et ce sans grande optimisation possible. On peut par contre éviter de permuter des 
valeurs si aucune valeur inférieure n’a été trouvée. Voici l’algorithme : 

PROGRAMME SELECTION
VAR
temp,i,j,min,Cpt:entiers
t:tableau[1..5] d’entiers
DEBUT
Cpt←5 
Pour i de 1 à Cpt-1 Faire 
min←i 
Pour j de i+1 à Cpt 
Si t[j]<t[min] alors 
min←j 
FinSi 
FinPour 
Si min<>j alors 
temp←t[min] 
t[min] ←t[i] 
t[i] ←temp 
FinSi 
FinPour 
FIN

À chaque passage dans la boucle, on effectue une comparaison de moins que lors du passage précédent. Le nombre 
total de passages est donc de   et ainsi de suite soit une complexité de l’algorithme de   ce 
qui développé donne une complexité d’ordre  . 

Voici le code Java correspondant : 

class chap5_triselect { 
public static void main(String[] args) { 
int t[]={27,44,12,18,23,19,101,54,29,77,52,88,10,32}; 
int i,j,cpt,temp,min; 
 

cpt=14; 
for(i=0;i<cpt-1;i++) { 
min=i; 
for(j=i+1;j<cpt;j++) { 
if(t[j]<t[min]) min=j; 

if(min!=i) { 
temp=t[min]; 
t[min]=t[i]; 
t[i]=temp; 

for(j=0;j<cpt;j++) { 
System.out.print(t[j]+" "); 

System.out.println(); 


}

9  17  25  48  34 

9  17  25  48  34 

9  17  25  48  34 

- 2 - © ENI Editions - All rigths reserved

Page 111

Le tri à bulles a un lointain rapport avec le champagne ou d’ailleurs toutes les boissons gazeuses. Le but est que par 
permutations successives des valeurs voisines,  les valeurs  les plus élevées remontent vers  les dernières places du 
tableau, tandis que les valeurs les plus basses migrent vers les premières places. Pour trier dans un ordre croissant, il 
faut que chaque valeur d’un élément du tableau soit plus petite que celle de l’élément qui suit (sauf pour le dernier, 
bien entendu). Voici une simulation pas à pas du premier passage : 

● Étape 1 : 48 est supérieur à 17, on permute. 

● Étape 2 : 48 est supérieur à 25, on permute. 

● Étape 3 : 48 est supérieur à 9, on permute. 

● Étape 4 : 48 est supérieur à 34, on permute. 

À l’issue de ce premier passage, vous remarquez que la valeur la plus élevée est déjà en dernière place du tableau 
mais  que  le  tableau  n’est  pas  entièrement  trié.  Aussi  il  faut  effectuer  plusieurs  passages  en  vérifiant  à  chaque 
passage  si  des permutations ont eu  lieu. Quand une permutation au moins a eu  lieu  lors d’un passage,  il  faut en 
relancer une autre. Ainsi il faut mettre en place un drapeau (flag) indiquant si une permutation a eu lieu ou non. Voici 
les résultats après les passages successifs : 

● Passe 1: 

● Passe 2 : 

● Passe 3 : 

La structure globale de l’algorithme est donc : 

PROGRAMME TRIBULLE 
VAR 
Permut :booléen 
temp,Cpt,i:entiers 
t:tableau[1..5] d’entiers 
DEBUT 
Cpt←5 
Permut←vrai 
TantQue Permut Faire 
Permut←Faux 

17  48  25  9  34 

17  25  48  9  34 

17  25  9  48  34 

17  25  9  34  48 

17  25  9  34  48 

17  9  25  34  48 

9  17  25  34  48 

- 3 -© ENI Editions - All rigths reserved

Page 220

}
}


class rectangle extends figure {
private double largeur,hauteur;

// Constructeur
rectangle(double c_x,double c_y,double r_l,double r_h) {
// appel du constructeur de figure
super("violet","marron");
this.x=c_x;
this.y=c_y;
this.largeur=r_l;
this.hauteur=r_h;
}

// Implémentation des méthodes abstraites
public double getSurface() {
return this.largeur*this.hauteur;
}

public double getPerimetre() {
return 2*(this.largeur+this.hauteur);
}
}

class chap9_heritage {
public static void main(String[] args) {
disque o1;
rectangle o2;

o1=new disque(100,100,10);

System.out.println(o1.getSurface());
System.out.println(o1.getPerimetre());

o2=new rectangle(10,10,35,25);
System.out.println(o2.getSurface());
System.out.println(o2.getPerimetre());

}
}

Encore une fois, en Java les interfaces sont exactement comme en algorithmique. Vous créez une interface avec le mot­
clé " "  et vous indiquez que la classe implémente cette interface avec le mot­clé " " après le nom 
de la classe, suivi du nom de l’interface. 

interface lecture {
public void lecture() ;
public void pause() ;
public void stop() ;
public void avance() ;
public void retour() ;
public void précédent() ;
public void suivant() ;
}

class Musique implements lecture {
private String morceau;
private int position,duree,piste;

Musique(String m, int p) {
this.morceau=m;
this.piste=p;

- 4 - © ENI Editions - All rigths reserved

Page 221

position=0;
}

// Début d’implémentation de l’interface
public void lecture() {
System.out.println("lecture de "+this.morceau);
}
public void pause() {
System.out.println("Pause à "+position);
}
public void stop() {
System.out.println("Arrêt piste "+this.piste);
}
public void avance() {
System.out.println("Avance");
}
public void retour() {
System.out.println("retour");
}
public void précédent() {
System.out.println("Précédent");
}
public void suivant() {
System.out.println("Suivant");
}
}

class chap9_interface {
public static void main(String[] args) {
Musique o1;

o1=new Musique("Somebody to love",10);
o1.lecture();
}
}

Une classe peut implémenter plusieurs interfaces, dans ce cas séparez les noms des interfaces par des virgules. 

Une  interface  peut  hériter  d’une  ou plusieurs  autres  interfaces  via  le mot­clé  " "  suivi  du nom de  la  ou des 
interfaces héritées. 

interface lecture1 {
public void lecture() ;
public void pause() ;
public void stop() ;
}
interface lecture2 {
public void avance() ;
public void retour() ;
public void précédent() ;
}

interface lecture extends lecture1, lecture2 {
public void suivant() ;

Ces deux derniers cas sont les seuls en Java où, indirectement, une sorte d’héritage multiple a été mis en place, dans 
le sens où une interface ou une classe peut hériter de plusieurs définitions de méthodes. C’est simpliste dans le sens 
où de toute façon ces méthodes doivent être implémentées obligatoirement dans la classe qui utilise les interfaces, et 
que du coup Java n’a pas à savoir s’il doit utiliser telle ou telle méthode de l’une des classes héritées. 

- 5 -© ENI Editions - All rigths reserved

Similer Documents