L'image d'une matrice est un peu vraie, mais un peu fausse.
Si on parle d'une matrice, on va avoir en basic quelque chose comme ça:
- Code: Tout sélectionner
dim Matrice(100000) integer
for i =1 to 100000
matrice(i)=i
end
Donc on va avoir une zone réservée en mémoire , éventuellement énorme, éventuellement tellement grande que ça va planter parce que la mémoire du PC est insuffisante.
Et on va avoir un temps incompressible pour initialiser cette matrice.
Là, on n'a pas cette zone mémoire.
On lui dit ; tant qu'il reste des trucs dans F3, envoie moi le suivant, et je vais effectuer Print(ii)
Et pour récupérer l'élément suivant de F3, il fait quoi, il va chercher dans F2 l'élément suivant, autant de fois que nécessaire si cet élément n'est pas compatible avec les règles de F3
Et pareil, F2 'sous-traite' à F1, et F1 ,lui, il va chercher à chaque fois l'entier suivant, entre 0 et 9999.
En gros. c'est à chaque fois 'envoie-moi le suivant'.
Bon... j'ai découvert récemment cette commande yield, elle m'amuse beaucoup, et du coup, je brode, je brode.
Revenons à nos moutons.
On cherche le nombre qui serait au rang 123456 si on listait tous les éléments.
Déjà, on sait que ce nombre sera un peu plus grand que 123456, en gros entre 124000 et 130000 ?
Si on a un seul critère, on sait dire :
- Testons 124000,
- si 124000*8-167 est un carré parfait, on arrête, on recommence avc l'entier suivant.
- et sinon, combien y a-t-il de nombres x entre 1 et 124000 tels que 8x-167 soit un carré parfait , et donc 124000 , il est au rang 123450 par exemple.
- et du coup, on recommence en testant 124006
Par tâtonnement, on va assez vite trouver la réponse.
Combien y a-t-il de nombres entre 1 et 124000 tels que 8x-167 soit un carré parfait, je me trompe peut-être, mais je pense que c'est 'simple'.
Si on a 2 contraintes ( ni 8x-167, ni 16x-279 ne doit être un carré parfait)
Ca revient à compter les x tels que 8x-167 est un carré parfait, puis compter les x tels que 16x-279 est un carré parfait... ça roule
Mais on a compté 2 fois les nombres x pour lesquels on a en même temps 8x-167 est un carré parfait et aussi 16x-279 est un carré parfait.
Sait-on facilement dire combien de nombres entre 1 et 124000 vérifient ces 2 propriétés ?
Faut réfléchir, ce sera l'objectif de l'après midi.
Si on sait faire ça, étendre à 3 ou plus devrait être du même registre.
La technique du crible de Poincaré va nous aider.
