Annonce

Réduire
Aucune annonce.

Challenge mathématique simple

Réduire
X
 
  • Filtre
  • Heure
  • Afficher
Tout nettoyer
nouveaux messages

  • Challenge mathématique simple

    Alors, je suis tombé "accidentellement" aujourd'hui sur un Challenge dans les archives...
    Envoyé par Geuks
    Ahh je voie le genre , je dois en avoir en stock ^^,
    Du genre,

    Soit un nombre composé de neufs chiffres distincts (de 1 à 9) disposés de telle sorte que:

    - Le premier chiffre soit divisible par un,
    -Le nombre formé des deux premiers chiffres soit divisible par deux,
    -Le nombre formé par les trois premiers chiffres divisible par trois,
    -Et ainsi de suite jusqu'à 9.

    Quel est ce nombre ?

    J'ai mis un petit moment à la trouver celle là ^^
    Pour y aller plus vite j'ai bidouillé un script Python qui se charge d'en trouver un "aléatoirement". Alors, j'en ai des tonnes
    Code:
    import random
    
    def force(base='1',mod=2):
        x = int(base)*10
        lst = list(range(9))
        random.shuffle(lst) #On donne la possibilite de trouver des sol diff.
        for i in lst:
            if (x+i)%mod == 0:
                return base+str(i)
    
    
    def find():
        #On donne la possibilite de trouver des sol diff.
        res = str(random.randint(1,9))
        for i in range(2,10):
            res = force(res, i)
        print ("The found number is : ", res)
    
    find()
    Dernière modification par comaX, 09 janvier 2012, 20h17. Motif: Petite erreur au passé en anglais : found est déjà le préterit de find ;) founded veut dire "fondé", au sens de "bâti".

  • #2
    Neuf chiffres distincts, ca veut pas dire qu'il ne doit pas y avoir de doublon ?

    Du genre : 123456789 :
    1 est divisible par un
    12 est divisible par deux
    123 est divisible par 3
    1234 n'est pas divisible par 4, merde.
    12345 est divisible par 5... etc.

    Bref, tu m'as compris quoi ^^ Moi c'est ce que j'avais compris, sans quoi ajouter "distincts" est superfétatoire.

    Amis de la poésie, notez comment j'ai calé ce mot de ouf. J'suis un peu fier là ; c'est pas tous les jours que j'arrive à le caler.
    Dernière modification par comaX, 09 janvier 2012, 20h21.

    Commentaire


    • #3
      Envoyé par comaX Voir le message
      Neuf chiffres distincts, ca veut pas dire qu'il ne doit pas y avoir de doublon ?

      Du genre : 123456789 :
      1 est divisible par un
      12 est divisible par deux
      123 est divisible par 3
      1234 n'est pas divisible par 4, merde.
      12345 est divisible par 5... etc.

      Bref, tu m'as compris quoi ^^ Moi c'est ce que j'avais compris, sans quoi ajouter "distincts" est superfétatoire.

      Amis de la poésie, notez comment j'ai calé ce mot de ouf. J'suis un peu fier là ; c'est pas tous les jours que j'arrive à le caler.
      Je crois bien que cerveau avait skippé "distincts" :mouarf:
      Il semble unique ce nombre "magique" alors là, on va faire du surmène-UC:
      Code:
      import random
      
      def verify(lst=[]):
          for i in range(1,10):
              val = int("".join(lst[:i]))
              if val%i!=0:
                  return False
          return True
      
      def brute_force():
          import time
          t0 = time.time()
          print("Started")
          lst = list("123456789")
          while not(verify(lst)):
              random.shuffle(lst)
          print("The Magic number is : " + "".join(lst))
          print("Ended " + str(time.time()-t0) + " seconds")
      
      brute_force()
      >>>
      Started
      The Magic number is : 381654729
      Ended 7.72900009155 seconds
      >>>
      Naturellement le temps pour trouver va et vient selon la volonté de votre bonne étoile.

      Commentaire


      • #4
        Ca me parait bon tout ça ! Par contre, je pige pas du tout le code. Où sont les "règles" dans le code ? C'est pas verifiy() quand même, si ?

        Started
        The Magic number is : 381654729
        Ended 6.732000112533569 seconds
        Il semble en effet unique...

        edit : avec 10 tests successifs. Effectivement le temps de génération est complètement aléatoire :
        Code:
        Started
        The Magic number is : 381654729
        Ended 6.621999979019165 seconds
        Started
        The Magic number is : 381654729
        Ended 9.58899998664856 seconds
        Started
        The Magic number is : 381654729
        Ended 2.6500000953674316 seconds
        Started
        The Magic number is : 381654729
        Ended 0.11599993705749512 seconds
        Started
        The Magic number is : 381654729
        Ended 1.7760000228881836 seconds
        Started
        The Magic number is : 381654729
        Ended 4.63700008392334 seconds
        Started
        The Magic number is : 381654729
        Ended 15.086999893188477 seconds
        Started
        The Magic number is : 381654729
        Ended 2.441999912261963 seconds
        Started
        The Magic number is : 381654729
        Ended 10.690999984741211 seconds
        Started
        The Magic number is : 381654729
        Ended 3.4260001182556152 seconds
        Dernière modification par comaX, 09 janvier 2012, 21h01.

        Commentaire


        • #5
          Envoyé par comaX Voir le message
          Ca me parait bon tout ça ! Par contre, je pige pas du tout le code. Où sont les "règles" dans le code ? C'est pas verifiy() quand même, si ?
          Les "règles" c'est effectivement la fonction verify.
          Code:
          import random
          
          def verify(lst=[]):
              for i in range(1,10): #parcours 9 fois de la liste <lst>, pour vérifier les 9 "divisibilités"
                  val = int("".join(lst[:i])) #produit un entier avec les élément o...i
                  if val%i!=0:    #vérifie que cet entier est divisible par i
                      return False    #Si c'est pas le cas pour toute la liste, cul de sac
              return True  #Si ca roule pour tout le monde, on a le Magic-Number
          
          def brute_force():
              import time
              t0 = time.time()
              print("Started")
              lst = list("123456789")
              while not(verify(lst)): #On s'entête à trouve un nombre qui marche
                  random.shuffle(lst) #On malaxe aléatoirement les 9 chiffres qu'on a et on reéssaie
              print("The Magic number is : " + "".join(lst))
              print("Ended " + str(time.time()-t0) + " seconds")
          
          brute_force()

          Commentaire


          • #6
            Hmm, ca s'éclaircie, mais je n'y suis toujours pas... En tout cas, merci beaucoup pour les commentaires !

            Si j'avais du coder ça, j'aurais d'abord défini toutes les combinaisons possibles d'un nombre de neuf chiffres sans répétition.
            Je n'ai plus les formules de combinatoires en tête (au pif, quelque chose comme 10!, soit 3 628 800), mais il ne doit pas y en avoir des masses. Ensuite je n'aurais gardé que les nombres avec un 0 ou un 5 en 5° position, ce qui devrait déjà grandement réduire la liste... Et ainsi de suite, selon les restrictions décroissantes de la divisibilité (donc on termine par le premier divisible par un, puisqu'ils le seront tous.

            Bref, si j'ose, ce serait plus un algorithme... J'essayerai en bash ou awk à l'occasion !

            Edit : d'après mes rapides vérifications, le nombre de possibilités est bien 10!. 3 ans sans faire de maths, et je me souviens de ça. "Like a boss".
            Dernière modification par comaX, 09 janvier 2012, 22h53.

            Commentaire


            • #7
              Envoyé par comaX Voir le message
              Edit : d'après mes rapides vérifications, le nombre de possibilités est bien 10!. 3 ans sans faire de maths, et je me souviens de ça. "Like a boss".
              En fait, un nombre de 9 chiffres distincts (1..9), ca fait : A(9 dans 9) == 9! == 362880

              Ta méthode est en fait la meilleure et la plus rapide, et démontre bien que cet élément est unique.
              Code:
              import itertools
              
              def verify(lst=[]):
                  for i in range(1,10): #parcours les 9 éléments de la liste <lst>
                      val = int("".join(lst[:i])) #produit un entier avec les élément o...i
                      if val%i!=0:    #vérifie que cet entier est divible par i
                          return False    #Si c'est pas le cas pour toute la liste, cul de sac
                  return True  #Si ca roule pour tout le monde, on a le Magic-Number
              
              #production de la liste avec les elements voulus
              lst = list("123456789") 
              
              #productiond de toutes les permutations possibles :9!
              cLst = list(itertools.permutations(lst))
              print("remaining items : ", len(cLst))
              
              ##Les suppressions des ici sont facultatives
              #suppression des non multiples de 2 en position 2
              cLst = [i for i in cLst if i[1] in "2468"]
              print("remaining items : ",len(cLst))
              #suppression des non multiples de 5 en position 5
              cLst = [i for i in cLst if i[4] == "5"]
              print("remainig items : ", len(cLst))
              
              
              res = [i for i in cLst if verify(i)]
              print("remaining items: ")
              for i in res:
                  print ("\t" + "".join(i))

              Commentaire


              • #8
                Effectivement, 9!... Va savoir pourquoi 10 m'est passé par la tête !

                Ravi de voir que ma méthode est plus rapide et meilleure, je suis flatté !

                Ceci-dit, est-ce qu'il ne serait pas encore plus rapide d'éliminer les 5 en premier ?

                Commentaire


                • #9
                  Envoyé par comaX Voir le message
                  Effectivement, 9!... Va savoir pourquoi 10 m'est passé par la tête !

                  Ravi de voir que ma méthode est plus rapide et meilleure, je suis flatté !

                  Ceci-dit, est-ce qu'il ne serait pas encore plus rapide d'éliminer les 5 en premier ?
                  Dans le mil, car pour l'élimination des 2 on aurait beaucoup moins d'éléments. :hola:

                  Commentaire


                  • #10
                    Oh yeah

                    J'ai grandement modifié le code *hum hum, menteur* pour afficher le temps, et en effet, c'est sans appel :

                    remaining items : 362880
                    remaining items : 161280
                    remainig items : 20160
                    remaining items:
                    381654729
                    Ended 0.29537987709 seconds

                    Je vais essayer avec les 5 en premier et je réédite !

                    remaining items : 362880
                    remainig items : 40320
                    remaining items : 20160
                    remaining items:
                    381654729
                    Ended 0.270968914032 seconds

                    Bon, c'est quand même pas très significatif à deux centièmes de seconde près...

                    Ceci dit, on passe quand même de 161K à traiter à 40K à traiter
                    Dernière modification par comaX, 10 janvier 2012, 16h10.

                    Commentaire


                    • #11
                      Envoyé par comaX Voir le message
                      Oh yeah

                      J'ai grandement modifié le code *hum hum, menteur* pour afficher le temps, et en effet, c'est sans appel
                      Je crois que toute modif de plus d'un caractère est une grande modification alors...

                      Bon, c'est quand même pas très significatif à deux centièmes de seconde près...
                      peut-être, mais pour un nombre magique à 3 chiffres de plus, ca ferait beaucoup (et vraiment) de secondes en moins
                      Dernière modification par afranck64, 10 janvier 2012, 16h24.

                      Commentaire


                      • #12
                        J'ai essayé avec 20, et ca a pris deux secondes (donc effectivement, beaucoup plus de temps, même si ca reste court), mais pas de chiffre trouvé. J'imagine qu'il n'y en a peut être simplement pas !

                        Commentaire


                        • #13
                          Envoyé par comaX Voir le message
                          J'ai essayé avec 20, et ca a pris deux secondes (donc effectivement, beaucoup plus de temps, même si ca reste court), mais pas de chiffre trouvé. J'imagine qu'il n'y en a peut être simplement pas !
                          Je crois que le pétard est dû au fait qu'il prend "10", "11", "12", ..."19" pour des chiffres alors... que le problème n'est pas "posable" pour plus de 9 chiffres

                          Commentaire


                          • #14
                            Je n'ai pas allongé la liste, seulement la taille du nombre final ! Ceci-dit, selon comment est foutu le code, comme je n'ai pas bien fait attention, ca peut revenir au même, in deed.

                            Commentaire


                            • #15
                              Envoyé par comaX Voir le message
                              Je n'ai pas allongé la liste, seulement la taille du nombre final ! Ceci-dit, selon comment est foutu le code, comme je n'ai pas bien fait attention, ca peut revenir au même, in deed.
                              Pour ce qui est d'allongé la liste... la méthode employé n'est pas RAM-friendly vu qu'on n! listes de n éléments en mémoire... j'ai fait un test en ajoutant 0, c'est passé, 3 solutions(moyennant un léger édit du code):
                              Code:
                              def verify(lst=[]):
                              
                                  for i in range(1,len(lst)): #parcours les 9 éléments de la liste <lst>
                                      val = int("".join(lst[:i])) #produit un entier avec les élément o...i
                                      if val%i!=0:    #vérifie que cet entier est divible par i
                                          return False    #Si c'est pas le cas pour toute la liste, cul de sac
                                  return True  #Si ca roule pour tout le monde, on a le Magic-Number
                              3 soluces (pas dispo car...)
                              Pour le test avec 11 éléments, j'ai eu au bout de ... peut-être 1 min 49 secondes une belle: MemoryERROR mes 2Go de RAM
                              étaient parties en fumées pour la production de permutations. Faut dire que ca fait tout de même 11!*liste_de_11_chars

                              Commentaire

                              Chargement...
                              X