MPO n°112 : fonction récursive
Modérateur : Politburo
- gege
- Fonctionne à 14400 bauds
- Messages : 7147
- Enregistré le : 31 janv. 2008 14:24
- Localisation : Banlieue Paârisienne
- Contact :
MPO n°112 : fonction récursive
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.
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.
Re: MPO n°112 : fonction récursive
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 :
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
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ꙙ
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
- gege
- Fonctionne à 14400 bauds
- Messages : 7147
- Enregistré le : 31 janv. 2008 14:24
- Localisation : Banlieue Paârisienne
- Contact :
Re: MPO n°112 : fonction récursive
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.
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.
- C.Ret
- Fonctionne à 9600 bauds
- Messages : 3419
- Enregistré le : 31 mai 2008 23:43
- Localisation : N 49°22 E 6°10
Re: MPO n°112 : fonction récursive
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:
Mais cela ne l'est pas du tout:
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.
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:
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.
Re: MPO n°112 : fonction récursive
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.
Antoine a fait très fort avec 84 pas de programme et pour son premier message. Bienvenue à lui.
- C.Ret
- Fonctionne à 9600 bauds
- Messages : 3419
- Enregistré le : 31 mai 2008 23:43
- Localisation : N 49°22 E 6°10
Re: MPO n°112 : fonction récursive
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.
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.
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.
- badaze
- Fonctionne à 14400 bauds
- Messages : 8402
- Enregistré le : 12 févr. 2007 18:36
- Localisation : Pas très loin de Lyon
- Contact :
Re: MPO n°112 : fonction récursive
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.
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.
Re: MPO n°112 : fonction récursive
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.
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
Sanyo CZ-0124 ? TI-57 ? HP-15C ? Canon X-07 + XP-140 Monitor Card ? HP-41CX ? HP-28S ? HP-50G ? HP-50G
- gege
- Fonctionne à 14400 bauds
- Messages : 7147
- Enregistré le : 31 janv. 2008 14:24
- Localisation : Banlieue Paârisienne
- Contact :
Re: MPO n°112 : fonction récursive
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
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
- C.Ret
- Fonctionne à 9600 bauds
- Messages : 3419
- Enregistré le : 31 mai 2008 23:43
- Localisation : N 49°22 E 6°10
Re: MPO n°112 : fonction récursive
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:
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
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 !! ( backward references inside )
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 » »
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) ))' »
Code : Tout sélectionner
U:« IF DUP 1 > THEN DUP 2 MOD 3 OVER - ROT 2 / IP U * SWAP - ELSE DROP 7 END »
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 » »
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.
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.
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.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ꙙ
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.
Re: MPO n°112 : fonction récursive
Bravo ce programme est à la fois génial et le nouvel parfait exemple de ce pourquoi le basic est une atrocité : la programmation spaghetti.
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.
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.
- gege
- Fonctionne à 14400 bauds
- Messages : 7147
- Enregistré le : 31 janv. 2008 14:24
- Localisation : Banlieue Paârisienne
- Contact :
Re: MPO n°112 : fonction récursive
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.
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.
- C.Ret
- Fonctionne à 9600 bauds
- Messages : 3419
- Enregistré le : 31 mai 2008 23:43
- Localisation : N 49°22 E 6°10
Re: MPO n°112 : fonction récursive
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
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.
- gege
- Fonctionne à 14400 bauds
- Messages : 7147
- Enregistré le : 31 janv. 2008 14:24
- Localisation : Banlieue Paârisienne
- Contact :
Re: MPO n°112 : fonction récursive
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.
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.
- C.Ret
- Fonctionne à 9600 bauds
- Messages : 3419
- Enregistré le : 31 mai 2008 23:43
- Localisation : N 49°22 E 6°10
Re: MPO n°112 : fonction récursive
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.