IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
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 :

[Recursivite] function/procedure d'une suite logique


Sujet :

Algorithmes et structures de données

  1. #1
    Nouveau Candidat au Club
    Profil pro
    Inscrit en
    Mars 2005
    Messages
    3
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Mars 2005
    Messages : 3
    Points : 1
    Points
    1
    Par défaut [Recursivite] function/procedure d'une suite logique
    Bonjour,
    Je ne suis pas encore familier de ces boards, et j espere que je post au bon endroit (si c'est pas le cas je suis desole).

    ma suite est:
    1
    11
    21
    1211
    111221
    312211
    etc

    ex de construction de ligne: ligne 4 -> 1211. elle est constituee de un 1, un 2 et deux 1. donc la ligne 5 -> 111221.

    Je dois construire une function/procedure recursive qui renvoit les 10 1eres lignes.

    Si vous pouviez me donner une piste (faute de constuire tout le programme, car je concois tres bien que vous n'etes pas la pour faire mon boulot ). ca fait 1 semaine que je lutte sur cet exo, et la j'ai épuisé tout ce que je savais.

    Merci d'avance.




    ps: c'est un copie/colle de la section DELPHI, à priori c'est plus appropié ici.

  2. #2
    Rédacteur

    Inscrit en
    Septembre 2004
    Messages
    626
    Détails du profil
    Informations forums :
    Inscription : Septembre 2004
    Messages : 626
    Points : 848
    Points
    848
    Par défaut
    Je ne vois pas du tout comment le faire de manière récursive ? Peut-être en commencant par la fin ? C'est un peu forcé...

    Sinon pour moi, on part de "1".
    On parcourt la chaine en comptant le nb de caractères consécutifs identiques : ca nous donne 11.
    On recommence avec 11 comme tu l'as décrit. On dispose d'une fonction G qui effectue ce traitement.

    Si tu le veux de manière récursive : si on a une fonction F qui prend en entrée un indice n, rang de la chaine qu'on souhaite calculer.

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
     
    function F(n) {
       if n = 1 then 
          return 1;
       else
          tmp := F(n-1)
          return G(tmp);
       end if;
    end;
    Ca te convient ?


    Laly.
    In the heart of the truly greats, perfection is never achieved but endlessly pursued.

    Mon article sur les fonctions analytiques d'Oracle (calcul de moyennes mobiles, de quartiles et bien d'autres...)

  3. #3
    Nouveau Candidat au Club
    Profil pro
    Inscrit en
    Mars 2005
    Messages
    3
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Mars 2005
    Messages : 3
    Points : 1
    Points
    1
    Par défaut
    G(tmp) renvoie quoi pour n = 5 par exemple? je suis pas sur d'avoir tout saisi.

    c'est simple si tous les nombres de la chaine sont identiques, mais comme on peut avoir un '11121' je peux pas juste utiliser un F := F(n-1) meme avec du code derriere. parceke ca me sortirait un F (n) du type := '3121111211' et pas juste '311211'. j ai egalement tente d'utiliser du copy parcek on peut remarquer ke chaque fin du string fini par les 2 derniers caracteres du F(n-2). mais la encore j'arrive pas a grand chose pour le centre de la chaine.

    en bref comme ca doit se voir, je suis perdu

  4. #4
    Membre averti
    Profil pro
    Inscrit en
    Septembre 2003
    Messages
    298
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Septembre 2003
    Messages : 298
    Points : 318
    Points
    318
    Par défaut
    Ce qu'il faut savoir, c'est quel est le mécanisne pour obtenir la ligne n à partir de la ligne n-1, après ça, c'est tout simple à coder.

    Donc généraliser le mécanisne ci-dessous pour une ligne quelconque, il faut parcourir la chaine pour compter les nombre identiques et générer la ligne suivante.
    ex de construction de ligne: ligne 4 -> 1211. elle est constituee de un 1, un 2 et deux 1. donc la ligne 5 -> 111221.
    Il faut une routine de conversion ligne n-1 vers ligne n, et que tu passe aussi un parametre pour savoir si il faut encore transformer la chaine.

    En gros
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    funtion F(n: Cardinal; ligne: string):string;
    begin
        if n = 1 then // ou 0 à verifier (condition d'arrêt)
            result := ligne
        else
            // Mettre dans ligne la transformatation en ligne + 1.
            //...
           result := F(n - 1, ligne);
    end;

  5. #5
    Membre éprouvé Avatar de Nemerle
    Inscrit en
    Octobre 2003
    Messages
    1 106
    Détails du profil
    Informations personnelles :
    Âge : 53

    Informations forums :
    Inscription : Octobre 2003
    Messages : 1 106
    Points : 1 213
    Points
    1 213
    Par défaut
    Il te faut une fonction de transformation,

    qui a une chaine d'entiers "111221" représentant ta ligne associe la ligne suivante.

    Disons que ta chaine est dans c[0...n] ou n+1 est la longeur. Je te donne le code dans le cas ou tu n'as pas de chaine d'identiques de plus de 9 (pour plus, il suffit d'éclater ton nombre en chaine de chiffre grace à la partie entière du log base 10)

    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
     
    int val=c[0]
    int compteur=1
    int long=0
    int position=0
     
    while&#40;long<n&#41;&#123;
       long=long+1
       if&#40;c&#91;long&#93;<>val&#41;&#123;
          newc&#91;position&#93;=compteur
          newc&#91;position+1&#93;=val
          position=position+2
          val=c&#91;long&#93;
          compteur=1
       &#125;
       else&#123;
          compteur=compteur+1
       &#125;
    &#125;
    newc&#91;position&#93;=compteur
    newc&#91;position+1&#93;=val
    Nemerle, mathématicopilier de bars, membre du triumvirat du CSTM, 3/4 centre

  6. #6
    Futur Membre du Club
    Inscrit en
    Avril 2003
    Messages
    8
    Détails du profil
    Informations forums :
    Inscription : Avril 2003
    Messages : 8
    Points : 7
    Points
    7
    Par défaut
    salut,
    ton problème me fait triper donc je m'y met voilà une solution je te le met en algo français puis en java.



    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
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
     
     
    procedure recursive&#40; ligne_restante &#58; entier,//nombre de ligne qu'il reste à faire
    	ligne_precedente &#58; chaine de caratère, //la ligne précédente
    	resultat_suivant &#58; tableau de chaine de caratère&#41;//le tableau à remplir pour
    							//l'affichage,si on affiche directement 	
     
    						       //dans la procedure on peut enlever ce 		
     
    						      //paramètre
    debut
    	nombre_de_fois &#58; entier;//nombre de fois que le chifre est à la suite
    	le_caractete_tester &#58; caractere//le caractère que l'on test
    	compteur &#58; entier//pour savoir ou est la fin de la cahine
    	resultat &#58; chaine de caractete
     
    	//initialisation
    	nombre_de_fois = 0
    	compteur = 0 
    	resultat  = null
    	le_caractete_tester = ligne_precedente&#91;0&#93;//on prend le premier cara
     
    	//on remplis le tableau avec la ligne précédente ou on peut afficher directement&#40;dans
    	// ce cas on a pas besoin de resultat_suivant comme paramètre
    	resultat_suivant&#91;ligne_restante-1&#93; = ligne_precedente 
     
     
    	//on parcours toute la chaine
    	tant que compteur < ligne_precedente.longueur alors
    		si le_caractere_tester <> ligne_precedente&#91;compteur&#93; alors
    			resultat = resultat + nombre_de_fois + 						
     
    		le_caractere_a_tester
    			nombre_de_fois = 0
    		fin si
    		le_caractere_a_tester = ligne_precedente&#91;compteur&#93;
    		compteur = compteur+1
    		nombre_de_fois = 0
     
    	fin tant que
    	resultat = resultat + nombre_de_fois + le_caractere_a_tester
    	si ligne_restante <> 0 alors
    		recherche&#40; ligne_restante-1,resultat,resultat_suivant&#41;
    	finsi
    fin procedure
    utilisation de la procédure
    si on affiche directement dans la procedure on doit juste faire

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
     
    debut
    recursive&#40;10,'1'&#41;
    fin
    sinon il faut faire l'affichage
    afficher() représente une fonction pour afficher des chaine de cara
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
     
    debut
    affiche &#58; tableau de chaine de caratère
    recursive&#40;10,'1',affiche&#41;
    pour i de 0 à 9 faire
    afficher&#40;affiche&#91;i&#93;&#41;
    fin pour
    fin
    voila le code java
    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
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
     
     
    import java.util.*;
    public class Aide &#123;
     
    	//on affiche diretement dans la procedure
    	public static void recur_affiche&#40;
    		int ligne_restante,
    		String ligne_precedente&#41; &#123;
    		int nombre_de_fois;
    		String le_caractete_tester;
    		int compteur;
    		String resultat;
     
    		resultat = "";
    		nombre_de_fois = 0;
    		compteur = 0;
     
    		System.out.println&#40;ligne_precedente&#41;;
    		le_caractete_tester = ligne_precedente.charAt&#40;0&#41; + "";
    		while &#40;compteur < ligne_precedente.length&#40;&#41;&#41; &#123;
    			if &#40;le_caractete_tester
    				.compareTo&#40;ligne_precedente.charAt&#40;compteur&#41; + ""&#41;
    				!= 0&#41; &#123;
    				resultat = resultat + nombre_de_fois + le_caractete_tester;
    				nombre_de_fois = 0;
    			&#125;
    			nombre_de_fois = nombre_de_fois + 1;
    			le_caractete_tester = ligne_precedente.charAt&#40;compteur&#41; + "";
    			compteur = compteur + 1;
    		&#125;
    		resultat = resultat + nombre_de_fois + le_caractete_tester;
     
    		if &#40;ligne_restante > 1&#41; &#123;
    			recur_affiche&#40;ligne_restante - 1, resultat&#41;;
    		&#125;
    	&#125;
     
    	//on met les resultats dans un tableau qui sera afficher plus tard
    	public static void recur&#40;
    		int ligne_restante,
    		String ligne_precedente,
    		Vector resultat_suivant&#41; &#123;
    		int nombre_de_fois;
    		String le_caractete_tester;
    		int compteur;
    		String resultat;
     
    		resultat = "";
    		nombre_de_fois = 0;
    		compteur = 0;
     
    		resultat_suivant.add&#40;ligne_precedente&#41;;
    		le_caractete_tester = ligne_precedente.charAt&#40;0&#41; + "";
    		//on prend le premier cara
    		while &#40;compteur < ligne_precedente.length&#40;&#41;&#41; &#123;
    			if &#40;le_caractete_tester
    				.compareTo&#40;ligne_precedente.charAt&#40;compteur&#41; + ""&#41;
    				!= 0&#41; &#123;
    				resultat = resultat + nombre_de_fois + le_caractete_tester;
    				nombre_de_fois = 0;
    			&#125;
    			nombre_de_fois = nombre_de_fois + 1;
    			le_caractete_tester = ligne_precedente.charAt&#40;compteur&#41; + "";
    			compteur = compteur + 1;
    		&#125;
    		resultat = resultat + nombre_de_fois + le_caractete_tester;
     
    		if &#40;ligne_restante > 1&#41; &#123;
    			recur&#40;ligne_restante - 1, resultat, resultat_suivant&#41;;
    		&#125;
    	&#125;
     
    	public static void main&#40;String&#91;&#93; args&#41; &#123;
     
    		//utilisation de la procedure qui met le résultat dans un tableau
    		Vector affiche = new Vector&#40;&#41;;
    		Aide.recur&#40;10, "1", affiche&#41;;
    		for &#40;int i = 0; i <= 9; i++&#41; &#123;
    			System.out.println&#40;&#40;String&#41; affiche.elementAt&#40;i&#41;&#41;;
    		&#125;
     
    		//utilisation de la procédure qui affiche les résultats
    		recur_affiche&#40;10, "1"&#41;;
     
    	&#125;
    &#125;
    jespère que ça va te servir, dis moi si j'ai pas été clair
    @++

  7. #7
    Nouveau Candidat au Club
    Profil pro
    Inscrit en
    Mars 2005
    Messages
    3
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Mars 2005
    Messages : 3
    Points : 1
    Points
    1
    Par défaut
    tu m autorises a te mailer?

  8. #8
    Futur Membre du Club
    Inscrit en
    Avril 2003
    Messages
    8
    Détails du profil
    Informations forums :
    Inscription : Avril 2003
    Messages : 8
    Points : 7
    Points
    7
    Par défaut
    no pb,mon adresse est dispo sur mon profil si t'as besoin
    mais mes compétences se limitent à java et C(et C++ éventuellement).
    Je crois que toi c'est plutot delphi mais si je peu t'aider se serra avec plaisir.

Discussions similaires

  1. [XL-2007] Créer une suite logique dans un tableau filtré
    Par Archiviste dans le forum Excel
    Réponses: 6
    Dernier message: 30/09/2014, 00h40
  2. Réponses: 3
    Dernier message: 11/11/2010, 22h05
  3. [PL/SQL] appel d'une procedure dans une procedure
    Par Ilhan_ dans le forum Oracle
    Réponses: 9
    Dernier message: 28/01/2005, 11h30
  4. Réponses: 10
    Dernier message: 19/11/2004, 00h12
  5. Reprendre une procedure dans une autre ?
    Par Poisson Rouge dans le forum Langage
    Réponses: 3
    Dernier message: 17/07/2002, 23h51

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