Annuler
connectez vous
autre en post-bac
- Ensemble et application Partie II
- Équations différentielles : un Cours complet avec des exemples
- Généralités sur les matrices, applications linéaires, changement de base, rang d'une matrice - supérieur
- Espaces vectoriels et Applications linéaires - supérieur
- Un best-of d'exos de probabilités (après le bac)
Inscription / Connexion Nouveau Sujet
Accueil l'île des mathématiques Forum de mathématiquesListe de tous les forums de mathématiques SupérieurOn parle exclusivement de maths, pour le supérieur principalement, les BTS, IUT, prépas... LicenceMaths 2e/3e a AutreTopics traitant de autre [tout]Lister tous les topics de mathématiques
Niveau LicenceMaths 2e/3e a
Programmation Python
Posté par Crysalya
Bonjour,
Je dois trouver la réponse de ce problème en programmant un algorithme python :
En divisant 100 millions par un nombre entier, il peut arriver que le diviseur, le quotient et le reste soient composés des mêmes chiffres. Plus précisément, tous les chiffres du diviseur sont présents au moins une fois dans le quotient et dans le reste et aucun autre chiffre n'apparaît.
Voici une possibilité : 100 000 000 / 91 810 = 1089. Le reste est 18 910. Le 0, le 1, le 8 et le 9 apparaissent dans les trois nombres et ce sont les 4 seuls chiffres qui apparaissent
Quelle est l'autre possibilité ?
J'ai donc essayé de programmé mais je ne suis pas très douée.
J'ai fait un programme qui me donne le diviseur, le quotient et le reste (en ayant pour diviseur tous les nombres inférieurs à 100 millions). Cependant, le programme est extrêmement long à exécuter et il est clairement impossible de chercher après parmi 100 millions de nombres lequel convient.
J'aurai donc aimé savoir si quelqu'un aurait quelque pistes pour m'aider à programmer ça sachant que je ne sais absolument pas comment programmer le fait que 3 nombres soient composés des mêmes chiffres.
Je vous montre le programme que j'ai fait (qui est largement insuffisant pour répondre au problème)
def probleme(x):
for y in range(1, x):
q, r = divmod(x, y)
print(y, q, r)
print(probleme(100000000))
Voilà donc si quelqu'un sur ce forum est doué en python, je serai bien preneuse d'un peu d'aide.
Merci d'avance
Louisa
En réalité, c'est la fonction print qui prend un temps gigantesque à s'éxécuter. Une fois ça va. 100 millions de fois, non.
Stocke toutes les solutions dans une liste, et affiche ensuite la liste en une seule fois, après la boucle
Je vais partir donc je mets la solution (je pense qu'il y a bcp plus simple) mais essaie de faire de toi même avant de regarder!
def probleme():
N = 100_000_000
for i in range(1,N):
### On transforme 233155 en '233155'
diviseur = str(i)
quotient = str(N//i)
reste = str(N - N//i*i)
### On transforme '233155' en ['2','3','3','1','5','5'] puis
### en supprimant les doublons en ['2','3', '1', '5']
diviseur = list(set([c for c in diviseur]))
quotient = list(set([c for c in quotient]))
reste = list(set([c for c in reste]))
### On trie ['2','3', '1', '5'] devient ['1', '2', '3', '5']
diviseur.sort()
quotient.sort()
reste.sort()
### Les 3 quantités diviseur, quotient, piochent dans les mm chiffres
### si les 3 listes transformées précédemment sont exactement les mêmes
if diviseur == quotient and quotient == reste :
print(i, diviseur, quotient, reste)
return i- c'est trivialement inutile pour 100_000_000, mais c'est plus conforme à l'énoncé d'aller jusqu'à N inclus
- quitte à faire ça naïvement, autant faire directement
def probleme(x):
s= []
for d in range(1, x+1):
q, r = divmod(x,d)
if set(str(d))==set(str(q))==set(str(r)):
s.append(d)
break
return s
print probleme(100000000)- il y a des manières intelligentes de traiter ce problème avec une meilleure complexité. Mais ces manières n'intéressent pas Crysalya qui s'est tirée une fois la réponse postée
Plutôt
def probleme(x):
for d in range(1, x+1):
q, r = divmod(x,d)
if set(str(d))==set(str(q))==set(str(r)):
return (d,q,r)
print probleme(100000000)salut
Ulmiere : on peut "gagner" une étape (et du temps 
) pour la boucle en allant jusqu'à x
car pour tout n : n = 1 * (n - 1) + 1
et le seul cas où n - 1 n'est constitué que de 1 ... ben c'est le seul cas où n - 1 n'est constitué que de 1
bon je m'en vais ... 
et même en poursuivant ce raisonnement on peut même aller jusqu'à x - 9
puisque pour tout chiffres c on a : n = 1 * (n - c) + c
(enfin si n > 10) ...
Il y a une relation forte entre quotient et diviseur, qui fait qu'on peut gagner encore plus de temps (modulo une petite vérification sur x), en ne parcourant que les dénominateurs inférieurs ou égaux à x//2, et en vérifiant que d, x//d et x-x*d*x//d donnent le même ensemble de chiffres.
oui effectivement : plus on met de contrôles plus on réduit le temps d'exécution ...
mais en même temps on effectue plus de tests à chaque tour ... il faut trouver le bon équilibre
une question : ton programme de 18h25 met combien de temps ?