Bonjour à tous!
C'est mon premier message sur le forum et j'espère poster dans la bonne catégorie.
Je pose une question ici car j'ai un problème de temps d'éxécution sur un algorithme.
Je dois écrire un programme qui prends en entrée 2 entiers, nbr1 et nb2, et qui renvoie les arrangements possibles de ces deux entiers.
je m'exprime mal , donc voici un exemple:
Si nbr1 = 5 et nbr2 = 3,
on a en sortie :
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6
7
8
9
10
1 2 3 
1 2 4 
1 2 5 
1 3 4 
1 3 5 
1 4 5 
2 3 4 
2 3 5 
2 4 5 
3 4 5
Ou encore, si nbr1 = 4 et nbr2 = 3,
sortie :
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
1 2 3 
1 2 4 
1 3 4 
2 3 4
Les contraintes d'entrées sont 1 <= nbr1,nbr2 <= 100

J'ai écris un algorithme qui visiblement marche, mais est trop long au niveau du temps d'éxécution. ( temps minimal : 1,5 s sur une machine à 1GHz)

Voila mon algorithme :


Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <iostream>
 
using namespace std;
 
int pile[100];
 
void fonction ( int nbrcours, int choisi , int debut, int choisidepart)
{
   if ( choisi != 0 ) 
   {
      for ( int k = debut ; k <= nbrcours ; k++ )
      {
         pile[choisidepart - choisi] = k;
         fonction ( nbrcours , choisi - 1 , k + 1 , choisidepart);
         pile[choisidepart - choisi] = 0;
      }
   }
   else
   {
      for ( int k1 = 0 ; k1 < choisidepart ; k1++)
      {
         cout << pile[k1] << " ";
      }
      cout << '\n';
   }
}
 
int main()
{
   int nb1 , nb2;
   cin >> nb1 >> nb2;
   fonction ( nb1 , nb2 , 1 , nb2);  
}
Je n'ai aucune idée pour diminuer le temps d'éxécution, je vous demande donc votre aide, si vous avez une idée.. Merci d'avance

Stanne.