Inscription / Connexion Nouveau Sujet
Niveau terminale
Partager :

Algorithme sous python

Posté par
SKYY
11-01-15 à 13:55

Bonjour,

J'ai un algorithme sous python réalisé mais je ne sais pas comment le faire voici l'énoncé:

Comment vérifier si un nombre est bien équilibré ?
Prenons les chiffres qui le composent comme s'ils étaient suspendus à une tige appuyée en son milieu sur un support.
Les chiffres des extrémités auront donc une influence plus grande que ceux situés près du "milieu" du nombre.

Par exemple, l'équilibre du nombre 12345 se détermine de la façon suivante : le 1 et le 5 sont affectés respectivement d'un coefficient 2 et (-2) puisque, par rapport au chiffre central, ils sont situés à une "distance" double de celle des chiffres 2 et 4.
Le chiffre central n'a aucune incidence sur l'équilibre général et aura donc un coefficient nul.

L'indicateur d'équilibre s'écrit donc   2x1 + 1x2 + 0x3 + (-1)x4 + (-2)x5 = -10.
Le nombre 12345 est donc fortement déséquilibré vers la droite.

On appellera nombre équilibré tout nombre dont l'indicateur est égal à 0.

Question : Quel est le plus petit nombre équilibré s'écrivant avec 9 chiffres tous différents (et ne commençant pas par zéro) ?
Les chiffres à gauche seront affectés respectivement des coefficients 4, 3, 2 et 1 en fonction de leur éloignement du chiffre central.
Idem à droite avec des coefficients négatifs.

Je sais que je vais devoir réalisé beaucoup de boucle et que je vais devoir testé tous les nombres a 9 chiffres tous différents.

Merci de vos aide futur.

Posté par
Revelli
re : Algorithme sous python 12-01-15 à 16:59

Bonjour,

Puisque le nombre N a 9 chiffres et ne commence pas par 0, on doit chercher parmi les nombres allant de 100 000 000 à 999 999 999

Puisqu'on doit trouver le plus petit nombre N de 9 chiffres différents d'indicateur 0, après avoir initialisé N à 102 345 678 on préfèrera une boucle Tant que N <= 999 999 999

On testera d'abord si les 9 chiffres sont différents les uns des autres

Pour cela on fait une boucle de I =1 à 9 sur les chiffres du nombre N et on vérifie que le même chiffre n'apparait pas 2 fois

Si le test est incorrect on passe au nombre N = N+1
Sinon on calcule l'indicateur du nombre N pour savoir s'il est nul

Si nul, on affiche le nombre N et on le force ensuite à 1 000 000 000 pour sortir de la boucle Tant que
Sinon on passe au nombre N = N+1

Il y a peut-être plus subtil en faisant des permutations des chiffres à partir de ceux du nombre N précédent mais je ne vois pas comment on peut assurer que le nombre permuté obtenu est le supérieur immédiat au nombre N précédent

Il faudra sans doute aussi utiliser le format Double Integer

Bon Courage

PS 1: Je vais essayer de programmer cela avec SCILAB (car je ne connais pas PYTHON)
PS 2: N'oublies pas de mettre à jour ton profil puisque maintenant tu es en Terminale semble-t-il!

Posté par
Revelli
re : Algorithme sous python 14-01-15 à 07:38

Bonjour,

J'ai programmé l'algorithme que j'ai précédemment proposé avec Scilab: en fait c'était mon premier programme dans ce langage, ce qui m'a permis de découvrir des subtilités et sa nature hautement abstraite mathématiquement parlant qui doit faciliter les erreurs de programmation!

Scilab est malheureusement un langage interprété, ce qui ralentit très fortement son exécution puisque chaque instruction doit être décodée à chaque passage au préalable à son exécution: ainsi il a fallu hier au soir sur mon PC la durée du match St-Etienne contre PSG regardé à la télé pour tester tous les nombres entre 102 345 678 et 103 000 000!

Pour comparaison et le fun, je vais essayer de faire le même programme en tant qu'application Java compilée pour gagner du temps d'exécution mais je devine que l'algorithme proposé n'est pas du tout le bon, surtout que l'on commence par des nombres totalement déséquilibrés

Simplement en réfléchissant sur des combinaisons visant à équilibrer les chiffres, on voit que le nombre 139 607 542 est peut-être celui recherché (il apparaît intéressant que le chiffre du milieu du nombre inhibé par le calcul de l'indicateur soit 0)

Le nombre 146 708 532 a aussi un indicateur nul mais est plus grand que le précédent

Cela prouve que notre cerveau a une vision globale que l'ordinateur n'a pas encore et n'est pas prêt d'avoir fort heureusement

Posté par
Revelli
re : Algorithme sous python 14-01-15 à 17:33

Bonsoir,

J'ai réussi à programmer l'algorithme proposé avec Java (c'est aussi une première pour moi)

En partant du nombre N=100 000 000, le premier nombre avec 9 chiffres tous différents et équilibré trouvé est: 109 865 432

Le nombre exactement de même nature immédiatement supérieur est 109 875 432

Le nombre suivant est 124 786 530

Il faut à peine 5 secondes au programme pour donner une réponse : on voit toute la différence entre les performances d'un programme compilé (JAVA) et celles d'un programme interprété (SCILAB)

Posté par
Arowbaz
re : Algorithme sous python 20-01-15 à 11:17

Bonjour, il est clair que, bien que critiqué, Java permet d'effectuer des calculs très rapidement ... (on arrive facilement à sortir les 100 premiers nombres de cette énigme en moins de 10 secondes), et en travaillant bit à bit je n'en parle pas ^^
Pour aller plus vite avec des grands nombres, je vous conseille d'utiliser la classe BigInteger qui est très puissante et résous les calculs là où python ne daigne même pas chercher ...

Posté par
Revelli
re : Algorithme sous python 20-01-15 à 11:59

Bonjour,

Lorsque j'ai dit que Java était un langage compilé, ce n'est pas totalement exact car le compilateur Java ne génère pas du code natif mais un code intermédiaire interprété par la machine virtuelle Java qui doit être présente sur la machine où le programme va être exécuté.

Mais les performances de la machine virtuelle sont telles qu'on approche les performances d'un codage natif - qu'il est aussi possible de générer à partir de Java, si on est par exemple confronté à des modules d'autres langages comme C ou C++ pour construire l'ensemble de son programme.

Posté par
Arowbaz
re : Algorithme sous python 20-01-15 à 12:11

oui ça tourne dans la JVM mais  les performances sont suffisantes, les limites sont en général celles de la machine
Pour des problèmes de maths je ne sais pas quel langage choisir, la programmation fonctionnelle est très pratique mais pas simple à maitriser au début



Vous devez être membre accéder à ce service...

Pas encore inscrit ?

1 compte par personne, multi-compte interdit !

Ou identifiez-vous :


Rester sur la page

Inscription gratuite

Fiches en rapport

parmi 1742 fiches de maths

Désolé, votre version d'Internet Explorer est plus que périmée ! Merci de le mettre à jour ou de télécharger Firefox ou Google Chrome pour utiliser le site. Votre ordinateur vous remerciera !