Cartes de nombres: B-Fibonacci-Zeckendorf

Télécharger le projet
Commenter

Description

Bonjour,

Voici un logiciel qui permet de générer un autre jeu de cartes de nombres dont l'explication est plus subtile.

Son codage est basé sur le théorème de Zeckendorf qui dit que tout entier positif peut s’écrire, de manière unique, comme somme de nombres de Fibonacci distincts non consécutifs et d'index > 1.
(voir WikipédiA: Théorème de Zeckendorf)

La suite de Fibonacci

La suite de Fibonacci est une suite d'entiers dans laquelle chaque terme est la somme des deux précédents; elle commence par 0 et 1:

F₀ = 0; F₁ = 1; Fₙ = Fₙ₋₂ + Fₙ₋₁ (pour n ≥ 2).
(voir: WikipédiA: Suite de Fibonacci et La suite de Fibonacci et le nombre d’or) 

Suite de Fibonacci:

   i: 0 1 2 3 4 5 6  7  8  9 10 11  12  13  14  15  16   17   18   19   20 …
F[i]=[0,1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2484,4181,6765,…]
nk=i-1:   1 2 3 4 5  6  7  8  9 10  11  12  13  14  15   (nk=numéro de la carte)

    n  = 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 …
  I[n] =[0,2,3,4,4,5,5,5,6,6, 6, 6, 6, 7, 7, 7, 7, 7, 7, 7, 7, 8 ,8, 8, 8, 8,…]
F[I[n]]=[0,1,2,3,3,5,5,5,8,8, 8, 8, 8,13,13,13,13,13,13,13,13,21,21,21,21,21,…]
I[n] est l'index du plus grand nombre de Fibonacci que n contient.
Il est calculé en même temps que F[i] dans la fonction Ini().

Décomposition selon Zeckendorf

Exemples: 
n =   77 =   55 + 21 +  1
         = F[10]+F[8]+F[2]

n =  999 =  987 +  8 +  3 +  1
         = F[16]+F[6]+F[4]+F[2]
     
n = 1596 =  987 + 377 + 144 +  55 + 21 +  8 +  3 +  1
         = F[16]+F[14]+F[12]+F[10]+F[8]+F[6]+F[4]+F[2]
 
n = 5007 = 4181  +  610  +  144  +   55  +  13  +   3  +   1
         = F[19] + F[15] + F[12] + F[10] + F[7] + F[4] + F[2]
Attention: la décomposition n'est unique que si deux index utilisés ne sont jamais consécutifs.

Affirmation:
Toute décomposition de n contient (au moins) le plus grand nombre de Fibonacci F[I[n]] (qui est donc plus petit ou égal à n).

En effet, la somme ∑ de tous les nombres de Fibonacci non voisins et strictement plus petits que F ne vaut que F-1: 
i: 0 1 2 3 4 5 6  7  8  9 10 11  12  13  14  15  16   17   18   19   20    21
F=[0,1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2484,4181,6765,10946,…]
∑=[0,0,0,1,2,4,7,12,20,33,54,88,143,232,376,609,986,1596,2483,4180,6764,10945,…]
                              ↑
              Exemple (F[11]=89): ∑[11] = 55+21+8+3+1 = 88 = 89-1

Développement du code

Notre code s'inspire de l'article CodeS-SourceS: Cartes de nombres: A-binaire.
Nous limiterons le nombre à deviner N à 1596 (= F[17]-1).
On aura donc au maximum 15 cartes.

La principale adaptation est la fonction IsOnCard(i,n): 
  function IsOnCard(i,n) { // n est-il sur la carte nk (nk=i-1) ?
    while (I[n]>i) n-=F[I[n]];
    return I[n]==i;
  }
qui remplace le simple test if (n&K) {...}.

La méthode utilisée peut aussi servir pour le WikipédiA: Codage de Fibonacci.

Déroulement du tour

Considérons par exemple le déroulement du tour proposé dans Blogdemaths: Un tour de magie mathématique…:

1. Demandez à un spectateur de choisir un nombre au hasard entre 1 et 100 et de l’inscrire sur une feuille de papier à l’abri des regards indiscrets.
2. Montrez-lui tour à tour chacune des 10 cartes ci-dessus, et demandez-lui à chaque fois si le nombre qu’il a choisi est inscrit sur la carte.
3. Faites semblant de réfléchir/de regarder dans votre boule de cristal/d’invoquer l’esprit de l’accordéon Yvette Horner… Bref, faites votre magicien.
4. Annoncez-lui le nombre qu’il avait choisi au départ. Demandez-lui de retourner le papier pour confirmer que c’était bien le nombre qu’il avait choisi.
5. Récoltez les fruits de votre nouvelle célébrité.

Malheureusement, ce déroulement n'a pas l'air de tenir compte de l'expression "non consécutif" du théorème de Zeckendorf.
En effet, lorsqu'un spectateur affirme que son nombre choisi figure sur une carte donnée, on est sûr (vérifiez-le !) que ce nombre ne se trouve pas sur les cartes voisines.
Dans ce cas, il est inutile de présenter ces cartes voisines ! Et on peut donc souvent réduire le nombre de cartes à présenter.

Pour pouvoir facilement retrouver les voisines d'une carte, il suffit de les "numéroter" (par exemple par A, B, C, …).

Dessiner un rectangle arrondi

Malgré les nombreux exemples de codes pour dessiner (en Javascript) un rectangle arrondi qu'on trouve sur le net, j'en ajoute un: 
  function RoundedRect(x,y,xx,yy,r) {
    ctx.beginPath();
    ctx.moveTo(x+r,y);
    ctx.arcTo(xx,y,xx,y+r,r);
    ctx.arcTo(xx,yy,xx-r,yy,r);
    ctx.arcTo(x,yy,x,yy-r,r);
    ctx.arcTo(x,y,x+r,y,r);
  }
Bien entendu, cette fonction doit être suivie de ctx.fill() pour le remplissage selon le ctx.fillStyle défini,
et(/ou) de ctx.stroke(), pour le dessin du contour conformément à ctx.fillStyle et ctx.lineWidth.


Bonne lecture...
Télécharger le projet

Codes Sources

A voir également

S'inscrire maintenant

Vous n'êtes pas encore membre ?

inscrivez-vous, c'est gratuit et ça prend moins d'une minute !

Les membres obtiennent plus de réponses que les utilisateurs anonymes.

Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.

Le fait d'être membre vous permet d'avoir des options supplémentaires.

Du même auteur (William VOIROL)