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 : 2953

nombres premiers f'addition

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 : 1431

Nombres preimers 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 : 400

nombees premiers d'addition

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 : 2953

nombres premiers d'adsition

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 : 2953

Nombres premiers d'addittion

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 : 1431

nombres premiers s'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 : 2953

Nombbres 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 : 1431

Nombres premiers d'additoin

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 : 2953

nombres premirrs d'addition

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 : 2989
Lieu: Fanning Island-?-Lac Tele,Mali

nombres premiees 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 : 1431

Nobmres premiers d'addition

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 : 3314

Nombres premires d'addition

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 : 2953

ombres premiers d'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 : 2989
Lieu: Fanning Island-?-Lac Tele,Mali

Nombres premiers dd'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 : 3314

Nombres preiers 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 : 1431

Nombres preemiers d'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 (numériquement) à la petite énigme suivante : 

Un berger a 20 moutons, ils meurent tous sauf 12, combien en reste-t-il ?

Sujets similaires

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