Algorithmique Groupe ALGO Lille

Algorithmique

Utilisation des langages Python Scilab et Xcas

Groupe ALGO Lille

Table des matières

1 Langage Python 3

2 Langage Scilab 10

2.1 Lignes de commentaires . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102.2 Boucles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102.3 an . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112.4 SI...ALORS...SINON . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112.5 TANT QUE... . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132.6 Inverses . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 142.7 Somme des n premiers inverses . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 152.8 Image d'un réel par une fonction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 152.9 Second degré . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

3 Langage Xcas 17

3.1 Lignes de commentaires . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 183.2 Somme des n premiers entiers non nuls . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 183.3 an . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 193.4 Nombre de pile et fréquence corresondante . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 193.5 Obtenir les six faces d'un dé . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 203.6 Longueurs de plusieurs segments dans [0 ;1] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 213.7 pgcd . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 213.8 Calcul du discriminant . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22

Ce document a pour but de proposer des exemples d'algorithmes traduits en langages Python, Scilab et en�n Xcas.

1 Langage Python

Sous Python, il n’est pas nécessaire de définir le type des variables avant de les utiliser. La le type qui correspond au mieux à la valeur fournie.

Les premiers exercices peuvent se traiter directement au clavier ou à l’aide d’un script.

#premier essai : ligne de commentairesa=3b=a+2c=bb=c+a

r=input ("b=")if r==b: print ("bravo")else: print ("perdu")

L’exécution donne :

b=9perdu>>>

>>> b=8bravo>>>Cependant, le plus simple sous python est de travailler avec des fonctions. Ainsi, pour le calcul du discriminant, est-il possible d’écrire :

#définition de la fonction et donnée des paramètres d'entréedef discriminant(a,b,c): return b^2-4*a*c

dont l’éxecution donne :

>>> discriminant(2,4,5)-34

Les boucles

Exemple 1 : affichage des n premiers entiers naturels non nuls et de leur somme.

def entiers1(n): s=0

for i in range(1,n+1): print i, s=s+i

print ("somme=",s)

Remarque : l’instruction range(1,n) donne les entiers compris entre 1 et n-1

Ce qui donne :

>>> entiers1(12)1 2 3 4 5 6 7 8 9 10 11 12 ('somme=', 78)>>>

Exemple 2 : affichage des n premières puissances de a

def puissance(a,n): for i in range(1,n+1): print a**i,ce qui donne, par exemple :

>>> puissance(2,5)2 4 8 16

Le Si .. alors … sinon

Le lecteur attentif en aura trouvé un premier exemple dans les premières lignes. Donnons-en quelques exemples supplémentaires.

Exemple 1 : Simulation du lancer d’une pièce équilibrée

L’algorithme La fonction Exemple d’utilisationDefinition de la fonction piece

Variable d’entréen nombre d’essaisVariables utiliséess nombre de « pile » obtenui compteur de boucleAlgo :Mettre s à 0Pour i variant entre 1 et n Si nhhasard<0.5 S augmente de 1 Fin du SiFin du PourRetourner s/n

def piece(n): s=0. for i in range(1,n+1): if random.random()<0.5: s=s+1 return s/n

>>> import random>>> piece(12)0.5>>> piece(1000)0.51800000000000002

Remarque : l’utilisation de l’instruction random.random() demande l’importation du module random.

Attention : Le fait d’écrire s=0. permet de forcer l’ordinateur à considérer que s est un nombre décimal. Ainsi la division s/n sera faite classiquement. Dans le cas contraire s/n donne 0 car le programme fait dans ce cas la division entière.

Exemple 2 : Le segment [AB] est un segment de longueur 1. Aux deux nombres x et y tirés au hasard entre 0 et 1, on associe les points C et D de [AB] définis par AC=min(x,y) et AD=max(x,y). Les points A, B C et D étant La fonction doit retourner la longueur des trois segments [AC] , [CD] , [DB] ainsi formés.

L’algorithme La fonction Exemple d’utilisationDéfinition de la fonction long

Variable d’entréeaucuneVariables utiliséesx nb aléatoire entre 0 et 1y nb aléatoire entre 0 et 1a,b et c longueurs des trois segmentsAlgo :Tirer x et ySi x<y Alors Mettre x dans a et y-x dans b Sinon Mettre y dans a et x-y dans bFin du SiMettre 1-(a+b) dans cRetourner a,b et c

def longueur(): import random x=random.random() y=random.random() if x<y: a=x b=y-x else: a=y b=x-y c=1-(a+b) return a,b,c

>>> >>> longueur()(0.43051276384573156, 0.17875160084316677, 0.39073563531110167)>>>

Le Tant que :

Exemple 1 : Algorithme d’Euclide

L’algorithme La fonction Exemple d’utilisationDéfinition de la fonction pgcd

Variable d’entréeLes entiers a et bVariables utiliséesr reste de la division de a par bAlgorithmeTant que b est non nul Mettre reste de a par b dans r Mettre b dans a Mettre r dans bFin du tant queRetourner a

def pgcd(a,b): while b!=0: r=a%b a=b b=r return a

pgcd(12,45)3>>>

Exemple 2 : Comptage du nombre de lancers d’un dé pour obtenir l’ensemble des six faces.

Cet exemple nous permettra d’introduire une liste.

Création d’une liste :

Liste des entiers de 1 à 6 (noter le décalage mais cela a déjà été signalé)

>>> liste=range(1,7) >>> liste [1, 2, 3, 4, 5, 6] >>>

La suite se passe de commentaires ou presque :

>>> liste[1]2>>> len(liste)6>>> liste.append(7)>>> liste[1, 2, 3, 4, 5, 6, 7]

>>> liste[2]=0>>> liste[1, 2, 0, 4, 5, 6, 7]>>> del liste[3]>>> liste[1, 2, 0, 5, 6, 7]>>>

>>> liste[-1]7>>> liste[1:3][2, 0]

>>> liste=[1,4,2,3]>>> liste.sort()>>> liste[1, 2, 3, 4]>>> liste.reverse()>>> liste[4, 3, 2, 1]>>> liste.index(3)1>>> liste_n_zeros=[0]*5>>> liste_n_zeros[0, 0, 0, 0, 0]>>>

En cas de problème, je vous invite à aller consulter l’aide et faire des progrès en anglais …Vous aurez remarqué que le premier terme de la liste est le terme d’indice 0 et non 1. Cela explique les résultats trouvés.

Principe : (c’en est un, il y en a d’autres)

On crée la liste l = (1,2,3,4,5,6)

Algo

Le lancer du dé donne a. On remplace le terme a de la liste par 0Avoir obtenu les faces possibles se traduit donc par le fait que les six termes de l sont nuls.

D’où :

L’algorithme La fonction Exemple d’utilisationDéfinition de la fonction lancer-de_1

Variable d’entréeaucuneVariables utiliséesl liste testl1 liste contenant les six facesnb nombre d’essaisAlgorithmeTant que l et l1 sont différentes Effectuer un lancer, on note x la face obtenue Indiquer que la face x a été obtenue. Augmenter de 1 nbFin du tant queRetourner nb

def lancer_de_1(): import random l=[0]*6 l1=range(1,7) nb=0 while l!=l1: x=random.randint(1,6) l1[x-1]=0 nb=nb+1 return nb

>>> >>> lancer_de_1()7>>> lancer_de_1()21>>> lancer_de_1()11>>> lancer_de_1()19>>>

Remarque : On peut désormais utiliser la fonction précédente pour estimer le nombre moyen de lancers nécessaire pour obtenir les six faces :

La fonction Exemple d’utilisationdef nb_moyen(n): total=0. for i in range(1,n+1): total=total+lancer_de_1() return total/n

>>> nb_moyen(1000)14.327>>> nb_moyen(1000)14.712>>> nb_moyen(1000)14.836>>> nb_moyen(10000)

14.766>>>

Quelques exercices et les corrections associées :

Exercice1 : un nombre n étant donné, afficher ses chiffres un par un.

Une idée possible :Partons d’un exemple n= 1428 :

Le chiffre des unités 8 est le reste de la division de n par 10. 8 étant trouvé, on peut recommencer avec 142, 14 etc soit tant que le nombre restant n’est pas nul.

L’algorithme La fonction Exemple d’utilisationDéfinition de la fonction chiffres

Variable d’entréeL’entier n à décomposerVariables utiliséesr chiffre des unitésl liste des chifresAlgorithmeInitialiser l à liste vide.Tant que n est non nul Calculer r Ajouter r à l Caluler la nouvelle valeur de n : (n-r)/10Fin du tant queRetourner l

def chiffres(n): l=[] while n!=0: r=n%10 l.append(r) n=(n-r)/10 return l

>>> >>> chiffres(15276)[6, 7, 2, 5, 1]>>>

Exercice 2 : A vous d’examiner les fonctions suivantes et les résultats obtenus. Expliquer ce qui se passe.

Les fonctions Exemple d’utilisationdef suivant(p): l=chiffres(p) l.sort() n1=0 n2=0 for i in range(1,len(l)+1): n1=n1+l[i-1]*10**(len(l)-i) n2=n2+l[i-1]*10**(i-1) return n2-n1

def kaprekar(n): liste=[] ecart=0

>>> >>> kaprekar(4742)(6174, 'nombre cyclique')>>> kaprekar(495)(495, 'kaprekar')>>> kaprekar(44)(0, 'les chiffres de n sont tous identiques')>>>

while (n in liste) ==False: liste.append(n) n=suivant(n) ecart=ecart+1 if ecart==1: rep="kaprekar" else: if n==0: rep="les chiffres de n sont tous identiques" else: rep="nombre cyclique" return n,rep

return l

2 Langage Scilab

2.1 Lignes de commentaires

On peut traiter cet exemple en ligne de commande directement.

a=3 ;b=a+2 ;c=b ;b=c+a ;r=input('b= ')if r==bthen disp("bravo")elsedisp("perdu")end

On peut expérimenter en cliquant sur ce lien : qui vous permet d'exécuter le programmeQuelques remarques concernant ce premier source :

� on a�ecte à a la valeur 3, mais pour ne pas l'a�cher, on place un ; qui bloque l'a�chage.� on peut écrire disp('b=') ou disp("b=") sans conséquence sur le résultat qui a�chera le texte b= et invitera à entrerune valeur que l'on a�ectera à la variable b.

� si, dans le texte à a�cher, se trouve une apostrophe, autrement dit, si par exemple on veut a�cher le texte : voicicomment on obtient l'apostrophe, il su�t d'écrire disp('voici comment on obtient l�apostrophe') donc on met deux �

Mais le plus pratique est d'écrire un script dans l'éditeur de textes pour le compiler ensuite.Si on veut, par exemple, calculer le discrimant d'une équation du second degré, on crée une fonction que l'on nommediscri de la façon suivante :

function y=discri(a,b,c)y=b**2-4*a*cendfunction

qui, une fois déclarer, peut être appelée par la commande : discri(3, 4, 2).Remarque : si on place un ; à la �n de la ligne y = b ∗ ∗2− 4 ∗ a ∗ c, le résultat ne s'a�chera pas mais sera

en mémoire pour d'autres calculs

2.2 Boucles

Voici un algorithme qui a�che les n premiers entiers non nuls et calcule la somme de ces derniers, n étant donné enentrée.

Algorithm Somme des n premiers entiers non nulsVariable

n:nombre entier

Begin

Saisir le nombre n

somme← 0For i from 1 to n Do

Afficher i

somme←somme + i

EndFor

Afficher “la somme des n premiers entiers non nuls vaut somme“End

Ce qui suit est une proposition de programme source traduit en langage Scilab

n=input('entrer le nommbre d�entiers n= ')somme=0 ;for i=1 :nisomme = somme + i ;end,disp('la somme des n premiers entiers non nuls vaut '+string(somme))

On peut expérimenter en cliquant sur ce lien : qui vous permet d'exécuter le programme

2.3 an

Voici un algorithme qui calcule an, a et n étant donnés en entrée.

Algorithm an

Variable

n:nombre entier

a:nombre réel

aPuissancen:nombre réel

Begin

Saisir le nombre a

Saisir le nombre n

aPuissancen← 1For i from 1 to n Do

aPuissancen←aPuissancen ∗ a

EndFor

Afficher “le nombre an vaut aPuissancen“End


n=input('entrer l�exposant n= ')a=input('entrer le nombre a= ')aPuissancen=1 ;for i=1 :naPuissancen=aPuissancen*a ;end,disp('aPuissancen= '+string(aPuissancen))


2.4 SI...ALORS...SINON

Remarque : dans le premier exemple, vous avez pu découvrir une utilisation de cette instruction conditionnelle.Lancer d'une pièce équilibrée

Algorithm Fréquence d’apparition de "pile"Variable

n:nombre entier

Begin

Saisir le nombre n

nb←0For i from 1 to n Do

If rand()<0.5 Then

nb←nb + 1Endif

EndFor

s←nb/n

Afficher “la fréquence d’apparition de pile vaut s“End

n=input('entrer le nombre de lancers n= ')nb=0 ;for i=1 :nif rand() < 0.5 ;then nb = nb + 1 ;end,end,s=nb/n ;disp('la fréquence d�apparition de pile vaut '+string(s))

function s = frequencepile(n)nb=0 ;for i=1 :nif rand() < 0.5then nb = nb + 1 ;end,end,s=nb/n ;disp('la fréquence d�apparition de pile vaut '+string(s))endfunctionfrequencepile(1000)

On peut expérimenter en cliquant sur ce lien :qui vous permet d'exécuter le programme

Calculs sur un segment

Le segment [AB] est un segment de longueur 1. Aux deux nombres x et y tirés au hasard entre 0 et 1, on associe lespoints C et D de [AB] dé�nis par AC = min(x, y) et AD = max(x, y). Les points A, B et C et D étant donnés, lafonction doit retourner la longueur des trois segments [AC], [CD] et [DB] ainsi formés.

Algorithm Calculs dans un segmentVariable

Begin

x←rand()y←rand()If x<y Then

c←x

d←y

Else

c←y

d←x

Endif

f←1− d

e←d− c

Afficher “la distance AC vaut c“Afficher “la distance CD vaut e“Afficher “la distance DB vaut f“

End

et le source Scilab correspondant :

x=rand() ;y=rand() ;if x < ythen c = x ; d = y ;else c = y ; d = x ;end,disp('AC vaut '+string(c))disp('CD vaut '+string(d− c))disp('DB vaut '+string(1− d))


2.5 TANT QUE...

Premier exemple Algorithme d'Euclide.Voici deux traductions Scilab :

a=input("a=")b=input("b=")while b<>0 r=modulo(a,b) ;a=b ; b=r ; enddisp('le pgcd de a et b est '+string(a))

function r=euclide(a,b)while b<>0 r=modulo(a,b) ;a=b ; b=r ; enddisp('le pgcd de a et b est '+string(a))endfunctioneuclide(2345,5432)

On peut expérimenter en cliquant sur ce lien : qui vous permet d'exécuter le programmeExemple 2 : Comptage du nombre de lancers d'un dé pour obtenir l'ensemble des six faces.Cet exemple nous permettra d'introduire une liste.Il faut savoir que Scilab travaille avec des matrices et n'a donc aucune di�culté à gérer les listes.Voici un source :

// on crée une liste de 6 zérosl1=zeros(1,6) ;// on crée une liste (1 ;2 ;3 ;4 ;5 ;6)for i=1 :6l(i)=i ;endnb=0 ;// tant que la somme des éléments de la liste l est di�érente de 0while sum(l)<>0 do

// on lance le dé et on remplace le xième élément de l par 0x=tirage_entier(1,1,6) ;l(x)=0 ;nb=nb+1 ;enddisp('le nombre de lancers est '+string(nb))

On peut expérimenter en cliquant sur ce lien : qui vous permet d'exécuter le programmeRemarque : On peut désormais utiliser la fonction précédente pour estimer le nombre moyen de lancers nécessaire pourobtenir les six faces.

// on crée la fonction qui donne le nombre moyen de lancers en fonction de nfunction m=moyenne(n)// on initialise m à 0m=0 ;l1=zeros(1,6) ;// on crée une liste (1 ;2 ;3 ;4 ;5 ;6)for i=1 :6l(i)=i ;endnb=0 ;// tant que la somme des éléments de la liste l est di�érente de 0while sum(l)<>0 do

// on lance le dé et on remplace le xième élément de l par 0x=tirage_entier(1,1,6) ;l(x)=0 ;nb=nb+1 ;end// on ajoute les nombres de lancers nécessairesm=m+nb ;end,// on calcule la fréquence correspondantem=m/nendfunction// on fait la simulation 6000 foismoyenne(6000)


2.6 Inverses

Voici un algorithme qui calcule les inverses des n premiers entiers non nuls, n étant donné en entrée.

Algorithm n premiers inversesVariable

n:nombre entier

Begin

Saisir le nombre n

For i from 1 to n Do

x←1i

Afficher “l’inverse de i vaut x“EndFor

End


n=input('entrer le nombre d�inverses n=')for i=1 :ndisp('l�inverse de '+string(i))1/iend


2.7 Somme des n premiers inverses

Voici un algorithme qui calcule la somme des inverses des n premiers entiers non nuls, n étant donné en entrée.

Algorithm n premiers inversesVariable

n:nombre entier

somme:nombre réel

Begin

Saisir le nombre n

somme←0For i from 1 to n Do

somme←somme +1i

EndFor

Afficher “la somme des n premiers inverses vaut somme“End


n=input('entrer le nombre n= ')somme=0 ;for i=1 :nsomme=somme+1/i ;enddisp('la somme des inverses des premiers entiers vaut')disp(string(somme))


2.8 Image d'un réel par une fonction

Voici un algorithme qui donne en sortie l'image, si elle existe, d'un réel x donné en entrée par la fonction f : x 7→ 1x− 3

.

Algorithm image de x par f : x 7→ 1x− 3

Variable

x:nombre réel

y:nombre réel

Begin

Saisir le nombre x

If x = 3 Then

Afficher “le réel x = 3 n’a pas d’image par f“Else

y← 1x− 3

Afficher “l’image de x par la fonction f est y“Endif

End


x=input('lire le nombre x dont on cherche l�image par la fonction f')if x==3 then disp('x n�a ps d�image par la fonction f'),else y=1/(x-3) ;disp('f(x)='+string(y)) ;end


2.9 Second degré

Voici un algorithme qui donne les solutions réelles, si elles existent, de l'équation ax2 + bx + c = 0, a b et c étant troisréels donnés en entrée, a 6= 0.

Algorithm Résolution de ax2 + bx + c = 0 dans RVariable

a:nombre réel non nul

b:nombre réel

c:nombre réel

delta:nombre réel

x1:nombre réel

x2:nombre réel

Begin

Saisir les nombres a, b et c

delta←b2 − 4 ∗ a ∗ c

If delta < 0 Then

Afficher “l’équation n’admet pas de racine réelle“Else

If delta = 0 Then

x1←−b

2 ∗ aAfficher “l’équation admet une solution unique x1“

Else

x1←−b +

√delta

2 ∗ a

x2←−b−

√delta

2 ∗ aAfficher “ l’équation admet deux solutions réelles x1 et x2“

Endif

Endif

End


a=input('entrer la valeur de a= ')b=input('entrer la valeur de b= ')c=input('entrer la valeur de c= ')delta=b**2-4*a*c ;if delta<0 then disp('l�équation n'admet pas de solution réelle')elseif delta==0 then disp('l�équation admet une solution double '+string(-b/(2*a)))else disp('l�équation admet une première solution '+string((-b+sqrt(delta))/(2*a))),disp(' et une deuxième solution '+string((-b-sqrt(delta))/(2*a)))end


A l'exécution des di�érents programmes sources traduits en langage Scilab, on s'aperçoit quele logiciel donne des valeurs approchées des variables demandées. L'interprétation peut en êtrefaussée. Une traduction en langage Xcas, par exemple, donnera les valeurs exactes des variablesdemandées, puis éventuellement des valeurs approchées.

3 Langage Xcas

Voici un lien qui ouvre le logiciel Xcas et vous permet alors d'ouvrir des �chiers.xws qui mettent en scène les di�érentsalgorithmes exposés précédement. 1

Cliquez ici

1. Il vous su�t de mettre dans le dossier dans lequel se trouve le �chier ALGOetLANGAGES.pdf les di�érents sources Xcas fournis avec

le document. Il se peut que Xcas ne s'ouvre pas, il faudra alors placer dans le même dosser les �chiers qui se trouvent dans le dossier XCAS.

3.1 Lignes de commentaires

On peut expérimenter en cliquant sur ce lien : qui vous permet d'exécuter le programme 2

3.2 Somme des n premiers entiers non nuls


2. si le lien n'est pas valide, il vous su�t d'ouvrir Xcas pour accéder aux di�érents sources proposés en exemples

3.3 an


3.4 Nombre de pile et fréquence corresondante


3.5 Obtenir les six faces d'un dé


3.6 Longueurs de plusieurs segments dans [0 ;1]


3.7 pgcd


3.8 Calcul du discriminant


Documents

Algorithmique Groupe ALGO Lille