Réduction d'une boucle
Résolu
Ryuku
Messages postés
112
Date d'inscription
Statut
Membre
Dernière intervention
-
Ryuku Messages postés 112 Date d'inscription Statut Membre Dernière intervention -
Ryuku Messages postés 112 Date d'inscription Statut Membre Dernière intervention -
A voir également:
- Réduction d'une boucle
- Reduction taille image - Guide
- Meilleur site coupon réduction - Guide
- Reduction url - Guide
- Airpods 4 reduction de bruit avis - Accueil - Audio
- Boucle excel sans macro - Forum Excel
3 réponses
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 ^^.
Ryuku
Messages postés
112
Date d'inscription
Statut
Membre
Dernière intervention
24
Merci pour votre réponse, mais j'ai trouvé une solution.
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) :
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.
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.