Annonce

Réduire
Aucune annonce.

Challenge mathématique simple

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

  • Yodark
    a répondu
    [?]([x] soit 2,4,6,8)([x][x]soit 13,31,17,71,26,62,39,93,48,84,79,97)[5]([x][x][x] soit ...pas mal de possibilités ^^)[?] . la sommes des trois premiers chiffres doit être divisible par 3.


    [EDIT]

    J'ai dit "pas mal de possibilités" Mais enfaîte pas tant que ça... Si ont enlève tous ceux qui contiennent un 5 un 0 et des doublons ça fait 42 possibilités(Si je n'ai pas fait d'erreur)
    Dernière modification par Yodark, 03 décembre 2012, 14h00.

    Laisser un commentaire:


  • afranck64
    a répondu
    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

    Laisser un commentaire:


  • comaX
    a répondu
    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.

    Laisser un commentaire:


  • afranck64
    a répondu
    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

    Laisser un commentaire:


  • comaX
    a répondu
    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 !

    Laisser un commentaire:


  • afranck64
    a répondu
    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.

    Laisser un commentaire:


  • comaX
    a répondu
    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.

    Laisser un commentaire:


  • afranck64
    a répondu
    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:

    Laisser un commentaire:


  • comaX
    a répondu
    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 ?

    Laisser un commentaire:


  • afranck64
    a répondu
    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))

    Laisser un commentaire:


  • comaX
    a répondu
    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.

    Laisser un commentaire:


  • afranck64
    a répondu
    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()

    Laisser un commentaire:


  • comaX
    a répondu
    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.

    Laisser un commentaire:


  • afranck64
    a répondu
    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.

    Laisser un commentaire:


  • comaX
    a répondu
    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.

    Laisser un commentaire:

Chargement...
X