FONCTION 91 MCCARTHY
vecchio56
Messages postés
6535
Date d'inscription
lundi 16 décembre 2002
Statut
Membre
Dernière intervention
22 août 2010
-
9 juin 2004 à 12:07
MetalDwarf Messages postés 241 Date d'inscription mardi 29 octobre 2002 Statut Membre Dernière intervention 23 janvier 2006 - 10 juin 2004 à 17:53
MetalDwarf Messages postés 241 Date d'inscription mardi 29 octobre 2002 Statut Membre Dernière intervention 23 janvier 2006 - 10 juin 2004 à 17:53
Cette discussion concerne un article du site. Pour la consulter dans son contexte d'origine, cliquez sur le lien ci-dessous.
https://codes-sources.commentcamarche.net/source/23526-fonction-91-mccarthy
https://codes-sources.commentcamarche.net/source/23526-fonction-91-mccarthy
10 juin 2004 à 17:53
Kirua > En fait, pour Caml 1997 ca fait vieux. C est un langage developpe a l INRIA et de nombreuses versions sont apparues depuis. Caml-light est une sorte de brouillon en fait, car il ne compile pas en code natif par exemple, et c est un systeme assez minimal. OCaml est apparu depuis, est oriente objet, compile en code natif sur Unix et Windows (et MacOS je crois), et possede aussi une machine virtuelle un peu a la java. De plus d apres les concepteurs de Caml, OCaml est au moins 2x plus rapide que Caml-light.
BruNews > Il est vrai qu un algorithme recursif est tres souvent plus rapide qu alogorithme iteratif. Cependant il ne faut pas oublier que la fiabilite d un code compte aussi. Passer des heures a debugger a cause d effets de bord subtiles est penible et peut etre un inconvenient plus grand que la difference de performances a l execution. Un autre point particulierement important est l aspect fiable des programmes ecris dans des langages fonctionnels comme OCaml. Il est en effet possible de prouver mathematiquement le bon fonctionnement d un algorithme en Caml (surtout si l algorithme est recursif et n utilise pas de variables au sens du C), ce qui est indispensable dans certains domaines. C est pour cela que certaines compagnies tres importantes utilisent des langages de ce type (par exemple je crois qu Airbus travaille avec des chercheurs en info pour prouver leurs programmes. Je ne sais pas si ils sont ecrit en Caml, mais c est important a noter).
Je tiens quand meme a signaler que je ne suis pas du tout un extremiste de la recursivite. Je n ecris presque jamais de fonctions recursives en C...
Juste un petit exemple d algo recursif qu on le veuille ou non : l algo Mini-Max ou alpha-beta utilise dans les jeux d echecs entre autres (il est peut etre possible de le faire iterativement, mais je ne l ai jamais vu).
9 juin 2004 à 21:50
9 juin 2004 à 21:38
9 juin 2004 à 21:36
9 juin 2004 à 21:31
C est vrai que sur le plan de la syntaxe c est un peu chiant (surtout Caml-Light, qui date quand meme de 1997!!), et qu a mon avis ce n est quand meme pas aussi bien que le C, mais c est assez puissant.
On a fait recemment des TPO sur les grands nombres. C est impressionnant la facilite avec laquelle ca se fait en Caml!! Pareil pour les operations sur les arbres.
En plus au debut j avais HORREUR de la recursivite et finalement c est tres agreable a utiliser, et tres naturel (meme si parfois mes instincts iteratifs du C reviennent...)
9 juin 2004 à 21:24
9 juin 2004 à 21:17
9 juin 2004 à 21:08
A titre indicatif :
http://www.bagley.org/~doug/shootout/craps.shtml
Ce benchmark a ete fait en 2001, mais permet de donner une idee...
Et je rappelle que les structures de donnees ont leur importance. Travailler sur un arbre recursivement est elegant et rapide, de meme que sur une liste. Et puis pour les tris et plein d autre choses, la recursivite est quasi-indispensable.
Voila. En tout cas jetez un oeil au Caml, j ai deteste au debut et maintenant je trouve ca tres fort.
9 juin 2004 à 19:10
Si CAML a un compilo qui traduit la recursivite en iteratif ok c'est performant sinon recursif sera toujours moins bon qu'iteratif, qu'on le regrette ou non.
9 juin 2004 à 18:54
... Oui et non. En fait ca peut le devenir si le langage est concu pour. Je ne sais pas si tu connais le langage Caml (ou plutot le OCaml, qui est oriente objet), il a ete entierement concu autour de la recursivite et de l informatique theorique. Il se trouve que ce langage est elegant (recursivite a tous les etages) ET performant. D apres des tests, il est pas loin du tout du C, ce qui est quand meme fort. Je ne connais pas l implementation interne de la chose, mais faire des fonctions relativement sophistiquees en 2 lignes ca me plais. Si tu veux essayer de voir ca va sur le site de l INRIA (je connais ce langage car il est au programme en prepa MPSI option info). Il est en d ailleurs de meme avec tous les langages fonctionnels comme le LISP.
> L interet de la fonction de McCarthy c est de faire calculer a des eleves la correction de l algorithme et de resoudre le probleme de sa terminaison ( ce que j ai effectivement fait cette annee...)
Voila sur ce @+
9 juin 2004 à 15:51
Elegance et performance, c'est bon pour Cabrel, a part rimer ça va rarement ensemble.
Recurrent va PUSHer nbr params + 1 (EIP) a chaque tour et ensuite recuperer valeurs pendant depilage, a savoir qu'un PUSH est couteux et la relecture sur la stack pas moins. Imagine un tableur ecrit de cette façon...
9 juin 2004 à 15:45
9 juin 2004 à 15:43
Dis BruNews, je rêve ou je ne reçois plus de mail quand c'est moi qui poste un commentaire? C'était ça la surprise que t'avais annoncée? :) Parce que j'aimerais que ce ne soit pas une erreur ponctuelle, c'état (c'est?) tellement emmerdant :p
9 juin 2004 à 15:37
9 juin 2004 à 15:29
c'est marrant qd même comme propriété. puis c une jolie illustration de la récurrence (quoique, les suites de fibonacci sont assez élégantes à programmer aussi ^^)
9 juin 2004 à 13:40
Ben si c'est ce que les etudiants apprennent.... Faut bien amuser les processeurs, ils sont si puissants maintenant.
if(x < 91) return 91;
9 juin 2004 à 13:34
func91McCarthy(63) donnera 97 et non 101."
Copiez coller de l'execution du programme :
> Si vous entrez une valeur <101, vous obtiendrez 91.
> x= 63
> Resultats: 91
"et si on entre une valeur >= 91?"
tant que l avaleur est inferieure à 101 tu obtiendras 91, sinon tu obtiendras ta valeur-10
"ET LE BUT ???"
c'est un exo classqiue que beaucoup d'étudiants d'université doivent connaitre.
9 juin 2004 à 13:16
func91McCarthy(63) donnera 97 et non 101.
ET LE BUT ???
9 juin 2004 à 12:07