billaj a écrit :[...](oui, j'ai foiré l'ordre des conditions et la flemme de remettre ça en ordre à 1h du mat...donc 101 pour simuler un <=100 2 lignes plus bas)[...]
Tiens, c'est marrant, j'allai aussi poster une version pour HP-15c ou autre classique, mais en essayant je me suis rendu compte que j'ai moi aussi m....r le sens du test. Et donc toutes les astuces ont été mises à mal. Il était tard, j'ai renoncé à poster un truc bancal.
charognard a écrit :L’idée, me semble t'il, n'était pas de faire un programme qui retourne 91 mais un programme light qui passe par toutes les étapes du calcul (Faire le chemin, plutôt que d'être présent à l'arrivée).
gege a écrit :EDIT : J'ai l'impression que M(x) vaut :
-- x > 100 => M(x) = x - 10
-- x <= 100 et entier => M(x) = 91
-- x <= 100 et non entier => M(x) = 90 + Frac(x)
C'est beaucoup plus rapide mais moins concis à programmer.
Voilà donc deux thèses opposées. L’une suggérant de suivre le chemin et donc de programmer plus ou moins directement la récursivité de la fonction 91 de McCarthy, l’autre faisant l’analyse des résultats de cette fonction et suggérant de programmer une fonction non récursive qui cependant donne les mêmes résultats.
A mon humble avis, les deux se valent, et je suis curieux de suivre les avancés des auteurs des différents codes de ce fils pour voir l’évolution des deux ou trois techniques qui seront utilisées.
Si je résume bien, il y donc pour le moment cinq chemins possibles (le cinquième n’étant pas recommandable) :
- La programmation de la récursivité brute et directe : évidemment réservée aux machines qui le supportent, quitte à perdre du temps d’exécution ou utiliser une pile d’appels monstrueuse par rapport au résultat qui n’est, en fait, qu’un nombre,
- La programmation de la récursivité indirectement : en utilisant un registre servant de compteur d’appels pour pallier aux capacités de la machine. Soit par un registre, soit par une boucle FOR/TO/STEP//NEXT astucieuse.
- L’analyse des résultats : dans le cas de la fonction 91 de McCarthy, cette approche est justifiée car pour les entiers en particulier l’analyse est simple, la fonction renvoie toujours la même valeur jusqu’au seuil critique de 101 à partir d’où la réponse est une fonction affine simple.
- L’analyse des résultats avec extrapolations aux décimaux et négatifs : afin de calculer sans récurrence la réponse mais en tenant compte des cas hors ‘entiers positifs’, c'est-à-dire nombre décimaux, nombres négatifs, etc…
- La méthode non recommandable des HP-41 : qui par un chemin erroné et sans afficher le moindre message d’alerte ou d’erreur affiche une réponse qui n’est juste que fortuitement pour les entiers positifs.
Hormis la dernière méthode qui n’est pas recommandable (aaah ! les HP-41 quel escroquerie !) , tous ces chemins ont leurs avantages et leurs inconvénients :
- Les deux dernières demandent à réaliser l’analyse de la fonction, de ne pas oublier certains cas particulier et cela va conduire à un algorithme peut-être plus complexe, mais qui aura l’avantage de ne pas à avoir suivre le chemin de la récursivité.
- Les deux premières sont plus simples en terme d’analyse et de compréhension de la fonction, mais demandent de bien maitriser l'effort. Sauf pour les systèmes RPL où les capacités mémoire énormes et le principe de fonctionnement permettent de ne pas avoir à réfléchir à cela, tout du moins pour manipuler des nombres, même négatifs jusqu'à quelques dizaines de milliers. Mais il y aura une limite ou même une HP50g fera un ‘Stack Overflow - Memory Low error !
Paradoxalement, le choix du chemin pour miser petit et optimiser n’est pas évident et dépend énormément des capacités de la machine. Même pour les Pocket SHARP, il faut faire attention,
charo explique bien que l’astuce du FOR :NEXT ne fonctionnera pas sur tous les modèles.
Les capacités modestes mais géniales des HP classiques vont contraindre les auteurs à des algorithmes plus sophistiqués. Ils seront différents, mais peut-être plus standards et implémentables sur un plus grand nombre de machines sans trop de modifications.
Décidément, ce sujet ne manque pas d’intérêt. Et je suis curieux de voir les stratégies que chacun va élaborer, puis de voir l’optimisation se faire dans chacun des cas de figure.
A la réflexion, je crois que l’on touche là du doigt la raison de cette fonction 91, J. McCarthy avait le géni de mettre en évidence tous les aspects des sciences de la programmation à partir d’exemples simples. Et j’imagine que comme nous, ces élèves et disciples ont aussi planché et transpiré sur les problèmes que ce grand professeur nous soumet.