Forum TI-Planet.org

Le but de ce défi est de créer une fonction syracuse(u0) qui donne, en sortie, une liste de dimension 3 contenant le nombre d'itérations i tel que après passage de u0 par la suite de Syracuse définie par :



le terme maximal de la suite ainsi que le plus petit indice n tel que . Ces données sont aussi appelées temps de vol, altitude maximale et temps de vol en altitude.

Il va falloir gérer à la fois la longueur de l'algorithme et sa rapidité . En effet, chaque algorithme aura une note. Par exemple, un algorithme de n caractères et qui répond en x secondes pour une entrée u0 aura une note égale à : n*50%+x*log(u0)*50% (le log est utilisé car u0 va être grand aussi, c'est une fonction croissante et donc, plus u0 est grand et plus. Bien entendu les notes seront attribuées en fonction du u0 d'entrée. Un exemple plus concret : un algorithme de 50 caractères qui répond au bout de 2.53 secondes pour u0=10^6 aura une note de 32.59.
Le gagnant sera le créateur de l'algorithme qui possédera le nombre de points le plus faible.

L'algorithme devra être présenté comme celui-ci :

Code: Select all

Define syracuse(u0)=
Func
VOTRECODE
EndFunc


On déterminera la longueur de l'algorithme en comptant le nombre de caractères de VOTRECODE.

NB :

• On entrera un nombre u0 positif.
• Si l'algorithme n'est pas exact (s'il ne sors pas le bon nombre d'itérations), il n'est pas noté est donc son créateur ne concourt pas.
• Le retour à la ligne est considéré comme un caractère (car remplacé par : si le code est en ligne)
• Les espaces ne sont pas comptés (pour l'indentation par exemple)
• La ligne "Local" n'est pas comptée
• Les noms des variables, peu importe leur longueur, auront une longueur de 1 (car d:=1 ou diviseur:=1 revient au même après tout )

Mais, ce n'est pas fini ! À l'aide de cet algorithme vous devrez créer un second qui permettra de trouver le nombre qui possède le plus grand temps de vol entre 1 et 10^7 !
Cette fonction renverra une liste de dimension 2 avec les deux données recherchées : le nombre en entrée et le temps de vol.
Là aussi, vous serez évalué sur la durée et la longueur du programme et vous aurez une seconde note (si le résultat trouvé est juste). La note finale sera donnée par une moyenne des deux notes.

Bonne chance

PS : Mon score au premier algorithme, en ne me cassant pas trop la tête : 79.5771 (avec u0 = 2361235441021745907775 qui correspond au nombre connu aujourd'hui dont le temps de vol est maximal)

--------------------------Scores 1er Algo (avec u0 = 2361235441021745907775)
davidElmaleh : 79.5771
Critor: 57.1198
Bisam : 52.9595
--------------------------Scores 2e Algo

Tu devrais préciser avec quelle Nspire tu testes (ClickPad, TouchPad, CX, logiciel...).

Parce que en ce qui me concerne, ton dernier exemple est instantané sous le logiciel Nspire.

Sous le logiciel, mais j'utilise un script Lua pour mesurer le temps. Mais, en fait, le premier algo est plus orienté sur la longueur de celui-ci. Tandis que le deuxième, sur le temps d'execution

Ah ok, c'est pour ça.
Je n'ai codé que le 1er pour le moment.

L'ennui avec le logiciel, c'est que nous n'aurons pas tous les mêmes temps d'exécution avec le même algo...

Peux-tu me l'envoyer? Comme ca j'évalue ton score..

Cela ne me dérange pas de le publier, et si quelqu'un réussit à l'améliorer tant mieux.
Mais pour le moment, j'aurai du mal à améliorer en performances un algo qui est déjà instantané.

Algo n°1 donc, sauf erreur de ma part:


Code source sans prettyprint afin de mieux compter les caractères:

Code: Select all

Define syracuse(u0)=
Func
   Local i,m,u,n
   0→i
   u0→u
   u→m
   0→n
   While u>1
      piecewise(((u)/(2)),mod(u,2)=0,3*u+1)→u
      If n≤0 and u≤u0
         i-1→n
      If u>m
         u→m
      i+1→i
   EndWhile
   {i,m,n}
EndFunc

(supprimé le return après la capture d'écran)

Algo n°1 corrigé:

Code: Select all

Define syracuse(u0)=
Func
   Local i,m,u,n
   0→i
   u0→u
   u→m
   0→n
   While u>1
      piecewise(((u)/(2)),mod(u,2)=0,3*u+1)→u
      If n≤0 and u≤u0
         i→n
      If u>m
         u→m
      i+1→i
   EndWhile
   {i,m,n}
EndFunc

Score de critor : 57.1198

Comment s'auto-évaluer?

Je prends l'exemple de critor :

• Commençons par compter le nombre de caractère:
  
  • On enlève les lignes "Define..", Func, EndFunc et Local
    
  • On remplace tous les noms des variables par 1 caractère : par exemple u0 devient u
    
  • On supprime les retours à la ligne qu'on remplace par des :
    
• Puis mesurons le temps d’exécution du programme à l'aide du script lua suivant:
  

  Code: Select all

  function on.enterKey()
    local tstart = timer.getMilliSecCounter()
    math.evalStr("syracuse(2361235441021745907775)")
    local tend = timer.getMilliSecCounter()
    print(tend-tstart)
end


Par exemple, pour le script de critor :

Code: Select all

Define syracuse(u0)=
Func
   Local i,m,u,n
   0→i
   u0→u
   u→m
   0→n
   While u>1
      piecewise(((u)/(2)),mod(u,2)=0,3*u+1)→u
      If n≤0 and u≤u0
         i→n
      If u>m
         u→m
      i+1→i
   EndWhile
   {i,m,n}
EndFunc

devient :

Code: Select all

0→i:u→u:u→m:0→n:Whileu>1:piecewise(((u)/(2)),mod(u,2)=0,3*u+1)→u:Ifn≤0andu≤u:i→n:Ifu>m:u→m:i+1→i:EndWhile:{i,m,n}

Donc la longueur de l'algo est de 113 caractères et son temps d'exéction est de 58 ms. Ce qui donne un score de 57.1198

Mon algo est très proche de celui de critor mais un poil plus court (et peut-être même plus rapide) :

Code: Select all

Define syracuse(u0)=
Func
Local u,i,m,p
u0→u
0→i
0→p
u→m
While u>1
  when(mod(u,2)=0,u/2,3*u+1)→u
  If p=0 and u≤u0
    i→p
  If u>m
    u→m
  i+1→i
EndWhile
{i,m,p}
EndFunc

Pour l'algo n°2, j'ai tenté d'éviter d'avoir à dérouler 10 millions de suites.

Pour cela je commence par la valeur initiale la plus élevée et utilise des listes retenant ce que je sais et ce que je ne sais pas sur les temps de vol correspondants à tous les termes rencontrés.

Sur les exemples testés, j'obtiens le temps de vol maximal des n suites en n'en déroulant qu'environ 27%:


Mais hélas, le volume de données nécessaire selon cette implémentation explose rapidement la capacité limite des listes en TI-Basic.