"Divide and conquer" comment pourai je faire dans ce cas la ...

"Divide and conquer" comment pourai je faire dans ce cas la ... - Algo - Programmation

Marsh Posté le 08-04-2004 à 04:36:01    

:hello: ,
j ai un vecteur d entiers exemple :
1 2 3 4 5 6
 
je dois suivre cette methode :
prendre le milieu , action (ici inserer l element dans un arbre binaire ordone)
 
puis prendre le milieu de la partie gauche , action
puis prendre le milieu de la partie droite , action
ect ....
 
voila ce que jai fait

Code :
  1. void truc() {
  3.    vector <int> v;
  4.    //je remplie le vecteur
  5.    //et j appelle _truc(....) pour faire le boulot par recurence.
  6.    _truc(v, 0, v.size()-1);
  7. }
  8. void _truc (vector <int> v, int debut, int fin) {
  10.    if (debut != fin) {
  11. int milieu = (debut + fin)/2;
  12. //exemple de 0 a 5 -> 2 qui corespond a 3  
  13. //dansle vecteur ,  c est bon.
  15. _truc(v, debut, milieu);
  16. // cest la que je coince, si j appelle la fonction pour
  17. // la partie gauche la partie droite ne sera jamais traite :/
  19. _truc(v, milieu+1, fin);
  20. }


une idee ?  :sweat:
 
edit : condition d arret


Message édité par xiluoc le 08-04-2004 à 06:23:16
Reply

Marsh Posté le 08-04-2004 à 04:36:01   

Reply

Marsh Posté le 08-04-2004 à 04:52:12    

xiluoc a écrit :

:hello: ,
j ai un vecteur d entiers exemple :
1 2 3 4 5 6
 
je dois suivre cette methode :
prendre le milieu , action (ici inserer l element dans un arbre binaire ordone)
 
puis prendre le milieu de la partie gauche , action
puis prendre le milieu de la partie droite , action
ect ....
 
voila ce que jai fait

Code :
  1. void truc() {
  2.    vector <int> v;
  3.    //je remplie le vecteur
  4.    //et j appelle _truc(....) pour faire le boulot par recurence.
  5.    _truc(v, 0, v.size()-1);
  6. }
  7. void _truc (vector <int> v, int debut, int fin) {
  8. int milieu = (debut + fin)/2;
  9. //exemple de 0 a 5 -> 2 qui corespond a 3  
  10. //dansle vecteur ,  c est bon.
  12. _truc(v, debut, milieu);
  13. // cest la que je coince, si j appelle la fonction pour
  14. // la partie gauche la partie droite ne sera jamais traite :/
  16. _truc(v, milieu+1, fin);
  17. }


une idee ?  :sweat:


oui, une fonction quand on l'appelle, elle retourne, et la suite du code de l'appelante est exécutée.


---------------
trainoo.com, c'est fini
Reply

Marsh Posté le 08-04-2004 à 04:54:08    

per contre, c'est pas mal de mettre une condition d'arrêt de récursivité en début de fonction.


---------------
trainoo.com, c'est fini
Reply

Marsh Posté le 08-04-2004 à 06:01:05    

nraynaud a écrit :

per contre, c'est pas mal de mettre une condition d'arrêt de récursivité en début de fonction.


wewe jai oublier de mettre un truc genre begin = end tu stop
je pense utiliser un 3 ieme parametre bool, si c est vrai tu vas a gauche (puis bool= false)sinon tu vas a droite (puis bool=right)
je test ca

Reply

Marsh Posté le 08-04-2004 à 06:41:53    

c etait tout simple ...

Code :
  1. void btree::dividAndConquer( vector<int> v, int begin, int end)
  2. {
  3.     if (begin!=end) {
  4.         insert(v[(begin+end) /2]);
  5.         dividAndConquer(v, begin, (begin+end) /2);
  6.         dividAndConquer(v, ((begin+end) /2) +1, end);
  7.     }
  8. }

Reply

Sujets relatifs:

Leave a Replay

Make sure you enter the(*)required information where indicate.HTML code is not allowed