
Forum dédié aux énigmes et à toutes formes de jeux de logique. | Déconnexion |
|
Tu n'es pas identifié sur Prise2tete : s'identifier. Accueil
Forum
|
![]() |
#1 - 21-10-2017 22:54:58
100 coffres (logiqeu et probas)Dans une salle se trouvent 100 coffres numérotés (de 1 à 100).
#0 Pub#2 - 22-10-2017 14:23:51
100 coffres (logique e tprobas)Pour la partie "logique" , je dirais pas plus de 50 coffres à ouvrir, vu qu'en échangeant deux contenus judicieusement choisis, on peut diviser une "boucle" par 2, avec l'assurance que chaque coffre soit dans sa propre boucle. Code:1 2 3 4 5 6 7 8 9 10 11 12 13 5 7 6 10 1 8 4 13 2 12 11 9 3 Donne les boucles : Code:(1 5) (2 7 4 10 12 9) (3 6 8 13) (11) (5 1) (7 4 10 12 9 2) (6 8 13 3) (11) ce qui en suivant la stratégie « j'ouvre le coffre portant le numéro de ma somme, puis celui de la somme trouvée dedans ….etc » oblige à ouvrir jusqu'à 6 coffres presque une fois sur 2, soit une moyenne de 4,75 coffres ouverts. Code:(1 5) (2 7 4) (10 12 9) (3 6 8 13) (11) (5 1) (7 4 2) (12 9 10) (6 8 13 3) (11) Le maximum de coffres ouverts passe à 4 , à peine une fois sur 3, pour une moyenne qui passe à 3,25 coffres ouverts. #3 - 23-10-2017 15:42:46
100 cofffres (logique et probas)Bravo pour la partie logique c'est bien ça. #4 - 23-10-2017 15:57:16
100 cffres (logique et probas)Bonjour, #5 - 23-10-2017 20:35:06
100 coffrrs (logique et probas)Partie logique : #6 - 24-10-2017 06:01:30#7 - 26-10-2017 16:37:09
100 coffres (logqiue et probas)40 minutes de calcul ? #8 - 26-10-2017 17:49:08#9 - 26-10-2017 22:29:41
100 coffres (logique et pprobas)Personne n'as trouvé la réponse ? #10 - 27-10-2017 07:55:08
100 coffres (logique et probas))Pour la méthode, si. #11 - 27-10-2017 22:34:38
100 coffres (logique ett probas)Bonsoir scarta, Code:Sans optimisation : nb moyen de coffres à ouvrir = 13/4 = 3.250000 nb moyen dans le pire des cas = 23759791/3628800 = 6.547561 Avec optimisation : nb moyen de coffres à ouvrir = 75781001/36288000 = 2.088321 nb moyen dans le pire des cas = 1382077/362880 = 3.808634 Je n'ai pas l'impression que ça concorde avec tes résultats. Pourrais-tu montrer tes valeurs pour 10 coffres ? #12 - 28-10-2017 08:00:22
100 coffres (logiique et probas)@ Enigmatus: je ne crois pas que tes résultats soient corrects pour le nb moyen de coffres à ouvrir, tu ne peux pas diviser par 3 par l'inversion d'un coffre. En fait, tu ne peux diviser au mieux que par 2. Les chiffres annoncés par Scarta me semblent plausibles. #13 - 28-10-2017 08:54:14#14 - 28-10-2017 09:58:19
100 coffres (llogique et probas)Pardon Enigmatus, j'ai fait une mauvaise lecture de ton algo. #15 - 28-10-2017 10:31:31
100 coffres (logiquee et probas)@nodgim #14 :
C'est juste cette valeur qui me paraît bizarre, à moins que ce ne soit le plus mauvais cas (une seule boucle de 100). #16 - 28-10-2017 14:45:26
100 coffres (logique et proabs)@ Enigmatus: si tu as regardé pour 10 coffres, sans doute aussi pour moins de 10. Tu dois donc trouver une tendance pour la moyenne des coffres à ouvrir. #17 - 28-10-2017 17:11:01
00 coffres (logique et probas)@nodgim #16 : Code: Pire cas
----------------
Sans Avec Sans Avec
échange échange échange échange
2 coffres => 1.500 1.000 1.500 1.000
3 coffres => 2.000 1.222 2.167 1.333
4 coffres => 2.500 1.479 2.792 1.708
5 coffres => 3.000 1.770 3.425 2.108
6 coffres => 3.500 2.047 4.043 2.400
7 coffres => 4.000 2.329 4.675 2.787
8 coffres => 4.500 2.609 5.296 3.103
9 coffres => 5.000 2.894 5.925 3.475
10 coffres => 5.500 3.177 6.548 3.809#18 - 28-10-2017 18:14:19#19 - 28-10-2017 22:00:24
100 cpffres (logique et probas)Pour la moyenne avec échange , de tête je me rappelle le résultat du 5 (qui tombe pile: 1.77) #20 - 28-10-2017 22:45:55
100 cpffres (logique et probas)Pour 5 coffres, j'obtiens bien les mêmes valeurs que scarta en #19. Code: Pire cas
----------------
Sans Avec Sans Avec
échange échange échange échange
50 coffres => 25.500 14.624 31.527 17.756Édité : Code:60 coffres => 30.500 17.490 37.771 21.242 #21 - 29-10-2017 06:54:05
1000 coffres (logique et probas)@Scarta: j'avais bien retrouvé l'évident (n+1)/2 après coup, et ai adopté le même mode de calcul à la main, avec cette somme de carrés. #22 - 30-10-2017 09:40:36
100 coffres (loique et probas)Le problème, c'est que ça risque d'être coton à calculer. #23 - 30-10-2017 11:31:49
100 cofffres (logique et probas)
Je tiens à dire que je désapprouve le forcément. #24 - 30-10-2017 16:54:14
100 coffres (logique e probas)Bon, j'ai tout réécrit pour encore optimiser un peu (en C cette fois, avec libgmp pour les grands entiers) Code:#include <sys/time.h>
#include <time.h>
#include <stdlib.h>
#include <stdio.h>
#include <gmp.h>
typedef struct timeval timer;
mpz_t *factorial;
int max_size = 500;
int size;
void compute(mpz_t res, int remaining_size, int max, int* stack, int stack_index)
{
if(remaining_size == 0 || max == 1)
{
for(int i=0; i<remaining_size; i++)
stack[stack_index + i] = 1;
mpz_t local_res, partition_count;
mpz_init_set_si(local_res, 1+(stack[0] * stack[0] - 1) / 2);
mpz_init_set(partition_count, factorial[size]);
for(int i=0; i<stack_index + remaining_size && stack[i] != 1; i++)
mpz_cdiv_q_ui(partition_count,partition_count,stack[i]);
int same_length_cycle_count = 1;
for(int i=1; i<stack_index + remaining_size; i++)
{
mpz_add_ui(local_res, local_res, stack[i]*stack[i]);
if(stack[i] == stack[i-1])
same_length_cycle_count++;
else
{
mpz_cdiv_q(partition_count, partition_count, factorial[same_length_cycle_count]);
same_length_cycle_count = 1;
}
}
mpz_cdiv_q(partition_count, partition_count, factorial[same_length_cycle_count]);
mpz_addmul(res, partition_count, local_res);
mpz_clear(partition_count);
mpz_clear(local_res);
return;
}
for(int cycle_length = max > remaining_size ? remaining_size : max; cycle_length >= 1; cycle_length --)
{
stack[stack_index] = cycle_length;
compute(res, remaining_size - cycle_length, cycle_length, stack, stack_index + 1);
}
}
int main(int argc, char *argv[])
{
factorial = malloc((max_size+1)*sizeof(mpz_t));
mpz_init_set_si(factorial[0],1);
double s;
for(int i=1; i<=max_size; i++)
{
mpz_init(factorial[i]);
mpz_mul_si(factorial[i], factorial[i-1], i);
}
for(size = 2; size <= max_size; size++)
{
timer start;
gettimeofday(&start, NULL);
mpz_t numerator, compute_result;
mpz_init(compute_result);
mpz_init_set_si(numerator, size*size);
mpz_mul(numerator, numerator, factorial[size]);
mpz_mul_ui(numerator, numerator, 1000000);
int* array = malloc(sizeof(int)*size);
compute(compute_result, size, size, array, 0);
timer stop;
gettimeofday(&stop, NULL);
s=difftime(stop.tv_sec, start.tv_sec) + ((double)stop.tv_usec - (double)start.tv_usec)/1000000.0;
mpz_cdiv_q(numerator, numerator, compute_result);
printf("%d\t%s\t(%.5fsec)\n", size, mpz_get_str(NULL, 10, numerator), s);
mpz_clear(compute_result);
mpz_clear(numerator);
}
}Les résultats Code:2 2000000 (0.00032sec) 3 2454546 (0.00000sec) 4 2704226 (0.00000sec) 5 2824859 (0.00001sec) 6 2931464 (0.00001sec) 7 3005770 (0.00001sec) 8 3066240 (0.00001sec) 9 3109529 (0.00001sec) 10 3147978 (0.00002sec) 11 3177389 (0.00002sec) 12 3203466 (0.00003sec) 13 3224175 (0.00004sec) 14 3243165 (0.00006sec) 15 3258971 (0.00008sec) 16 3273472 (0.00011sec) 17 3285569 (0.00013sec) 18 3296934 (0.00019sec) 19 3306748 (0.00026sec) 20 3315903 (0.00032sec) 21 3323859 (0.00041sec) 22 3331411 (0.00054sec) 23 3338073 (0.00071sec) 24 3344388 (0.00088sec) 25 3350003 (0.00070sec) 26 3355366 (0.00139sec) 27 3360199 (0.00391sec) 28 3364818 (0.01100sec) 29 3368984 (0.00809sec) 30 3372995 (0.00328sec) 31 3376657 (0.00848sec) 32 3380174 (0.01561sec) 33 3383394 (0.00626sec) 34 3386507 (0.01293sec) 35 3389374 (0.02011sec) 36 3392145 (0.03047sec) 37 3394705 (0.03608sec) 38 3397188 (0.04315sec) 39 3399497 (0.04983sec) 40 3401736 (0.06640sec) 41 3403819 (0.07488sec) 42 3405847 (0.08422sec) 43 3407746 (0.11873sec) 44 3409591 (0.15425sec) 45 3411321 (0.19212sec) 46 3413008 (0.18688sec) 47 3414595 (0.21655sec) 48 3416143 (0.24483sec) 49 3417602 (0.29722sec) 50 3419027 (0.42788sec) 51 3420375 (0.34802sec) 52 3421692 (0.39035sec) 53 3422938 (0.49760sec) 54 3424159 (0.54944sec) 55 3425317 (0.61576sec) 56 3426451 (0.69368sec) 57 3427528 (0.78667sec) 58 3428585 (0.89454sec) 59 3429591 (1.04672sec) 60 3430578 (1.13582sec) 61 3431518 (1.44800sec) 62 3432442 (1.66220sec) 63 3433324 (1.95147sec) 64 3434190 (2.16669sec) 65 3435018 (2.64504sec) Je vais laisser tourner toute la nuit, on verra bien demain #25 - 31-10-2017 08:28:53
100 coffres (logique et prboas)Les résultats suivants Réponse rapideSujets similaires
|
![]() | |||||||||||||||||||||||||||||||||
| Prise2Tete Forum Statistiques Liste des membres Hall of Fame Contact | |||||||||||||||||||||||||||||||||||