Suite de Conway

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
 $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 programme écrit en C qui affiche les n premiers termes de la suite de Conway, n étant passé en ligne de commande :

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int main(int argc, char **argv)
{
	const int nb_terms = argc > 1 ? atoi(argv[1]) : 10;
	int max_length = 1024;
	char *s1 = malloc(max_length), *s2 = malloc(max_length);
	strcpy(s1, "1");
	for (int i = 0; i < nb_terms; ++i) {
		puts(s1);
		if (strlen(s1) > max_length / 2) {
			max_length *= 2;
			s1 = realloc(s1, max_length);
			free(s2); s2 = malloc(max_length);
		}
		s2[0] = 0;
		char *start = s1;
		do {
			char *stop = start + 1;
			while (*stop == *start) ++stop;
			sprintf(s2, "%s%td%c", s2, stop - start, *start);
			start = stop;
		} while (*start);
		strcpy(s1, s2);
	}
	free(s1); free(s2);
	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

let rec suivant c l e = match l with
    | [] -> [c; e]
    | t::q when t = e -> suivant (c + 1) q t
    | t::q -> c::e::(suivant 1 q t)
    
let conway n =
    let rec aux n l =
        print_newline (List.iter print_int l);
        if n > 1 then aux (n - 1) (suivant 1 (List.tl l) (List.hd l)) in
    aux n [1]

let () = conway 10

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 org.wikibooks.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);
	}

}

Références

Liens externes

• (anglais) Suite A005150 sur l'Encyclopédie en ligne des suites de nombres entiers
• (anglais) Eric W. Weisstein, « Look and Says Sequence », sur MathWorld
• (anglais) Henry Bottomley, « Evolution of Conway's 92 Look and Say audioactive elements » : une compilation des 92 éléments « audioactifs » de la suite