Le mot de Fibonacci est une chaine de caractères infinie. Elle se construit par récurrence :
\(M_0 = \texttt{"0"}\)
\(M_1 = \texttt{"01"}\)
Ensuite, chaque terme est la concaténation du précédent et de celui qui le précède.
On constate donc que pour tout \(i\), \(M_i\) est un mot préfixe des suivants.
Le mot de Fibonacci est la limite de cette suite. Pour obtenir au moins les n premiers caractères, il suffit d'avoir un terme \(M_k\) de longueur supérieure ou égale à n.
On pourra vérifier que ce mot commence par \(\texttt{"010010100100101001010"}\cdots\)
Exercice 1
Coder une fonction mot_Fibonacci qui prend en paramètre un entier n et qui renvoie les n premiers caractères du mot de Fibonacci.
###(Dés-)Active le code après la ligne # Tests (insensible à la casse) (Ctrl+I)
Entrer ou sortir du mode "deux colonnes" (Alt+: ; Ctrl pour inverser les colonnes)
Entrer ou sortir du mode "plein écran" (Esc)
Tronquer ou non le feedback dans les terminaux (sortie standard & stacktrace / relancer le code pour appliquer)
Si activé, le texte copié dans le terminal est joint sur une seule ligne avant d'être copié dans le presse-papier
On admettra que les positions perdantes (i, j) avec i < j sont les termes de la suite [(1, 2), (3, 5), (4, 7), (6, 10), ...], obtenue en zippant pos_zéros et pos_uns.
Le terme position se comprend comme commençant à 1, ainsi le premier caractère du mot de Fibonacci est celui dont la position est 1, et ce chiffre est 0.
Exercice 2
Compléter la classe JeuReine.
Coder l'initialisateur __init__() qui prend en paramètre n un entier, la taille de l'échiquier carré et prépare du matériel utile à la question 2. C'est à vous de décider ce que va contenir ce matériel, c'est votre choix !
Coder une méthode est_gagnante qui prend en paramètres i et j la ligne et la colonne d'une case et qui renvoie un booléen : True si la case est une position gagnante à ce Jeu de la Reine, False sinon.
Dans les tests secrets, il y a aura une initialisation jeu=JeuReine(n) (avec une valeur adaptée pour n) qui précèdera des utilisations de est_gagnante. De la même manière que dans les tests publics.
Contraintes - tests secrets
On garantit que n <= 100_000, ce qui est beaucoup.
D'autre part, la fonction est_gagnante sera sollicitée environ 200_000 fois dans les tests secrets, ce qui est beaucoup.
On attend que :
L'initialisation ait un cout linéaire en n.
La méthode est_gagnante ait un cout constant (rapide) à chaque appel. (Aucune boucle n'est attendue.)
Le problème a été testé en ligne sur une simple petite tablette Android. Sur PC, on peut travailler avec \(n=10^7\) sans problème.
###(Dés-)Active le code après la ligne # Tests (insensible à la casse) (Ctrl+I)
Entrer ou sortir du mode "deux colonnes" (Alt+: ; Ctrl pour inverser les colonnes)
Entrer ou sortir du mode "plein écran" (Esc)
Tronquer ou non le feedback dans les terminaux (sortie standard & stacktrace / relancer le code pour appliquer)
Si activé, le texte copié dans le terminal est joint sur une seule ligne avant d'être copié dans le presse-papier
une case ou plus, au choix !
Dans les tests secrets, il y a aura une initialisation
# Tests(insensible à la casse)(Ctrl+I)
(Alt+: ; Ctrl pour inverser les colonnes)
(Esc)