/* Topic des codeurs couche-tard [2] */

Compteur du TdCCT · Le 06/12/2010, à 07:42

Scores totaux, depuis le début :

1) 2012    nesthib
2) 1925    samuncle
3) 1611    Pylade
4) 1249    Кຼزດ
5) 1034    cm-t
6) 908+5  grim7reaper /* ./viewtopic.php?pid=3486252#p3486252 */
7) 710    \\Ouranos//
8) 696    Р☢w ! ✰ :mad: ✰ (эй !)
9) 670    helly
10) 431    gnuuat
11) 424    Lagierl
12) 299    tshirtman
13) 196    Askelon
14) 172    nathéo
15) 167    Kanor
16) 121    ǤƦƯƝƬ
17) 93    petifrancais
18) 78    edge_one
19) 70    gulp
20) 68    pierguiard
21) 59    kamui57
21) 59    The Uploader
23) 37    ilagas
24) 32    Le Rouge
25) 30    keny
26) 25    GentooUser
27) 24    ไ୦บเઢ'
28) 20    Morgiver
28) 20    CROWD
28) 20    xapantu
31) 18    Ph3nix_
32) 15    timsy
33) 14    kouskous
34) 12    stratoboy
34) 12    sailing
36) 11    alexises
36) 11    Crocoii
36) 11    Steap
39) 10    Toineo
39) 10    NutMotion
39) 10    pseudovingtcinqcaracteres
39) 10    pfriedZ
43) 8    Mornagest
43) 8    Sherwood51
45) 7    Vista
46) 6    Zeibux
46) 6    ubuntlin
46) 6    asma.geek
49) 5    tendances-tdct
50) 4    danychou56
50) 4    Neros
50) 4    Biaise
50) 4    totoflute
50) 4    pinballyoda ㋛
55) 2    SoJaS
55) 2    ceric
57) 1    geenux

Compteur du TdCCT · Le 06/12/2010, à 07:42

Scores de la période en cours :

1) 35    nesthib
1) 35    samuncle
3) 32    Кຼزດ
4) 27    cm-t
5) 24    Pylade
6) 21    grim7reaper
7) 16    Lagierl
8) 14    helly
9) 11    \\Ouranos//
10) 6    tshirtman
10) 6    Steap
12) 5    Р☢w ! ✰ :mad: ✰ (эй !)
13) 4    gnuuat
14) 1    xapantu

tshirtman · Le 06/12/2010, à 08:17

hum, une list comprehension ça doit bouffer beaucoup trop de mémoire (on veut que les dix derniers non?)… j'aurais plutot été du coté de l'iteratteur moi…

grim7reaper · Le 06/12/2010, à 09:06

On veut les 10 derniers chiffres de la sommes des termes.

Ça dépend de la manière dont ton langage gère les list comprehension.
En haskell, j'utilise autant de mémoire avec une liste qu'en faisant faisant la somme termes à termes en tail recursion.

helly · Le 06/12/2010, à 11:57

\o/ enfin trouvé la solution du 5 !

--plus petit nombre divisble par [1..n]

miniNb :: Int -> Int
miniNb n = fcnt 1 [1..n]

fcnt :: Int -> [Int] -> Int
fcnt a [] = a
fcnt a (x:xs) = fcnt ((a*x)`div`(pgcd a x)) xs

pgcd :: Int -> Int -> Int
pgcd a 0 = a
pgcd a b = pgcd b (a `rem` b)

Par contre, il doit y avoir un problème : pour 10, ça marche, mais pas pour 20 !
La valeur pour n == 20, je la trouve en lançant miniNb 19…

Dernière modification par helly (Le 06/12/2010, à 11:58)

grim7reaper · Le 06/12/2010, à 12:03

J'ai fait ça sans PGCD moi.
Tu n'avais pas dis que tu utiliserais la décomposition en facteur premier ?

helly · Le 06/12/2010, à 12:09

Oui, j'avais dit, mais j'en ai pas eu besoin .
Jvoyais pas comment poser ça en code.

Sinon, c'est pas pour dire, mais y'a une grosse faille dans l'énoncé !

Quel est le plus petit nombre qui est divisible par tous les nombres de 1 à 20 ?

Bhaaa

miniNb :: Int -> Int
miniNb n = 0

Et voilà.

Dernière modification par helly (Le 06/12/2010, à 12:11)

grim7reaper · Le 06/12/2010, à 12:11

Les 2 sembles aussi rapides mais

*Main> miniNb 200
-39562552

Vs

*Main> product (factor (takeWhile (< 200) primes) 2 200)
337293588832926264639465766794841407432394382785157234228847021917234018060677390066992000

Ne force pas le type Int, contente toi de le restreindre à Integral et laisse le choisir

Dernière modification par grim7reaper (Le 06/12/2010, à 12:13)

helly · Le 06/12/2010, à 12:13

sed s/Int/Integer/s .
Mais ok oui, autant toujours mettre en Integer.

Dernière modification par helly (Le 06/12/2010, à 12:15)

grim7reaper · Le 06/12/2010, à 12:15

Integral c'est plus propre, il n'utilise pas les Integer pour rien (c'est plus lent que les Int donc si on peut les éviter).

miniNb :: (Integral a) => a -> a 
miniNb n = fcnt 1 [1..n]

fcnt :: (Integral a) => a -> [a] -> a 
fcnt a [] = a
fcnt a (x:xs) = fcnt ((a*x)`div`(pgcd a x)) xs

pgcd :: (Integral a) => a -> a -> a
pgcd a 0 = a
pgcd a b = pgcd b (a `rem` b)

Sinon, je deviens meilleurs que toi vers 1000. Les nombres premiers vaincront

Dernière modification par grim7reaper (Le 06/12/2010, à 12:17)

helly · Le 06/12/2010, à 12:17

Ha, j'avais pas pensé à utiliser Integral !
J'ai pas encore fini de lire le tuto en fait…
Y'a pas une commande via ghci pour mesurer le temps d'execution d'une commande ?

Dernière modification par helly (Le 06/12/2010, à 12:23)

grim7reaper · Le 06/12/2010, à 12:19

Non, je ne crois pas (mais j'ai pas des masse cherché non plus).
En général je compile, ou sinon je chrono à la main dans ghci ^_^ (c'est approximatif, mais ça suffit pour voir si je suis < 1 min).

grim7reaper · Le 06/12/2010, à 19:59

@helly : alors, tu as trouvé la fonction magique pour le problème 12 ?

Sinon, j'ai fait quelques bench pour comparer ta solution (à base de PGCD) à la mienne (à base de décomposition en facteurs premiers).
À partir de 1 000, des différences très minimes sont visible.
Pour 10 000

time ./helly
real    0m0.141s
user    0m0.127s
sys    0m0.000s

time ./grim
real    0m0.018s
user    0m0.017s
sys    0m0.000s

Pour 100 000

time ./helly
real    0m13.522s
user    0m11.059s
sys    0m0.010s

time ./grim
real    0m0.262s
user    0m0.177s
sys    0m0.000s

Dernière modification par grim7reaper (Le 06/12/2010, à 20:00)

tshirtman · Le 06/12/2010, à 20:03

à première vue, une complexité n² et une complexité n,

helly · Le 06/12/2010, à 20:05

tshirtman a écrit :

à première vue, une complexité n² et une complexité n,

Au lieu de te moquer, trouve nous l'algo en log(n) !
@grim : pas revu depuis, je boss un peu les cours là.
Sinon non, à vu de nez comme ça, je vois pas trop.

Dernière modification par helly (Le 06/12/2010, à 20:09)

grim7reaper · Le 06/12/2010, à 20:10

helly a écrit :

@grim : pas revu depuis, je boss un peu les cours là.

C'est ce que je devrais faire aussi…

Sinon non, à vu de nez comme ça, je vois pas trop.

(1) Tu cherches un nombre qui possède un certains nombre de diviseurs.
(2) Et pour tester ça il te faudrait une fonction.
Une combinaison de mots de la phrase (1) et (2) + une recherche sur Internet devrait te donner une bonne piste pour une solution efficace (après il faudra la comprendre et la coder, mais bon ça devrait être jouable )

Dernière modification par grim7reaper (Le 06/12/2010, à 20:13)

helly · Le 06/12/2010, à 20:17

Merci, je vais faire mariner ça.
edit : je pense avoir trouvé un truc, sans internet : on cherche un nombre le plus petit possible, possédant plus de N diviseurs.
Pour trouver un nombre le plus petit à N diviseurs, il suffit de de mutliplier [1..N], puis on veut un nombre triangulaire, donc on cherche le premier nombre triangulaire <= à cette multiplication.
/me va tester ça.

Dernière modification par helly (Le 06/12/2010, à 20:25)

Pylades · Le 06/12/2010, à 20:32

http://projecteuler.net/index.php?secti … lems&id=10
/me se félicite d'être en 64 bits. Et se demande sérieusement comment vont faire ceux qui sont en C sur du 32 bits.
long long sera probablement votre ami… mais voilà, quoi…

Ouais, integer overflow sur un unsigned int. /me a été pris d'un vivacité d'esprit dont il s'étonne encore pour trouver d'où venait le problème. En même temps, ça ne pouvait être que ça : ses codes sont toujours parfaits.

grim7reaper · Le 06/12/2010, à 20:37

helly a écrit :

je pense avoir trouvé un truc, sans internet : on cherche un nombre le plus petit possible, possédant plus de N diviseurs.
Pour trouver un nombre le plus petit à N diviseurs, il suffit de de mutliplier [1..N], puis on veut un nombre triangulaire, donc on cherche le premier nombre triangulaire <= à cette multiplication.
/me va tester ça.

Tu peux tester ça, mais je ne sais pas ce que ça risque de donner. Enfin, il faut expérimenter
Moi j'ai encore utilisé les nombres premiers , et le résultat est plutôt performant.

@Pylade : ouais, long long ou GMP si on est au taquet.
Sinon, il y a pire : le 97 .
Là je crois que GMP s'impose (ou une solution bricolée maison).

Dernière modification par grim7reaper (Le 06/12/2010, à 20:47)

Pylades · Le 06/12/2010, à 21:03

Non, pour le 97, je pense qu'un crayon peut suffire. Il faut juste se rappeler de la spé maths de TS, et ça devrait rouler. Je suis sûr d'avoir su faire des trucs comme ça.

grim7reaper · Le 06/12/2010, à 21:05

Possible, moi j'ai fait ça à l'arrache vu que j'avais le résultat suffisament vite (et sans rien optimiser ni compiler).
Mais si tu as une technique plus intelligente, je serais preneur bien évidemment

Pylades · Le 06/12/2010, à 21:14

Ouais, je vais devoir fouiller dans mes souvenirs… ^^

http://projecteuler.net/index.php?secti … lems&id=79
Euh, c'est quoi le rapport avec le code, là ? La solution saute aux yeux… et d'après ce que j'ai pu lire dans le forum, je ne suis pas le seul dans ce cas…

grim7reaper · Le 06/12/2010, à 21:20

Oui, il y a certains problèmes qui sont plus simple à faire à la main qu'à coder.

helly · Le 06/12/2010, à 21:31

Oui, par exemple le célèbre problème sois disant incodable mais très simple à déduire humainement, je me souvients plus de sa teneur, ça parle d'un pancarte et de sœurs cadette je crois.

Elzen · Le 06/12/2010, à 22:52

Un truc genre « la somme de l'âge de mes filles est égal au numéro sur la porte d'en face.
– Il me manque une donnée.
– Oui, j'ai oublié de dire que l'aînée était blonde. » ?

Ubuntu-fr

Navigation

Liens de recherche

Annonce

#1951 Le 06/12/2010, à 07:42

Re : /* Topic des codeurs couche-tard [2] */

#1952 Le 06/12/2010, à 07:42

Re : /* Topic des codeurs couche-tard [2] */

#1953 Le 06/12/2010, à 08:17

Re : /* Topic des codeurs couche-tard [2] */

#1954 Le 06/12/2010, à 09:06

Re : /* Topic des codeurs couche-tard [2] */

#1955 Le 06/12/2010, à 11:57

Re : /* Topic des codeurs couche-tard [2] */

#1956 Le 06/12/2010, à 12:03

Re : /* Topic des codeurs couche-tard [2] */

#1957 Le 06/12/2010, à 12:09

Re : /* Topic des codeurs couche-tard [2] */

#1958 Le 06/12/2010, à 12:11

Re : /* Topic des codeurs couche-tard [2] */

#1959 Le 06/12/2010, à 12:13

Re : /* Topic des codeurs couche-tard [2] */

#1960 Le 06/12/2010, à 12:15

Re : /* Topic des codeurs couche-tard [2] */

#1961 Le 06/12/2010, à 12:17

Re : /* Topic des codeurs couche-tard [2] */

#1962 Le 06/12/2010, à 12:19

Re : /* Topic des codeurs couche-tard [2] */

#1963 Le 06/12/2010, à 19:59

Re : /* Topic des codeurs couche-tard [2] */

#1964 Le 06/12/2010, à 20:03

Re : /* Topic des codeurs couche-tard [2] */

#1965 Le 06/12/2010, à 20:05

Re : /* Topic des codeurs couche-tard [2] */

#1966 Le 06/12/2010, à 20:10

Re : /* Topic des codeurs couche-tard [2] */

#1967 Le 06/12/2010, à 20:17

Re : /* Topic des codeurs couche-tard [2] */

#1968 Le 06/12/2010, à 20:32

Re : /* Topic des codeurs couche-tard [2] */

#1969 Le 06/12/2010, à 20:37

Re : /* Topic des codeurs couche-tard [2] */

#1970 Le 06/12/2010, à 21:03

Re : /* Topic des codeurs couche-tard [2] */

#1971 Le 06/12/2010, à 21:05

Re : /* Topic des codeurs couche-tard [2] */

#1972 Le 06/12/2010, à 21:14

Re : /* Topic des codeurs couche-tard [2] */

#1973 Le 06/12/2010, à 21:20

Re : /* Topic des codeurs couche-tard [2] */

#1974 Le 06/12/2010, à 21:31

Re : /* Topic des codeurs couche-tard [2] */

#1975 Le 06/12/2010, à 22:52

Re : /* Topic des codeurs couche-tard [2] */

Pied de page des forums