Suite de Conway

Ajouter des liens
Un livre de Wikilivres.
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 programmation[modifier | modifier le wikicode]

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

Avec le PHP[modifier | modifier le wikicode]

 <?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[modifier | modifier le wikicode]

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[modifier | modifier le wikicode]

  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[modifier | modifier le wikicode]

    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[modifier | modifier le wikicode]

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[modifier | modifier le wikicode]

  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[modifier | modifier le wikicode]

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[modifier | modifier le wikicode]

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[modifier | modifier le wikicode]

Liens externes[modifier | modifier le wikicode]

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

Récupérée de « https://fr.wikibooks.org/w/index.php?title=Suite_de_Conway&oldid=670306 »