Réduction d'une boucle Résolu/Fermé

Question

Bonjour,

Voici mon problème :
soit nCk = n!/k!(n-k)! le nombre de combinaisons sans répétition.

je cherche tous les (n, k) qui vérifient nCk = a où a une constante donnée.

Moi j'ai fait une boucle pour les n de 0 à a qui contient une boucle de 0 à n pour les k :
 si nCk = a alors je sauvegarde (n,k).

Moi je cherche une méthode plus rapide.

xmoix · Answer

ah ! là... moi je suis pas matheux en tout cas, mais je peux toujours demander à mon prof d'info, lui il sait tout ce qui ressort des math ^^.

KX · Answer

Je pense qu'un petit rappel de théorie mathématiques s'impose...
Une propriété intéressante pour ton problème : k parmi n = (n-k) parmi n

On peut donc envisager de refaire une boucle mais en allant que jusqu'à n/2 puisqu'au delà on se retrouve à refaire les mêmes calculs (inutilement)

Après je ne sais pas en quel langage tu codes, mais l'idéal est d'utiliser des accumulateurs pour ne pas recalculer les factorielles à chaque fois...

Exemple en Pascal (je peux aussi te le faire en C/C++ ou Caml) :function Recherche(a,n:integer):integer; // renvoie -1 si échec
var k,x,y,z:integer; // x=n! y=k! z=(n-k)!
begin
     
     // cas particuliers

     if a<1 then begin
                 result:= -1;
                 exit;
                 end;

     if a=1 then begin
                 result:=0;
                 exit;
                 end;

     // calcul de n!

     x:=1;
     for k:=2 to n do
         x:=x*k;

     // calcul des (k|n)

     y:=1;
     z:=x;

     for k:=1 to (n div 2) do
     begin
         y:=y*k;
         z:=z div k;

         if a*y*z=x then begin
                         result:=k;
                         exit;
                         end;
     end;

     // résultat par défaut

     result:= -1;
end;

Ryuku · Answer

Salut, Vous avez raison en ce qui concerne la réduction de la boucle à n/2 itérations mais en réfléchissant bien j'ai trouvé cette solution (En Pascal Delphi) : function CmbPsbles(A : integer) : string; // Combinaisons possibles qui donnent A, résultat sous chaîne de caractères var N, K : integer; begin // pour A = 1 il existe une infinité de combinaisons. if A = 2 then // pour A = 2 le seul résultat est 2C1 Result := '2C1|' else begin Result := ''; N := 2; while nCk(N, 2) <= A do // on cherche inc(N); // le N qui vérifie nC2 <= A, car si ce N existe il ne doit satisfaire cette condition (preuve par le triangle de Pascal. dec(N); // revenir de 1 car on s'est arrêté à N + 1. if N <> A then // le cas de N = A est traité seul begin for K := 2 to N do // On cherche if nCk(N, K) = A then // le premier K qui vérifie break; // nCk = A if K < N then // pour vérifier que le N et le K existent réellement. begin Result := Result + IntToStr(N) + 'C' + IntToStr(K) + '|'; // le résultat nCk if K <> N / 2 then // si le K est égal vraiment à n / 2 alors on fait pas nCn-k Result := Result + IntToStr(N) + 'C' + IntToStr(N - K) + '|' // le résultat nCn-k end end; Result := Result + IntToStr(A) + 'C1|' + IntToStr(A) + 'C' + IntToStr(A - 1) + '|' // le cas de N = A donc le résultat est AC1 et ACA-1 end end; Merci.

Réduction d'une boucle

3 réponses

Discussions similaires