Discussion :

[stanne]

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.

[transgohan]

Supprimes les affichages pour vérifier que la majorité du temps ne se passe pas en accès console.

Après tu peux optimiser l'accès au tableau en utilisant des pointeurs plutôt que des index.
Car à chaque fois que tu marques pile[choisidepart - choisi] tu parcours le tableau depuis l'index 0 à chaque fois.

[koala01]

Salut,

Après tu peux optimiser l'accès au tableau en utilisant des pointeurs plutôt que des index.
Car à chaque fois que tu marques pile[choisidepart - choisi] tu parcours le tableau depuis l'index 0 à chaque fois.

Non, malheureux!!!

Les tableaux donnent la certitude que les objets sont contigus en mémoire, et que l'adresse de chaque élément en mémoire est clairement connue.

Tu as donc une garantie d'accès en temps constant (il faut juste le temps de faire l'addition / la soustraction )

Les cas d'utilisation de pointeurs sont particulièrement limités en C++, et nous ne pourront jamais cautionner leur utilisation en dehors de ces quelques cas bien précis.

D'autant plus que là, tu proposes, en plus, d'utiliser l'arithmétique des pointeurs qui, bien que n'étant pas forcément difficile, reste néanmoins particulière

[CedricMocquillon]

ben y'a quand même une boucle (cf. parties en gras plus bas). Sinon +1 pour revoir l'algo et éviter la récursivité.

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
34
#include <iostream>
 
using namespace std;
 
int pile[100];
 
void fonction ( int nbrcours, int choisi , int debut, int choisidepart)
{
   if ( choisi != 0 ) 
   {
      int& elt = pile[choisidepart - choisi];
      for ( int k = debut ; k <= nbrcours ; k++ )
      {
         elt = k;
         fonction ( nbrcours , choisi - 1 , k + 1 , choisidepart);
         elt = 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);  
}

[Iradrille]

Hello,

Met ton code dans les balises [ code] ça sera plus simple à lire.

Sinon, évite la récursion si possible (utilise une stack par exemple) tu gagnera probablement pas mal.

Puis... essaye de revoir ton algo si possible, actuellement t'a une complexité en O(n!) (j'ai pas compris le problème, donc je sais pas si c'est possible)

edit:

Après tu peux optimiser l'accès au tableau en utilisant des pointeurs plutôt que des index.
Car à chaque fois que tu marques pile[choisidepart - choisi] tu parcours le tableau depuis l'index 0 à chaque fois.

pile[choisidepart - choisi] est équivalent à pile + (choisidepart - choisi)*sizeof(int) (à quelques casts près).
Il n'y à pas de parcours entier, on gagnerai juste une addition, une soustraction et une multiplication par itération si on stockait l'adresse de pile[choisidepart - choisi]. (?)

[transgohan]

edit:
pile[choisidepart - choisi] est équivalent à pile + (choisidepart - choisi)*sizeof(int) (à quelques casts près).
Il n'y à pas de parcours entier, on gagnerai juste une addition, une soustraction et une multiplication par itération si on stockait l'adresse de pile[choisidepart - choisi]. (?)

C'était en ce sens que je parlais de parcours. Ma formulation était mal choisie (partir de l'adresse pointée par 0 et la décaler de x = parcours / déplacement / ect).

Quand je parlais de supprimer les affichages c'était pour savoir si le temps d'affichage était prépondérant à ton traitement. Généralement on n'affiche que rarement, on traite les données.
Donc si à terme tu vas stocker les données au lieu de les afficher autant regarder tout de suite si cet affichage est ce qui te pose problème.

Tu peux aussi passer à une version non récursive de ton algo.

Et sinon une piste (que je n'ai pas lu) : http://www.developpez.net/forums/d1445/autres-langages/algorithmes/algo-trouver-arrangement-combinaison-delements/

[stanne]

Je ne comprends pas bien la phrase "supprimer les affichages". Pour les pointeurs, je viens de découvrir cette notion et je n'y suis pas du tout familier.
Cela permettrait de faire diminuer la compléxité de l'algorithme ?