Réduction d'une boucle

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 ^^.

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;

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.