Suite de Conway - Définition et Explications

Source: Wikipédia sous licence CC-BY-SA 3.0.
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 (Dans l'intonation, les changements de fréquence fondamentale sont perçus comme des variations de hauteur : plus la fréquence est élevée, plus la hauteur perçue est haute et inversement. Chaque voyelle se...) le terme précédent.

Définition

Le premier terme de la suite de Conway (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...) est posé comme égal à 1. Chaque terme de la suite se construit en annonçant le terme précédent, c (Le C++ est un langage de programmation permettant la programmation sous de multiples paradigmes comme la programmation procédurale, la programmation orientée objet et la programmation générique. 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

La fonction conway() représentant la suite de Conway

Avec le PHP (PHP (sigle de PHP: Hypertext Preprocessor), est un langage de scripts libre principalement utilisé pour produire des pages Web dynamiques via un serveur HTTP, mais pouvant également fonctionner comme n'importe quel...)

On peut très facilement avec une fonction récursive (En informatique et en mathématiques, le terme fonction récursive désigne deux concepts liés, mais distincts. Plus généralement les termes « récursif »,...), 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é (Le passé est d'abord un concept lié au temps : il est constitué de l'ensemble des configurations successives du monde et s'oppose au...) en paramètre (Un paramètre est au sens large un élément d'information à prendre en compte pour prendre une décision ou pour effectuer un calcul.) 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 (La main est l’organe préhensile effecteur situé à l’extrémité de l’avant-bras et relié à ce dernier par le poignet....)()       {        	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 (NeXT Computer, Inc (devenue NeXT Software, Inc) était une entreprise d’informatique fondée par Steve Jobs en 1985 après son départ d’Apple.)()      

En Prolog (Prolog est l’un des principaux langages de programmation logique inventé à l'I.N.S.E.A.. Le nom Prolog est un acronyme de PROgrammation LOGique. Il a...)

        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 (Tableau peut avoir plusieurs sens suivant le contexte employé :) 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 (CLASS (CLS) est un célèbre groupe de l'underground informatique. CLASS a cessé son activité le 8 janvier 2004 et en a profité pour...) 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);      	}             }      
Page générée en 0.051 seconde(s) - site hébergé chez Amen
Ce site fait l'objet d'une déclaration à la CNIL sous le numéro de dossier 1037632
Ce site est édité par Techno-Science.net - A propos - Informations légales
Partenaire: HD-Numérique