Caclul de factorielle

Caclul de factorielle - C - Programmation

Marsh Posté le 04-12-2008 à 18:28:50    

Bonjour à tous,

 

Je débute ma formation en langage C et j'essaye de faire un programme me permettant de calculer la factorielle d'un nombre donnée, j'ai écrit le programme suivant :

 
Code :
  1. #include <stdio.h>
  2.  
  3.  
  4. int facto(int x) {
  5. if (x==1) {
  6. return 1;
  7. }else{
  8. facto(x-1)*x;
  9. }
  10. }
  11.  
  12. int main(){
  13.  
  14. int n;
  15. printf("entrez un nombre : " );
  16. scanf("%d",&n);
  17. printf("facto(%d) = %d \n",n,facto(n));
  18. system("pause" );
  19. }
  

Or lorsque je rentre un chiffre différent de 1 la factorielle n'est pas calculée...pk et d'où vient mon erreur?

 


Merci pour vos réponses.


Message édité par Elmoricq le 04-12-2008 à 19:19:54
Reply

Marsh Posté le 04-12-2008 à 18:28:50   

Reply

Marsh Posté le 04-12-2008 à 18:31:46    

ta fonction facto ne renvoit rien si x different de 1

Reply

Marsh Posté le 04-12-2008 à 18:39:47    

dsl j'avais oublier de mettre le : return facto(x-1)*x;
 
Merci


Message édité par kira974 le 04-12-2008 à 18:57:50
Reply

Marsh Posté le 04-12-2008 à 19:23:00    

En vrac :
- main() est une fonction de type int mais n'a aucun return
- scanf() c'est mal, entre une chaîne de caractère pour le constater. Utilise fgets()  + strtol()
- n'oublie pas de faire un petit test pour vérifier que le nombre entré est >=1. Sinon ton programme plantera sur une explosion de la pile (pas de condition d'arrêt à ta récursivité)
- et donc il manque le return à ta fonction si x != 1 (j'ai vu ta réponse, mais à tout hasard met à jour le code dans ton post pour qu'on voit où ça se situe, si tu as toujours le problème bien sûr)

Reply

Marsh Posté le 05-12-2008 à 17:54:06    

Tu arrives à me donner n! pour n=13 ?
 
quelques exemples aussi,  
 
http://www.luschny.de/math/factorial/index.html


---------------
What if I were smiling and running into your arms? Would you see then what I see now?  
Reply

Marsh Posté le 05-12-2008 à 19:49:28    

La méthode avec for :
 

Code :
  1. int facto(int x) {
  2.     int result = 1;
  3.  
  4.     for(int i = x;i<1;i--) {
  5.         result *= i;
  6.     }
  7.  
  8.     return result;
  9. }


 
est elle plus rapide que la méthode récursive ?
Merci ;)

Reply

Marsh Posté le 05-12-2008 à 20:03:31    

l'itératif est *en général* plus efficace que le récursif (modulo les trace caches ou les compilos sioux)

Message cité 1 fois
Reply

Marsh Posté le 05-12-2008 à 20:21:50    

ok ;)

Reply

Marsh Posté le 05-12-2008 à 22:34:45    

Joel F a écrit :

l'itératif est *en général* plus efficace que le récursif (modulo les trace caches ou les compilos sioux)


 
Mon prof d'image processing nous a dit exactement le contraire hier  :heink:  
Il nous a dit qu'en général le récursif est plus rapide mais que par contre t'as intérêt à avoir un ordio avec pas mal de RAM de bonne qualité sinon tu te manges la gueule..
 
Tu peux développer ta réponse du coup s'il te plait?


---------------
Si la vérité est découverte par quelqu'un d'autre,elle perd toujours un peu d'attrait
Reply

Marsh Posté le 05-12-2008 à 22:49:29    

En gros, dans la plupart des langages fonctionels par contre, le récursif est en général comparable voir meilleurs que l'itératif -qui pose ne outre d'autre probleme.
 
Par contre, la récursivité dans les langages impératifs nécessite de sauvegarder le contexte d'appel et de potentiellement allouées enormement de variables locales sur la pile. Chaque coup te coute en outre les 4-5 cycles necessaires à effectuer le saut vers la fonction elle-même.
 
Sauf que, actuellement, pas mal de processeur on des caches de traces qui mémoisent les séquences d'instructions et les rechargent pas à chaque passage. Dans ce cas, la récursivité a un coup moindre car seul le cout sur la pile coute.
Fut aussi un temps ou certains front-end C tenter de dérécursifier les fonctions récursives à récursivité terminales, mais en je sais pas si ça a abouti.
 
Autre cas, la fonction qui calcule récursivement plusierus fois la meme valeur (genre fibonnacci et equivalent). Dans ce cas,l'algo récursif nécessite pour etre efficace d'etre réécrit sous forme d'algo de programmation dynamique qui va explicitement effectuer cette memoisation.

Message cité 1 fois
Reply

Marsh Posté le 05-12-2008 à 22:49:29   

Reply

Marsh Posté le 06-12-2008 à 08:59:52    

Ok merci beaucoup :)


---------------
Si la vérité est découverte par quelqu'un d'autre,elle perd toujours un peu d'attrait
Reply

Marsh Posté le 07-12-2008 à 16:31:53    

Joel F a écrit :


Sauf que, actuellement, pas mal de processeur on des caches de traces qui mémoisent les séquences d'instructions et les rechargent pas à chaque passage. Dans ce cas, la récursivité a un coup moindre car seul le cout sur la pile coute.

 

C'est vraiment propre à l'x86, et son petit nombre de registres. Sur d'autres architectures, il y a des barillets, qui sollicitent beaucoup moins la pile que ne le ferait un programme sous x86.

 
Citation :

Fut aussi un temps ou certains front-end C tenter de dérécursifier les fonctions récursives à récursivité terminales, mais en je sais pas si ça a abouti.

 

Largement, les compilateurs aujourd'hui savent optimiser la plupart des tail-calls, exemple avec fact():

 

sans optimisation:

 
Code :
  1. 080486dc <fact>:
  2. 80486dc:       55                      push   %ebp
  3. 80486dd:       89 e5                   mov    %esp,%ebp
  4. 80486df:       83 ec 04                sub    $0x4,%esp
  5. 80486e2:       83 7d 08 01             cmpl   $0x1,0x8(%ebp)
  6. 80486e6:       7f 09                   jg     80486f1 <fact+0x15>
  7. 80486e8:       c7 45 fc 01 00 00 00    movl   $0x1,0xfffffffc(%ebp)
  8. 80486ef:       eb 19                   jmp    804870a <fact+0x2e>
  9. 80486f1:       8b 45 08                mov    0x8(%ebp),%eax
  10. 80486f4:       48                      dec    %eax
  11. 80486f5:       83 ec 0c                sub    $0xc,%esp
  12. 80486f8:       50                      push   %eax
  13. 80486f9:       e8 de ff ff ff          call   80486dc <fact>
  14. 80486fe:       83 c4 10                add    $0x10,%esp
  15. 8048701:       89 c2                   mov    %eax,%edx
  16. 8048703:       0f af 55 08             imul   0x8(%ebp),%edx
  17. 8048707:       89 55 fc                mov    %edx,0xfffffffc(%ebp)
  18. 804870a:       8b 45 fc                mov    0xfffffffc(%ebp),%eax
  19. 804870d:       c9                      leave 
  20. 804870e:       c3                      ret
 

avec:

 
Code :
  1. 080486dc <fact>:
  2. 80486dc:       55                      push   %ebp
  3. 80486dd:       89 e5                   mov    %esp,%ebp
  4. 80486df:       8b 55 08                mov    0x8(%ebp),%edx
  5. 80486e2:       83 fa 01                cmp    $0x1,%edx
  6. 80486e5:       7e 18                   jle    80486ff <fact+0x23>
  7. 80486e7:       b8 01 00 00 00          mov    $0x1,%eax
  8. 80486ec:       eb 04                   jmp    80486f2 <fact+0x16>
  9. 80486ee:       89 f6                   mov    %esi,%esi
  10. 80486f0:       89 ca                   mov    %ecx,%edx
  11. 80486f2:       8d 4a ff                lea    0xffffffff(%edx),%ecx
  12. 80486f5:       0f af c2                imul   %edx,%eax
  13. 80486f8:       83 f9 01                cmp    $0x1,%ecx
  14. 80486fb:       75 f3                   jne    80486f0 <fact+0x14>
  15. 80486fd:       c9                      leave 
  16. 80486fe:       c3                      ret   
  17. 80486ff:       b8 01 00 00 00          mov    $0x1,%eax
  18. 8048704:       c9                      leave 
  19. 8048705:       c3                      ret   
  20. 8048706:       89 f6                   mov    %esi,%esi

Message cité 2 fois
Message édité par Gf4x3443 le 07-12-2008 à 16:32:57

---------------
Petit guide Kerberos pour l'administrateur pressé
Reply

Marsh Posté le 07-12-2008 à 17:33:09    

Gf4x3443 a écrit :


C'est vraiment propre à l'x86, et son petit nombre de registres. Sur d'autres architectures, il y a des barillets, qui sollicitent beaucoup moins la pile que ne le ferait un programme sous x86.


Oui bien entendu.  
 

Gf4x3443 a écrit :


Largement, les compilateurs aujourd'hui savent optimiser la plupart des tail-calls, exemple avec fact():


Ah bah voila maintenant je sais  ;)

Reply

Marsh Posté le 07-12-2008 à 18:34:38    

Gf4x3443 a écrit :


 
C'est vraiment propre à l'x86, et son petit nombre de registres. Sur d'autres architectures, il y a des barillets, qui sollicitent beaucoup moins la pile que ne le ferait un programme sous x86.
 


Largement, les compilateurs aujourd'hui savent optimiser la plupart des tail-calls, exemple avec fact():
 
sans optimisation:
 

Code :
  1. 080486dc <fact>:
  2. 80486dc:       55                      push   %ebp
  3. 80486dd:       89 e5                   mov    %esp,%ebp
  4. 80486df:       83 ec 04                sub    $0x4,%esp
  5. 80486e2:       83 7d 08 01             cmpl   $0x1,0x8(%ebp)
  6. 80486e6:       7f 09                   jg     80486f1 <fact+0x15>
  7. 80486e8:       c7 45 fc 01 00 00 00    movl   $0x1,0xfffffffc(%ebp)
  8. 80486ef:       eb 19                   jmp    804870a <fact+0x2e>
  9. 80486f1:       8b 45 08                mov    0x8(%ebp),%eax
  10. 80486f4:       48                      dec    %eax
  11. 80486f5:       83 ec 0c                sub    $0xc,%esp
  12. 80486f8:       50                      push   %eax
  13. 80486f9:       e8 de ff ff ff          call   80486dc <fact>
  14. 80486fe:       83 c4 10                add    $0x10,%esp
  15. 8048701:       89 c2                   mov    %eax,%edx
  16. 8048703:       0f af 55 08             imul   0x8(%ebp),%edx
  17. 8048707:       89 55 fc                mov    %edx,0xfffffffc(%ebp)
  18. 804870a:       8b 45 fc                mov    0xfffffffc(%ebp),%eax
  19. 804870d:       c9                      leave 
  20. 804870e:       c3                      ret


avec:
 

Code :
  1. 080486dc <fact>:
  2. 80486dc:       55                      push   %ebp
  3. 80486dd:       89 e5                   mov    %esp,%ebp
  4. 80486df:       8b 55 08                mov    0x8(%ebp),%edx
  5. 80486e2:       83 fa 01                cmp    $0x1,%edx
  6. 80486e5:       7e 18                   jle    80486ff <fact+0x23>
  7. 80486e7:       b8 01 00 00 00          mov    $0x1,%eax
  8. 80486ec:       eb 04                   jmp    80486f2 <fact+0x16>
  9. 80486ee:       89 f6                   mov    %esi,%esi
  10. 80486f0:       89 ca                   mov    %ecx,%edx
  11. 80486f2:       8d 4a ff                lea    0xffffffff(%edx),%ecx
  12. 80486f5:       0f af c2                imul   %edx,%eax
  13. 80486f8:       83 f9 01                cmp    $0x1,%ecx
  14. 80486fb:       75 f3                   jne    80486f0 <fact+0x14>
  15. 80486fd:       c9                      leave 
  16. 80486fe:       c3                      ret   
  17. 80486ff:       b8 01 00 00 00          mov    $0x1,%eax
  18. 8048704:       c9                      leave 
  19. 8048705:       c3                      ret   
  20. 8048706:       89 f6                   mov    %esi,%esi


 
J'dit p'tet une connerie, mais c'est pas pour les changement de contexte qu'on a invensté les registres virtuels ?
 
Ce qui fait qu'en realité le nombre de registre a un impact limité sur les perfs vu qu'on en a beaucoup plus en pratique. (meme si y'a des tables de translations et tout ça...)
 
Sinon THEORIQUEMENT, quelque soit le type de jeux d'instruction, une boucle for va BEAUCOUP plus vite qu'une fonction recursive.

Message cité 1 fois

---------------
| AMD Ryzen 7 7700X 8C/16T @ 4.5-5.4GHz - 64GB DDR5-6000 30-40-40 1T - AMD Radeon RX 7900 XTX 24GB @ 2680MHz/20Gbps |
Reply

Marsh Posté le 07-12-2008 à 19:00:19    

MEI a écrit :


J'dit p'tet une connerie, mais c'est pas pour les changement de contexte qu'on a invensté les registres virtuels ?


 
Principe des fenetres de registre: http://www.sics.se/~psm/sparcstack.html (entre autres).
 
Un changement de contexte est un cas particulier d'appel de fonction.
 

Citation :


Ce qui fait qu'en realité le nombre de registre a un impact limité sur les perfs vu qu'on en a beaucoup plus en pratique. (meme si y'a des tables de translations et tout ça...)


 
Euh si. Le nombre de registre, et la manière dont ils sont utilisés, a un impact sur la performance. Le design de la FPU de l'x86 en est le plus bel exemple foireux.
 
C'est un compromis: plus il y a de registres, et plus cela en fait à sauvegarder lors d'un changement de contexte (volontaire ou non). Quand ca n'est pas géré électroniquement, c'est couteux (les interruptions hard sur des DSP sont très lourdes pour cette raison).


---------------
Petit guide Kerberos pour l'administrateur pressé
Reply

Sujets relatifs:

Leave a Replay

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