Algorithmes fonctionnels en javascript sous la forme de cours et d'exercices. Utilisation de js dans un contexte de liste, de map, list_it. Inspiré de caml. A lire à l'envers...

lundi 8 septembre 2008

Tié puissant mon fils!

Paradigme diviser pour régner


Pour continuer sur la voie de la récursion et de l'algorithmique, une petite illustration du principe de Machiavel "Diviser pour régner" ou encore en anglais "Divide and Conquer"...
Comment calculer la puissance n de x ?
Je vois tout de suite les malins qui répondent qu'il y a une fonction toute prête x^n ! Oui mais comment peut-on le faire sans cette fonction.
Première solution, naïve :

var pow = function(x,n){ return n==1 && x || x * pow(n-1,x) ;}
pow(2,10);// 1024

Mais si on réfléchit, il faut faire n calculs pour obtenir le résultat, y a-t-il une solution pour effectuer moins de calculs?
Evidemment la solution c'est diviser pour régner..

var power = function(x,n){
if(n ==1 ) return x ;
if(n%2 ==0){
var powbis = power(x,n/2) ;
return powbis * powbis;
}
else{
var powpair = power(x, n-1) ;
return x * powpair
}
}

Dans cette solution pour faire:
power(2,10), on calcul d'abord power(2,5)* power(2,5) puis
power(2,5) est obtenu en calculant x*power(2,4) ;
power(2,4) est obtenu en calculant power(2,2) * power(2,2 ) ;
power(2,2) est obtenu en calculant power(2,1) * power(2,1) ;
On a donc effectué 5 calculs, là où la solution naïve aurait effectué 10 calculs.
D'accord, c'est pas un super génial, surtout pour le calcul de puissance qui pourrait être encore optimisé. Cette solution illustre le principe et montre qu'il ne faut pas se jeter immédiatement sur la solution naïve d'un problème. En pratique, utilisez l'opérateur ^, qui est probablement très optimisé.

Aucun commentaire: