« Suite de Conway » : différence entre les versions
Contenu supprimé Contenu ajouté
m 1 version depuis w:Suite de Conway |
Aucun résumé des modifications |
||
Ligne 1 :
{{feuille volante}}
{{Wikipédia}}
== Générer la suite de Conway avec des [[Langage de programmation|langages de programmation]] ==
[[Image:Fonction Conway.png|thumb|upright=1.5|La fonction <code>conway()</code> représentant la suite de Conway]]
=== Avec le [[PHP]] ===
<div class="exemple">
<source lang="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
?>
</source>
</div>
=== 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 :
<div class="exemple">
<source lang="c">
#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;
}
</source>
</div>
=== En [[Haskell]] ===
<div class="exemple">
<source lang="haskell">
import Data.List
conway = iterate step [1] where
step l = [f x | x <- group l, f <- [length,head] ]
main = print . take 10 $ conway
</source>
</div>
=== En [[Perl (langage)|Perl5]] ===
<div class="exemple">
<source lang="perl">
for ( $_=1;; ) { say; s/((.)\2*)/length($1).$2/xeg; }
</source>
</div>
ou depuis le shell:
<div class="exemple">
<source lang="bash">
perl -E 'for ( $_=1;; ) { say; s/((.)\2*)/length($1).$2/xeg; }'
</source>
</div>
=== En [[Python (langage)|Python]] ===
<div class="exemple">
<source lang="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()
</source>
</div>
=== En [[Prolog]] ===
<div class="exemple">
<source lang="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).
</source>
</div>
=== En [[Ocaml]] ===
<div class="exemple">
<source lang="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
</source>
</div>
=== En [[Java (langage)|Java]] ===
<div class="exemple">
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 })
<source lang="java">
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);
}
}
</source>
</div>
== Références ==
{{Références}}
=== Liens externes ===
* {{en}} [http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A005150 Suite A005150] sur l'[[Encyclopédie en ligne des suites de nombres entiers]]
* {{en}} [[Eric W. Weisstein]], « [http://mathworld.wolfram.com/LookandSaySequence.html Look and Says Sequence] », sur [[MathWorld]]
* {{en}} Henry Bottomley, « [http://www.btinternet.com/~se16/js/lands2.htm Evolution of Conway's 92 Look and Say audioactive elements] » : une compilation des 92 éléments « audioactifs » de la suite
| |||