Misez p'tit, Optimisez - N°38 (comptez les 1 2 3 4 5)

[dprtl]

Bonjour,

En ce dimanche de février, pas très ensoleillé en Alsace, je me lance sur la rédaction mon premier MPO. Soit la matrice de dimension Nx2 suivante :

Code : Tout sélectionner

[ 1  2  3  ... N  ]
[ n1 n2 n3 ... nN ]

La première ligne contient des valeurs constantes. La deuxième ligne contient N variables ; ce sont des nombres entiers compris entre 1 et N. Le but est d'écrire un programme qui permet de trouver les valeurs de n1 à nN, telles que :

n1 = le nombre de nombres 1 sur l'ensemble de la matrice Nx2
n2 = le nombre de nombres 2 sur l'ensemble de la matrice Nx2
...
nN = le nombre de nombres N sur l'ensemble de la matrice Nx2

Avec la donnée N en entrée unique, votre programme doit permettre de trouver la solution (ou l'absence de solution) pour une matrice de dimension Nx2 quelconque, jusqu'à N=6 au minimum ; ou plus loin, si votre calculette le permet.

Par exemple, pour N=5, la solution est la suivante :

Code : Tout sélectionner

[ 1  2  3  4  5 ]
[ 3  2  3  1  1 ]

Le format d'affichage de la solution complète est libre ; de même que le codage de l'absence de solution (proposer un affichage optimal, en fonction des possibilités de chaque machine). L'affichage de la première ligne de la matrice (valeurs constantes) est facultatif. L'affichage des autres solutions (s'il y en a plusieurs ?!) est facultatif.

Dernière bricole : l'usage des tables pré-calculées est interdit ; sauf celles qui sont présentes dans la ROM des calculatrices. Par contre, pour optimiser le temps de calcul, on peut s'abstenir de re-calculer certaines valeurs triviales. Par exemple, nN semble toujours être égal à 1 dans les solutions. Avec des règles trop complexes, attention à ne pas faire exploser la taille du programme.

Vu le niveau observé dans les MPO précédents, je ne doute pas que vous allez trouver rapidement un algorithme très efficace, et réussir à l'implémenter de manière optimale sur vos pockets et calculatrices (ou ordinateurs anciens à la rigueur).

Bon courage

Pour d'autres énoncés de MPO, tous plus agaçants et passionnants les uns que les autres, consultez le sommaire des MPO.

[dprtl]

Pour le classement final des programmes et des machines simultanément, je propose la formule suivante :

Bogonote = round(K1*(2013-A)/F/T + K2/B + K3/R)

K1 = 200
A = Année de production de la machine (plus elle est ancienne, plus la bogonote est avantageuse)
F = Fréquence du CPU en MHz
T = Temps d'éxécution du programme pour N=5 en secondes (minimum = 1 seconde). Dans le cas où ce temps serait variable (ex : usage de variables aléatoires), on prendra un temps moyen sur un nombre significatif d'éxécutions chronométrées.
K2 = 2000
B = taille totale du programme en octets + nombre de variables + nombre de registres utilisés (pour N=5)
K3 = 40
R = Rang de publication de l'article dans le forum. Une mise à jour éventuelle du programme (edit sur le même article) dégradera ce rang. Vous pouvez bien-sûr publier plusieurs versions successivement, et votre première version, moins optimisée en général, sera avantagée.

Exemple fictif : une HP-15C sortie en 1982 (A), dont le CPU est cadencé à 0,220 MHz (F), qui mettrait 480s (T) à résoudre le problème pour N=5, avec 39 octets en taille de programme + 4 registres (soit B=43), publié en 4ème position (R), aurait une bogonote de 115.

Après quelques ajustements, et même si elle n'est pas parfaite, je bloque la formule

Classement :
1er - proposition 1 de Gilles59, FX-602P, A=1981, F=0,2, T=1, B=67, R=5, bogonote=32038 !
2e - proposition 2 de C.Ret, HP-28S, A=1986, F=1, T=1, B=157, R=7, bogonote=5418
3e - proposition 3 de bernouilli92, HP-48SX, A=1990, F=2, T=1, B=175, R=6, bogonote=2318
4e - proposition 2 de bernouilli92, HP-48SX, A=1990, F=2, T=2, B=271, R=4, bogonote=1167
5e - proposition 1 de dprtl, PB-700, A=1983, F=0,7, T=17, B=250, R=8, bogonote=517
6e - proposition 1 de bernouilli92, HP-48SX, A=1990, F=2, T=17, B=249, R=3, bogonote=157
7e - proposition 1 d' Okinawok, TI-92, A=1995, F=10, T=5, B=480, R=2, bogonote provisoire=96 (programme non "paramétrique")
8e - proposition 1 de C.Ret, HP-28S, A=1986, F=1, T=600, B=286, R=1, bogonote=56

[Okinawok]

Bonjour,

Joli problème

Juste une petite question car je ne suis pas sûr de bien comprendre le problème

Si la première ligne vaut [5,5,5,5,5] ? Le problème est il soluble ??? C'est à dire que e ne peut valoir 5 (puisqu'il vaut lui même 5, cela en fait un de plus). Alors combien vaut e ? A moins que les variables puissent être supérieures à 5 ?

[dprtl]

Si la première ligne vaut [5,5,5,5,5] ? Le problème est il soluble ???

La première ligne vaut toujours [1,2,3,4,5], elle est constante, ou invariable. Et si la deuxième ligne vaut [5,5,5,5,5] ce n'est pas la solution. Car, dans cette matrice à deux lignes :

[1,2,3,4,5]
[5,5,5,5,5]

Il n'y a pas 5 fois le nombre 1, ni 5 fois le nombre 2, et il y a 6 fois le nombre 5.

[C.Ret]

Première bouture HP-28S - 1 MHz - 1986:

Code : Tout sélectionner

« 
[[ 1  2  3  4  5] 
 [ 3  2  3  1  1]]
 »

79.5 octets
Immédiat (1s).

Edit: un pas deux mille cycles par seconde.

[Okinawok]

PAREIL ! mais sans programmation : on arrive assez vite, sur le papier, à ce résultat en éliminant progressivement les cas impossibles. La somme des constantes (EDIT : variables) vaut forcemment 10. Donc e ne peut valoir que 1. Pour d on arrive également à prouver qu'il ne peut valoir qu'un, c'est un peu plus long.
Après coder tout cela, c'est une autre paire de manche, enfin pour moi
J'attends impatiemment les codes

[Okinawok]

Ben en fait ton problème, c'est le même que les pièces (valant cette fois 1,...,N) et dont la somme doit atteindre 2N ! Avec une contrainte en plus à vérifier ,

EDIT : Non ce n'est pas pareil La contrainte 2N porte sur le nombre de pièces, pas la somme obtenue...

[Okinawok]

C'est du bourrin comme je sais faire sur ma TI-92 J'ai recopié le code à la main alors j'espère n'avoir pas commis d'erreur. La fonction 'compte(x)' compte le nombre de fois que x est présent dans {a,b,c,d,e}. Le programme matrice() donne la solution en 5 secondes approximativement et fait 474 octets (fonction comprise). Je passe sur la Bogonote, désolé.

Alors évidemment, on peut simplifier les boucles : par démonstration mathématique, on montre que e ne peut valoir que 1, idem pour d ... jusqu'à aboutir au résultat directement sur le papier

Code : Tout sélectionner

matrice()
Prgm
1->b:1->c:1->d:1->e
While e<=5
While d<=5
While d<=5
While d<=5
10-b-c-d-e->a
If e=1+compte(5) and d=1+compte(4) and c=1+compte(3) and b=1+compte(2) and
a=1+compte(1) Then
Disp {a,b,c,d,e}
Stop
Endif
b+1->b
EndWhile
1->b
c+1->b
EndWhile
1->b
1->c
d+1->d
EndWhile
1->b
1->c
1->d
e+1->e
EndWhile
EndPrgm

compte(x)
Func
Local i
0->i
If a=x Then
i+1->i
EndIf
If b=x Then
i+1->i
EndIf
If c=x Then
i+1->i
EndIf
If d=x Then
i+1->i
EndIf
If e=x Then
i+1->i
EndIf
Return i
EndFunc

[bernouilli92]

Voici ma solution pour hp48, elle fonctionne également sur hp28s et sûrement sur les hp49 et suivants.

Pour la bogonote, il va falloir attendre ce soir que je l'exécute sur une vraie hp48.

Code : Tout sélectionner

« 0 3124 
  FOR I
    I 1 5
    START
      DUP 5 MOD 1 + SWAP 5 / IP
    NEXT 1 + 
    5 ->LIST 
    -> L 
    « 
      1 DUP DUP2 DUP 5 ->LIST
      1 5
 	  FOR I
         L I GET DUP2 GET 1 + PUT
      NEXT
      IF L ==
      THEN 
        L KILL
      END
    »
  NEXT
»

[dprtl]

Merci beaucoup pour vos premières propositions ! Néanmoins, je m'attendais à des programmes un peu plus travaillés... Surtout pour celui de C.Ret Donc, pour éviter les dérives vers le "trop simple", je vais m'autoriser à modifier légèrement mon énoncé.

Votre travail ne sera pas perdu, et vous conserverez votre rang de publication (1 : C.Ret, 2 : Okinawok, 3 : bernouilli92).

... à condition, bien sûr, que votre nouvelle version de programme réponde au problème modifié

(désolé c'est mon premier MPO, la formulation initiale n'était pas au point !)

[dprtl]

Je vous rassure tout de même sur la faisabilité : ma version actuelle pour PB-1000 répond parfaitement au problème nouvellement formulé et pèse 118 octets + quelques variables. On doit donc pouvoir faire largement mieux !

Réponse pour N=11 obtenue en un temps "raisonnable" :

Code : Tout sélectionner

[ 1 2 3 4 5 6 7 8 9 10 11 ]
[ 8 3 2 1 1 1 1 2 1 1  1  ]

[currybleu]

Hello,
Il semble que ton ennoncé prêt à interpretation.
est-ce que le programme doit trouver une solution? répondre par vrai ou faux? solution ou pas de solution), indiquer toutes les solutions, et sous quel format?
Le plus simple serait que tu prennes un exemple avec par exemple N=7 et que tu affiche le resultat souhaité.

[dprtl]

Il semble que ton ennoncé prêt à interpretation.
est-ce que le programme doit trouver une solution? répondre par vrai ou faux? solution ou pas de solution), indiquer toutes les solutions, et sous quel format?

Je commence à imaginer le calvaire des enseignants qui fabriquent les sujets d'examen, dans lesquels toute ambiguité est interdite

Mes réponses :
- oui, le programme doit afficher la solution, si elle existe, dans un format adapté à la calculette (en plusieurs fois si nécesaire)
- s'il n'y a pas de solution, le programme doit l'indiquer dans un format libre, adapté à la calculette (ex : "1" )
- sur les solutions multiples, pour l'instant, je n'en ai toujours trouvé qu'une seule, quand elle existe. L'affichage de toutes les solutions pour une valeur de N donnée (probablement élevée ?) reste donc facultatif.

[currybleu]

Bon alors je n'ai pas compris l’énoncé car pour moi, une des solution pour chaque matrice peut etre:

[1 2 3 4 5 6 7 8 9]
[1 1 1 1 1 1 1 1 1]

[1 2 3 4 5 6 ]
[1 1 1 1 1 1 ]

[1 2 3 4 5]
[1 1 1 1 1]

[1 2 3 4]
[1 1 1 1]

[Hobiecat]

D'après l'énoncé, on regarde le nombres de 1, 2, 3, 4 et 5 sur l'ensemble de la matrice et pas uniquement sur la première ligne. Tes matrices exemples sont remplies de 1, donc sont fausses, car il y a plusieurs fois 1, et non pas une seule fois.