Décomposition d'un entier

Aplatir une liste:

Parfois il est utile de réduire un tableau contenant soit des tableaux soit des éléments, par un tableau simple ne contenant que des éléments.

// Fonction flatten:
function flatten(a,r){
    if(a.length == 0) return r;
    var cur= a.shift();
    cur instanceof Array && flatten(cur,r) || r.push(cur) ;
    return flatten( a, r);
}
flatten([1,3,4,[5,6]],[]);
// En évitant d'initialiser le tableau à []:

Décomposition d'un entier:

Savez vous combien de façons existe-t-il d'écrire une addition dont le résultat est 5 ?
[11111], [1112],[1,2,2],[3,2],[11,3],[1,4],[5] : 7

D'une façon général, utilisez la récursion pour calculer le nombre de façons d'écrire un nombre ?

Indice :
Pour écrire une addition dont la somme est n, à l'aide d'un entier inférieur à q, on peut écrire alors
n = q +(n-q) ;
Il y aura donc (n-q) décompositions possibles pour écrire les décompositions dont au moins un élément est de valeur q et les autres de valeur inférieure à q.
On peut également dire que pour avoir toutes les décompositions de n avec des éléments dont la valeur est inférieure à q; il faut rajouter toutes les décompositions de n avec un élément de valeur q-1;

On peut donc écrire
toutesDec(n,q)= toutesDec(n,q-1)+ toutesDec(n-q,q) ;
Par ailleurs,

• il n'existe qu'une décomposition de n avec q=1


• 0 décompositions avec q<=0 ou n<0 ;


• On suppose également qu'il n'y a qu'une décomposition de n=0 avec q>0 correspondant au cas de la décomposition de n par lui meme; exemple ttes Dec(0,5) = 1 car cela correspond au cas ou= toutesDec(n-q,q) ou n=q ,

Réponse:

function toutesDec(n,q){
 if(n==0) return 1;
 if(n<=0 || q<=0) return 0;
 if(q==1) return 1;
 return  toutesDec(n,q-1)+toutesDec(n-q, q)  ;
}

toutesDec( 12,12) ; //77  

On peut aller plus loin en écrivant ces décompositions:
Attention ne lisez pas tout de suite la solution... c'est quand même pas super simple !
Un truc important js n'est pas typé, donc pensez type à chaque retour de valeur, dans ma solution, chaque valeur retournée correspond à un tableau de tableaux ou plutôt une liste de listes.

// instructions de débuggage:
function clear(){document.body.innerHTML="";}
function d(m){ document.body.innerHTML += '
'+m.toString()+'
' ;} 

function toutesDec(n,q){
        if(n&tl;q) return toutesDec(n,n);
        if(n <= 0 || q <= 0 ) return [[]];
 if(q==1){
            var r= [];
            for(var i=0; i < n;i++) r.push(1);
             return [r];
        }
        var suite = toutesDec(n-q, q)  ;
        var listeb = map(suite, function(sousliste){ sousliste.push(q); return sousliste;}) ;                
        var listea = toutesDec(n,q-1)  ; 
        return listea.concat(listeb);

}
dolist= function(l,f ){ for(var i in l){ f(l[i]);} };
dolist(toutesDec( 10,4),d);

A vous d'inventer des problèmes plus compliqués encore, cette fonction est appelée "petite fonction de Ramanujan"
grand mathématicien du début du 20ème siècle.