FORUM DE DISCUSSION SUR LE LANGAGE PANORAMIC

Développement d'applications avec le langage Panoramic
 
AccueilAccueil  FAQFAQ  RechercherRechercher  S'enregistrerS'enregistrer  MembresMembres  GroupesGroupes  Connexion  
Derniers sujets
» TourD Version 2
par Minibug Aujourd'hui à 1:50

» La métamatière et le peuple
par JL35 Hier à 21:18

» Capture d'une zone de l'écran total
par JL35 Hier à 18:41

» Logiciel de soutien scolaire en langues.
par Pedro Alvarez Hier à 11:49

» qui peut résoudre mon prb
par pascal10000 Jeu 16 Nov 2017 - 17:30

» évènements et objets système : listage automatique
par Jean Claude Jeu 16 Nov 2017 - 11:15

» Panoramic et la reconnaissance vocale.
par papydall Jeu 16 Nov 2017 - 3:45

» Bizzarerie dans Edge
par Marc 37 Mer 15 Nov 2017 - 17:45

» KGF_dll - nouvelles versions
par Klaus Mer 15 Nov 2017 - 2:08

» Analyser un code Panoramic
par JL35 Lun 13 Nov 2017 - 18:38

» Un bonjour en passant...
par Minibug Dim 12 Nov 2017 - 19:57

» mise a jour calculatrice
par joeeee2017 Dim 12 Nov 2017 - 4:20

» comment accèder à l'heure et à la date d'un fichier
par Klaus Sam 11 Nov 2017 - 0:53

» Compilateur FBPano
par Jicehel Mer 8 Nov 2017 - 15:22

» Mon adresse e-mail
par treehouse Mer 8 Nov 2017 - 14:36

Navigation
 Portail
 Index
 Membres
 Profil
 FAQ
 Rechercher
Rechercher
 
 

Résultats par :
 
Rechercher Recherche avancée
Novembre 2017
LunMarMerJeuVenSamDim
  12345
6789101112
13141516171819
20212223242526
27282930   
CalendrierCalendrier

Partagez | 
 

 Reflexion sur la récursivité

Voir le sujet précédent Voir le sujet suivant Aller en bas 
AuteurMessage
Nardo26

avatar

Nombre de messages : 2294
Age : 49
Localisation : Valence
Date d'inscription : 02/07/2010

MessageSujet: Reflexion sur la récursivité   Mar 30 Juin 2015 - 3:46

Hello !!
J'ouvre un nouveau topic pour ne pas pourrir l'excellentissime Interpreteur LOGO de Papydall.

Avec le langage LOGO, on arrive assez rapidement à des notions de récursivité.
Dans le cas de procédures simples, on arrive facilement à simuler des empilements d'appels à l'aide d'une DLIST.
Exemple:
Code:
rem ============================================================================
Init_Turtle()  : ' Indispensable
' Votre programme débute ici

Flocon_Koch()

caption 0,"terminé"
end

rem ============================================================================
SUB Flocon_Koch()
    dim_local i
    Position_XY(-200,100 )  : Turn_Right(90)
    while i < 3
         PUSH(4) :  Koch() : TURN_Right(120) : i = i + 1
    end_while
END_SUB

rem ============================================================================
SUB Koch()
    IF VARIABLE("iterations")=0 THEN DIM iterations
    IF EXIT_RECURSE=1 THEN EXIT_SUB
    POP(0) : iterations = POP_return
    if iterations = 0
        forward(5)
    else
        PUSH(iterations - 1) : Koch()
        Turn_Left(60)   : PUSH(iterations - 1) : Koch()
        Turn_right(120) : PUSH(iterations - 1) : Koch()
        Turn_Left(60)   : PUSH(iterations - 1) : Koch()
    end_if
    CLR() : POP(0): iterations = POP_RETURN
END_SUB


rem ============================================================================
rem   Spécifiques aux traitements récursifs
rem ============================================================================
SUB PUSH(v)
    IF VARIABLE("PILE")=0
        DIM PILE: PILE = NUMBER_OBJECTS + 1 : DLIST PILE
        DIM EXIT_RECURSE : EXIT_RECURSE=0
    END_IF
    ITEM_ADD PILE,v
    IF INKEY$<>"" THEN EXIT_RECURSE=1:CLEAR PILE: EXIT_SUB
    WAIT 1 : ' pour éviter de saturer l'UC
END_SUB

SUB POP(n)
  IF VARIABLE("POP_return")=0 THEN DIM POP_return
  IF COUNT(PILE) > n THEN POP_return=VAL(ITEM_READ$(PILE,COUNT(PILE)-n))
END_SUB

SUB CLR()
  IF COUNT(PILE)<>0 THEN ITEM_DELETE PILE,COUNT(PILE)
END_SUB


rem ============================================================================
'  !!!!!  LA COMMANDE A NE PAS OUBLIER      !!!!!
#Include "Include_Turtle.bas"
rem =========================== FIN ============================================
(pour le fichier Include_Turtle.bas, voir le lien en debut de topic)
Jusque là, tout se passait bien.  cheers

Puis j'ai voulu reprendre l'exemple de Klaus pour la factorielle en utilisant les procédures PUSH(), POP() et CLR().

J'ai pris volontairement le cas de la factorielle car il est simple à "visualiser".
Pseudo-code:
Code:
factorielle (entier n)
début
  si (n = 1) alors
    retourne 1;
  sinon
    retourne n* factorielle(n-1);
  finsi
fin

Il est clair que l'on peut écrire de manière plus simple celle-ci. Mais c'est juste un exemple...

Badaboum : plus rien ne marche !
Dans le cas de la factorielle, on est obligé d'utiliser des variables locales (variable n pour la multiplication).
Or comme pour les appels, des déclarations de DIM_LOCAL doivent être aussi empilés à leur tour : faire plusieurs déclarations successives de Dim locaux, Panoramic n'aime pas du tout !

Une solution : procéder de la même manière pour les variables locales (utilisation de DLIST)
Cela commence à être de la haute voltige.

Cela donne ceci :
Code:

PUSH(7):Factorielle()
MESSAGE "7! = "+ STR$(Factorielle_return)
END

SUB Factorielle()
  IF VARIABLE("Factorielle_return") = 0 THEN DIM Factorielle_return
  POP(0): ' On recupere le parametre d'entrée
  PUSH_VAR(POP_return)  : ' on stocke ce paramètre dans un "DIM" local
  IF POP_return=1
    Factorielle_return = 1
  ELSE
    PUSH(POP_return-1):Factorielle()
  END_IF
  POP_VAR(0):CLR_VAR() : ' on récupère notre variable "locale" et on la libère (FREE)
  Factorielle_return = Factorielle_return * POPVAR_return
  CLR()
END_SUB

rem ============================================================================
rem   Spécifiques aux traitements récursifs
rem ============================================================================
SUB PUSH_VAR(v)
    IF VARIABLE("VARLOC")=0 THEN DIM VARLOC:VARLOC = NUMBER_OBJECTS + 1 : DLIST VARLOC
    ITEM_ADD VARLOC,v
END_SUB

SUB POP_VAR(n)
  IF VARIABLE("POPVAR_return")=0 THEN DIM POPVAR_return
  IF COUNT(VARLOC)>n THEN POPVAR_return=VAL(ITEM_READ$(VARLOC,COUNT(VARLOC)-n))
END_SUB

SUB CLR_VAR()
  IF COUNT(VARLOC)<>0 THEN ITEM_DELETE VARLOC,COUNT(VARLOC)
END_SUB

SUB PUSH(v)
    IF VARIABLE("PILE")=0
        DIM PILE: PILE = NUMBER_OBJECTS + 1 : DLIST PILE
        DIM EXIT_RECURSE : EXIT_RECURSE=0
    END_IF
    ITEM_ADD PILE,v
    IF INKEY$<>"" THEN EXIT_RECURSE=1:CLEAR PILE: EXIT_SUB
    WAIT 1 : ' pour éviter de saturer l'UC
END_SUB

SUB POP(n)
  IF VARIABLE("POP_return")=0 THEN DIM POP_return
  IF COUNT(PILE)>n THEN POP_return=VAL(ITEM_READ$(PILE,COUNT(PILE)-n))
END_SUB

SUB CLR()
  IF COUNT(PILE)<>0 THEN ITEM_DELETE PILE,COUNT(PILE)
END_SUB


Le but c'est d'arriver à pouvoir mettre en place un système suffisamment assez clair et lisible pour pouvoir être utilisé par la suite pour des procédures beaucoup plus complexes...

Pour l'instant, je ne regarde que le cas des variables locales...   study
pour la valeur de retour, j'utilise encore une variable globale et je pense que cela ne va pas être simple non plus (cf le cas du 1er appel)

Quelqu'un est intéressé par l'aventure ? Des avis ?
Revenir en haut Aller en bas
Voir le profil de l'utilisateur http://nardo26.lescigales.org
papydall

avatar

Nombre de messages : 5587
Age : 67
Localisation : Moknine (Tunisie) Entre la chaise et le clavier
Date d'inscription : 03/03/2012

MessageSujet: Re: Reflexion sur la récursivité   Mar 30 Juin 2015 - 5:51

Hello Nardo twenty six

C’est intéressant ce que tu proposes.
Jusque-là, les procédures ne nécessitaient qu’un seul paramètre : Le flocon, l’arbre ou la factorielle.
Mais comment doit-on s’y prendre pour les procédures avec un nombre de paramètres plus important ?

Voici  une procédure récursive du problème de la tour de Hanoï
Code:

rem ============================================================================
rem               Résolution du problème des Tours de HANOI
rem               Déplacer n disques de la tour A à la tour C
rem               en utilisant la tour B comme intermédiaire
rem Le nombre minimum nécessaire de déplacements pour N disques est : 2^N - 1
rem ============================================================================
rem ############################################################################
rem ATTENTION :
rem NE FONCTIONNE QUE AVEC LE COMPILATEUR, PAS AVEC L INTERPRETEUR
rem ############################################################################
dim n : ' nombre de disques
dim i : ' compteur du nombre de déplacements
dim t$
height 0,700
caption 0,"Les Tours de Hanoï  /  Résolution récursive"
n = 5 : ' exemple
t$ = " Nombre de déplacements nécessaires pour résoudre ce problème avec "
t$ = t$ + str$(n) + " disques " + " = " + str$(power(2,n)-1)
print  t$ : print
hanoi(n,"A","B","C")

end
rem ============================================================================
' Procédure récursive
SUB Hanoi(n,depart$,intermediaire$,arrivee$)
    if n > 0  : ' test du point d'arrêt
       hanoi(n-1,depart$,arrivee$,intermediaire$) : ' 1er appel récursif avec changement des paramètres
       i = i + 1 : ' incrémentation du nombre de déplacements
       print "Déplacement N° " + str$(i) + ": deplacer de " + depart$ +" à " + arrivee$
       hanoi(n-1,intermediaire$,depart$,arrivee$) : ' 2ème appel récursif avec changement des paramètres
    end_if
end_sub
rem ============================================================================

Cette procédure nécessite quatre paramètres.
Je pense qu’il faille utiliser quatre piles : j’ai essayé et c’est l’échec complet.

J’ai exécuté ce code avec le compilateur et le résultat est vite trouvé.

Code:

Nombre de déplacements nécessaires pour résoudre ce problème avec 5 disques  = 31

Déplacement N° 1: deplacer de A à C
Déplacement N° 2: deplacer de A à B
Déplacement N° 3: deplacer de C à B
Déplacement N° 4: deplacer de A à C
Déplacement N° 5: deplacer de B à A
Déplacement N° 6: deplacer de B à C
Déplacement N° 7: deplacer de A à C
Déplacement N° 8: deplacer de A à B
Déplacement N° 9: deplacer de C à B
Déplacement N° 10: deplacer de C à A
Déplacement N° 11: deplacer de B à A
Déplacement N° 12: deplacer de C à B
Déplacement N° 13: deplacer de A à C
Déplacement N° 14: deplacer de A à B
Déplacement N° 15: deplacer de C à B
Déplacement N° 16: deplacer de A à C
Déplacement N° 17: deplacer de B à A
Déplacement N° 18: deplacer de B à C
Déplacement N° 19: deplacer de A à C
Déplacement N° 20: deplacer de B à A
Déplacement N° 21: deplacer de C à B
Déplacement N° 22: deplacer de C à A
Déplacement N° 23: deplacer de B à A
Déplacement N° 24: deplacer de B à C
Déplacement N° 25: deplacer de A à C
Déplacement N° 26: deplacer de A à B
Déplacement N° 27: deplacer de C à B
Déplacement N° 28: deplacer de A à C
Déplacement N° 29: deplacer de B à A
Déplacement N° 30: deplacer de B à C
Déplacement N° 31: deplacer de A à C
Revenir en haut Aller en bas
Voir le profil de l'utilisateur http://papydall-panoramic.forumarabia.com/
silverman

avatar

Nombre de messages : 469
Age : 45
Localisation : Picardie
Date d'inscription : 19/03/2015

MessageSujet: Re: Reflexion sur la récursivité   Mar 30 Juin 2015 - 13:23

Bonjour panoramiciens!

@Nardo26
l'aventure m'interesse! J'aime faire bouillir mes ptites cellulles grises Very Happy

Je me suis attaqué à la tour de Hanoi direct, même pas peur. Cool
Précaution à prendre, tous ce qui a été empilé doit être dépilé, comme en assembleur(que j'ai pratiqué au siècle dernier  lol! ).


la tour de Hanoï pour l'interpréteur:
Code:


rem ============================================================================
rem               Résolution du problème des Tours de HANOI
rem               Déplacer n disques de la tour A à la tour C
rem               en utilisant la tour B comme intermédiaire
rem Le nombre minimum nécessaire de déplacements pour N disques est : 2^N - 1
rem ============================================================================
rem ############################################################################
rem
rem FONCTIONNE AVEC L`INTERPRETEUR
rem
rem ############################################################################
dim n : ' nombre de disques
dim i : ' compteur du nombre de déplacements
dim t$

' pour creer une pile de données:
dim stack$
dlist 10

height 0,700
caption 0,"Les Tours de Hanoï  /  Résolution récursive"
n = 5 : ' exemple
t$ = " Nombre de déplacements nécessaires pour résoudre ce problème avec "
t$ = t$ + str$(n) + " disques " + " = " + str$(power(2,n)-1)
print  t$ : print
hanoi(n,"A","B","C")

end
rem ============================================================================
' Procédure récursive
SUB Hanoi(n,depart$,intermediaire$,arrivee$)
' Tant qu'on ENTRE dans la sub, les variables locales SONT CREES, mais PAS DETRUITES. Il faut
' éviter la recréation, sinon panoramic retourne une erreur
 if variable("nn")=0
    dim_local nn,dd$,ii$,aa$
 end_if
 nn=n
 dd$=depart$
 ii$=intermediaire$
 aa$=arrivee$
 
    if n > 0  : ' test du point d'arrêt
       push(str$(nn))
       push(dd$)
       push(ii$)
       push(aa$)   :' Attention, dernière variable empilée(sur la pile de données), donc...
      
       hanoi(nn-1,dd$,aa$,ii$) : ' 1er appel récursif avec changement des paramètres
       ' On SORT de la sub, à partir d'ici, toutes les variables locales ont ETE DETRUITES, il faut les recréer!
       dim_local nn,dd$,ii$,aa$
       pop() : aa$=stack$   :' c'est la première à être dépilée!
       pop() : ii$=stack$
       pop() : dd$=stack$
       pop() : nn=val(stack$)

       i = i + 1 : ' incrémentation du nombre de déplacements
      
       push(str$(nn))
       push(dd$)
       push(ii$)
       push(aa$)

       print "Déplacement N° " + str$(i) + ": deplacer de " + dd$ +" à " + aa$
       hanoi(nn-1,ii$,dd$,aa$) : ' 2ème appel récursif avec changement des paramètres

       dim_local nn,dd$,ii$,aa$
       pop() : aa$=stack$
       pop() : ii$=stack$
       pop() : dd$=stack$
       pop() : nn=val(stack$)
    end_if
end_sub
rem ============================================================================


sub push(value$)
   item_add 10,value$
end_sub


sub pop()
      stack$=item_read$(10,count(10))
      item_delete 10,count(10)
end_sub


@papydall
Une seule pile à suffit, il faut juste être rigoureux dans sa gestion. Par contre, il faut utiliser une pile par sub je pense.
Revenir en haut Aller en bas
Voir le profil de l'utilisateur
Nardo26

avatar

Nombre de messages : 2294
Age : 49
Localisation : Valence
Date d'inscription : 02/07/2010

MessageSujet: Re: Reflexion sur la récursivité   Mar 30 Juin 2015 - 13:35

Bravo Silverman !
Oui, c'est bête cette histoire de dim_local et ta solution est nickel !
La redéclaration et le test au début sont logiques après coup.

J'ignorai que la cde VARIABLE() fonctionnait pour les "locales"
C'est bon à savoir !

Il y a encore un truc qui pourrait être amélioré dans ta version :
C'est pas bien beau cette variable globale (i) qui traine dans la procédure.
Revenir en haut Aller en bas
Voir le profil de l'utilisateur http://nardo26.lescigales.org
silverman

avatar

Nombre de messages : 469
Age : 45
Localisation : Picardie
Date d'inscription : 19/03/2015

MessageSujet: Re: Reflexion sur la récursivité   Mar 30 Juin 2015 - 14:41

Nardo26 a écrit:
C'est pas bien beau cette variable globale (i) qui traine
Je n'ai fait que "traduire" le code de papydall, c'est pas moi! tongue

Je suis passé par des variables locales à cause d'un méchant bug avec les subs; le résultat est carrement improbable.
Voici ce que retourne mon code de test:
a=5 b=10 c=15 d=20
a=10 b=10 c=20 d=20
a=10 b=10 c=20 d=20
a=10 b=10 c=20 d=20
a=10 b=10 c=20 d=20
...

et le code de test en question
Code:


' BUG des subs

dim fin


test(5,10,15,20)

end
sub test(a,b,c,d)
fin=fin+1 :' sécurité pour éviter une infinité de subs
if fin>10 then exit_sub


   print "a=";a;"   b=";b;"   c=";c;"   d=";d
   test(b,a,d,c)
      
end_sub


sinon, pour la factorielle c'est plus simple, pas besoin d'une pile:
Code:


' Panoramic_editor 0.9.25
'
' Exemple de récursion


dim factorielle
dim nb


 nb=5
 Factorielle(nb)
 print "factorielle(";nb;")=";factorielle

 print

 nb=3
 Factorielle(nb)
 print "factorielle(";nb;")=";factorielle


end
sub Factorielle(n)
'
 if variable("null")=0
    ' astuce pour initialiser une variable globale dans une procédure RECURSIVE:
    ' ---> on passe par la création d'une variable locale qui ne sert à rien
    dim_local null
    ' ainsi, la variable globale est automatiquement mise à 1 à chaque nouvel appel de la sub
    factorielle=1
 end_if

   if n>0
      factorielle=factorielle*n
      Factorielle(n-1)
   end_if
   '
end_sub
Revenir en haut Aller en bas
Voir le profil de l'utilisateur
Nardo26

avatar

Nombre de messages : 2294
Age : 49
Localisation : Valence
Date d'inscription : 02/07/2010

MessageSujet: Re: Reflexion sur la récursivité   Mar 30 Juin 2015 - 16:07

silverman a écrit:
Je suis passé par des variables locales à cause d'un méchant bug avec les subs; le résultat est carrement improbable.
Oui j'avais constaté cela aussi... c'est un peu pour cette raison que j'avais commencé à ne plus utilisé au départ le passage de paramètre et les DIM_LOCAUX.
Exemple:
Code:

DIM Niv$
Roll(1,8,12)
END

SUB Roll(a,b,c)
  Niv$=Niv$+"    "
  PRINT Niv$+"Entrée dans Roll(a:";a;", b:";b;", c:";c;")"
  IF a<>MAX(MAX(a,b),c)
    PRINT Niv$+"> Appel à Roll(b:";b;", c:";c;", a:";a;")"
    Roll(b,c,a)
  END_IF
  PRINT Niv$+"Sortie"
  Niv$=LEFT$(Niv$,LEN(Niv$)-4)
END_SUB
Je m'attendais à avoir :
Code:
   Entrée dans Roll(a:1, b:8, c:12)
    > Appel à Roll(a:8, b:12, c:1)
        Entrée dans Roll(a:8, b:12, c:1)
        > Appel à Roll(a:12, b:1, c:8)
            Entrée dans Roll(a:12, b:1, c:8)
            Sortie
        Sortie
    Sortie

Il semble que les paramètres passés aux procédures ne sont pas stockées dans une pile.
Dans le cas de la factorielle ou du flocon de Koch, le pb est masqué puisqu'il n'y a qu'un seul paramètre.

C'est bien pour cette raison que tu push() les dim_locaux, non ?  Wink


silverman a écrit:
sinon, pour la factorielle c'est plus simple, pas besoin d'une pile
Oui et pas besoin de récursion non plus. La méthode itérative reste simple...

C'était juste un exemple pour faciliter le sujet.
Si tu veux, je peut te passer une procédure de reéquilibrage d'un arbre AVL (cf mon site) lol ! Laughing
D'ailleurs, il va falloir que je dépoussière ce code... drunken
Revenir en haut Aller en bas
Voir le profil de l'utilisateur http://nardo26.lescigales.org
papydall

avatar

Nombre de messages : 5587
Age : 67
Localisation : Moknine (Tunisie) Entre la chaise et le clavier
Date d'inscription : 03/03/2012

MessageSujet: Re: Reflexion sur la récursivité   Mar 30 Juin 2015 - 17:34

Silverman a écrit:
l'aventure m'interesse! J'aime faire bouillir mes ptites cellulles grises

En tout cas, bravo pour la solution et surtout n'arrête pas de faire bouillir tes cellules grises : car il ne peut qu'en sortir des idées géniales!

Nardo26 a écrit:
Il y a encore un truc qui pourrait être amélioré dans ta version :
C'est pas bien beau cette variable globale (i) qui traine dans la procédure.  

Cette variable globale n’a qu’un seul rôle pour le comptage des coups, sans plus.
Bon, pour le beauté, on peut la virer et aussi simplifier l’affichage.

Code:

rem ============================================================================
rem              Résolution du problème des Tours de HANOI
rem              Déplacer n disques de la tour A à la tour C
rem              en utilisant la tour B comme intermédiaire
rem Le nombre minimum nécessaire de déplacements pour N disques est : 2^N - 1
rem ============================================================================
rem ############################################################################
rem
rem FONCTIONNE AVEC L`INTERPRETEUR
rem
rem ############################################################################
dim n : ' nombre de disques
dim i : ' compteur du nombre de déplacements
dim t$

' pour creer une pile de données:
dim stack$
dlist 10

height 0,700
caption 0,"Les Tours de Hanoï  /  Résolution récursive"
n = 5 : ' exemple
t$ = " Nombre de déplacements nécessaires pour résoudre ce problème avec "
t$ = t$ + str$(n) + " disques " + " = " + str$(power(2,n)-1)
print  t$ : print
hanoi(n,"A","B","C")

end
rem ============================================================================
' Procédure récursive
SUB Hanoi(n,depart$,intermediaire$,arrivee$)
' Tant qu'on ENTRE dans la sub, les variables locales SONT CREES, mais PAS DETRUITES. Il faut
' éviter la recréation, sinon panoramic retourne une erreur
 if variable("nn")=0
    dim_local nn,dd$,ii$,aa$
 end_if
 nn=n
 dd$=depart$
 ii$=intermediaire$
 aa$=arrivee$

    if n > 0  : ' test du point d'arrêt
      push(str$(nn))
      push(dd$)
      push(ii$)
      push(aa$)  :' Attention, dernière variable empilée(sur la pile de données), donc...

      hanoi(nn-1,dd$,aa$,ii$) : ' 1er appel récursif avec changement des paramètres
      ' On SORT de la sub, à partir d'ici, toutes les variables locales ont ETE DETRUITES, il faut les recréer!
      dim_local nn,dd$,ii$,aa$
      pop() : aa$=stack$  :' c'est la première à être dépilée!
      pop() : ii$=stack$
      pop() : dd$=stack$
      pop() : nn=val(stack$)

  '    i = i + 1 : ' incrémentation du nombre de déplacements

      push(str$(nn))
      push(dd$)
      push(ii$)
      push(aa$)

  '    print "Déplacement N° " + str$(i) + ": deplacer de " + dd$ +" à " + aa$
      print dd$ + " ---> " + aa$
      hanoi(nn-1,ii$,dd$,aa$) : ' 2ème appel récursif avec changement des paramètres

      dim_local nn,dd$,ii$,aa$
      pop() : aa$=stack$
      pop() : ii$=stack$
      pop() : dd$=stack$
      pop() : nn=val(stack$)
    end_if
end_sub
rem ============================================================================
' Silverman

sub push(value$)
  item_add 10,value$
end_sub
' ==============================================================================

sub pop()
      stack$=item_read$(10,count(10))
      item_delete 10,count(10)
end_sub
rem ============================================================================
Revenir en haut Aller en bas
Voir le profil de l'utilisateur http://papydall-panoramic.forumarabia.com/
silverman

avatar

Nombre de messages : 469
Age : 45
Localisation : Picardie
Date d'inscription : 19/03/2015

MessageSujet: Re: Reflexion sur la récursivité   Mar 30 Juin 2015 - 20:36

Nardo26 a écrit:
C'est bien pour cette raison que tu push() les dim_locaux, non ?
Exact!

Un autre exemple classique de récursivité, le tri. Je sais que Panoramic possède une fonction de tri, mais là, c'est juste pour rester dans le thème.

Algorithme QuickSort:
Code:

'
'
' Tri par récursion : Qsort
'
'
' Panoramic 0.9.25


' nb maximum de valeurs à trier
dim maxvalue
maxvalue=20
dim triage(maxvalue)
dim k

' la pile de données
dim stack$
dlist 10



' fabrique une suite de nombres et l'affiche
for k=0 to maxvalue
   triage(k)=int(rnd(100))
   print triage(k);" ";
next k
print : print

' le tri en action
 Qsort_d(0,maxvalue)

' affiche le résultat
for k=0 to maxvalue
   print triage(k);" ";
next k



END
sub Qsort_d(mini,maxi)
if variable("i")=0
   dim_local mini_local,maxi_local,x,tmp   :' variables ponctuelles
   dim_local i,j   :' variables qui ont besoin d'être sauvegardées
end_if

i=mini:j=maxi
x=triage(int((i+j)/2))

REPEAT
   WHILE triage(i)<x:i=i+1:END_WHILE
   WHILE triage(j)>x:j=j-1:END_WHILE
   IF i<=j
      tmp=triage(i)
      triage(i)=triage(j)
      triage(j)=tmp
      rem
      i=i+1
      j=j-1
   END_IF
UNTIL i>j


IF j>mini
' On va transmettre soit: mini/j, soit i/maxi
' Donc, il faut sauvegarder(empiler) ces 4 variables
   push(str$(mini))
   push(str$(maxi))
   push(str$(i))
   push(str$(j))

   ' Bonne habitude pour la récursion:
   mini_local=mini   :' on ne transmet à la sub que des variables locales, sinon --->BUG
   Qsort_d(mini_local,j)
   ' Qsort_d(mini,j)

   ' Au retour mini la sub, toutes les variables locales ont été détruites
   ' il faut les recréer et réinitialiser celles dont on à besoin
   dim_local mini_local,maxi_local,x,tmp
   dim_local i,j
   pop() : j=val(stack$)
   pop() : i=val(stack$)
   pop() : maxi=val(stack$)
   pop() : mini=val(stack$)
end_if


IF i<maxi
' on va transmettre soit: mini/j, soit i/maxi
' il faut sauvegarder(empiler) ces 4 variables
   push(str$(mini))
   push(str$(maxi))
   push(str$(i))
   push(str$(j))
  
   ' Bonne habitude pour la récursion:
   maxi_local=maxi   :' on ne transmet à la sub que des variables locales, sinon --->BUG
   Qsort_d(i,maxi_local)
   ' Qsort_d(i,maxi)
  
   ' Au retour mini la sub, toutes les variables locales ont été détruites
   ' il faut les recréer et réinitialiser celles dont on à besoin
   dim_local mini_local,maxi_local,x,tmp
   dim_local i,j
   pop() : j=val(stack$)
   pop() : i=val(stack$)
   pop() : maxi=val(stack$)
   pop() : mini=val(stack$)
end_if

END_SUB



sub push(value$)
   item_add 10,value$
end_sub


sub pop()
      stack$=item_read$(10,count(10))
      item_delete 10,count(10)
end_sub
Revenir en haut Aller en bas
Voir le profil de l'utilisateur
Jicehel

avatar

Nombre de messages : 5859
Age : 45
Localisation : 77500
Date d'inscription : 19/04/2011

MessageSujet: Re: Reflexion sur la récursivité   Mar 30 Juin 2015 - 23:05

Si vous voulez-vous amuser en vous triturant les méninges vous pouvez plancher sur l'évaluation du meilleur coup dans un jeu de dans en utilisant l'algorithme min max. On peut utiliser le principe des arbres de Nardo et l'évaluation des coups pour calculer sur un certain nombres de coups à l'avance ( 3 à 5 ). C'est un très bon exercice, j'avais commencé à bosser dessus mais j'avais capitulé car moi, je m'étais perdu dans le dév... Je n'ai même pas gardé cette version.
Je ne sais pas si ce défit intéressera quelqu'un mais j'espère. C'est en plein dans le sujet, mais bon c'est du boulot ...
Revenir en haut Aller en bas
Voir le profil de l'utilisateur
Nardo26

avatar

Nombre de messages : 2294
Age : 49
Localisation : Valence
Date d'inscription : 02/07/2010

MessageSujet: Re: Reflexion sur la récursivité   Mer 1 Juil 2015 - 8:21

Laughing
Bonjour Jicehel !
Min-max ? voir  ici
...la demande date un peu...
Il faut que je me replonge dans mes cartons sur ce sujet. Wink
Je jette un coup d'oeil à ton code Silverman... il y a aussi le tri fusion qui peut egalement être réalisé en recursif (enfin, je crois...)
Revenir en haut Aller en bas
Voir le profil de l'utilisateur http://nardo26.lescigales.org
Jicehel

avatar

Nombre de messages : 5859
Age : 45
Localisation : 77500
Date d'inscription : 19/04/2011

MessageSujet: Re: Reflexion sur la récursivité   Mer 1 Juil 2015 - 8:58

Bonne chance Nardo et si tu arrives à l'appliquer à un jeu de dames, je me replongerais dans le code de l'époque pour finir. C'est beau les gens courageux .... Wink
Revenir en haut Aller en bas
Voir le profil de l'utilisateur
Nardo26

avatar

Nombre de messages : 2294
Age : 49
Localisation : Valence
Date d'inscription : 02/07/2010

MessageSujet: Re: Reflexion sur la récursivité   Mer 1 Juil 2015 - 9:11

Je dis pas que je vais y arriver : c'est que je sature en ce moment au niveau ordi, tv, etc... mais comme je n'ai que ça à faire...

Merci Silverman pour ton code :
cela me clarifie les idées drunken et certainement que mes sources pour les arbres AVL vont être revues en fct de cela...
Revenir en haut Aller en bas
Voir le profil de l'utilisateur http://nardo26.lescigales.org
Jicehel

avatar

Nombre de messages : 5859
Age : 45
Localisation : 77500
Date d'inscription : 19/04/2011

MessageSujet: Re: Reflexion sur la récursivité   Mer 1 Juil 2015 - 10:55

Nardo26 a écrit:
c'est que je sature en ce moment au niveau ordi, tv
Je te comprends, mais j'avoue que contrairement à toi, je peux faire autre chose.
Perso, en ce moment, je n'ai pas trop envie de me casser la tête.
Si tu y arrives,je l'intégrerais au jeu car le plus "prise de tête" sera fait et coder des trucs simples, ça me détent plutôt Wink
Revenir en haut Aller en bas
Voir le profil de l'utilisateur
Nardo26

avatar

Nombre de messages : 2294
Age : 49
Localisation : Valence
Date d'inscription : 02/07/2010

MessageSujet: Re: Reflexion sur la récursivité   Lun 6 Juil 2015 - 1:45

Une petite fonction qui permet de parcourir l'ensemble des sous-répertoires d'un dossier.  

L'appui sur une touche du clavier permet de terminer le programme.
Adaptez le chemin passé en paramètre lors de l'appel...


Code:
DIM a$ : a$=DIR_CURRENT$
WIDTH 0,SCREEN_X
MEMO 1:FULL_SPACE 1 : BAR_VERTICAL 1
font_name 1,"Courier New"

Parcours("C:\Langages\Panoramic",1)

ITEM_ADD 1,"Fini !"

DIR_CHANGE a$

END

SUB Parcours(d$,N)
  if VARIABLE("EXIT_RECURSE")=1 THEN EXIT_SUB
  IF VARIABLE("t$")=0 THEN DIM_LOCAL t$,tmp$
  DIR_CHANGE d$
  t$= FILE_FIND_FIRST$
  IF t$="." THEN t$= FILE_FIND_NEXT$
  IF t$=".." THEN t$= FILE_FIND_NEXT$
  WHILE t$<>"_"
   IF DIR_EXISTS(t$)=1
     PUSH(t$):Parcours(t$,N): DIM_LOCAL t$ ,tmp$
     POP():t$=POP_return$
     tmp$= FILE_FIND_FIRST$
     WHILE tmp$<>t$
      tmp$= FILE_FIND_NEXT$
      if VARIABLE("EXIT_RECURSE")=1 THEN EXIT_WHILE
     END_WHILE
     t$= FILE_FIND_NEXT$
   ELSE
    ITEM_ADD N,DIR_CURRENT$+CHR$(92)+t$
    t$ = FILE_FIND_NEXT$
   END_IF
   if VARIABLE("EXIT_RECURSE")=1 THEN EXIT_WHILE
  END_WHILE
  DIR_CHANGE ".."
END_SUB



rem ============================================================================
rem   Spécifiques aux traitements récursifs
rem ============================================================================
SUB PUSH(v$)
    IF VARIABLE("PILE")=0 THEN DIM PILE: PILE = NUMBER_OBJECTS + 1 : DLIST PILE
    ITEM_ADD PILE,v$
    IF SCANCODE<>0 THEN DIM EXIT_RECURSE:CLEAR PILE: EXIT_SUB
    WAIT 1 : ' pour éviter de saturer l'UC
END_SUB

SUB POP()
  IF VARIABLE("POP_return$")=0 THEN DIM POP_return$,POP_return
  IF COUNT(PILE)>0
    POP_return$= ITEM_READ$(PILE,COUNT(PILE))
    IF NUMERIC(POP_return$)=1:POP_return=VAL(POP_return$):ELSE:POP_return=0:END_IF
  END_IF
  IF COUNT(PILE)<>0 THEN ITEM_DELETE PILE,COUNT(PILE)
END_SUB
Revenir en haut Aller en bas
Voir le profil de l'utilisateur http://nardo26.lescigales.org
Jicehel

avatar

Nombre de messages : 5859
Age : 45
Localisation : 77500
Date d'inscription : 19/04/2011

MessageSujet: Re: Reflexion sur la récursivité   Lun 6 Juil 2015 - 10:59

C'est une autre apporche que la fonction de JL35 mais c'est intéressant et utile comme fonction Wink
Revenir en haut Aller en bas
Voir le profil de l'utilisateur
papydall

avatar

Nombre de messages : 5587
Age : 67
Localisation : Moknine (Tunisie) Entre la chaise et le clavier
Date d'inscription : 03/03/2012

MessageSujet: Re: Reflexion sur la récursivité   Lun 6 Juil 2015 - 15:36

Revenir en haut Aller en bas
Voir le profil de l'utilisateur http://papydall-panoramic.forumarabia.com/
Nardo26

avatar

Nombre de messages : 2294
Age : 49
Localisation : Valence
Date d'inscription : 02/07/2010

MessageSujet: Re: Reflexion sur la récursivité   Lun 6 Juil 2015 - 21:21

Jicehel a écrit:
C'est une autre apporche que la fonction de JL35 mais c'est intéressant et utile comme fonction   Wink
J'ai pas trouvé la version de JL35... Crying or Very sad

Pour ma petite fonction : il est facile de l'adapter pour en faire un DIR_REMOVE version 2. Wink
Revenir en haut Aller en bas
Voir le profil de l'utilisateur http://nardo26.lescigales.org
Contenu sponsorisé




MessageSujet: Re: Reflexion sur la récursivité   

Revenir en haut Aller en bas
 
Reflexion sur la récursivité
Voir le sujet précédent Voir le sujet suivant Revenir en haut 
Page 1 sur 1

Permission de ce forum:Vous ne pouvez pas répondre aux sujets dans ce forum
FORUM DE DISCUSSION SUR LE LANGAGE PANORAMIC :: PANORAMIC :: Vos sources, vos utilitaires à partager-
Sauter vers: