Misez p'tit Optimisez n°94 : les nombres de Motzkin

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
C.Ret
Fonctionne à 9600 bauds
Fonctionne à 9600 bauds
Messages : 3405
Enregistré le : 31 mai 2008 23:43
Localisation : N 49°22 E 6°10

Misez p'tit Optimisez n°94 : les nombres de Motzkin

Message par C.Ret »

Image


Le moi dernier, Danny nous proposait dans le fort sympathique MPO93 de calculer la racine digitale d'un nombre de façon récursive.

Dans le même esprit, je vous propose aujourd'hui de composer un code aussi court ou performant que possible permettant de calculer sur nos calculettes et pockets préférés le nombre Mn correspondant au n-ième terme de la série des Nombres de Motzkin.

Le code attendu ne semble présenter aucune difficulté technique, on entre l'indice n et la calculette affiche (ou imprime) le nombre de Motzkin Mn correspondant. Il n'y a rien de compliqué.

Le nombre de Motzkin Mn d'indice n est le nombre de façons de choisir des cordes ne se coupant pas, parmi les cordes reliant n points disposés sur un cercle. Les nombres de Motzkin satisfont la relation de récurrence suivante :

Image

avec Image et Image

Les nombres de Motzkin correspondent à la suite A001006 de l'OEIS et les premiers de ces nombres sont:

Code : Tout sélectionner

Nombres de Motzkin:

   n │    0│    1│    2│    3│    4│    5│    6│    7│    8│    9│   10│  ... 
─────┼─────┼─────┼─────┼─────┼─────┼─────┼─────┼─────┼─────┼─────┼─────┼─────
  Mn │    1│    1│    2│    4│    9│   21│   51│  127│  323│  835│ 2188│  ...
En mathématiques, et plus particulièrement en combinatoire, les nombres de Motzkin forment une suite d'entiers naturels utilisée dans divers problèmes de dénombrement. Ils sont nommés ainsi d'après le mathématicien d'origine allemande Théodore Motzkin (1908-1970). Les nombres de Motzkin ont de nombreuses applications en géométrie, combinatoire et théorie des nombres.
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: Misez p'tit Optimisez n°94 : les nombres de Motzkin

Message par gege »

Bonjour,
Taper la définition directe sur HP Prime fonctionne très bien, c'en est déprimant...
On doit pouvoir faire mieux !
G.E.
Avatar du membre
Danny
Fonctionne à 2400 bauds
Fonctionne à 2400 bauds
Messages : 1248
Enregistré le : 28 déc. 2013 16:34

Re: Misez p'tit Optimisez n°94 : les nombres de Motzkin

Message par Danny »

Tu veux aussi le tracé des arbres / chemins, sur les calcs graphiques ? :D 8)
? Apple, Atari, Canon, Casio, ????????????, HP, Psion, Sharp, Tandy... même TI.
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: Misez p'tit Optimisez n°94 : les nombres de Motzkin

Message par gege »

Bonjour,
Bientôt une version moins "bourrin", mais je regardais une autre suite reliée, qui est le nombre d'appels récursifs de la fonction si on l'écrit trivialement.
Pour motzkin(10) on trouve 4348 appels… Wow
G.E.
Avatar du membre
C.Ret
Fonctionne à 9600 bauds
Fonctionne à 9600 bauds
Messages : 3405
Enregistré le : 31 mai 2008 23:43
Localisation : N 49°22 E 6°10

Re: Misez p'tit Optimisez n°94 : les nombres de Motzkin

Message par C.Ret »

Danny a écrit : 08 juil. 2020 09:56Tu veux aussi le tracé des arbres / chemins, sur les calcs graphiques ? :D 8)
Ce n'est pas interdit de le faire, mais je ne le demande pas. L'idée est d'optimiser et rendre le code efficace pour calculer les valeurs de Mn avec des n allant jusqu'à quelques dizaines seulement (si cela est possible).
Parcourir toutes les combinaisons en les comptant est certainement possible mais cette méthode doit être plus longue et plus complexe qu'un simple calcul.
gege a écrit : 08 juil. 2020 16:55 [...]Pour motzkin(10) on trouve 4348 appels… Wow
G.E.
Ah? J'avais cru lire dans ton premier message que tout se passait bien sur HP Prime ??


C'est comme je disais dans mon intro, rien ne parait compliqué. Un simple calcul à programmer !

Sur HP Prime, j'utilise l'Application SEQUENCE où j'indique de commencer à n=0, donne les deux valeurs initiales et la formule donnant U1(N+2):
MPO94 HP Prime Motzkin Sequence Definition.png
MPO94 HP Prime Motzkin Sequence Definition.png (16.85 Kio) Vu 10750 fois
Puis une pression sur la touche NUM me donne le tableau des valeurs :
MPO94 HP Prime Motzkin Numbers 0 to 12.png
MPO94 HP Prime Motzkin Numbers 0 to 12.png (11.89 Kio) Vu 10750 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
Danny
Fonctionne à 2400 bauds
Fonctionne à 2400 bauds
Messages : 1248
Enregistré le : 28 déc. 2013 16:34

Re: Misez p'tit Optimisez n°94 : les nombres de Motzkin

Message par Danny »

Quand on développe l’expression

Image

on voit qu’il y a une symétrie sympa, qui devrait logiquement permettre de réduire par 2 le nombre de calculs par rapport à l’algo de bourrin... reste à trouver comment faire :| :mrgreen:
? Apple, Atari, Canon, Casio, ????????????, HP, Psion, Sharp, Tandy... même TI.
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: Misez p'tit Optimisez n°94 : les nombres de Motzkin

Message par gege »

Bonjour,
Sur Prime la puissance est telle que le calcul est quasi-instantané.
On va quand même diviser le temps de calcul par un gros facteur !
Et il serait intéressant de ne pas trop se limiter sur n (pourquoi tant de "n" ??).
G.E.
Avatar du membre
Danny
Fonctionne à 2400 bauds
Fonctionne à 2400 bauds
Messages : 1248
Enregistré le : 28 déc. 2013 16:34

Re: Misez p'tit Optimisez n°94 : les nombres de Motzkin

Message par Danny »

Bon j’ai un algo itératif sur HP 42S qui a besoin de 20 boucles pour trouver M(10), 90 boucles pour trouver M(20), 210 pour M(30)...
? Apple, Atari, Canon, Casio, ????????????, HP, Psion, Sharp, Tandy... même TI.
Avatar du membre
C.Ret
Fonctionne à 9600 bauds
Fonctionne à 9600 bauds
Messages : 3405
Enregistré le : 31 mai 2008 23:43
Localisation : N 49°22 E 6°10

Re: Misez p'tit Optimisez n°94 : les nombres de Motzkin

Message par C.Ret »

Wow bien, j'ai un code de 24 pas sur HP-15C qui calcule M10 M20 et M30 en respectivement cinq, dix et quinze tours de boucle utilisant les Nombres de Catalan.

Image

En fait, je n'ai pas de code courts et efficace avec la définition des Nombres de Motzkin que j'ai donné en introduction. J'utilise d'autres équations, elles aussi récursives ou itératives, mais qui ne nécessitent pas une formule 1. Il n'y a que les babasses d'aujourd'hui pour réaliser les 4348 appels emboités en un temps raisonnable pour afficher M10.

Oui, je sais, c'est pas bien de mettre tout le monde sur une fausse piste dès l'intro du MPO, mais ce n'est pas la première fois que je joue ce vilain tours. :twisted:

En tout cas, je suis impatient que Danny nous présente son code, il doit y avoir une ruse que je n'ai pas trouvée.
Modifié en dernier par C.Ret le 10 juil. 2020 06:13, 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
Danny
Fonctionne à 2400 bauds
Fonctionne à 2400 bauds
Messages : 1248
Enregistré le : 28 déc. 2013 16:34

Re: Misez p'tit Optimisez n°94 : les nombres de Motzkin

Message par Danny »

« Ta ruse avec les nombres de Catalan est aussi grosse que la mienne »

Image
? Apple, Atari, Canon, Casio, ????????????, HP, Psion, Sharp, Tandy... même TI.
Avatar du membre
C.Ret
Fonctionne à 9600 bauds
Fonctionne à 9600 bauds
Messages : 3405
Enregistré le : 31 mai 2008 23:43
Localisation : N 49°22 E 6°10

Re: Misez p'tit Optimisez n°94 : les nombres de Motzkin

Message par C.Ret »

Et, la ruse que j'utilise sur HP-15C est celle adaptée aux machines qui ont la possibilité de calculer les coefficients binomiaux en une seule instruction C x,y ou COMB .

J'ai sur mon sabre laser d'autres ruses que j'adapte aux capacités des machines plus BASIC et autres systèmes quatre opérations * / - +.

Image
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
Danny
Fonctionne à 2400 bauds
Fonctionne à 2400 bauds
Messages : 1248
Enregistré le : 28 déc. 2013 16:34

Re: Misez p'tit Optimisez n°94 : les nombres de Motzkin

Message par Danny »

En effet, grâce aux nombres espagn... euh de Catalan j'ai pu faire une version semblable à celle de C.Ret 8)
En 32 pas par contre, mais il doit y avoir moyen d'optimiser ça avec de l'arithmétique de pile et peut-être d'autres subtilités qui m'auraient échappé :)
? Apple, Atari, Canon, Casio, ????????????, HP, Psion, Sharp, Tandy... même TI.
Avatar du membre
C.Ret
Fonctionne à 9600 bauds
Fonctionne à 9600 bauds
Messages : 3405
Enregistré le : 31 mai 2008 23:43
Localisation : N 49°22 E 6°10

Re: Misez p'tit Optimisez n°94 : les nombres de Motzkin

Message par C.Ret »

Oui, l'économie majeure de cet algorithme est de profiter de la répétition des arguments 2k. Je jongle un peu avec la pile et un LASTx bien placé pour enchainer les deux déterminations binomiales.

Image

Mon premier code faisait aussi dans les 35-37 pas, jusqu'à ce que je pense à deux astuces supplémentaires :
- ne pas calculer Image mais utiliser la valeur 2k que l'on utilise pour les deux coefficients binomiaux et la comparer à n afin de limiter le nombre d'itérations pour le calcul de la somme.
- incrémenter k au milieu de la boucle afin d'avoir immédiatement le diviseur Image


J'ai alors plusieurs codes de longueurs identiques qui ne varient que de la façon dont j'entre et sort de la boucle de sommation, un de plus lisible utilise les registres R0 et R1 pour mémoriser respectivement n et k. La sommation se fait dans la pile. L'argument n doit être présent en x: et à l'issue du calcul y: contient n et x: contient le nombre de Motzkin Mn.
MPO94 - HP15C Motzkin Numbers (v1).gif
MPO94 - HP15C Motzkin Numbers (v1).gif (65.78 Kio) Vu 10648 fois
L'instruction n° 013 (PAUSE) n'est jamais exécutée, c'est en réalité une NOP qui est systématiquement skippée par l'instruction ISG 1 précédente.
Je sens que je vais avoir les associations de défense des instructions délaissées et martyrisées sur le DOS :(

P.S.: Mince, je viens de me rendre compte que les Nombres de Catalan ne sont pas hispaniques mais belges:
La suite de Catalan fut décrite pour la première fois au xviiie siècle par Leonhard Euler, qui s'était intéressé au dénombrement des différentes façons de partager un polygone en triangles. La suite est nommée ainsi en l'honneur de Eugène Charles Catalan, qui découvrit la relation avec le parenthésage d'expressions pendant son étude du problème des tours de Hanoï.

La première publication sur ces nombres est due à Segner et ils prennent alors le nom de nombres de Segner. Eugène Charles Catalan fit le lien avec le nombre d'expressions « parenthésées » et le nom de Catalan remplaça celui de Segner. L'astuce de comptage des mots de Dyck fut trouvée par Désiré André en 1887.
Eugène Charles Catalan, né le 30 mai 1814 à Bruges et mort le 14 février 1894 à Liège, est un mathématicien franco-belge, spécialiste de la théorie des nombres.
Mince alors utiliser une calculette sans parenthèse pour déterminer à l'aide des Nombres de Catalan, le nombre d'expression parenthésées Mn c'est un comble :tongue: :tongue:
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
C.Ret
Fonctionne à 9600 bauds
Fonctionne à 9600 bauds
Messages : 3405
Enregistré le : 31 mai 2008 23:43
Localisation : N 49°22 E 6°10

Re: Misez p'tit Optimisez n°94 : les nombres de Motzkin

Message par C.Ret »

gege a écrit : 08 juil. 2020 20:02 [...]Sur Prime la puissance est telle que le calcul est quasi-instantané.[...]
Au secours gégé, je crois que mon HP Prime est cassée ! Je n'ai réussi à utiliser la définition multi-récurrente de Mn qu'avec l'aide de l'Application SEQUENCE. Je n'arrive à rien en entrant la définition directement en mode CAS !!

Comment as-tu fais ?

Lorsque je définis les Nombres de Motskin mz(n) de la façon suivante:
MPO94 HP Prime direct Motzkin Numbers definition.png
MPO94 HP Prime direct Motzkin Numbers definition.png (10.46 Kio) Vu 10642 fois
J'obtient un message indiquant "mz: recursive definition", tout marche bien pour évaluer mz(0) et mz(1).
par contre dès mz(2) l'HP Prime se bloque et ne donne aucun résultat (plante ?) :( :(

J'ai oublié quelque chose ?
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: Misez p'tit Optimisez n°94 : les nombres de Motzkin

Message par gege »

Bonjour,
Je ne sais pas, n'étant pas aussi subtil, j'ai juste tapé une fonction.
A noter que dans les paramètres du CAS page 2 la valeur de "Evaluation récursive" peut être augmenté sans limite (il me semble).

La fonction récursive très bête :

Code : Tout sélectionner

EXPORT motzkin(n)
BEGIN
LOCAL j;
IF n<2 THEN RETURN 1;END;
RETURN motzkin(n-1)+Σ(motzkin(j)*motzkin(n-j-2),j,0,n-2);
END;
Avec une boucle cela donne :

Code : Tout sélectionner

EXPORT motzkin2(n)
BEGIN
LOCAL j,k,m;
{1,1}►m;FOR j FROM 2 TO n DO
m[j]+Σ(m[k+1]*m[j-k-1],k,0,j-2)►m[j+1]
END;RETURN m[n+1];
END;
La version à boucle est rapide, permettant de calculer le 260ème nombre de Motzkin en 7 secondes (c'est environ 3.9e120).
Et vos versions ?
(non la valeur 260 n'est pas prise au hasard)
G.E.
Répondre

Retourner vers « Tous les Pockets »