Suite de Conway

Cette page est une feuille volantelink={{{link}}}

Il faudrait la ranger dans un wikilivre où elle aurait sa place.

Générer la suite de Conway avec des langages de programmationModifier

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

Avec le PHPModifier

 <?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 CModifier

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 HaskellModifier

  import Data.List

  conway = iterate step [1] where
    step l = [f x | x <- group l, f <- [length,head] ]

  main = print . take 10 $ conway

En Perl5Modifier

    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 PythonModifier

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 PrologModifier

  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 OcamlModifier

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 JavaModifier

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érencesModifier

Liens externesModifier

 

Wikipédia propose un article sur : « Suite de Conway ».