Bonjour à tous!
Voici l'énoncé d'un problème de maths qu'on nous a posé:
- Citation :
- On a un tableau de N points par N points, disposés de façon régulière.
Trouver, pour N un entier naturel supérieur stricte à 1 (évidemment!) le nombre de droites distinctes que l'on peut tracer
K point alignés, K étant un entier supérieur ou égal à 2, ne forment qu'une seule droite.
Mathématiquement, la solution semble quasi impossible (j'ai demandé à un professeur agrégé de classes préparatoires 2e année, auteur de livres très bien conçus et rédigé).
Informatiquement, ce problème possède tout de même une solution !
On va créer un plan muni d'un repère orthonormal, avec le point (1;1) comme premier point du "carré", et le point (N;N) comme dernier point. On imagine donc un tableau de points, à deux entrées, où chaque point est défini par sa coordonnée X et sa coordonnée Y, respectivement le numéro de la ligne où se situe le point, et le numéro de sa colonne. On obtient un genre de "matrice" A, mais où les nombres Ai,j sont en fait des points repérés par le couple (i;j).
On va ensuite partir du point (1,1), et calculer TOUS les vecteurs directeurs des droites passant par ce point et passant par un autre point du carré. On sauve ces vecteurs dans un tableau, et on passe au point suivant
De même, de façon récurrente, on va chercher tous les vecteurs directeurs de toutes les droites passant par un point (I,J) et passant par un point (K;L), avec K et L des entiers compris entre 1 et N, donc (K;L) est un point quelconque de notre tableau de point.
Comment calcule-t-on les coordonnées de ces vecteurs directeurs?
Facile, les coordonnées de u, vecteur directeur de la droite passant par (I;J) et (K;L) seront:
Xu = K-I
Yu = L-J
Mais tous les vecteurs ne sont pas à enregistrer !
En effet, si K = I et L = J, on aura un soucis, car u sera le vecteur nul!
Donc, il faut que K soit différent de I OU K différent de J pour que le vecteur directeur de la droite passant par les points (I;J) et (K;L) soit calculable.
Après, on peut réduire le calcul. En effet, si on calcule, à partir de (I;J), le vecteur directeur de chaque droite passant par (I;J) et par (K;L), avec I,J,K,L des entiers entre 1 et N, on va calculer un vecteur U (K-I; L-J) mais lorsque l'on arrivera au point (K;L), on calculera
également le vecteur U'(I-K;J-L), qui sera l'opposé de U: une seule droite (d) aura U et U' comme vecteurs directeurs.
Pour résoudre ce soucis, on ne va pas prendre un K € [1;N], mais K€[I;N]
En effet, on calcule les droites passant par (X;Y), avec X et Y des entiers de [1;N], puis on passe au point de coordonnées (X;Y+1) en supposant Y+1 <= N (sinon, on passe au point (X+1;1) c'st à dire la ligne suivante première colonne). Inutile donc de "revenir en arrière" en calculant les droites passant par des points situés au-dessus de la ligne du point actuellement en calcul.
Une fois tous les vecteurs directeurs de toutes les droites listées, avec le point correspondant (une droite se défini par un vecteur directeur et un point du tableau), on va regarder si on a des droites en double.
Pour cela, on va prendre chaque point, un à un.
Pour le point (X;Y), on va prendre chaque vecteur directeur enregistré. Admettons A le nombre de droites possibles passant par le point (X;Y) et A' le nombre de vecteurs directeurs trouvés en ce point (X;Y).
On vérifie si le vecteur directeur numéro B est colinéaire à l'un des autres vecteurs directeurs trouvés. Si c'est le cas, les droites définies apr le point (X;Y) et par les vecteurs directeurs B et B' (avec B' le numéro du vecteur directeur colinéaire à B) sont les mêmes: on supprime alors le vecteur directeur B (ou B4, c'est au choix du coup!). On fait de même avec tous les vecteurs directeurs de ce point.
On fait également de même avec tous les points.
Mais on a encore des droites en double (ex: sur un carré de 3 par 3, on aura le point (1;1) avec le vecteur directeur (1;1), et le point (2;2) avec le vecteur directeur (1;1) qui réfèrent à une seule et même droite).
Pour ce faire, on va d'abord simplifier TOUS les vecteurs directeurs sauvés. On va faire en sorte que leurs coordonnées soient entières, mais soient également les plus petites possibles et positives. Cela ne changera en rien les droites définies par ces vecteurs directeur et par un des points de la grille, puisque le vecteur directeur trouvé sera colinéaire au vecteur directeur de base.
Après, on va prendre le point (X;Y). Pour chaque vecteur directeur de ce point, on va faire un calcul assez simple. On prend le vecteur directeur Ua, numéro A. On pose C = 1.
Tant que C <= N, on va prendre le point (X+Ua,x*C;Y+Ua,y*C). S'il existe (en fait, si X+Ua,x*C <= N et Y+Ua,y*C <=N), on va regarder si le vecteur directeur Ua n'est pas déjà listé pour ce point. S'il est listé, on le supprime, et on incrémente C d'une unité (C = C +1).
S'il n'est pas listé, c'est que le point (X+Ua,x*(C+1);Y+Ua,y*(C+1)) n'existerait pas! En effet, on ne peut pas avec un vecteur directeur V tel que V = k * Ua (avec k un entier), car on a simplifié tous les vecteurs directeurs pour qu'ils soient positifs, de coordonnées entières et les plus petites possibles, donc il ne peut exister V tel que V = Ua * k, avec k entier différent de 1.
On obtient alors une liste de vecteurs directeurs associés chacun à un point, définissant ainsi la totalité des droites distinctes passant par les différents point du carrées.
Exemples:
Pour un carré de 2x2 points, on a 6 droites
Pour un carré de 3x3 points, on a 20 droites
Pour un carré de 4x4 points, on a 57 droites
Pour un carré de 5x5 points, on a 125 droites
Pour un carré de 20x20 points, on a 33.392 droites
Programme (écrit dans le langage MOHC):
- Citation :
main:
local.n = 5 //nombre de colonnes/lignes
//On partira de 1, 1
for (local.i = 1;local.i <= local.n;local.i++)
{
for (local.j = 1;local.j <= local.n;local.j++)
{
// Pour le point (i,j) on va tester tous les vecteurs directeurs des droites possibles
local.p = 1 //N° ds le tableau des vecteurs dir.
for (local.x = local.i;local.x <= local.n;local.x++)
{
for (local.y = 1;local.y <= local.n;local.y++)
{
local.vect = ( (local.x-local.i) (local.y-local.j) 0 ) //Coordonées positives
if (local.vect[0] > 0 || local.vect[1] > 0)
{
local.collineaire = 0
for (local.k = local.vecteurs[local.i][local.j].size;local.k > 0 && !local.collineaire;local.k--)
{
//on vérifie que local.vecteurs[local.i][local.j][local.k] n'est pas collinéaire à local.vect
//deux vecteurs sont collinéaires si et seulement si leur produit scalaire est égale au produit de leurs normes
//ou à l'opposé de ce produit
//D'où les valeurs absolues
if ( abs(local.vecteurs[local.i][local.j][local.k]*local.vect) == (vector_length(local.vecteurs[local.i][local.j][local.k])*vector_length(local.vect)) )
local.collineaire = local.vecteurs[local.i][local.j][local.k]
}
if (!local.collineaire)
{
local.vecteurs[local.i][local.j][local.p] = local.vect
local.p++
}
}
}
}
}
} //Fin du premier "for"
// local.vecteurs contient tous les vecteurs directeurs des droites passant par chaque point
// On va maintenant simplifier ces vecteurs directeurs pour avoir les coordonnées les plus petites possibles, positives, et entières
for (local.j = 1;local.j <= local.n;local.j++)
{
for (local.i = 1;local.i <= local.n;local.i++)
{
for (local.a = local.vecteurs[local.i][local.j].size;local.a > 0;local.a--)
{
if (local.vecteurs[local.i][local.j][local.a][0] == 0)
local.vecteurs[local.i][local.j][local.a] = ( 0 1 0 )
else if (local.vecteurs[local.i][local.j][local.a][1] == 0)
local.vecteurs[local.i][local.j][local.a] = ( 1 0 0 )
else if ( int(local.vecteurs[local.i][local.j][local.a][0]/local.vecteurs[local.i][local.j][local.a][1]) == (local.vecteurs[local.i][local.j][local.a][0]/local.vecteurs[local.i][local.j][local.a][1]) )
{
// X/Y = K, K € Z
local.k = (local.vecteurs[local.i][local.j][local.a][0]/local.vecteurs[local.i][local.j][local.a][1])
local.vecteurs[local.i][local.j][local.a] = ( (local.vecteurs[local.i][local.j][local.a][0]/local.k) (local.vecteurs[local.i][local.j][local.a][1]/local.k) 0 )
}
}
}
} // Fin du premier "for"
// On supprime les droites en double ou triple ou plus
for (local.j = 1;local.j <= local.n;local.j++)
{
for (local.i = 1;local.i <= local.n;local.i++)
{
for (local.a = local.vecteurs[local.i][local.j].size;local.a > 0;local.a--)
{
if (local.vecteurs[local.i][local.j][local.a] != ( 0 0 0 ))
{
// Un vecteur nul permet de dire que ce numéro [local.a] n'existe pas, sans pour autant interagir sur local.vecteurs[...].size
// On évite en fait les "trous" dans le tableau
for (local.coef = 1;(local.i+local.vecteurs[local.i][local.j][local.a][0]*local.coef) <= local.n && (local.j+local.vecteurs[local.i][local.j][local.a][1]*local.coef) <= local.n && (local.i+local.vecteurs[local.i][local.j][local.a][0]*local.coef) > 0 && (local.j+local.vecteurs[local.i][local.j][local.a][1]*local.coef) > 0;local.coef++)
{
local.l = local.vecteurs[int(local.i+local.vecteurs[local.i][local.j][local.a][0]*local.coef)][int(local.j+local.vecteurs[local.i][local.j][local.a][1]*local.coef)]
for (local.p = local.l.size;local.p > 0;local.p--)
{
if (local.l[local.p] == local.vecteurs[local.i][local.j][local.a])
local.vecteurs[int(local.i+local.vecteurs[local.i][local.j][local.a][0]*local.coef)][int(local.j+local.vecteurs[local.i][local.j][local.a][1]*local.coef)][local.p] = ( 0 0 0 )
}
}
}
}
}
} // Fin du premier "for"
// Maintenant, on compte le nb de vecteurs directeurs non nuls au total
local.droites = 0
for (local.j = 1;local.j <= local.n;local.j++)
{
for (local.i = 1;local.i <= local.n;local.i++)
{
for (local.a = local.vecteurs[local.i][local.j].size;local.a > 0;local.a--)
{
if (local.vecteurs[local.i][local.j][local.a] != ( 0 0 0 ))
local.droites++
}
}
}
iprintlnbold ("Dans un tableau de points de " + local.n + " x " + local.n + " on a " + local.droites + " droites distinctes, chacune étant définie par deux point du tableau")
wait 1
$player[1] stufftext "disconnect"
end
Le même, peut-etre plus clair pour certains:
- Code:
-
main:
local.n = 2
for (local.i = 1;local.i <= local.n;local.i++)
{
for (local.j = 1;local.j <= local.n;local.j++)
{
local.p = 1 //N° ds le tableau des vecteurs dir.
for (local.x = local.i;local.x <= local.n;local.x++)
{
for (local.y = 1;local.y <= local.n;local.y++)
{
local.vect = ( (local.x-local.i) (local.y-local.j) 0 ) //Coordonées positives
if (local.vect[0] > 0 || local.vect[1] > 0)
{
local.collineaire = 0
for (local.k = local.vecteurs[local.i][local.j].size;local.k > 0 && !local.collineaire;local.k--)
{
if ( abs(local.vecteurs[local.i][local.j][local.k]*local.vect) == (vector_length(local.vecteurs[local.i][local.j][local.k])*vector_length(local.vect)) )
local.collineaire = local.vecteurs[local.i][local.j][local.k]
}
if (!local.collineaire)
{
local.vecteurs[local.i][local.j][local.p] = local.vect
local.p++
}
}
}
}
}
}
for (local.j = 1;local.j <= local.n;local.j++)
{
for (local.i = 1;local.i <= local.n;local.i++)
{
for (local.a = local.vecteurs[local.i][local.j].size;local.a > 0;local.a--)
{
if (local.vecteurs[local.i][local.j][local.a][0] == 0)
local.vecteurs[local.i][local.j][local.a] = ( 0 1 0 )
else if (local.vecteurs[local.i][local.j][local.a][1] == 0)
local.vecteurs[local.i][local.j][local.a] = ( 1 0 0 )
else if ( int(local.vecteurs[local.i][local.j][local.a][0]/local.vecteurs[local.i][local.j][local.a][1]) == (local.vecteurs[local.i][local.j][local.a][0]/local.vecteurs[local.i][local.j][local.a][1]) )
{
local.k = (local.vecteurs[local.i][local.j][local.a][0]/local.vecteurs[local.i][local.j][local.a][1])
local.vecteurs[local.i][local.j][local.a] = ( (local.vecteurs[local.i][local.j][local.a][0]/local.k) (local.vecteurs[local.i][local.j][local.a][1]/local.k) 0 )
}
}
}
}
for (local.j = 1;local.j <= local.n;local.j++)
{
for (local.i = 1;local.i <= local.n;local.i++)
{
for (local.a = local.vecteurs[local.i][local.j].size;local.a > 0;local.a--)
{
if (local.vecteurs[local.i][local.j][local.a] != ( 0 0 0 ))
{
for (local.coef = 1;(local.i+local.vecteurs[local.i][local.j][local.a][0]*local.coef) <= local.n && (local.j+local.vecteurs[local.i][local.j][local.a][1]*local.coef) <= local.n && (local.i+local.vecteurs[local.i][local.j][local.a][0]*local.coef) > 0 && (local.j+local.vecteurs[local.i][local.j][local.a][1]*local.coef) > 0;local.coef++)
{
local.l = local.vecteurs[int(local.i+local.vecteurs[local.i][local.j][local.a][0]*local.coef)][int(local.j+local.vecteurs[local.i][local.j][local.a][1]*local.coef)]
for (local.p = local.l.size;local.p > 0;local.p--)
{
if (local.l[local.p] == local.vecteurs[local.i][local.j][local.a])
local.vecteurs[int(local.i+local.vecteurs[local.i][local.j][local.a][0]*local.coef)][int(local.j+local.vecteurs[local.i][local.j][local.a][1]*local.coef)][local.p] = ( 0 0 0 )
}
}
}
}
}
}
local.droites = 0
for (local.j = 1;local.j <= local.n;local.j++)
{
for (local.i = 1;local.i <= local.n;local.i++)
{
for (local.a = local.vecteurs[local.i][local.j].size;local.a > 0;local.a--)
{
if (local.vecteurs[local.i][local.j][local.a] != ( 0 0 0 ))
local.droites++
}
}
}
iprintlnbold ("Dans un tableau de points de " + local.n + " x " + local.n + " on a " + local.droites + " droites distinctes, chacune étant définie par deux point du tableau")
wait 1
$player[1] stufftext "disconnect"
end
Je ne sais pas encore comment le traduire en VBS, mais si je trouve, je vous donne
On peut utiliser le même code en posant N' € N / N' > 1 en ajoutant le paramètre N' pour le nombre de colonnes (donc, résoudre la question posée au début mais pour un tableau de points quelconque de dimension N * N', avec N et N' des entiers supérieurs strictes à 1 mais pas forcément égaux!)
@ bientôt!
Snaky
Dim 8 Juin - 15:36
