Enigmes

Forum dédié aux énigmes et à toutes formes de jeux de logique.

Déconnexion

Tu n'es pas identifié sur Prise2tete : s'identifier.

accueil Accueil forum Forum
[+]

 #26 - 03-05-2016 17:43:07

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 3136

nombres premiers d'adsition

Scarta, c'est bon également, bravo à toi.

Si tu te sens inspiré par le second problème, avec les chiffres binaires, n'hésite pas...

#0 Pub

 #27 - 04-05-2016 00:25:13

scarta
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 1473

Nombres premierrs d'addition

Si j'ai bien compris, tu veux pareil mais en changeant + par | (bitwise or) dans les deux lignes sums[...+...]
Je te donnerai le résultat demain quand j'aurai mon ordi sous la main mais d'instinct je dirais que le résultat doit être sensiblement plus grand

 #28 - 04-05-2016 07:22:09

enigmatus
Professionnel de Prise2Tete
Enigmes résolues : 0
Messages : 422

Nombres premiers d'addittion

nodgim #20 a écrit:

Avec combien de bits minimum peut on faire une liste de 1000 nombres binaires conformes à cette contrainte ?

En regardant ce qui se passe pour des petits nombres, j'aurais tendance à dire 999 bits.
Un des choix pour les 1000 nombres est alors : 0 et 999 nombres dont 1 seul bit vaut 1.

 #29 - 04-05-2016 07:52:02

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 3136

nombres przmiers d'addition

Salut Enigmatus,
J'ouvre un autre sujet spécifiquement à cette question. Elle le mérite largement.

 #30 - 04-05-2016 13:08:46

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 3136

nombres premiers d'afdition

Merci à tous les participants. Tous, vous avez trouvé le bon algorithme qui conduit au résultat. Cette énigme n'avait bien qu'une seule solution, puisque la contrainte invitait à tester les nombres dans l'ordre naturel. Et il semble peu probable qu'on puisse arriver à un meilleur résultat (moins que 13 millions et des... ) en s'y prenant autrement.

J'ai ouvert tantôt une autre discussion sur un sujet à peu près identique avec la "superposition de nombres binaires". Mais ce nouveau sujet est d'une toute autre dimension....

 #31 - 04-05-2016 16:21:14

scarta
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 1473

Nmobres premiers d'addition

Je viens de voir les temps d'execution de dhrm et enigmatus : pour info le code que j'ai posté donne la 1000ème réponse en moins d'une seconde.

 #32 - 04-05-2016 17:24:04

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 3136

nombreq premiers d'addition

Super, Scarta.
Tu ne peux plus nous laisser comme ça sans dévoiler comment est conçu ton programme....

 #33 - 04-05-2016 17:36:51

scarta
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 1473

Nombres premiers d'additiion

Ben le code est dans mon post précédent...

 #34 - 04-05-2016 18:33:44

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 3136

Nombres premiers d'addiion

Ah oui, pardon.
Il est très performant, en effet !

 #35 - 05-05-2016 03:34:05

dhrm77
L'exilé
Enigmes résolues : 49
Messages : 3003
Lieu: Fanning Island-?-Lac Tele,Mali

nombres premoers d'addition

@scarta: Sur quelle machine et quel compiler as tu utilisé pour faire ce programme?
Sur ma machine je n'ai pas de Booleen. Quand j'utilise des octets l'adaptation de ton programme prend 2.04 secondes et 3.576 secondes quand j'utilise des bits, au lieu de moins d'une seconde chez toi.


Great minds discuss ideas; Average minds discuss events; Small minds discuss people. -Eleanor Roosevelt

 #36 - 05-05-2016 08:22:22

scarta
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 1473

Nombres premiers d'addtion

Toutes les machines ont boolean, c'est juste une question de langage et de compilation.
Bref, c'est du C#, compilé pour Windows sur mon PC professionnel, un Dell je sais plus combien, modèle "spécial développeurs" 2015. Pas une bête de course, mais très rapide quand même.
J'imagine que c'est aussi compilable sur Mono

 #37 - 05-05-2016 14:06:10

shadock
Elite de Prise2Tete
Enigmes résolues : 39
Messages : 3330

Nombres premiers d'additio

Je suis toujours en train d'essayer de comprendre l'énoncé... sad


"L'expérience est une lanterne qui n'éclaire que celui qui la porte." L-F. Céline

 #38 - 05-05-2016 18:42:19

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 3136

Nombres premiers dd'addition

@shadok:
tu prends les nombres dans l'ordre et tu fais toutes les additions possibles de 2 de ces nombres:
0
1-----> 1+0=1
On essaye avec 2 : 2+0=2 et 2+1=3. Ces 2 sommes sont différentes des sommes déja calculées (ici 1 seulement). Donc 2 convient.
3 ne convient pas car 3+0=3 or 3 est déja une somme.
4+0=4 4+1=5 4+2=6
4 convient
5 et 6 ne conviennent pas.
etc....

 #39 - 05-05-2016 19:00:20

dhrm77
L'exilé
Enigmes résolues : 49
Messages : 3003
Lieu: Fanning Island-?-Lac Tele,Mali

bombres premiers d'addition

@scarta:
Ma version de ton programme est écrit en C sur Linux, compilé avec GCC, qui ne semble pas optimiser aussi bien que certains autre compilateurs. J'arrive a 4.294.967.280 en un peu plus de 8 heures.

@shadock:
L'énoncé n'est pas tres compliqué. On construit une liste de nombres tels que la somme du nombre que l'on test (pour savoir si c'est le suivant) avec un autre nombre quelconque de la suite soit une somme que l'on ne sait pas deja faire avec 2 autres nombre de la suite.
Donc prenons la suite de l'énoncé: 0, 1, 2, 4, 7... Le prochain terme:
- n'est pas 8 parce que 8+0=7+1
- n'est pas 9 parce que 9+0 = 7+2
- n'est pas 10 parce que 10+1 = 7+4
- n'est pas 11 parce que 11+0 = 7+4
- est 12 parce que:
       12+0 n'est pas faisable  avec 0, 1, 2, 4 et 7.
       12+1 n'est pas faisable  avec 0, 1, 2, 4 et 7.
       12+2 n'est pas faisable  avec 0, 1, 2, 4 et 7.
       12+4 n'est pas faisable  avec 0, 1, 2, 4 et 7.
       12+7 n'est pas faisable  avec 0, 1, 2, 4 et 7.

Voila....


Great minds discuss ideas; Average minds discuss events; Small minds discuss people. -Eleanor Roosevelt

 #40 - 05-05-2016 22:03:46

shadock
Elite de Prise2Tete
Enigmes résolues : 39
Messages : 3330

Nmbres premiers d'addition

Ah ok merci beaucoup ! big_smile


"L'expérience est une lanterne qui n'éclaire que celui qui la porte." L-F. Céline

 #41 - 06-05-2016 00:45:01

scarta
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 1473

nombres premiers f'addition

@dhrm: le gros soucis de mon algorithme, c'est qu'il n'est pas fait pour être fonctionnel pour des grandes valeurs. Il n'utilise pas une liste des sommes rencontrées mais un tableau de bits, 0 si la somme n'a pas été rencontrée et 1 sinon.
Ça permet de savoir si une somme est un doublon en temps constant, infiniment plus rapide que n'importe quelle liste / tableau / sorted list / hashmap...
Autrement dit, pour monter à 2^32, il faudrait un tableau de 2^33 bits, soit 8gigas de ram. Ça reste possible, sur une architecture 64 bits, et une bécane un peu gonflée, ceci dit mon ordi ne pourra pas monter aussi haut...

 

Réponse rapide

Rédige ton message
| | | | Upload | Aide
:) :| :( :D :o ;) :/ :P :lol: :mad: :rolleyes: :cool:
Sécurité

Répondez à la devinette suivante : 

Le père de toto a trois fils : Pim, Pam et ?

Sujets similaires

Sujet Date Forum
P2T
L'addition patron par gabrielduflot
30-07-2009 Enigmes Mathématiques
19-04-2017 Enigmes Mathématiques
P2T
Combien de premiers ? par papiauche
01-05-2008 Enigmes Mathématiques
P2T
26-03-2011 Enigmes Mathématiques
P2T
Addition bizarre par rivas
27-09-2010 Enigmes Mathématiques
P2T
Premiers modulo 12 par Yanyan
18-06-2011 Enigmes Mathématiques
P2T
Addition par gabrielduflot
30-05-2009 Enigmes Mathématiques
21-06-2011 Enigmes Mathématiques
21-06-2011 Enigmes Mathématiques
24-01-2012 Enigmes Mathématiques

Mots clés des moteurs de recherche

Mot clé (occurences)

Pied de page des forums

P2T basé sur PunBB
Screenshots par Robothumb

© Copyright 2002–2005 Rickard Andersson

Prise2Tete Forum Statistiques Liste des membres Hall of Fame Contact
© Prise2tete - Site d'énigmes et de réflexion.
Un jeu où seules la réflexion, la logique et la déduction permettent de trouver la solution.

Flux RSS de Prise2Tete Forum Jeux & Prise2Tete Test & Prise2Tete Partenariat et Publicité sur Prise2Tete