probleme de recursivite

probleme de recursivite - Perl - Programmation

Marsh Posté le 05-06-2004 à 18:32:18    

Voila mon probleme c ke mon maitre de stage ma demande de resoudre un probleme et de me servir de la recursivite.  
Je ne sai pas ce ke c donc jai fait des recherches sur google et je n'ai pas trouver ce ke je chercher j'ai juste trouver des fonctions pour essayer de comprendre la chose main en vain.  
voila le source a modifier:  
 

Code :
  1. #boucle de changement de 4 par 4
  2. $i = 0;
  3. $index = 0;
  4. $j = 0;
  5. while ($index < $vector_n)
  6. { $vector[$index] .= $seq[$j];
  7. }
  8. continue
  9. { $index = $index+1;
  11. ## essayer de transformer en f(i)
  12.   $i = $i + 1;
  13.   $j = int($i/$seq_n);
  14.   if ($j == $seq_n) { $i = 0; $j = 0;}
  15. }
  16. il faut que le j disparaise et kil ni ai plus que le i
  17. j'ai essayer cela mais sa marche po :
  18. continue
  19. { $index = $index+1;
  20.   $i = &calci_4($index , $seq_n , $i); 
  21. }
  22. ########################################################################
  23. #                                                                    #
  24. #              1.00    0206504  nico                                 #
  25. #                    #
  26. # calci_4($index , $seq_n , $i)             #
  27. #                    #
  28. #it is a procedure in order to reduce the row of the code and this procedure  #
  29. #is use in the boucle while to calculate the number of combinaison    #
  30. #################################################################################
  31. sub calci_4(i){
  32. my $index = 0;
  33. my $i = 0;
  34. if ($i<3)
  35. { 
  36.   $i = int($index/$seq_n);
  37.   calci_4( $i + 1);
  38.   if ($i == $seq_n) { $i = 0; } 
  39. }
  40.   return($i);
  41. }

Reply

Marsh Posté le 05-06-2004 à 18:32:18   

Reply

Marsh Posté le 05-06-2004 à 18:33:01    

je sais je passe pour une quiche mai je sui en premiere anne de bts iris et je fais du c++ et la mon stage est en perl et je connais pas la recursiviter donc je galere.  
merci d'avance de votre reponse ki meclairera je lespere

Reply

Marsh Posté le 05-06-2004 à 20:39:05    

La recursivité n'a rien a voir avec le langage.
Tourne toi plutot vers des bouquins ou des sites d'algo. Je n'ai pas de sites en tete sur le sujet et je manque de temps pour te trouver ca. Alors cherche un peu par toi meme.
(Repense eventuellement a tes cours de premiere/terminale sur la recursivite des suites).

Reply

Marsh Posté le 05-06-2004 à 21:01:25    

tiens, trouvé sur google:
http://www.chambily.com/recursivite/
c'est en pascal, mais les principes sont les memes
 
tiens, un truc en C:
http://perso.wanadoo.fr/carlov/cou [...] ivite.html

Reply

Marsh Posté le 07-06-2004 à 08:23:13    

merci a vous deux  
et pour le 1er site je connaisai mai le 2eme est pas mal du tout  
je vais continuer mes tests en esperant de la reussite cette fois.

Reply

Marsh Posté le 08-06-2004 à 15:39:04    

voila c encor moi jai encor un pti probleme jai ecir une fonction recursive( decidement jai du mal  :cry: ).  il ni a pas derreur mais elle naffiche rien.

Code :
  1. #
  2. # shared data
  3. #
  4. my $seq_n = 4;
  5. my @vector;
  6. my @element={"A","B","C","D"};
  7. my $element_n = 4;
  8. my $combi_n = 3;
  9. my $vector_n = $element_n^($combi_n);
  10. #================================================================================
  11. # SUBROUTINES
  12. #================================================================================
  13. #################################################################################
  14. # 1.00 080604 nico #
  15. # init_vector #
  16. #it consist to initialise the vector about blank #
  17. #################################################################################
  18. sub init_vector{
  20. my $i = 0;
  22. $vector_n = $seq_n * $seq_n;
  23. for ($i=0; $i<$vector_n; $i++)
  24. { push (@vector, $blank);
  25. }
  26. }
  27. #################################################################################
  28. # 1.00 080604 nico #
  29. # gen_block #
  30. #it consist to use recursivite in the project #
  31. #################################################################################
  32. sub gen_block{
  34. my $range = 0;
  35. my $offset = 0;
  36. my $block_size = $range/$element_n;
  37. my $i = 0;
  38. my $j = 0;
  39. my $k = 0;
  40. my $t = 0;
  42. while ($i<$range){
  43. $vector[$offset+$i].=$element[$k];
  44. $j= $j+1;
  45. if ($j == $block_size){
  46. $j = 0;
  47. $k = $k+1;
  48. $t = $t +$range;
  49. print "$i","$j","$k","$t" ;
  50. }
  51. gen_block($block_size,$t);
  52. }
  53. continue{
  54. $i = $i+1;
  55. }
  56. }
  58. #================================================================================
  59. # MAIN
  60. #================================================================================
  63. &init_vector($vector_n);
  64. print &gen_block($vector_n,0);
  66. exit 0;


si il y a kelkun ki peut me dire ce ki va pas svp :D  
 

Reply

Marsh Posté le 08-06-2004 à 19:21:08    

Code :
  1. sub calci_4(i){ 
  2.      my $index = 0; 
  3.      my $i = 0; 
  4.      if ($i<3) 
  5.      { 
  6.         $i = int($index/$seq_n); 
  7.         calci_4( $i + 1); 
  8.         if ($i == $seq_n) { $i = 0; } 
  9.      } 
  10.       return($i); 
  11.   }


 
Ceci est la définition de calci_4.
Dans cette fonction, tu fais appel à ... calci_4.
C'est ça la récursivité, c'est quand tu fais appel à la fonction dans sa propre définition. Pour éviter que ça ne boucle et ça ne finisse par exploser (les appels et les calculs intermédiaires étant empilés), il faut une condition d'arrêt qui sera vérifiée à chaque appel ; ici, if($i >= 3), on arrête.

Reply

Marsh Posté le 08-06-2004 à 19:46:59    

royou1 a écrit :

voila c encor moi jai encor un pti probleme jai ecir une fonction recursive( decidement jai du mal  :cry: ).  il ni a pas derreur mais elle naffiche rien.
 
si il y a kelkun ki peut me dire ce ki va pas svp :D


 
Ca fait quelque temps que je n'ai pas fait de perl,
 
Mais je doute de ta syntaxe sur
 

Code :
  1. print &gen_block($vector_n,0);


---------------
Les bureaucrates: "S'ils tombaient d'un immeuble, il leur faudrait une semaine pour s'ecraser." "All I ever wanted All I ever needed Is here in my arms Words are very unnecessary They can only do harm               Enjoy the silence"
Reply

Marsh Posté le 08-06-2004 à 21:24:31    

Ouaip, moi non plus, ça ne me rappelle rien. Mais avec Perl, faut se méfier de ses souvenirs.
 
Le & -> bizarre. Et dans la subroutine, j'aurais mis des shift(@_) pour récuperer les arguments.

Reply

Marsh Posté le 08-06-2004 à 22:07:01    

le & est optionel pour les appels de fonctions, et en fait il n'est plus vraiment souhaitable depuis Perl 5.
 
Pour les arguments effectivement tu ne les recuperes par dans ton gen_block!


Message édité par pospos le 14-06-2004 à 20:25:26
Reply

Marsh Posté le 08-06-2004 à 22:07:01   

Reply

Marsh Posté le 09-06-2004 à 09:21:30    

saye jai corrriger en tenant compte de vos remarque et jai ceci maintenant:

Code :
  1. my $seq_n = 4;
  2. my @vector;
  3. my @element={"A","B","C","D"};
  4. my $element_n = 4;
  5. my $combi_n = 3;
  6. my $vector_n = $element_n**$combi_n;
  9. #================================================================================
  10. # SUBROUTINES
  11. #================================================================================
  12. #################################################################################
  13. #              1.00 080604 nico #
  14. # init_vector                 #
  15. #it consist to initialise the vector about blank        #
  16. #################################################################################
  17. sub init_vector{
  19. my $i = 0;
  20. for ($i=0; $i<$vector_n; $i++)
  21. { push (@vector, $blank);
  22. }
  23. }
  26. #################################################################################
  27. #              1.00 080604 nico #
  28. # gen_block ( $range , $offset )            #
  29. #it consist to use recursivite in the project         #
  30. #################################################################################
  31. sub gen_block
  32. {
  33. my ( $range , $offset ) = @_;
  34. my $block_size = $range/$element_n;
  35. my $i = 0;
  36. my $j = 0;
  37. my $k = 0;
  38. my $t = 0;
  39. my $str = "";
  41.  while ($i<$range){
  42.   $vector[$offset+$i].=$element[$k];
  43.   $str = $vector[$offset+$i];
  44.   $j= $j+1;
  45.    if ($j == $block_size){
  46.     $j = 0;
  47.     $k = $k+1;
  48.     $t = $t + $range;
  49.     print str_vec2str("\n",@vector);
  50.    }
  51.   gen_block($block_size,$t);
  52.  }
  53.  continue{
  54.   $i = $i+1;
  55.  }
  56. }
  57. #================================================================================
  58. # MAIN
  59. #================================================================================
  60. my @aa;
  62. &init_vector($vector_n);
  63. @aa = &gen_block($vector_n,0);
  64. print str_vec2str("\n",@vector);
  65. print @aa;
  67. exit 0

;
 
le petit probleme c ke jai une erreur de hash donc il y a un truc ke je fai pas comme il fo.
en fait moi ce ke je ve c ke cette fonction recursive me retourne un truc de ce style mais avec abcd:

Code :
  1. CAPV
  2. AAPV
  3. PAPV
  4. VAPV
  5. CAPV
  6. AAPV
  7. PAPV
  8. VAPV
  9. CAPV
  10. AAPV
  11. PAPV
  12. VAPV
  13. CAVV
  14. AAVV
  15. PAVV
  16. VAVV
  17. CAVV
  18. AAVV
  19. PAVV
  20. VAVV
  21. CAVV
  22. AAVV
  23. PAVV
  24. VAVV
  25. CAVV
  26. AAVV
  27. PAVV
  28. VAVV


ci dessus ce ke jai obtenue en faisant le test avec des boucles for ou while.et comme sa faisait tro de ligne mon maitre de stage( :kaola: ) ma di de faire avec la recursivite( :cry: ) jai reussi a l'ecrire mais pas a la faire fonctionner( :fou: ).
voila je sais jsuis chiant :D  a tou le temps dmd mai je galer avec la recursivité :cry:  ke je connaisai pas il y a encor 1 semaine

Reply

Marsh Posté le 09-06-2004 à 13:45:20    

pk ton maitre de stage te demande ca??
ca ressemble plus à un exam qu'autre chose!
en plus en Perl al recursivité c'est loin d'etre efficace! Les boucles c'est bien mieux géré

Reply

Marsh Posté le 09-06-2004 à 13:48:59    

c parce ke jai fai avec les boucles et le nombre de ligne de code est 4 fois plus important ke si jutilise la recursivite donc il ve sa pour reduire le nombre de ligne de code et pour ke japrene la recursivite.
jai essayer de mentrainer avec des tutos et du delphi pour comprendre la recursivite mais c vraiment chaud.

Reply

Marsh Posté le 09-06-2004 à 17:26:17    

n'empêche que tu ne récupères toujours pas tes arguments dans la fonction init_vector.
 
Edit: j'ai rien dit, désolé  :sweat: (oubli des portées de variables)


Message édité par Tentacle le 09-06-2004 à 17:29:10
Reply

Marsh Posté le 09-06-2004 à 17:43:35    

Je crois que tu as un soucis sur ta condition d'arrêt. Si j'ai bien compris (à voir), ta condition d'arrêt est $i >= $range, soit $range=0 ce qui stopera la récursivité. Or ici tu envoies $range/$element_n pour $range. Au début $range=$vector_n=4**3=64, ensuite $range = 16, puis 4, puis 1, puis 1/4, puis 1/16 etc ... ce qui sera toujours strictement supérieur à 0 :/

Reply

Marsh Posté le 09-06-2004 à 20:41:30    

ben tu lui dira qu'en Perl la recurcivité c'est pas efficace: ca bouffe un max de memoire et c'est plus lent.
 
En gros voila l'explication: pour gagner en vitesse Perl garde la memoire alouée pour chaque variable d'une fonction qu'il a deja exectué. Par exemple si dans une fonction tu declare une varibale "my $a" et que tu lui alloue une chaine de 10ko, et ben meme si tu quite ta fonction Perl garde une memoire allouée à 10ko pour $a. Ca lui permet de ne pas réalouer la fois suivante, et donc de gagner en vitesse. Le probleme c'est qu'il est obligé de faire ca pour chaque niveau de recursion dans ta fonction, sans jamais libérer la memoire. Dans ton cas tu n'a pas ce probleme vu que tu utilise des variables globales, mais de toutes facons je ne pense pas queton maitre de stage sera tres content en voyant ca...
 
Sans compter le fait que les appels de fonction sont tout de meme assez lents en perl...

Reply

Marsh Posté le 09-06-2004 à 20:47:11    

Tu as des cours de français dans ton stage ? :whistle:
 
 
Sinon tu n'utilises pas le couple  

Code :
  1. use strict;
  2. use warnings;

?

Reply

Marsh Posté le 10-06-2004 à 08:47:38    

:heink: hum sa commence a me gonfler cette recursivite( :cry: ) de m.... mais bon on me demande sa :fou: .
donc pour repondre a toute vos suggestion et vos conseils .
Aparament le probleme est bien sur la condition de sortie, ensuite
 

Citation :

rasthor a dit:Tu as des cours de français dans ton stage ? :whistle:

 
 :D ben jecri a larache pour aller + vite et c labitude desd texto sur le tel.
 
et pour les fonctions oui jutilise la librairie use strict; mais pas celle use warnings;
bon en bref jsui pas ariver mais jai 2semaine( :pt1cable: ) pour essayer car il me reste 2 semaines de stage et jai deja fini le projet alors on ma dmd de loptimiser.
 

Reply

Marsh Posté le 10-06-2004 à 10:58:40    

bon saye jai coriger la plupar des choses mais il me reste un bleme sur t :

Code :
  1. sub gen_block
  2. {
  3. my ( $range , $offset ) = @_;
  4. my $block_size = $range/$element_n;
  5. my $i = 0;
  6. my $j = 0;
  7. my $k = 0;
  8. my $t = 0;
  10. print "------------------------------------------------------------------------------\n";
  11. while (($i<$range) && ($block_size>=1) && ($offset<=($vector_n-$range)))
  12. { $vector[$offset+$i] .= $element[$k];
  13.  print "$range\t$block_size\t$offset\t$i\t$j\t$k\t$t\t".$element[$k]."\t".$vector[$offset+$i]."\n";
  14.  $j++;
  15.  if ($j == $block_size)
  16.  { $k++;
  17.   $j = 0;
  18.   $t = $block_size*($k-1);
  19.   &gen_block($block_size,$t);
  20.  }
  21. }
  22. continue
  23. { $i++;
  24. }
  25. }


voila ce ke jobtient et il merde au 2eme tour de boucle:

Code :
  1. range   bsize   offset  i       j       k       t       el[k]   vec[offset+i]
  2. ------------------------------------------------------------------------------
  3. 27      9       0       0       0       0       0       A       -A
  4. 27      9       0       1       1       0       0       A       -A
  5. 27      9       0       2       2       0       0       A       -A
  6. 27      9       0       3       3       0       0       A       -A
  7. 27      9       0       4       4       0       0       A       -A
  8. 27      9       0       5       5       0       0       A       -A
  9. 27      9       0       6       6       0       0       A       -A
  10. 27      9       0       7       7       0       0       A       -A
  11. 27      9       0       8       8       0       0       A       -A
  12. ------------------------------------------------------------------------------
  13. 9       3       0       0       0       0       0       A       -AA
  14. 9       3       0       1       1       0       0       A       -AA
  15. 9       3       0       2       2       0       0       A       -AA
  16. ------------------------------------------------------------------------------
  17. 3       1       0       0       0       0       0       A       -AAA
  18. ------------------------------------------------------------------------------
  19. 3       1       0       1       0       1       0       B       -AAB
  20. ------------------------------------------------------------------------------
  21. 3       1       0       2       0       2       1       C       -AAC
  22. ------------------------------------------------------------------------------
  23. 9       3       0       3       0       1       0       B       -AB
  24. 9       3       0       4       1       1       0       B       -AB
  25. 9       3       0       5       2       1       0       B       -AB
  26. ------------------------------------------------------------------------------
  27. 3       1       3       0       0       0       0       A       -ABA
  28. ------------------------------------------------------------------------------
  29. 3       1       3       1       0       1       0       B       -ABB
  30. ------------------------------------------------------------------------------
  31. 3       1       3       2       0       2       1       C       -ABC
  32. ------------------------------------------------------------------------------
  33. 9       3       0       6       0       2       3       C       -AC
  34. 9       3       0       7       1       2       3       C       -AC
  35. 9       3       0       8       2       2       3       C       -AC
  36. ------------------------------------------------------------------------------
  37. 3       1       6       0       0       0       0       A       -ACA
  38. ------------------------------------------------------------------------------
  39. 3       1       6       1       0       1       0       B       -ACB
  40. ------------------------------------------------------------------------------
  41. 3       1       6       2       0       2       1       C       -ACC
  42. ------------------------------------------------------------------------------
  43. 27      9       0       9       0       1       0       B       -B
  44. 27      9       0       10      1       1       0       B       -B
  45. 27      9       0       11      2       1       0       B       -B
  46. 27      9       0       12      3       1       0       B       -B
  47. 27      9       0       13      4       1       0       B       -B
  48. 27      9       0       14      5       1       0       B       -B
  49. 27      9       0       15      6       1       0       B       -B
  50. 27      9       0       16      7       1       0       B       -B
  51. 27      9       0       17      8       1       0       B       -B
  52. ------------------------------------------------------------------------------
  53. 9       3       9       0       0       0       0       A       -BA
  54. 9       3       9       1       1       0       0       A       -BA
  55. 9       3       9       2       2       0       0       A       -BA
  56. ------------------------------------------------------------------------------
  57. 3       1       0       0       0       0       0       A       -AAAA
  58. ------------------------------------------------------------------------------
  59. 3       1       0       1       0       1       0       B       -AABB
  60. ------------------------------------------------------------------------------
  61. 3       1       0       2       0       2       1       C       -AACC
  62. ------------------------------------------------------------------------------
  63. 9       3       9       3       0       1       0       B       -BB
  64. 9       3       9       4       1       1       0       B       -BB
  65. 9       3       9       5       2       1       0       B       -BB
  66. ------------------------------------------------------------------------------
  67. 3       1       3       0       0       0       0       A       -ABAA
  68. ------------------------------------------------------------------------------
  69. 3       1       3       1       0       1       0       B       -ABBB
  70. ------------------------------------------------------------------------------
  71. 3       1       3       2       0       2       1       C       -ABCC
  72. ------------------------------------------------------------------------------
  73. 9       3       9       6       0       2       3       C       -BC
  74. 9       3       9       7       1       2       3       C       -BC
  75. 9       3       9       8       2       2       3       C       -BC
  76. ------------------------------------------------------------------------------
  77. 3       1       6       0       0       0       0       A       -ACAA
  78. ------------------------------------------------------------------------------
  79. 3       1       6       1       0       1       0       B       -ACBB
  80. ------------------------------------------------------------------------------
  81. 3       1       6       2       0       2       1       C       -ACCC
  82. ------------------------------------------------------------------------------
  83. 27      9       0       18      0       2       9       C       -C
  84. 27      9       0       19      1       2       9       C       -C
  85. 27      9       0       20      2       2       9       C       -C
  86. 27      9       0       21      3       2       9       C       -C
  87. 27      9       0       22      4       2       9       C       -C
  88. 27      9       0       23      5       2       9       C       -C
  89. 27      9       0       24      6       2       9       C       -C
  90. 27      9       0       25      7       2       9       C       -C
  91. 27      9       0       26      8       2       9       C       -C
  92. ------------------------------------------------------------------------------
  93. 9       3       18      0       0       0       0       A       -CA
  94. 9       3       18      1       1       0       0       A       -CA
  95. 9       3       18      2       2       0       0       A       -CA
  96. ------------------------------------------------------------------------------
  97. 3       1       0       0       0       0       0       A       -AAAAA
  98. ------------------------------------------------------------------------------
  99. 3       1       0       1       0       1       0       B       -AABBB
  100. ------------------------------------------------------------------------------
  101. 3       1       0       2       0       2       1       C       -AACCC
  102. ------------------------------------------------------------------------------
  103. 9       3       18      3       0       1       0       B       -CB
  104. 9       3       18      4       1       1       0       B       -CB
  105. 9       3       18      5       2       1       0       B       -CB
  106. ------------------------------------------------------------------------------
  107. 3       1       3       0       0       0       0       A       -ABAAA
  108. ------------------------------------------------------------------------------
  109. 3       1       3       1       0       1       0       B       -ABBBB
  110. ------------------------------------------------------------------------------
  111. 3       1       3       2       0       2       1       C       -ABCCC
  112. ------------------------------------------------------------------------------
  113. 9       3       18      6       0       2       3       C       -CC
  114. 9       3       18      7       1       2       3       C       -CC
  115. 9       3       18      8       2       2       3       C       -CC
  116. ------------------------------------------------------------------------------
  117. 3       1       6       0       0       0       0       A       -ACAAA
  118. ------------------------------------------------------------------------------
  119. 3       1       6       1       0       1       0       B       -ACBBB
  120. ------------------------------------------------------------------------------
  121. 3       1       6       2       0       2       1       C       -ACCCC
  122. ------------------------------------------------------------------------------


au lieu de faire des combis de 3 el fait des combis de 5 bizare non et le bleme il vien de sa:

Code :
  1. $t = $block_size*($k-1);


 :ange: merci de maider svp

Reply

Marsh Posté le 14-06-2004 à 08:41:03    

e sans dec yen a pas un ki peut me dire ce ki va pas .


---------------
bordeaux:nos chants et notre amour n' ont pas de frontiere car notre maillot au scapulaire est un maillot legendaire.
Reply

Marsh Posté le 14-06-2004 à 20:22:42    

royou1 a écrit :

e sans dec yen a pas un ki peut me dire ce ki va pas .

Ton français :o

Reply

Marsh Posté le 14-06-2004 à 20:24:36    

Royou1, tu fais koi de tes journée si 10 jours t'arrive pas à regler ce problème?
Un stage c'est fait pour apprendre, alors apprend

Reply

Marsh Posté le 15-06-2004 à 14:29:15    

vous inkiete pas le probleme est regler  
si yen a ki veule la solution je la posterai. :D


---------------
bordeaux:nos chants et notre amour n' ont pas de frontiere car notre maillot au scapulaire est un maillot legendaire.
Reply

Marsh Posté le    

Reply

Sujets relatifs:

Leave a Replay

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