Inscription / Connexion Nouveau Sujet
Niveau énigmes
Partager :

Multiplication(s)

Posté par
derny
28-04-18 à 08:43

Bonjour. Après les lettres et chiffres de dpi voici uniquement les chiffres.
Vous avez tous appris à l'école primaire à faire une multiplication (voir ci-dessous).
Trouver une (ou plusieurs) multiplication (s) qui comporte exactement 2 fois tous les chiffres. Puis 3 fois. Puis 4 fois ...
Comme il y a beaucoup de (bons) programmeurs sur ce site c'est un peu une course de vitesse.

Multiplication(s)

Posté par
dpi
re : Multiplication(s) 28-04-18 à 10:26

Bonjour
Et merci d'animer (pas de grille 3 ???)
Ici il sera difficile de trouver 10 ,20 ou 30 chiffres pour avoir un multiple des 10
chiffres originaux.
Quelques sondages:
12x45 nécessite  9 chiffres
92x45 nécessite  11 chiffres
192x45 nécessite  15 chiffres
892x45 nécessite  18 chiffres
292x 145 nécessite  22 chiffres
etc...

Posté par
derny
re : Multiplication(s) 28-04-18 à 10:39

Oui il y aura grille (3) mais je laisse un peu "reposer" les neurones de ceux qui se sont investis car le sujet est difficile.
Pour multiplication(s) il faut évidemment 20 ou 30 ou 40 ... chiffres exactement.

Posté par
dpi
re : Multiplication(s) 28-04-18 à 17:51

Bonsoir
Pour amorcer la pompe et sans blank pour aider je donne le genre de disposition  
       192
   x  253
---------
        576
    960
384
--------
48576
a) il y a bien 20 chiffres
b) mais hélas il faudrait un 1 de plus et un 6 de moins

Posté par
vham
re : Multiplication(s) 28-04-18 à 18:03

Bonjour,

 Cliquez pour afficher

Posté par
vham
re : Multiplication(s) 28-04-18 à 18:15

Bonjour,

 Cliquez pour afficher

Posté par
vham
re : Multiplication(s) 28-04-18 à 18:42

Bonjour,

 Cliquez pour afficher

Posté par
derny
re : Multiplication(s) 30-04-18 à 08:18

Bonjour
Un seul participant déclaré : donc, tous les programmeurs sont en vacances ...

Posté par
vham
re : Multiplication(s) 30-04-18 à 10:03

Bonjour,

La programmation était trop facile peut-être ?
2 solutions en attente pour 4 fois chaque chiffre

Posté par
derny
re : Multiplication(s) 30-04-18 à 11:33

A vham

 Cliquez pour afficher

Posté par
dpi
re : Multiplication(s) 30-04-18 à 11:43

>derny
2 participants ;j'ai essayé comme tu as pu le voir...sans programmation.
Pour 2 fois je n'étais pas loin....mais vham est trop fort.

Posté par
derny
re : Multiplication(s) 30-04-18 à 13:17

Je pense qu'il est pratiquement impossible de se passer de programmation pour ce genre de problèmes sauf peut-être pour 2 fois chaque chiffre et encore. Ceci dit, je ne suis qu'un "programmeur" très occasionnel et qui programme avec "l'antique" Basic.

Posté par
vham
re : Multiplication(s) 30-04-18 à 19:29

Bonsoir,
le VisualBasic.net est tellement supérieur et plus facile,en mode console, bien documenté etc.
Il ne faut pas hésiter, sauf à passer occasionnellement en Python quand le temps d'exécution reste court.

Posté par
derny
re : Multiplication(s) 03-05-18 à 17:49

Bonsoir
Moi qui pensais que les "programmeurs" ne feraient qu'une bouchée de ce problème ...

Posté par
derny
re : Multiplication(s) 07-05-18 à 21:59

Bonsoir
A vham

 Cliquez pour afficher

Posté par
LittleFox
re : Multiplication(s) 10-05-18 à 06:29


Désolé Derny, j'aurais bien tenté mais sans accès à un ordi dur de programmer ^^

Je suis en Équateur depuis 2 mois mais je suis l'île depuis mon smartphone

Je reviens bientôt (2 semaines)

Posté par
derny
re : Multiplication(s) 20-05-18 à 19:33

Bonsoir
En attendant que LittleFox revienne tout bronzé, je signale que j'ai des solutions jusqu'à "5 fois". Je m'étais arrêté là car j'avais peur que, pour mon logiciel Basic, "6 fois" prenne trop de temps.  

Posté par
LittleFox
re : Multiplication(s) 05-06-18 à 11:56


Holà, je suis revenu

J'ai fait un petit script rapide qui teste toutes les multiplications (il ne s'arrête jamais ), qui compte les chiffres obtenus et affiche le résultat si tous les chiffres sont présents le même nombre de fois.

L'énoncé initial n'empêche pas les solutions du style :


   251
   86
______
 1506
2008
_____
21586


Où tous les chiffres sont présents 3 fois. Mais on a que 6 chiffres. Ça rajoute quelques solutions mais on considérera pour la suite qu'il faut les 10 chiffres.

Quid des solutions avec un 0 dans le deuxième terme? Par exemple 3729x2094 :


   3729            3729
   2094            2094
_______         _______
  14916           14916
 33561    ou     33561
    0            0000    
7458            7458
_______         _______
7808526         7808526


J'ai considéré la première solution mais ça va compliquer l'analyse pour améliorer l'algorithme.

Pour des termes inférieurs à 27500, j'ai obtenu les résultats suivants :

1x tous les chiffres : aucune solution

2x tous les chiffres :
179   x 224
9     x 15408


3x tous les chiffres :
3729  x 2094
938   x 5342
2198  x 7034
368   x 7595
818   x 9395
14738 x 245
17906 x 245


4x tous les chiffres :
3908  x 15278
17934 x 6825
19752 x 7275
22782 x 3795
11939 x 24860
26588 x 5153


Amélioration de l'algorithme : On peut calculer que si n est le nombre de chiffres du premier terme et m le nombre de chiffres du deuxième terme alors le nombre total de chiffres est compris entre 2(m+n)+mn-1 et 2(m+n)+m(n+1)  (à condition qu'il n'y ai pas de zéro dans le deuxième terme).
Soit k le nombre de total de chiffres (doit être un multiple de 10) alors \frac{k-2n}{n+3} \le m \le \frac{k-2n+1}{n+2} . Ce qui est finalement un petit intervalle et permet de limiter le nombre de tests.

Reste plus qu'à implémenter .

Posté par
LittleFox
re : Multiplication(s) 05-06-18 à 15:55

Bon, ça marche, je trouve d'autres solutions mais c'est pas fabuleusement plus rapide non plus. Toujours pas trouvé de solutions avec 5 fois tous les chiffres.

2x tous les chiffres : L'algo a fini l'analyse, du coup s'il y a d'autres solutions elles ont un 0 dans le deuxième terme.
(179, 224)
(9, 15408)
(9, 80154)

3x tous les chiffres : Ça commence doucement puis ça explose quand on arrive dans les millions. C'est loin d'être fini. On remarque que deux solutions trouvées avant sont absentes mais elles ont bien des zéros (3729  x 2094 et 2198  x 7034)

 Cliquez pour afficher


4x tous les chiffres : ça devient très lent, seulement 3 nouvelles solutions mais on est qu'au tout début de l'exploration.
(17934, 6825)
(19752, 7275)
(22782, 3795)
(26588, 5153)
(31544, 9215)
(32619, 6432)
(35484, 3252)
...

5x tous les chiffres :  Pas de solutions trouvées après quelques heures. On a largement réduit l'espace de recherche, de 1032 candidats à 1010 + ... + 1017 2,11x1017 . Mais ça reste beaucoup.

Entre temps l'algorithme initial se rapproche des 50000 avec de nouvelles solutions :

3 fois :
173 x 49406

4 fois :
31544 x 9215
32619 x 6432
16392 x 35052
19541 x 35204
12179 x 35240
13943 x 35402
13943 x 35420
35484 x 3252
2069 x 37871
13154 x 40367
22587 x 41403
13118 x 43067
13943 x 45230
39729 x 46005

5 fois : Ma première solution de niveau 5
46509 x 46893

Posté par
LittleFox
re : Multiplication(s) 05-06-18 à 17:09


En laissant tourner un peu plus :

3 fois:
329 x 53120

4 fois:
53976 x 1248
17093 x 54320
11723 x 54830

5 fois:
52965 x 46386
52967 x 39524
38921 x 53597
37932 x 54597
55143 x 37629

C'est tout pour aujourd'hui. Et j'arrête de vous spammer Sauf si je trouve une nouvelle technique bien plus efficace.

Posté par
derny
re : Multiplication(s) 06-06-18 à 09:47

Merci à tous ceux qui se sont penchés sur cet exercice de programmation.
La façon de positionner les "0" m'a fait éliminer certaines configurations que LittleFox a admis. Je les admets volontier même si, personnellement j'avais appris à l'école primaire de ne pas inscrire les lignes intermédiaires nulles (voir exemples ci-dessous).

Multiplication(s)

Multiplication(s)

Posté par
derny
re : Multiplication(s) 06-06-18 à 09:58

Personnellement, je n'avais pas retenu les lignes nulles mais j'avais retenu les cas avec 2 ou 4 "0" rajoutés (voir ci-dessous par exemples).

Multiplication(s)

Posté par
derny
re : Multiplication(s) 06-06-18 à 10:09

Avant de me lancer je ne m'attendais pas à ce que, plus on veut "de fois tous les chiffres", plus il y a de solutions. Pour 5 fois, une centaine de solutions environ.
Personnellement j'ai fait un programme par dispositions possibles de tous les chiffres.
Je pense qu'on peut clôturer ce sujet.

Posté par
LittleFox
re : Multiplication(s) 07-06-18 à 09:26


Ah tiens oui, je n'avais pas remarqué qu'on pouvait adapter le nombre de 0 (en en ajoutant un multiple de 2 dans ton cas, un multiple de 3 dans le mien).

Clairement ce sont les zéros qui sont sujets à controverse. Je ne me souviens plus de mes méthodes de primaires , ça m'avait juste semblé naturel de mettre zéro sur la ligne et d'incrémenter le décalage.

Faudra que tu m'expliques comment tu fais pour avoir un algo efficace par disposition possible de tous les chiffres.

Posté par
derny
re : Multiplication(s) 07-06-18 à 17:05

Bonsoir
Quand je parle de dispositions différentes je parle de différentes façons de placer les 20 (ou 30 ou 40 ou …) chiffres de la multiplication. Comme par exemples la multiplication de l'énoncé initial ou comme ci-dessous. A noter 2 curiosités ci-dessous : 1)_ les rois "8" sont positionnés au même endroit pour les 2 premières multiplications et 2)_ on a le même multiplicateur pour les 2 dernières multiplications.

Multiplication(s)

Posté par
LittleFox
re : Multiplication(s) 08-06-18 à 11:07


Oui mais il y a 1043 façon de disposer les 5x10 chiffres du niveau 5 (à multiplier par le nombre de "schémas": est-ce qu'on mets 2,3,4 ou 5 chiffres dans le premier terme, etc). C'est totalement impraticable. Déjà mon espace de rechercher de 1017 est beaucoup trop grand.

J'avais comme idée de choisir un schéma (n chiffres pour le premier terme et n chiffres pour le second), d'ensuite disposer les chiffres dans le premier terme et enfin disposer les chiffres dans le second terme un par un (et le produit de ce chiffre avec le premier terme) en utilisant la contrainte que les chiffres déjà disposés ne peuvent pas être plus nombreux que le niveau.
Ça pourrait marcher mais le code est beaucoup plus compliqué.

Posté par
LittleFox
re : Multiplication(s) 08-06-18 à 17:46


Bon j'ai implémenté un code qui marche, est un tout petit peu plus rapide mais est bien plus complexe (python), il implémente la version de derny avec les lignes à zéro
non écrites :

 Cliquez pour afficher


Comme d'habitude s'il y a d'autres solutions alors le deuxième terme contient des zéros.

2 fois
(179, 224)

3 fois
 Cliquez pour afficher


4 fois
 Cliquez pour afficher


5 fois
 Cliquez pour afficher

Posté par
derny
re : Multiplication(s) 09-06-18 à 13:29

Bonjour. Merci LittleFox pour ta contribution "pro" de programmateur. Tu as cerné le problème d'une façon efficace. Comme je ne connais pas le langage python je ne comprends pas tout. Il faudrait que je m'y mette. Bien sûr je n'avais pas étudié toutes les dispositions possibles mais pas mal quand même.



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

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 !