MPO n°112 : fonction récursive

Ici, on fait dans le petit, le LCD qui déchire sa race, on y cause même calculatrices quand on est en manque !

Modérateur : Politburo

Avatar du membre
gege
Fonctionne à 14400 bauds
Fonctionne à 14400 bauds
Messages : 7141
Enregistré le : 31 janv. 2008 14:24
Localisation : Banlieue Paârisienne
Contact :

MPO n°112 : fonction récursive

Message par gege »

Bonjour,
Un petit défi de programmation puisque numériquement c'est assez trivial.

Vous devez programmer votre machine Basic (le vrai, pas celui d'une calculatrice graphique - elles sont interdites !) Pour qu'elle demande un entier n>O et renvoie la valeur de U(n) en respectant trois règles :
U(1)=7
U(2*n)=3*U(n)
U(2*n+1)=2*U(n)-1

Exemple : U(9)=2*U(4)-1=2*(3*U(2))-1=2*(3*(3*U(1)))-1=2*3*3*7-1=125

Que vaut U(574) ?
A+
G.E.
antoine
Fonctionne à 75 bauds
Fonctionne à 75 bauds
Messages : 14
Enregistré le : 04 août 2022 10:18

Re: MPO n°112 : fonction récursive

Message par antoine »

bonjour,

je m'appelle antoine j'ai gardé de ma scolarité une fx4000P et une fx850P ainsi qu'une EL9300, je suis resté un peu nostalgique de ces années et j'apprécie surtout le fait d'avoir une machine simple qu'on peut maîtriser raisonnablement avec un manuel en bon papier de pas trop de pages. Je me retrouve perdu avec la programmation au XXIeme siècle, les appels à des gigaoctets de librairies nébuleuses, l'aide en ligne tentaculaire, des kilomètres de lecture sur les forums, l'approche "j'essaie pour voir", etc.
Je regrette donc l'époque où je comprenais ce que je faisais de A à Z et où écrire un programme restait abordable.
Je suis malheureusement assez occupé professionnellement mais de temps en temps j'aime faire l'exercice du MPO, c'est sympa et je déconnecte de plein d'autres trucs.

je propose pour cet exercice une solution pour fx4000P qui tient en 84 pas :

Code : Tout sélectionner

?->A:0->B:Lbl0:2*Frac(A/2)->D[B]:Int(A/2)->A:B+1->B:A≠1=>Goto0:7->C:Lbl1:C*(3-D[B-1])-D[B-1]->C:DszB:Goto1:Cꙙ
le dernier caractère est le petit triangle "Disp" qui affiche le contenu de la variable C. Pas facile de transcrire les caractères spéciaux sur un ordinateur.

Pour 574 le programme renvoie 18051.
Ce programme fonctionne à partir de N=2 et jusqu'à 2^24-1. Au-delà il faut allouer de la mémoire supplémentaire par le mode Defm.

antoine
Avatar du membre
gege
Fonctionne à 14400 bauds
Fonctionne à 14400 bauds
Messages : 7141
Enregistré le : 31 janv. 2008 14:24
Localisation : Banlieue Paârisienne
Contact :

Re: MPO n°112 : fonction récursive

Message par gege »

Bonjour,
Réponse correcte !
Belle astuce avec le calcul de 3 ou 2 en fonction du reste...
Je vais essayer d'optimiser ma solution...
G.E.
Avatar du membre
C.Ret
Fonctionne à 9600 bauds
Fonctionne à 9600 bauds
Messages : 3400
Enregistré le : 31 mai 2008 23:43
Localisation : N 49°22 E 6°10

Re: MPO n°112 : fonction récursive

Message par C.Ret »

Je suis content, je suis pas le premier à répondre...

Ca risque pas, je découvre le sujet 12 heures après la première réponse.

Bon, je suis embêté avec ce MPO !, car cela est visiblement très récursif:
Image

Mais cela ne l'est pas du tout:
votre machine Basic

Voyons, voyons, l'auteur de ce dilemme n'aurait-il pas, il y a quelque temps publié dans une Gazette, une méthode qui "dote le BASIC de possibilités incroyables" ???

Je m'édite cette nuit et demain soir j'attaque.
Modifié en dernier par C.Ret le 05 août 2022 19:46, modifié 1 fois.
SHARP PC-1211 PC-1360 EL-5150 PC-E500 | Commodore C=128D | Texas Instruments Ti-57LCD Ti-74BASICalc Ti-92II Ti-58c Ti-95PROCalc Ti-30XPROMathPrint | Hewlett-Packard HP-28S HP-41C HP-15C HP-Prime HP-71B | CASIO fx-602p | NUMWORKS | Graphoplex Rietz Neperlog | PockEmul | Sommaire des M.P.O. | Ma...dov'il sapone.
Zebulon
Fonctionne à 1200 bauds
Fonctionne à 1200 bauds
Messages : 569
Enregistré le : 28 juin 2022 10:21

Re: MPO n°112 : fonction récursive

Message par Zebulon »

Hé oui le Basic n'est effectivement pas doué pour la récursivité. Pour cela il faut simuler une pile. Mais une pile ne suffit pas. Il faut aussi que le code puisse être ré-entrant.

Antoine a fait très fort avec 84 pas de programme et pour son premier message. Bienvenue à lui. :wink:
Avatar du membre
C.Ret
Fonctionne à 9600 bauds
Fonctionne à 9600 bauds
Messages : 3400
Enregistré le : 31 mai 2008 23:43
Localisation : N 49°22 E 6°10

Re: MPO n°112 : fonction récursive

Message par C.Ret »

Ah! Oui! Hier soir, il devait faire trop chaud, je n'ai pas vu qu'Antoine postait son premier message.

Bienvenue Antoine.
Ton code n'est pas en Basic, mais il m'inspire bien et mes doigts me chatouillent de taper une Expression Algébrique pour une SHARP EL-5150.

Sinon, ce MPO est finalement bien trop facile, surtout en BASIC j'ai une solution irréprochable pour SHARP PC-1211 en 21 octets n'utilisant aucun registre.
MPO 112  - Basic SHARP PC-1211 (21 octets).gif
MPO 112 - Basic SHARP PC-1211 (21 octets).gif (10.74 Kio) Vu 2976 fois
SHARP PC-1211 PC-1360 EL-5150 PC-E500 | Commodore C=128D | Texas Instruments Ti-57LCD Ti-74BASICalc Ti-92II Ti-58c Ti-95PROCalc Ti-30XPROMathPrint | Hewlett-Packard HP-28S HP-41C HP-15C HP-Prime HP-71B | CASIO fx-602p | NUMWORKS | Graphoplex Rietz Neperlog | PockEmul | Sommaire des M.P.O. | Ma...dov'il sapone.
Avatar du membre
badaze
Fonctionne à 14400 bauds
Fonctionne à 14400 bauds
Messages : 8372
Enregistré le : 12 févr. 2007 18:36
Localisation : Pas très loin de Lyon
Contact :

Re: MPO n°112 : fonction récursive

Message par badaze »

Bravo !
Tout est bon dans le pocket.
Moi j'aime tout.... Casio, HP, Sharp, TI et les autres sauf que les TI semblent ne pas m'aimer :(
http://www.emmella.fr
Mes Casio - HP - Sharp - TI
Homme invisible.
FLISZT
Fonctionne à 1200 bauds
Fonctionne à 1200 bauds
Messages : 655
Enregistré le : 09 mars 2022 19:14

Re: MPO n°112 : fonction récursive

Message par FLISZT »

Bonjour Antoine et bienvenue à toi !

Voici un symbole (Unicode : U+25E2) qui te sera sûrement utile par la suite :



PS : sur mon ordi (Ubuntu) je saisi CTRL+SHIFT+u puis les chiffres et / ou les lettres (hexa) nécessaires.
Bruno
Sanyo CZ-0124 ? TI-57 ? HP-15C ? Canon X-07 + XP-140 Monitor Card ? HP-41CX ? HP-28S ? HP-50G ? HP-50G
Avatar du membre
gege
Fonctionne à 14400 bauds
Fonctionne à 14400 bauds
Messages : 7141
Enregistré le : 31 janv. 2008 14:24
Localisation : Banlieue Paârisienne
Contact :

Re: MPO n°112 : fonction récursive

Message par gege »

Bonjour,
C'est pas beau de tricher !!
Et je crois que pour une fois ce n'est pas C.ret qui a tué le jeu...

Ma version (140 octets) utilise un emboîtement de GOSUB, sur X07 :
10 INPUT N:GOSUB 20:PRINT U:END
20 IF 1=N THEN U=7:RETURN
30 M=N/2:IF M=INT(M) THEN 50
40 N=M-.5:GOSUB 20:U=2*U-1:RETURN
50 N=M:GOSUB 20:U=3*U:RETURN
Sur cette machine, pas de limite au nombre d'appels de GOSUB... ;-)
G.E.

Ah zut je vois un moyen de gratter 5 octets
Avatar du membre
C.Ret
Fonctionne à 9600 bauds
Fonctionne à 9600 bauds
Messages : 3400
Enregistré le : 31 mai 2008 23:43
Localisation : N 49°22 E 6°10

Re: MPO n°112 : fonction récursive

Message par C.Ret »

Zebulon a écrit : 05 août 2022 09:55Hé oui le Basic n'est effectivement pas doué pour la récursivité.
En réalité, il y a une autre exception à cette réglé très commune car vérifiée sur la plupart des pockets sauf les quelques cas spéciaux comme le CANON X07 au nombre de GOSUB non limité.

On peut programmer directement la définition de la suite sans se poser de question:
Image

Code : Tout sélectionner

CAT       MPO112         BASIC       94     08/03/22 22:55
LIST      1 INPUT N @ DISP N;FNU(N)
          10 DEF FNU(N)
          20 IF N=1 THEN FNU=7 ELSE IF MOD(N,2) THEN FNU=2*FNU(IP(N/2))-1 ELSE FNU=3*FNU(N/2)
          30 END DEF
RUN       ? 2^24-1 [END LINE]          16777215  50331649
CONT      ? 574    [END LINE]          574  18051
La définition aux lignes 10~30 ce fait de façon récursive sans aucune difficulté outre le fait qu'il faille veiller à ce que N/2 soit arrondi à un entier lorsque N est impair.
On remarquera que la structure de ce code est exactement celle utilisée par notre ami gégé sur son gros CANON à la différence notable cependant qu'il n'y a pas d'enchevêtrement de numéro de ligne ni de spaghettis de GOSUB et GOTO !! ( :mrgreen: backward references inside :mrgreen: )

Comme pour le CANON X07, la profondeur d'appels récursifs d'une fonction utilisateur d'un Hewlett-Packard HP-71B n'est limitée que par la mémoire disponible dans le block principal. Et comme sur cette machine, il est très courant d'avoir un ou plusieurs blocks mémoire d'extension secondaires où sont stockés les fichiers contenant les programmes. On arrive aujourd'hui à des configurations de plusieurs méga-octets (cf. FRAM71 et autres extensions à la mode dopant ce pauvre pocket des années 1985.

Mon code ci-dessus comporte deux parties; outre la définition de la suite FN U(n) (qui fortuitement est ici récursive), l'autre partie concerne la saisie et l'affichage du résultat. Cette première partie est facultative. L'affichage des résultats pouvant se faire directement en ligne de commande (mais pas dans le mode CALC) en utilisant la syntaxe FNU(574)[END LINE].

Il existe des machines basées sur un environnement interactif plus évolué que les pockets BASIC qui fonctionnent directement et naturellement sur ce mode d'évaluation directe. Ce qui les rend encore plus efficaces et puissantes. Sans surprise, la première d'entre-elles est le HP-28S. Cette machine ont été conçue par les développeurs du HP-71B.

Code : Tout sélectionner

U:
« DUP 2 / IP → n k
   « n 2 MOD
     « k 
       « k U 2 * 1 - »
       « 7 »
       IFTE »
     « k U 3 * »
     IFTE » »
Quintessence de la récursivité, non seulement le principe du calcul est récursif (U s'appelle elle-même), mais de plus U est un programme composé de programmes. C'est pour cela que je trouve étrange la traduction de RPL en Reverse Polish Lisp (pourtant donné dans une interview par un des créateur de ce système). Pour moi, RPL correspond plus volontiers à Recursive Programming Language.

Ou plus algébriquement:

Code : Tout sélectionner

U:« → n 'IFTE(n==1 , 7 , IFTE( MOD(n,2) , 2*U(IP(n/2))-1 , 3*U(n/2) ))' »
Ou pour un MPO:

Code : Tout sélectionner

U:« IF DUP 1 > THEN DUP 2 MOD 3 OVER - ROT 2 / IP U * SWAP - ELSE DROP 7 END » 
Cette version est dédié à marge qui, à juste titre, adore ce genre de cryptoprogramme.


Et ma version préférée pour ce pocket éminemment symbolique:

Code : Tout sélectionner

U: « DUP 2 / IP → n k « k « n 2 MOD 3 OVER - 'x' * SWAP - 3 k U EXSUB » 7 IFTE » »
1 U affiche 7
9 U affiche '2*(3*(3*7))-1'
99 U affiche '2*(2*(3*(3*(3*(2*7-1))))-1)-1'
574 U affiche '3*(2*(2*(2*(2*(2*(3*(3*(3*7)))-1)-1)-1)-1)-1)' puis EVAL renvoie 18051
Pour obtenir les valeurs numériques faire EVAL ou →NUM.

badaze a écrit : 05 août 2022 19:09Bravo !
C'est pas bien de m'encourager dans le vice, en gage badaze va devoir nous présenter une version en BASIC pour Texas Instruments. Je sais , je suis dur mais injuste, les Ti ne l'aiment pas.

antoine a écrit : 04 août 2022 10:42 je propose pour cet exercice une solution pour fx4000P qui tient en 84 pas :

Code : Tout sélectionner

?->A:0->B:Lbl0:2*Frac(A/2)->D[B]:Int(A/2)->A:B+1->B:A≠1=>Goto0:7->C:Lbl1:C*(3-D[B-1])-D[B-1]->C:DszB:Goto1:Cꙙ
Au risque de me répéter, très bon code. Dommage qu'il soit implémenté sur une CASIO, je vais donc utiliser cet algorithme sur SHARP et faire des étincelles et surtout exploser la limite des 2^24-1.
gege a écrit : 05 août 2022 23:36C'est pas beau de tricher !!
Je ne triche pas, je gruge juste un peu faute d'astuces efficaces...
Mais je ne posterai pas la vraie version immédiatement, laissant à chacun le temps de chercher un peu. Car il y a là une astuce qui rendra la programmation de cette suite extrêmement facile sur toute calculatrice programmable...
Modifié en dernier par C.Ret le 06 août 2022 09:37, modifié 4 fois.
SHARP PC-1211 PC-1360 EL-5150 PC-E500 | Commodore C=128D | Texas Instruments Ti-57LCD Ti-74BASICalc Ti-92II Ti-58c Ti-95PROCalc Ti-30XPROMathPrint | Hewlett-Packard HP-28S HP-41C HP-15C HP-Prime HP-71B | CASIO fx-602p | NUMWORKS | Graphoplex Rietz Neperlog | PockEmul | Sommaire des M.P.O. | Ma...dov'il sapone.
Zebulon
Fonctionne à 1200 bauds
Fonctionne à 1200 bauds
Messages : 569
Enregistré le : 28 juin 2022 10:21

Re: MPO n°112 : fonction récursive

Message par Zebulon »

Bravo ce programme est à la fois génial et le nouvel parfait exemple de ce pourquoi le basic est une atrocité : la programmation spaghetti. :D

Il fonctionne très bien sur mon FX-880P qui n'a semble-t-il pas non plus de "limite" aux appels de GOSUB même si on est bien d'accord qu'il y a une limite qui est celle de la mémoire de l'appareil.

EDIT tu as posté juste avant ma réponse C.Ret.
Avatar du membre
gege
Fonctionne à 14400 bauds
Fonctionne à 14400 bauds
Messages : 7141
Enregistré le : 31 janv. 2008 14:24
Localisation : Banlieue Paârisienne
Contact :

Re: MPO n°112 : fonction récursive

Message par gege »

Bonjour,
Bien d'accord c'est enchevêtré mais franchement, est-ce illisible ? On voit bien les trois cas...

J'aime bien la simplicité sans tableau ni définition de fonctions réservée à un Basic de luxe.
Mais vos solutions sont super quand même !

En comprimant le programme sur X07 on tombe à 90 octets :
1 INPUTN:GOSUB2:PRINTU:END
2 IF 1=N THENU=7:RETURN
3 M=N/2:N=INT(M):IF M=N THEN5
4 GOSUB2:U=2*U-1:RETURN
5 GOSUB2:U=3*U:RETURN

Grattons les octets...
G.E.
Modifié en dernier par gege le 06 août 2022 10:25, modifié 1 fois.
Avatar du membre
C.Ret
Fonctionne à 9600 bauds
Fonctionne à 9600 bauds
Messages : 3400
Enregistré le : 31 mai 2008 23:43
Localisation : N 49°22 E 6°10

Re: MPO n°112 : fonction récursive

Message par C.Ret »

gege a écrit : 05 août 2022 23:36Ah zut je vois un moyen de gratter 5 octets
On peut gagner un peu plus que 5 octets:

Code : Tout sélectionner

1 INPUT N:GOSUB 2:PRINT U:END
2 A=N:N=INT(N/2):IF A=1 THEN U=7:RETURN
3 IF 2*N=A THEN GOSUB 2:U=3*U:RETURN
4 GOSUB 2:U=2*U-1:RETURN
L'astuce avec les spaghettis c'est de mettre une noix de beurre, un peu de sauce à la tomate et un brin de basilic comme cela chaque bouchée glisse mieux dans le gosier.

Et les trois cas sont au moins aussi lisibles que dans le code original !
Modifié en dernier par C.Ret le 06 août 2022 10:46, modifié 1 fois.
SHARP PC-1211 PC-1360 EL-5150 PC-E500 | Commodore C=128D | Texas Instruments Ti-57LCD Ti-74BASICalc Ti-92II Ti-58c Ti-95PROCalc Ti-30XPROMathPrint | Hewlett-Packard HP-28S HP-41C HP-15C HP-Prime HP-71B | CASIO fx-602p | NUMWORKS | Graphoplex Rietz Neperlog | PockEmul | Sommaire des M.P.O. | Ma...dov'il sapone.
Avatar du membre
gege
Fonctionne à 14400 bauds
Fonctionne à 14400 bauds
Messages : 7141
Enregistré le : 31 janv. 2008 14:24
Localisation : Banlieue Paârisienne
Contact :

Re: MPO n°112 : fonction récursive

Message par gege »

Bonjour,
Ah ah on s'est croisés !

Sut TI74, on n'a que 5 niveaux d'appels de GOSUB je crois, et les fonctions récursives sont interdites...
Il va falloir faire la technique du tableau d'antoine.
GO

G.E.
Avatar du membre
C.Ret
Fonctionne à 9600 bauds
Fonctionne à 9600 bauds
Messages : 3400
Enregistré le : 31 mai 2008 23:43
Localisation : N 49°22 E 6°10

Re: MPO n°112 : fonction récursive

Message par C.Ret »

Tableau d'antoine ? Ou astuce de badaze ??
SHARP PC-1211 PC-1360 EL-5150 PC-E500 | Commodore C=128D | Texas Instruments Ti-57LCD Ti-74BASICalc Ti-92II Ti-58c Ti-95PROCalc Ti-30XPROMathPrint | Hewlett-Packard HP-28S HP-41C HP-15C HP-Prime HP-71B | CASIO fx-602p | NUMWORKS | Graphoplex Rietz Neperlog | PockEmul | Sommaire des M.P.O. | Ma...dov'il sapone.
Répondre

Retourner vers « Tous les Pockets »