Décembre

Avril

Ce mois çi, en attendant noël, on a travaillé sur les algorithmes Gloutons. Mais qu'est ce que c'est que c'est quoi que c'est ça?

Mise en Œuvre:

Imaginez que vous avez un village de 200 maisons et que vous voudriez les relier à l'électricité depuis la mairie en utilisant le moins possible de câbles et de poteaux?

Méthode n°1:

On essaie au pif

Méthode n°2:

On calcule toute les possibilités pour trouver la plus optimale.

Alors NON parce que ça fait vraiment beaucoup. Vous savez combien de possibilités on a ?

200*199*198...*2*1 ou 200 factoriel, soit : 788657867364790503552363213932185062295135977687173263294742533244359449963403342920304284011984623904177212138919638830257642790242637105061926624952829931113462857270763317237396988943922445621451664240254033291864131227428294853277524242407573903240321257405579568660226031904170324062351700858796178922222789623703897374720000000000000000000000000000000000000000000000000 possibilités.

Ca fait beaucoup là, non?

Méthode n°3:

Choisir le chemin le plus court d'une maison à l'autre, c'est à dire partir de la mairie. Et ça c'est bien.

" Mé komman on va fair Nathan? "Me direz vous, et bien, disons que on a une carte avec toutes les maisons dessus et la mairie au centre. A chaque maison on va attribuer des coordonnées, qui seront stockées dans une liste x et une liste y.

Sur Python:

x=[0, 54, -15, -23, 47, 12, 28, 30, 14, -88, 2, 92, -6, 13,-27]
y=[0, 41, 99, -40, -20, 0, -99, -5, 14, -98, 16, 97, 55, 43, 3]

Là, on à la mairie à 0:0 au centre de la carte

Maintenant qu'on a ces points, il faut calculer leur distances les uns des autre.

Mais au fait, comment on calcule une distance en math?

○Pour ca, il faut que vous visualisez la grille avec des point, vous l'avez? La voici:

Réalisé sur paint avec une IA.

Or ces points suivent des abscisses et des ordonnées. Si on croise leurs axes et qu'on relie les deux points, on obtient un triangle rectangle.

def distance_entre_deux_points (xa,xb,ya,yb):
return sqrt((xb-xa)**2+(ya-yb)**2)