Suite de Conway - Définition
La liste des auteurs de cet article est disponible ici.
Introduction
La suite de Conway est une suite inventée en 1986 par le mathématicien John Horton Conway, initialement sous le nom de « suite audioactive ». Elle est également connue sous le nom anglais de Look and Say (« regarder et dire »). Dans cette suite, un terme se détermine en annonçant les chiffres formant le terme précédent.
Définition
Le premier terme de la suite de Conway est posé comme égal à 1. Chaque terme de la suite se construit en annonçant le terme précédent, c'est-à-dire en indiquant combien de fois chacun de ses chiffres se répète.
Concrètement :
- X0 = 1
Ce terme comporte juste un « 1 ». Par conséquent, le terme suivant est :
- X1 = 11
Celui-ci est composé de deux « 1 » :
- X2 = 21
En poursuivant le procédé :
- X3 = 1211
- X4 = 111221
- X5 = 312211
- X6 = 13112221
Et ainsi de suite.
Il est possible de généraliser le procédé en prenant un terme initial différent de 1. Dans le reste de l'article, on supposera que ce n'est pas le cas.
Générer la suite de Conway avec des langages de programmation
conway() représentant la suite de ConwayAvec le PHP
On peut très facilement avec une fonction récursive, ou avec les boucles créer la fonction conway() :
$a1 = array('1', '2', '3'); $a2 = array('a', 'b', 'c'); $b1 = array('bbb', 'aaa', 'cc', 'bb', 'aa', 'c', 'b', 'a'); $b2 = array('32', '31', '23', '22', '21', '13', '12', '11'); function conway($n, $str = '1', $i = 0) { // $n: la ligne de la suite de conway à afficher // $i est passé en paramètre lors de la récursivité (appel à la fonction même) // On rend globales les variables $a1, $a2, $b1 et $b2, pour ne pas avoir à les définir à chaque fois. global $a1, $a2, $b1, $b2; if($i < $n) { return conway($n, str_replace($b1, $b2, str_replace($a1, $a2, $str)), ++$i); } else { return $str; } } echo conway(3, $str = '1', $i = 0); // Execution: cela affichera 3 lignes de la suite ?> En C++
Voici un bout de code écrit en C++ permettant d'afficher les n premières lignes de la suite de Conway. L'entier n est lu au clavier :
#include#include using namespace std; template <typename T> inline void echange(T & p1, T & p2) { T tmp; tmp = p1; p1 = p2; p2 = tmp; } int main() { list <int> int_list; list <int> int_list_temp; list <int> * l = &int_list; list <int> * ltemp = &int_list_temp; l->push_back(1); list <int>::iterator iter; int temp = 0; int counter = 0; int n; cin >> n; cout << 1 << endl; for (int i = 1; i < n; ++i) { ltemp->clear(); for (iter = l->begin(); iter != l->end(); counter = 0) { temp = *iter; ++counter; ++iter; while ((iter != l->end()) && (*iter == temp)) { ++counter; ++iter; } cout << counter << temp; ltemp->push_back(counter); ltemp->push_back(temp); } cout << endl; echange(l, ltemp); } return 0; }
En Haskell
import Data.List conway = iterate step [1] where step l = [f x | x <- group l, f <- [length,head] ] main = print . take 10 $ conway
En Perl5
for ( $_=1;; ) { say; s/((.)\2*)/length($1).$2/xeg; }
ou depuis le shell:
perl -E 'for ( $_=1;; ) { say; s/((.)\2*)/length($1).$2/xeg; }'
En Python
import itertools def conway(): x = '1' while True: yield x nx = '' for item, grouper in itertools.groupby(x): nx += '%d%s' % (len(list(grouper)), item) x = nx suite = conway() for i in range(10): print suite.next()
En Prolog
conway(0,[1]). conway(N,R):- N>0, M is N-1, conway(M,L), conwayLigneSuivante(L,R). conwayLigneSuivante([],[]). conwayLigneSuivante([E],[1,E]). conwayLigneSuivante([E,E|L],[M,E|R]) :- conwayLigneSuivante([E|L],[N,E|R]), M is N+1. conwayLigneSuivante([E,F|L],[1,E|R]) :- dif(E,F), conwayLigneSuivante([F|L],R).
En Ocaml
open List let repetitions_au_debut l = let rec ajoute_repetition n x l = if l = [] then (n,x,l) else let (y::l1) = l in if x = y then ajoute_repetition (n+1) x l1 else (n,x,l) in let x::l1 = l in ajoute_repetition 1 x l1 let rec ligne_suivante l = if l = [] then [] else let (n,x,l1) = repetitions_au_debut l in n::x::(ligne_suivante l1) let conway n = let l = ref [1] in for i = 0 to n do iter (fun x -> print_string ((string_of_int x)^" ")) !l; print_string "\n\n"; l := ligne_suivante !l; done ;; conway 30;;
En Java
La classe ConwayTerm représente un terme donné de la suite. Sa méthode nextTerm calcule le terme suivant. Dans l'exemple ci-dessous, le premier terme est 1. Si l'on veut commencer avec 22, il faut un tableau de 2 bytes contenant chacun 2 et non un byte contenant 22 (new byte[] { 2,2 })
package fr.math.suite; import java.util.Arrays; public class ConwayTerm { private byte[] digits; /** * @param args */ public static void main(String[] args) { ConwayTerm term = new ConwayTerm(new byte[] { 1 }); // Premier terme de la suite:1 //Affiche les 25 premiers termes for (int i = 0; i < 25; i++) { System.out.println("u(" + i + ")=" + term); term = term.nextTerm(); } } public ConwayTerm(byte[] digits) { this.digits = digits; } /** * calcule le terme suivant de la suite. */ public ConwayTerm nextTerm() { if (digits.length != 0) { byte count = 1; while ((count < digits.length && digits[0] == digits[count])) count++; return concat(count, digits[0], new ConwayTerm(Arrays.copyOfRange( digits, count, digits.length)).nextTerm()); } else { return this; } } /** * Affiche les chiffres du terme de la suite */ public String toString() { StringBuffer buffer = new StringBuffer(); for (byte b : digits) buffer.append(b); return buffer.toString(); } private ConwayTerm concat(byte count, byte digit, ConwayTerm other) { byte[] result = new byte[2 + other.digits.length]; result[0] = count; result[1] = digit; for (int i = 0; i < other.digits.length; i++) result[i + 2] = other.digits[i]; return new ConwayTerm(result); } }
