Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

Algorithmes et structures de données Discussion :

[Récursivité] Recherche basique dans un tableau


Sujet :

Algorithmes et structures de données

  1. #1
    Membre à l'essai
    Homme Profil pro
    Auditeur informatique
    Inscrit en
    décembre 2014
    Messages
    17
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : Royaume-Uni

    Informations professionnelles :
    Activité : Auditeur informatique
    Secteur : Boutique - Magasin

    Informations forums :
    Inscription : décembre 2014
    Messages : 17
    Points : 14
    Points
    14
    Par défaut [Récursivité] Recherche basique dans un tableau
    Bonjour.
    J'ai beaucoup de mal avec la récursivité, et notamment la logique qu'il y a derrière. Je sais qu'en principe à chaque fois qu'on a une boucle on peut la remplacer par un appel à la fonction. Donc je me suis essayé à un exo simple, et très classique, recherche du maximum dans un tableau. Ici l'exemple classique d'une itération :
    Code Java : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    static void rechercheMax(int unTab []) {
    		int max = unTab[0];
     
    		for (int j = 0; j < unTab.length; j++) {
    			if (unTab[j] > max) {
    				max = unTab[j];
    			}
    		}
    		System.out.println("Le max est " + max);
     
    	}
    Rien d'exceptionnelle sous le soleil. Par contre là ou ça se corse sérieusement c'est la version récursive que j'ai fait :

    Code Java : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    static int rechercheMaxRec(int[] unTab, int j, int max) {
    		if (j < unTab.length-1) {
    			if (unTab[j] > max) {
    				max = unTab[j];
    				j++;
    				rechercheMaxRec(unTab, j, max);
    			}else {
    				j++;
    				rechercheMaxRec(unTab, j, max);
    			}
    		}
    		return max;
    	}
    Là où j'hallucine et c'est vraiment un truc de "fou" c'est qu'une fois arrivé à la fin de la boucle, le compteur repart dans le sens inverse. Honnêtement je ne comprends pas, et même pas du tout.
    Quand j'appelle ma fonction dans main elle se fait de la façon suivante
    Code Java : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
                   .....//il y a bien sur du code avant,
                    int unTab[] = { 7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 103, 10, 5, 16, 8, 4, 2, 1 };
    		System.out.println("Le max dans la recursive est " + rechercheMaxRec(unTab, 0,0));
    si parmi vous pouvez m'expliquer deux choses, pourquoi que ça ne donne pas le bon résultat, et pourquoi que ce foutu compteur repart dans l'autre sens, c'est un phénomène particulièrement angoissant, parce que ça montre que j'ai rien compris à la récursivité.
    Par avance merci.

  2. #2
    Expert éminent Avatar de Flodelarab
    Homme Profil pro
    Inscrit en
    septembre 2005
    Messages
    4 061
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Charente (Poitou Charente)

    Informations forums :
    Inscription : septembre 2005
    Messages : 4 061
    Points : 9 998
    Points
    9 998
    Par défaut
    Bonjour

    En voilà une série de bonnes questions.
    Quelques idées en vrac :

    • j < unTab.length-1 ? j < unTab.length ? j <= unTab.length-1 ?
    • Avec d'autres langages, on aurait imaginé un tableau toujours plus petit. Mais je comprends que tu n'aies pas envie de reconstruire un tableau plus petit à chaque fois avec ce langage. Alors, allons-y pour l'indice qui change.
    • Tu as bien pensé à une condition d'arrêt : quand j est maximum. Le maximum local est donc dans la valeur de la dernière case du tableau.
    • rechercheMaxRec(unTab, j, max); ? Ce serait pas plutôt return rechercheMaxRec(unTab, j, max); ? Comment veux-tu qu'elle change ? Ou max=rechercheMaxRec(unTab, j, max); ?
    • Perso, je ne comprends pas ta méthode. Le maximum du tableau est le maximum entre la case d'indice j et le maximum du reste du tableau. Et là ! C'est récursif !
      Code Java : Sélectionner tout - Visualiser dans une fenêtre à part
      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      int rechercheMaxRec(int[] unTab, int j) {
          if (j==unTab.length-1)
              return unTab[j];
          else 
          {
              reste=rechercheMaxRec(unTab, j+1);
              if (unTab[j]>reste)
                  return unTab[j];
              else
                  return reste;
          }
      }
    Cette réponse vous apporte quelque chose ? Cliquez sur en bas à droite du message.

  3. #3
    Rédacteur/Modérateur

    Homme Profil pro
    Ingénieur qualité méthodes
    Inscrit en
    décembre 2013
    Messages
    2 712
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Ingénieur qualité méthodes
    Secteur : Conseil

    Informations forums :
    Inscription : décembre 2013
    Messages : 2 712
    Points : 5 927
    Points
    5 927
    Par défaut
    Je réécris ta procédure, en changeant vraiment très peu de choses. Ça ne change rien sur le fond, ça va juste permettre de mieux voir ce qui se passe (enfin j'espère)

    Code Java : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    static int rechercheMaxRec(int[] unTab, int j, int max) {
                   time0 = date()
                   wait(10)
                   System.out.println ( "lancement de la procedure à " + time0  + " j vaut =" + j + " max vaut " + max )
    		if (j < unTab.length-1) {
    			if (unTab[j] > max) {
    				max = unTab[j];
                            }
    			j++;
    			rechercheMaxRec(unTab, j, max);
     
    		}
                    System.out.println ( "fin de la procedure lancée à " + time0 + " rappel, j vallait " + j  + " max vaut " + max )
    		return max;
    	}

    J'ai mis 2 fonctions à moi, il faudra probablement les traduire :
    date() : fonction qui renvoie date et heure ... pour qu'on voie bien le timing
    wait(10) : attendre 10 centièmes de seconde , sinon ça va aller tellement vite qu'on ne verra pas la différence entre les différents lancements de date().

    Ainsi tu devrais comprendre pourquoi j augmente de 1 a n, puis redescend de 1 à n.


    Dans ta procédure, tu as une instruction return. Tu es bien conscient que cette instruction ne sert à rien . Elle servirait uniquement si tu faisais X =rechercheMaxRec(unTab, j, max);.
    Et en l'occurrence, je pense que ta solution, c'est de faire max =rechercheMaxRec(unTab, j, max);.


    Une image pour illustrer le fonctionnement.
    Tu prends une feuille de papier, et tu écris sur cette feuille de papier les valeurs des différentes variables. Si il y a des opérations (j++) , tu barres la valeur de j, et tu mets la nouvelle valeur
    Quand tu as un appel à une fonction, tu prends une nouvelle feuille de papier, qui vient couvrir la feuille actuelle. Et tu écris sur cette nouvelle feuille ce qui se passe : les valeurs de j, de max etc etc.
    Quand tu as une instruction return, ou quand une procédure se finit, tu jettes la feuille qui était sur le dessus de la pile, et tu retournes donc sur la feuille qui était utilisée avant.
    Et tu peux dérouler tout ton programme comme ça.
    N'oubliez pas le bouton Résolu si vous avez obtenu une réponse à votre question.

  4. #4
    Membre confirmé

    Homme Profil pro
    Directeur de projet
    Inscrit en
    mai 2013
    Messages
    105
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Yvelines (Île de France)

    Informations professionnelles :
    Activité : Directeur de projet
    Secteur : Administration - Collectivité locale

    Informations forums :
    Inscription : mai 2013
    Messages : 105
    Points : 576
    Points
    576
    Par défaut Bornes et limites
    Bonjour,

    Je pense que la comparaison devrait être j < unTab.length et non j < unTab.length-1. Pour un tableau de n éléments le dernier indice est n-1 or avec j < n-1 le dernier indice est n-2.

    Si c'est une fonction, le code doit utiliser le retour de valeur. Par exemple :
    Code Java : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    static int rechercheMaxRec(int[] unTab, int j, int max) {
       if (j >= unTab.length) return max;
       if (unTab[j] > max) max = unTab[j];
       j++;
       return rechercheMaxRec(unTab, j, max);
    }

    Bien sûr, il faut appeler la fonction avec i = 0, max = 0x80000000 (en 32 bits).

    Ça devrait tomber en marche.

    Salutations
    Ever tried. Ever failed. No matter. Try Again. Fail again. Fail better. (Samuel Beckett)

  5. #5
    Membre à l'essai
    Homme Profil pro
    Auditeur informatique
    Inscrit en
    décembre 2014
    Messages
    17
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : Royaume-Uni

    Informations professionnelles :
    Activité : Auditeur informatique
    Secteur : Boutique - Magasin

    Informations forums :
    Inscription : décembre 2014
    Messages : 17
    Points : 14
    Points
    14
    Par défaut
    Messieurs -et Dames ? S'il y en a- je vous remercie tous pour vos réponses trés rapides. Honnetement, je n'attendais pas à réponses avant aujourd'hui. Je suis à la fois surpris, et content. J'en ai vu meme qui ont répondu le jour meme.
    Le problème a été effectivement résolu, en ajoutant à la fonction une valeur de retour. Malgrés tout ça, je ne vous cache pas que j'ai de gros problèmes à faire de la récurisivité. J'ai besoin de faire plus d'exercices, et pour cela je m'adresse à vous. Connaissez vous un bon site web, ou un livre qui me permettrait de m'exercer.
    En vous remerciant tous infiniment pour votre aide.

  6. #6
    Rédacteur

    Homme Profil pro
    Administrateur de base de données
    Inscrit en
    août 2013
    Messages
    399
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Oise (Picardie)

    Informations professionnelles :
    Activité : Administrateur de base de données
    Secteur : Finance

    Informations forums :
    Inscription : août 2013
    Messages : 399
    Points : 1 821
    Points
    1 821
    N'hésitez pas à consulter mon mémento sur la programmation en VBA pour EXCEL tome 1.
    Ou le tome 2 qui aborde la programmation en mode graphique avec un exemple de programmation d'un jeu d'arcade en VBA
    Et pour les curieux, le tome 3 qui aborde le problème du voyageur de commerce.
    Le tome 4 est consacré à la cryptologie en VBA et satisfera ceux qui ont besoin de confidentialité.
    Vous découvrirez dans le tome 5 les fonctions SQL pour gérer les tableaux de données et l'application Sentinelle qui veille sur vos fichiers.
    Le tome 6, dernier de la série, vous apprendra à créer des fonctions pour simplifier la vie des utilisateurs.
    Le Crible Quadratique donne toutes les fonctions pour les opérations sur les grands nombres en VBA.
    N'oubliez pas de consulter les FAQ EXCEL et les cours et tutoriels comme par exemple celui de Jean-Marc RABILLOUD qui est très complet.

+ Répondre à la discussion
Cette discussion est résolue.

Discussions similaires

  1. recherche optimisée dans un tableau
    Par h_adil dans le forum Macros et VBA Excel
    Réponses: 4
    Dernier message: 12/06/2008, 22h33
  2. Réponses: 6
    Dernier message: 28/06/2007, 12h17
  3. Recherche aléatoire dans un tableau
    Par Ykroxor dans le forum Excel
    Réponses: 1
    Dernier message: 11/04/2007, 10h58
  4. Réponses: 23
    Dernier message: 10/01/2006, 14h33
  5. Réponses: 6
    Dernier message: 05/01/2006, 15h23

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo