La suite de Prouhet-Thue-Morse (appelée souvent suite de Thue-Morse chez les anglo-saxons) est une certaine suite binaire.
Principe
Le principe est simple, schématisé par l'animation ci-contre :
On admet tout d'abord que <math>\(t_0 = 0\)</math>.
Pour trouver <math>\(t_1\)</math>, il faut calculer le complément à un de <math>\(t_0\)</math>, c'est à dire 1.
Ensuite, il suffit de prendre <math>\(t_0\)</math> et mettre son complément à 1 à sa droite pour obtenir <math>\(t_1\)</math>, qui est donc égal à <math>\(01\)</math>. Vous suivez ?
Pour obtenir <math>\(t_2\)</math>, on prend <math>\(t_1\)</math>, et on met à droite le complément à 1 de <math>\(t_1\)</math>. Cela nous donne 0110.
Et ainsi de suite...
L'énoncé est simple : trouver l'algorithme le plus rapide pour générer la ligne n de cette suite.
NB : Comme la suite de Conway, la suite de Prouhet-Morse peut facilement générer un très grand nombre de chiffre et facilement envahir votre console. Vous pouvez donc écrire le résultat dans un fichier grâce à la commande ci-dessous (par candide) :
Il y a un problème dans ta première définition de la suite : tu utilises un indice n de manière ambiguë.
Est-ce qu'il s'agit de l'indice d'un terme de la suite, ou l'indice d'un bit donné sur un terme de la suite ?
J'ai pas regardé l'autre définition, la formule est lâchée un peu gratuitement, j'ai la flemme de regarder.
Edit:
Voilà ma solution, linéaire:
def ptm(n):
if n == 0: return '0'
res, inv = '0', '1'
for _ in xrange(1, n):
res, inv = res + inv, inv + res
return res + inv
>>> for n in xrange(6): print ptm(n)
...
0
01
0110
01101001
0110100110010110
01101001100101101001011001101001
Je pense qu'il y a moyen de travailler directement avec des entiers.
Voilà, une version qui travaille avec des entiers plutôt que des chaines de caractères, ce qui devrait être beaucoup plus efficace en termes de performances (mémoire et temps CPU) en fait non :
def ptm(n):
if n == 0: return '0'
res, inv, off = 0, 1, 1
for _ in xrange(n):
res, inv, off = (res << off) + inv, (inv << off) + res, off * 2
return '0' + bin(res)[2:]
for n in xrange(6):
print ptm(n)
Ce qui est rigolo, c'est que j'ai réfléchi en termes de chaines de bits et que je me suis retrouvé à implémenter indirectement la formule de la seconde définition.
Edit:
Après un petit bench, j'obtiens environ, pour le calcul du 15ème terme de la suite:
0.25 ms pour cette version (int) de la fonction
0.06 ms pour ma première version (chaines de caractères)
7 ms pour la fonction de josmiley
Edit2: à noter que dans cette version de la fonction (avec les entiers), c'est la dernière ligne (la conversion de l'entier en sa représentation binaire) qui bouffe le plus de performances. Le calcul du 15ème terme, en lui-même, prend entre 65 et 70 µs sur ma machine.
def suite(n):
if n == 0:
return [False]
else:
temp = suite(n - 1)
return temp + [not x for x in temp]
Au lieu de 0 et de 1, je renvoie une liste de booléens (la conversion éventuelle devrait être négligeable devant le calcul du n-ème terme, la flemme de vérifier).
timeit me donne un temps de 3.9 ms pour le 15ème terme - je m'attendais à pire.
NoHaR est toujours le premier à trouver l'algo le plus performant ...
je n'avais pas lu les autres réponses,
j'ai mis plusieurs heures après mon premier jet pour en trouver un autre plus performant,
et finalement après lecture, je me suis rendu compte que c'était quasiment le même que dans la première réponse de NoHaR.
ça en est énervant et frustrant ...
Je ne suis pas un pythonien chevronné, ne vous attendez pas à un code remarquable. Le seul avantage de ce code, c'est qu'il n'y a pas à entrer de ligne : "if n == 0: return '0'"
def ptm(n):
i = 0
t = "0"
while n < 0:
n = int(input("Le nombre doit etre positif. Veuillez reessayer s'il vous plait : "))
while i < n:
for j in t:
if j == "0":
t = t[:len(t)] + "1"
else:
t = t[:len(t)] + "0"
i = i + 1
return t
n = int(input("Tapez un entier positif : "))
print ptm(n)
Ce code renvoi une chaine de caractère. Je compte bien sur améliorer ce code : le rendre plus compact, plus propre, et faire en sorte qu'il renvoie un nombre
Si le but est de faire un code plus concis, je pourrais reprendre ma méthode pour apporter cette modification aussi :
def ptm(n):
res, inv = '0', '1'
for _ in xrange(n):
res, inv = res + inv, inv + res
return res
Mais ce code est moins performant que le précédent, car il génère une valeur de "inv" supplémentaire inutilement et utilise 2 fois plus de RAM à cause de ça (et dans le cas de cette suite, ça commence à se faire sentir très vite…).
Edit:
Ah, et tu implémentes aussi l'algo exponentiel…
Par ailleurs, t=t[:len(t)]+'1' peut être remplacé par t+='1'.
Edit2:
Oh, et puis pour le fun, un petit one-liner :
ptm = lambda n, r='0', i='1': r if n == 0 else ptm(n-1, r+i, i+r)
Je trouve que cet exo permet de bien visualiser la relation entre le mode de réflexion d'un programmeur et le langage utilisé. Je pense qu'un codeur C, par exemple, aurait eu naturellement une approche du problème assez différente.
Mon code C pour illustrer mes propos (car je "réfléchis" naturellement en C) :
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
char* suite_ptm (unsigned n)
{
unsigned i,j,k;
char* ret = calloc(1+(k=pow(2,n)), sizeof(char));
ret[0] = '0';
for (i=1; i<k; i*=2)
for (j=i; j<2*i; j++)
ret[j] = ret[j-i] == '0' ? '1' : '0';
return ret;
}
int main (void)
{
int i;
char* s;
for (i=0; i<=6; i++)
puts(s = suite_ptm(i)), free(s);
return 0;
}
Par ailleurs, il est intéressant de remarquer que personne n'a cherché de solution récursive. Je serais curieux de voir comment un programmeur habitué au fonctionnel traiterait l'exercice...
EDIT : solution récursive en C++
#include <iostream>
#include <string>
std::string suite (unsigned n)
{
if (n==0)
return "0";
else
{
std::string s1, s2;
s1 = s2 = suite(n-1);
for (unsigned i=0; i < s2.size(); i++)
s2[i] = (s2[i] == '0' ? '1' : '0');
return s1+s2;
}
}
int main ()
{
for (int i=0; i<=6; i++)
std::cout << suite(i) << std::endl;
return 0;
}
Bonjour,
Par ailleurs, il est intéressant de remarquer que personne n'a cherché de solution récursive. Je serais curieux de voir comment un programmeur habitué au fonctionnel traiterait l'exercice...
Je débute en fonctionnel (Haskell) mais ça me semblait un bon exercice :
import Data.Bits
ptm :: Int -> [Int]
ptm 0 = [0]
ptm n = beginning ++ [x `xor` 1 | x <- beginning]
where beginning = ptm (n - 1)
Ce qui retourne une liste d'entiers. Mais bon, c'est le même code que nax.
× Après avoir cliqué sur "Répondre" vous serez invité à vous connecter pour que votre message soit publié.
× Attention, ce sujet est très ancien. Le déterrer n'est pas forcément approprié. Nous te conseillons de créer un nouveau sujet pour poser ta question.
Python c'est bon, mangez-en.
Python c'est bon, mangez-en.