Forum dédié aux énigmes et à toutes formes de jeux de logique. | Déconnexion |
Tu n'es pas identifié sur Prise2tete : s'identifier. |
#1 - 18-08-2021 20:12:21
Rayons cosmiiquesUn entier naturel aléatoire multiple de [latex]3[/latex] est stocké sous forme binaire sur un disque dur.
#0 Pub#2 - 19-08-2021 09:11:39
Rayons coosmiquesBonjour #3 - 19-08-2021 11:38:00
rayonq cosmiques@Vasimolo
Quid de:
Ok. #4 - 19-08-2021 12:10:58
Rayons comsiquesJe me suis sans doute mal exprimé #5 - 19-08-2021 13:04:25
ratons cosmiques@Vasimolo
On est d'accord.
Je crois avoir compris d'où vient la confusion. #6 - 19-08-2021 17:17:25
Rayons cosmqiuesSalut, #7 - 19-08-2021 18:33:57#8 - 19-08-2021 23:47:56
rayons cosmuques@Franky1103 et @Vasimolo #9 - 20-08-2021 12:42:37
raypns cosmiquesLa question serait donc de savoir si pour un multiple de 3 , il y a en moyenne autant de 0 en rang pair que de 0 en rang impair que de 1 en rang pair et que de 1 en rang impair . Cela me semble complètement évident sauf si on limite le nombre de bits , il faut le démontrer ? #10 - 20-08-2021 13:48:09
Rayons cosmiquues@Vasimolo #11 - 20-08-2021 14:56:09
Rayoons cosmiquesAllez je me lance : on commence par regarder 2^n modulo 3 : on trouve alternativement 1 et -1 #12 - 20-08-2021 15:26:31
raypns cosmiquesVoilà, c'est fait. Sur tous les entiers 32 bits : Code:Total: 355050630208 of 710101259440 65.45s user 0.31s system 99% cpu 1:06.38 total Une bonne minute pour sortir le nombre de bitflips valides sur tous les bitflips possibles, uniquement pour les multiples de 3. #13 - 20-08-2021 15:27:03
rayons cosmiqies@scarta #14 - 20-08-2021 15:37:48#15 - 20-08-2021 16:02:14
tayons cosmiquesje pense que les formules que j'utilise dans mon code peuvent grandement faciliter cette démonstration - oui parce que j'ai pas testé à la main les 710101259440 combinaisons. Code:#include <stdio.h> int bitCount(unsigned long n) { int result = 0; while(n) { result ++; n = n&(n-1); } return result; } int main(int argc, char** argv) { //Borne max (32 bits) unsigned long limit = 1L<<32; //Bitflips possibles ( 32*31/2 possibilités pour chaque multiple de 3) unsigned long count = (limit / 3) * 32 * 31 / 2; //Magic number : 101010101010... en binaire - pour faire des calculs rapides unsigned long magicNumber = 2863311530; unsigned long result = 0; unsigned long n; for(n=3; n<limit; n+=3) { //on calcule PZ, PU, IZ, IU, le nombre de zero et de 1 pour chaque parité unsigned long IN = n&magicNumber; int IU = bitCount(IN); int IZ = 16 - IU; int PU = bitCount(n) - IU; int PZ = 16 - PU; //Combinaison valide : bits identiques sur indexs de parités différentes ou bits différents sur parité identique // - bits différents sur parité identique : on compte tous les 0 et tous les 1, pour une parité donnée, on a Z et U // Nombre de résultats valides : Z * U (on prend un "zero" et un "un" parmi la disponibilité) result += IU * IZ + PU * PZ; // - bits identiques sur parité différente : on compte PZ * IZ et PU * IU result += PU * IU + PZ * IZ; } printf("Total: %lu of %lu\n", result, count); } #16 - 20-08-2021 17:29:10
rayons vosmiquesDeux petites remarques : Code:Bits:2, result: 100.000000% - 1 of 1 Bits:3, result: 75.000000% - 3 of 4 Bits:4, result: 68.181818% - 15 of 22 Bits:5, result: 54.166667% - 39 of 72 Bits:6, result: 54.430380% - 129 of 237 Bits:7, result: 50.884956% - 345 of 678 Bits:8, result: 51.062699% - 961 of 1882 Bits:9, result: 50.202347% - 2481 of 4942 Bits:10, result: 50.257181% - 6351 of 12637 Bits:11, result: 50.047783% - 15711 of 31392 Bits:12, result: 50.062770% - 38283 of 76470 Bits:13, result: 50.011479% - 91491 of 182940 Bits:14, result: 50.015413% - 215797 of 431461 Bits:15, result: 50.002786% - 502461 of 1004866 Bits:16, result: 50.003800% - 1157901 of 2315626 Bits:17, result: 50.000681% - 2643309 of 5286546 Bits:18, result: 50.000940% - 5985747 of 11971269 Bits:19, result: 50.000167% - 13456755 of 26913420 Bits:20, result: 50.000233% - 30059335 of 60118390 Bits:21, result: 50.000041% - 66759375 of 133518640 Bits:22, result: 50.000058% - 147499881 of 294999421 Bits:23, result: 50.000010% - 324359553 of 648718974 Bits:24, result: 50.000014% - 710235705 of 1420471002 Bits:25, result: 50.000003% - 1549096329 of 3098192502 Bits:26, result: 50.000004% - 3366628279 of 6733256077 Bits:27, result: 50.000001% - 7292496615 of 14584993048 Bits:28, result: 50.000001% - 15748213731 of 31496426902 Bits:29, result: 50.000000% - 33912346011 of 67824691812 Bits:30, result: 50.000000% - 72835487421 of 145670974197 Bits:31, result: 50.000000% - 156050478501 of 312100956762 Bits:32, result: 50.000000% - 333575793733 of 667151586730 Edit : bugfix --> nouveaux resultats, mais ça change pas grand chose #17 - 21-08-2021 00:16:30
Rayons cosmiqques@scarta
Oui, la probabilité recherchée tend vers [latex]1/2[/latex] lorsque le nombre initial tend vers l'infini. Et donc sur l'ensemble des multiples de [latex]3[/latex] la probabilité moyenne (celle d'un multiple choisi au hasard) est elle aussi [latex]1/2[/latex]. #18 - 21-08-2021 22:00:49
Rayons cosmiuqesJ’ai un autre algo qu’il faut que j’écrive. Ça serait du o(n) en fonction du nombre de bits. #19 - 23-08-2021 09:49:46
Rayons cosmiquseEt voilà le travail - les stats pour chaque nombre de bit possible (entre 1 et 55), ça tourne en moins de 1ms Code:Using exactly 2 bits : 100.000000% - 1 of 1 Using exactly 3 bits : 66.666664% - 2 of 3 Using exactly 4 bits : 66.666664% - 12 of 18 Using exactly 5 bits : 48.000000% - 24 of 50 Using exactly 6 bits : 54.545456% - 90 of 165 Using exactly 7 bits : 48.979591% - 216 of 441 Using exactly 8 bits : 51.162792% - 616 of 1204 Using exactly 9 bits : 49.673203% - 1520 of 3060 Using exactly 10 bits : 50.292397% - 3870 of 7695 Using exactly 11 bits : 49.906693% - 9360 of 18755 Using exactly 12 bits : 50.073208% - 22572 of 45078 Using exactly 13 bits : 49.974640% - 53208 of 106470 Using exactly 14 bits : 50.018307% - 124306 of 248521 Using exactly 15 bits : 49.993286% - 286664 of 573405 Using exactly 16 bits : 50.004578% - 655440 of 1310760 Using exactly 17 bits : 49.998249% - 1485408 of 2970920 Using exactly 18 bits : 50.001144% - 3342438 of 6684723 Using exactly 19 bits : 49.999550% - 7471008 of 14942151 Using exactly 20 bits : 50.000286% - 16602580 of 33204970 Using exactly 21 bits : 49.999886% - 36700040 of 73400250 Using exactly 22 bits : 50.000069% - 80740506 of 161480781 Using exactly 23 bits : 49.999977% - 176859672 of 353719553 Using exactly 24 bits : 50.000023% - 385876152 of 771752028 Using exactly 25 bits : 49.999992% - 838860624 of 1677721500 Using exactly 26 bits : 50.000000% - 1817531950 of 3635063575 Using exactly 27 bits : 49.999996% - 3925868336 of 7851736971 Using exactly 28 bits : 50.000000% - 8455717116 of 16911433854 Using exactly 29 bits : 50.000000% - 18164132280 of 36328264910 Using exactly 30 bits : 50.000000% - 38923141410 of 77846282385 Using exactly 31 bits : 50.000000% - 83214991080 of 166429982565 Using exactly 32 bits : 49.999996% - 177525315232 of 355050629968 Using exactly 33 bits : 50.000000% - 377957121728 of 755914243920 Using exactly 34 bits : 50.000000% - 803158884726 of 1606317768891 Using exactly 35 bits : 49.999996% - 1703670360384 of 3407340721295 Using exactly 36 bits : 50.000000% - 3607772529060 of 7215545057490 Using exactly 37 bits : 50.000000% - 7627861917288 of 15255723835170 Using exactly 38 bits : 50.000000% - 16103264048938 of 32206528097173 Using exactly 39 bits : 50.000000% - 33947421507128 of 67894843014921 Using exactly 40 bits : 50.000000% - 71468255805960 of 142936511611140 Using exactly 41 bits : 50.000000% - 150266589128880 of 300533178258500 Using exactly 42 bits : 50.000000% - 315559837172286 of 631119674343711 Using exactly 43 bits : 50.000000% - 661905999920592 of 1323811999842003 Using exactly 44 bits : 50.000000% - 1386850666502092 of 2773701333003238 Using exactly 45 bits : 50.000000% - 2902710697328024 of 5805421394656950 Using exactly 46 bits : 50.000000% - 6069304185324210 of 12138608370647385 Using exactly 47 bits : 50.000004% - 12678102076008456 of 25356204152017901 Using exactly 48 bits : 50.000000% - 26458647810802416 of 52917295621603704 Using exactly 49 bits : 50.000000% - 55169095435287840 of 110338190870576760 Using exactly 50 bits : 50.000004% - 114935615490185350 of 229871230980369475 Using exactly 51 bits : 50.000000% - 239253730204056800 of 478507460408114775 Using exactly 52 bits : 50.000000% - 497647758824440692 of 995295517648880058 Using exactly 53 bits : 50.000000% - 1034326714419423048 of 2068653428838847370 Using exactly 54 bits : 50.000000% - 2148217022255727546 of 4296434044511453661 Using exactly 55 bits : 50.000000% - 4458563631096790104 of 8917127262193581585 Sortir plus de résultat n'est pas plus long, simplement ça demande d'utiliser autre chose que des longs... Code:#include <stdio.h> #include <stdlib.h> int main(int argc, char** argv) { int bitLimit = argc > 1 ? atoi(argv[1]) : 48; unsigned long *currentCount = (unsigned long*)malloc((bitLimit+1) * sizeof(unsigned long)); unsigned long *nextCount = (unsigned long*)malloc((bitLimit+1) * sizeof(unsigned long)); unsigned long *tmp; int size, i, currentQ; unsigned long result, total; currentCount[0] = currentCount[1] = 1; for(size = 1; size < bitLimit; size++){ result = 0; for(currentQ = (2 * size + 1)%3; currentQ <= size; currentQ += 3) result += currentCount[currentQ] * (currentQ + (size&1)) * ((size|1) - currentQ); total = ((1UL<<size)+1)/3 * size * (size+1)/2; printf("Using exactly %2d bits : %f%% - %lu of %lu\n", size+1, 100.0f*result / total, result, total); for(i=0; i<=size+1; i++) nextCount[i] = currentCount[size + 1 - i] + currentCount[size - i]; tmp = nextCount; nextCount = currentCount; currentCount = tmp; } } #20 - 23-08-2021 09:58:20#21 - 23-08-2021 21:20:59
rayons cosmisuesBon, pour la beauté de la chose, j'ai refait un algo avec support des bigIntegers, je suis monté sans souci jusqu'à 10.000 bits en moins de 30 secondes - après ce sont les opérations de base sur les bigints qui prennent de plus en plus de temps... Code:import java.math.BigInteger; class Multiple { public static void main(String[] args) { int bitLimit = args.length == 0 ? 48 : Integer.parseInt(args[0]); BigInteger[] currentCount = new BigInteger[bitLimit + 1]; int size, i, currentQ; BigInteger result, total; currentCount[0] = currentCount[1] = BigInteger.ONE; for(i=2; i<=bitLimit; i++) currentCount[i] = BigInteger.ZERO; for (size = 1; size < bitLimit; size++) { result = BigInteger.ZERO; for (currentQ = (size * 2 + 1)%3; currentQ <= size; currentQ += 3) result = result.add(currentCount[currentQ].multiply(BigInteger.valueOf((currentQ + (size&1)) * ((size | 1) - currentQ)))); total = BigInteger.ONE.shiftLeft(size).add(BigInteger.ONE).divide(BigInteger.valueOf(3)).multiply(BigInteger.valueOf(size*(size+1)/2)); System.out.println("Using exactly " + (size+1) + " bits : " + result.doubleValue()*100 / total.doubleValue() + "% - " + result.toString()+" of " + total.toString()); for(i=size+1; i>=1; i--) currentCount[i] = currentCount[i].add(currentCount[i-1]); } } } Réponse rapideSujets similaires
|
||||||||||||||||||||||||||||||||
Prise2Tete Forum Statistiques Liste des membres Hall of Fame Contact |