FONCTION 91 MCCARTHY

Signaler
Messages postés
6535
Date d'inscription
lundi 16 décembre 2002
Statut
Modérateur
Dernière intervention
22 août 2010
-
Messages postés
241
Date d'inscription
mardi 29 octobre 2002
Statut
Membre
Dernière intervention
23 janvier 2006
-
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

Messages postés
241
Date d'inscription
mardi 29 octobre 2002
Statut
Membre
Dernière intervention
23 janvier 2006

vecchio56 > Oui c est vrai qu audebut c est tres bizarre, et meme tres chaint, mais comme je suis oblige d en faire, j ai du m interesser un minimum, meme si je prefere le C et le C++. Je trouve que c est un langage tres propre, mais je n ai jamais fait un programme complet avec (l objectif du programme de prepa est d apprendre l algorithmique et un peu d informatique theorique, pas de faire des programmes entiers)

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).
Messages postés
21041
Date d'inscription
jeudi 23 janvier 2003
Statut
Modérateur
Dernière intervention
21 août 2019
30
MetalDwarf > tu as jete un oeil sur l'implementation de qsort() de la CRT ? Tu peux le voir sinon dans ma source sur Villes <=> CP, je l'ai detourne pour enlever les pointeurs sur callback de tri. Y a pas un iota de recursivite la dedans et je n'ai pas encore pu trouver un autre algo qui fasse mieux, pourtant j'en ai fai des tests.
Messages postés
3006
Date d'inscription
dimanche 14 avril 2002
Statut
Membre
Dernière intervention
31 décembre 2008

1997 ça fait pas encore vieux, le C est qd même de loin son ainé, et sa syntaxe est tjs aussi agréable :)
Messages postés
6535
Date d'inscription
lundi 16 décembre 2002
Statut
Modérateur
Dernière intervention
22 août 2010
9
j'ai fait ca en premiere année de deug mias, mais il faut dire qu'on est pa allé très loin, et comme je connaissais déja le c++, j'ai eu du mal à m'interesser...
Messages postés
241
Date d'inscription
mardi 29 octobre 2002
Statut
Membre
Dernière intervention
23 janvier 2006

T es en prepa?
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...)
Messages postés
6535
Date d'inscription
lundi 16 décembre 2002
Statut
Modérateur
Dernière intervention
22 août 2010
9
moi en ce qui concerne caml j'en suis encore au début, c'est a dire que je déteste
Messages postés
3006
Date d'inscription
dimanche 14 avril 2002
Statut
Membre
Dernière intervention
31 décembre 2008

intéressant comme page, merci!
Messages postés
241
Date d'inscription
mardi 29 octobre 2002
Statut
Membre
Dernière intervention
23 janvier 2006

Je ne crois pas que le compilateur de OCaml retranscrive les fonctions recursives en fonctions iteratives, car bien qu un theoreme existe en informatique theorique la dessus, il est TRES difficile (voir parfois presque impossible) de faire la traduction.

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.
Messages postés
21041
Date d'inscription
jeudi 23 janvier 2003
Statut
Modérateur
Dernière intervention
21 août 2019
30
Le truc serait de savoir si on fait des comparaisons sur une func recursive C et CAML, il faudrait comparer a une fonction C bien ecrite j'entends par la ou on a supprime la recursivite.
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.
Messages postés
241
Date d'inscription
mardi 29 octobre 2002
Statut
Membre
Dernière intervention
23 janvier 2006

> La recursivite c est pas efficace...

... 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 @+
Messages postés
21041
Date d'inscription
jeudi 23 janvier 2003
Statut
Modérateur
Dernière intervention
21 août 2019
30
non ceci est un des nombreux bugs apprarus depuis le dernier crash chez l'hebergeur il y a a peu pres 2 mois. Ce n'est pas sur toutes les sources, certaines je n'ai pas non plus de retour.

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...
Messages postés
3006
Date d'inscription
dimanche 14 avril 2002
Statut
Membre
Dernière intervention
31 décembre 2008

ah ben non j'ai rêvé, dommage :(
Messages postés
3006
Date d'inscription
dimanche 14 avril 2002
Statut
Membre
Dernière intervention
31 décembre 2008

itératif c'est avec des boucles, c'est ça? j'y connais pas grand chose en compilation, mais il me semble que qd c récursif, ça grossit la place oqp dans le tas. Si c'est itératif comme tu dis, je suppose que ce phénomène n'a plus court. Dommage, parce que la récursivité c'est élégant ^^

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
Messages postés
21041
Date d'inscription
jeudi 23 janvier 2003
Statut
Modérateur
Dernière intervention
21 août 2019
30
les suites de Fibonacci tout comme cet exemple feraient un tres bon exemple en tant que modele dont on supprimerait la recursivite. Le passage du recursif a l'iteratif me semble plus interessant car nettement plus performant, il y a une nombreuse litterature sur le sujet.
Messages postés
3006
Date d'inscription
dimanche 14 avril 2002
Statut
Membre
Dernière intervention
31 décembre 2008

mouarf brunews, ts les étudiants arrivent pas à l'unif en sachant programmer :) et puis ça ns fait une lgueur d'avance qd on y est :p (enfin, toi ça fait un bail que t'y es plus il me semble).

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 ^^)
Messages postés
21041
Date d'inscription
jeudi 23 janvier 2003
Statut
Modérateur
Dernière intervention
21 août 2019
30
1 MILLION d'excuses, je n'avais pas vu la double imbrication d'appel recurrent.
Ben si c'est ce que les etudiants apprennent.... Faut bien amuser les processeurs, ils sont si puissants maintenant.
if(x < 91) return 91;
Messages postés
11
Date d'inscription
vendredi 28 mai 2004
Statut
Membre
Dernière intervention
7 mai 2008

"A vue de nez et en mangeant, me semble que
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.
Messages postés
21041
Date d'inscription
jeudi 23 janvier 2003
Statut
Modérateur
Dernière intervention
21 août 2019
30
A vue de nez et en mangeant, me semble que
func91McCarthy(63) donnera 97 et non 101.

ET LE BUT ???
Messages postés
6535
Date d'inscription
lundi 16 décembre 2002
Statut
Modérateur
Dernière intervention
22 août 2010
9
et si on entre une valeur >= 91?