logo de CoffeeScript

Algorithmique avec CoffeeScript

Pour programmer, cliquer dans le cadre de gauche et modifier (sélection puis Suppr ou taper sous le curseur pour insérer, ou copier-coller depuis un fichier coffee...). Attention à l'indentation qui structure les blocs d'instructions (boucles et tests par exemple).

aide

Affectation, entrée et sortie de données

Affectation

En coffeescript, l'affectation est notée par un "=".

Par exemple,

  1. Pour mettre 2 dans x:
    x = 2
  2. Pour le remplacer par 3:
    x = x+1

Une variable peut être affectée par un nombre mais aussi par du texte, une liste ou même une fonction.

Affectation simultanée

On peut affecter simultanément a par 1 et b par 2 avec

[a,b] = [1,2]

Raccourcis

Pour augmenter x de 1, on peut faire indifféremment

x = x+1
x += 1
x++

Entrée de données

Pour faire entrer un nombre x par l'utilisateur, il faut affecter x (donc écrire un signe "égal") et afficher un message d'invite rappelant ce que représente le nombre. Par exemple

x = entre "Allo non mais allo quoi! Tu veux mettre quoi dans x ?"

Affichage de données

Tant qu'on ne demande pas à CoffeeScript d'afficher le résultat d'un calcul, on ne peut pas connaître celui-ci. Il y a deux moyens de faire connaître le contenu de x:

  • créer une boîte modale d'affichage contenant x avec
    alerte x
  • afficher x dans le cadre prévu à cet effet à droite de la page avec
    affiche x

Simulation du hasard

Pour lancer un dé à 6 faces

affiche dé 6

Le nombre de faces doit être en entier, sans limite.

Pour vérifier, on peut lancer 10 fois le dé:

(dé 6 for n in [1..10])

Pile ou face

Pour jouer à pile ou face, on lance un dé à deux faces.

Loi uniforme sur [0;1[

affiche alea()

donne un nombre aléatoire entre 0 et 1

Application

On peut alors simuler une variable aléatoire Z normale centrée (d'espérance 0) et réduite (d'écart-type 1) avec

Z = -6
for n in [0...12]
    Z += alea()
affiche Z

Logique

Égalité

Pour tester l'égalité entre deux objets, il y a deux manières:

  • avec un double égal comme dans 2+2 == 4
  • avec le verbe is ("est") comme dans 2+2 is 4

affiche 2+2 is 5

affiche false (ben oui!)

Négation

Pour obtenir le contraire d'une proposition, la précéder par un point d'exclamation

affiche not 2+2==5
affiche 2+2 isnt 5

Le symbole "≠ se note donc isnt ou !=, au choix.

Conjonction

Pour dire que x est à la fois positif et pair, on peut écrire

x > 0 && x%2 is 0

Disjonction

Pour dire que x est, ou bien positif, ou bien pair (ou les deux), on peut écrire

x > 0 || x%2 is 0

Pour taper le symbole "trait vertical", appuyer avec la main droite sur et, sans lâcher ce bouton, actionner le en haut du clavier, de la main gauche.

Booléens

Tests

Test simple

Un test est une instruction conditionnelle; Pour n'effectuer quelque chose que lorsqu'une condition est vraie (par exemple seulement si le dé est tombé sur 6), faire

if dé(6)==6
    affiche "gagné"

On remarque l'indentation qui précise que la partie affiche "gagné" ne doit s'effectuer que si le dé vaut 6.

affiche "gagné" if dé(6)==6

a le même effet.

Test multiple

Que faire quand le dé ne tombe pas sur 6 ?

if dé(6)==6
    affiche "gagné"
else
    affiche "perdu"

Intervalles

On peut aussi faire un test dans un intervalle:

(x for x in [1..12] when x%2==0)

Intervalles

En CoffeeScript, les intervalles sont composés uniquement d'entiers. L'intervalle fermé [a;b] se note [a..b] avec deux points; L'intervalle ouvert à droite [a;b[ se note [a...b] avec trois points; L'appartenance se note in; Pour vérifier que 2 est compris entre 0 et 5:

affiche 2 in [0..5]
affiche 0 <= 2 <= 5
	

L'appartenance est aussi utilisée pour appliquer une fonction à un intervalle:

affiche (x*x for x in [0..5])

Ensembles

Ajout d'un élément

Pour ajouter un élement x à un ensemble A:

A.push x

Retrait d'un élément

Pour enlever le nombre 5 d'un ensemble A:

A = (x for x in A if x isnt 5)

Intervalles d'entiers

Ensembles

Intersection

L'intersection de deux ensembles A et B est formée des x de A qui sont aussi dans B:

I=(x for x in A when x in B)

Complémentaire

Une légère différence mais qui change tout:

(x for x in A when x not in B)

est le complémentaire de B dans A.

En probabilités, cette notion formalise le contraire d'un évènement.

Réunion

La réunion de deux intervalles n'est pas nécessairement un intervalle:

A=(x for x in [0..100] when 2 < x < 15 or 80 <= x < 90)
affiche A

l'Infini dans CoffeeScript

Si on divise 0 par 0 on obtient NaN (not a number) qui signifie que la division n'a pas de sens. Mais si on divise 1 (ou tout autre nombre non nul) par 0, on obtient Infinity, ce qui veut dire que lorsqu'une variable x tend vers 0, son inverse 1/x tend vers l'infini;

De même,

1/Infinity

donne 0: Si une variable x tend vers l'infini, son inverse 1/x tend vers 0.

Opérations

Addition

affiche Infinity+Infinity

La somme de deux fonctions qui tendent vers +∞ tend elle-même vers +∞

affiche 3+Infinity

La somme d'une fonction qui tend vers 3 et d'une fonction qui tend vers +∞ tend elle-même vers +∞

affiche Infinity-Infinity

On ne peut rien conclure sur la somme d'une fonction qui tend vers +∞ et d'une fonction qui tend vers -∞: Il s'agit d'une forme indéterminée.

Multiplication

affiche Infinity*Infinity

Le produit de deux fonctions qui tendent vers +∞ tend lui-même vers +∞

affiche 3*Infinity

Le produit d'une fonction qui tend vers 3 et d'une fonction qui tend vers +∞ tend lui-même vers +∞

affiche 0*Infinity

On ne peut pas conclure sur le produit d'une fonction qui tend vers ∞ et d'une fonction qui tend vers 0: Il s'agit d'une forme indéterminée.

Croissance comparée

affiche leLogarithmeDe 0
affiche leLogarithmeDe Infinity

La limte de ln en 0 est -∞ et la limite de ln en +∞ est +∞

affiche exp -Infinity
affiche exp Infinity

La limite de ex est 0 lorsque x tend vers -∞ et +∞ lorsque x tend vers +∞.

Fonctions

Une fonction associe à une variable d'entrée (ou plusieurs) appelée antécédent, une (ou plusieurs) variable de sortie appelée image; l'image de x par la fonction f est notée f(x); Aussi, en CoffeeScript, une fonction est-elle désignée par une flèche -> séparant l'antécédent, entre parenthèses, de l'image, qui est une expression. Après la flèche on peut insérer un algorithme destiné à calculer la fonction par algorithme.

La dernière ligne écrite dans la fonction est la valeur retournée.

Une fonction peut ne pas avoir d'antécédent, dans ce cas c'est une procédure.

Cas particuliers

Fonctions constantes

(x) -> 3

est une fonction constante.

Fonctions affines
(x) -> x/2+1

est une fonction affine.

Une variable peut être une fonction

On peut affecter une variable par une fonction comme dans

f = (x) ->
    x*x-2*x-1

Ensuite on peut entrer f(3) ou f 3 pour avoir l'image de 3 par f.

Fonctions prédéfinies

Parmi les fonctions prédéfinies, on trouve

  • sinus et cosinus en degrés (pour l es radians, utiliser sin et cos)
  • laRacineDe pour la racine carrée; leCarréDe, leCubeDe pour le carré et le cube d'un nombre; lInverseDe pour l'inverse d'un nombre (1 divisé par ce nombre)
  • leLogarithmeDe pour le logarithme népérien, et lExponentielleDe pour ex.
  • les fonctions de JavaScript sont disponibles dans CoffeeScript

Boucles

Boucler n fois

Pas à pas

Pour répéter 10 fois une action, on a besoin d'une variable appelée indice de la boucle. Ici on notera i cet indice, qui ira de 1 à 10.

Par exemple, pour lancer un dé 10 fois, on peut entrer

for i in [1..10]
    affiche dé 6

Un bon moyen de suivre l'indice d'une boucle est d'afficher celui-ci dans la boucle:

for in in [1..10]
    affiche i
Remarque:
affiche i for i in [1..10]

a le même effet...

Les nombres 1, 2, 3 etc parcourus forment une suite arithmétique de raison 1.

Autres suites arithmétiques

Pour faire descendre l'indice (compte à rebours) on peut faire

affiche i for i in [10..1]

Pour aller de 3 en 3 on peut faire

affiche i for i in [1..10] when i%3 is 1

ou, mieux:

affiche i for i in [1..10] by 3

Boucler sur les nombres premiers

Pour boucler sur les nombres premiers inférieurs à 20:

for i in [2,3,5,7,11,13]

Boucler jusqu'à une condition

Pour lancer un dé jusqu'à ce qu'on ait un 6 (et compter les lancers dans un indice i), on fait

Jusque

i=0
i++ until dé(6) is 6

Il y a plusieurs manières de faire ça; par exemple

i=1
i++ while dé(6) isnt 6

Tant que

On peut aussi faire comme ceci:

i=1
while dé(6) isnt 6
    i=i+1

Statistiques

Pour faire des statistiques sur une liste, il est parfois nécessaire de la trier (par exemple, pour calculer les qunatiles). Comme "trier" se dit "sort" en anglais, on trie la liste L ainsi:

Tri dans l'ordre croissant

	L.sort (x,y)->(x > y)
	

Tri dans l'ordre décroissant

	L.sort (x,y)->(x < y)
	

Maximum et minimum

Math.max.apply  null,L
Math.min.apply  null,L

Pour connaître l'effectif total d'une liste, on peut utiliser sa "longueur" (en anglais, length):

Compter les éléments d'une liste

L.length

Somme des éléments d'une liste

somme=0
for e in L
    somme+=e

Exemples

Algorithme d'Euclide

Pour calculer le pgcd de deux nombres a et b, on remplace a et b par b et r jusqu'à ce que r soit nul (r est le reste de la division de a par b).

version classique:

pgcd = (a,b) ->
    [x,y]=[a,b]
    while y>0
        [x,y]=[y,x%y]
    x

affiche pgcd 55,34
	

Version CoffeeScript:

pgcd = (a,b) ->
    [x,y]=[a,b]
    [x,y]=[y,x%y] until y is 0
    x

affiche pgcd 55,34
	

Calcul de racines carrées par l'algorithme de Heron

Pour calculer la racine carrée de 5 par l'algorithme de Heron, on remplace une valeur approchée a (par défaut), par sa moyenne avec 5/a (valeur approchée par excès); et on recommence jusqu'à ce que la différence entre les valeurs approchées par défaut et par excès soit devenue imperceptible.

Calcul de √(5)

[a,b]=[1,5]
until (abs b-a)<1e-16
    a=(a+b)/2
    b=5/a
affiche a
	
	

Fonction racine carrée

racineDe = (x) ->
    [a,b]=[1,x]
    until (abs b-a)<1e-16
        a=(a+b)/2
        b=x/a
    a
    
affiche racineDe 5
	
	

Suites géométriques

Combien de fois faut-il lancer un dé équilibré pour que la probabilité d'avoir un 6 dépasse 0,99 ?

La condition de sortie se traduisant par le fait que la probabilité de ne pas avoir de 6 est en-dessous de 0,01; et comme si les lancers sont indépendants, cette probabilité suit une suite géométrique de raison 5/6:

proba = 1
nombreDeLancers=1
until proba < 0.01
    proba *= 5/6
    nombreDeLancers++
affiche "En lançant #{nombreDeLancers} fois le dé, la probabilité d'avoir un 6 est #{1-proba}"
	

Suite de Fibonacci

La suite Fn est définie par la relation de récurrence Fn+2=Fn+1+Fn. Si F0=F1=1, la suite est entièrement déterminée.

Version classique

[a,b]=[1,1]
for n in [1..10]
    [a,b]=[a+b,a]
    affiche "F(#{n})=#{b}"
	

Formule de Binet

nombreDor = (1 + racine 5)/2 
for n in [1..10]
    b = puissance nombreDor, n
    b /= racine 5
    b = arrondi b
    affiche "F(#{n})=#{b}"

Problème du Grand-Duc de Toscane

Lorsque Galilee lui donnait des cours, Cosme de Medicis, futur Grand-Duc de Toscane, lui a demandé comment ça se fait que lorsqu'on additionne les résultats de 3 dés, le 10 sort plus souvent que le 9, alors que

  • 9=1+2+6=1+3+5=1+4+4=2+2+5=2+3+4=3+3+3
  • 10=1+3+6=1+4+5=2+2+6=2+3+5=2+4+4=3+3+4
soit 6 manières dans chaque cas.

Simulation

effectifs=(0 for n in [3..18])
for n in [1..100000]
    effectifs[dé(6)+dé(6)+dé(6)-3]++
affiche "Le 9 est sorti #{effectifs[6]} fois"
affiche "Le 10 est sorti #{effectifs[7]} fois"

Calcul des probabilités

effectifs = (0 for n in [3..18])
for a in [1..6]
    for b in [1..6]
        for c in [1..6]
            effectifs[a+b+c-3]++
d = puissance 6,3
affiche "La probabilité d'avoir un 9 est #{effectifs[6]/d}"
affiche "La probabilité d'avoir un 10 est #{effectifs[7]/d}"
	

Problème du Chevalier de Méré

Dans une lettre à Blaise Pascal, le Chevalier de Méré lui a posé la question suivante: Comment se fait-il qu'en lançant 4 dés, on a plus d'une chance sur 2 d'avoir au moins un 6 ?

Simulation du lancer de 4 dés

gains=0
for n in [1..100000]
    jeu=(dé(6) for n in [1..4])
    if (x for x in jeu when x is 6).length
        gains++
affiche gains/100000

Calcul de la probabilité

gains=0
for a in [1..6]
    for b in [1..6]
        for c in [1..6]
            for d in [1..6]
                if a is 6 or b is 6 or c is 6 or d is 6
                    gains++
d = puissance 6,4
affiche gains/d

Poker avec 32 cartes

Tirer 5 cartes (une "main") dans un jeu de 32 cartes, c'est constituer un échantillon d'effectif 5 dans une population totale de 32. C'est donc la base d ela statistique.

Tirage avec remise

Si on répète 5 fois l'expérience de tirer une carte, on risque d'avoir plusieurs fois la même carte (tirage avec remise). Mais ce risque est minime:

couleur=['♢','♡','♤','♧']
valeur=['1','7','8','9','10','V','D','R']
jeu=[]
for c in couleur
    for v in valeur
      jeu.push "#{v}#{c}"
main=[]
for n in [1..5]
    main.push jeu[dé(32)-1]
affiche main