Calcule nb de multiplication et complexité (algorithme)?

Signaler
-
yg_be
Messages postés
9406
Date d'inscription
lundi 9 juin 2008
Statut
Contributeur
Dernière intervention
26 janvier 2020
-
Fonction puiss (n,p:entier):entier;
var m:entier;
debut
si (p=0) alors
puiss<==1
sinon
si (p mod 2=0) alors
puiss<==puiss(n,p div 2)*puiss(n,p div 2);
fin_si
sinon
puiss<==n*puiss(n,p div 2)*puiss(n,p div 2);
fin_sinon;
fin_sinon;
fin_fonction;


Calculer le nombre minimal de multiplication noté Min(p) nécéssaire pour réaliser un
calcul à partir de cette fonction, donner sa complexité, sa nature!

Est-ce que qq1 peut m'aider avec la méthode? mon probleme ici c'est comme cette fonction est RECURSIVE , mrc d'avance

1 réponse

Messages postés
9406
Date d'inscription
lundi 9 juin 2008
Statut
Contributeur
Dernière intervention
26 janvier 2020
499
bonjour, moi je commencerais à déterminer Min(p) pour p= 0, 1, 2, 3, 4, 5, ...