Générez n'importe quel entier aléatoire

17

Votre programme / fonction doit

  • produire exactement un entier
  • sortie tout entier avec une probabilité positive
  • sortie un entier supérieur à 1.000.000 ou inférieur à -1.000.000 avec au moins une probabilité de 50%.

Exemples de sorties (toutes doivent être possibles):

59875669123
12
-42
-4640055890
0
2014
12
24
-7190464664658648640055894646646586486400558904644646646586486400558904646649001

Précisions:

  • Un saut de ligne arrière est autorisé.
  • Les zéros non significatifs ne sont pas autorisés.
  • -0 est autorisé.

Le code le plus court gagne.

randomra
la source
2
@Optimizer pourquoi supposez -vous une probabilité uniforme? La question ne l'indique pas. En fait, il semble clair à partir de ce moment que la distribution ne doit pas être uniforme tant qu’au moins 50% de celle-ci se situe en dehors de [-1 million, 1 million].
Hobbs
10
Une solution qui produit une " distribution uniforme sur tous les entiers" est impossible. Il y a une infinité de nombres entiers, donc chaque entier individuel apparaîtrait avec une probabilité de 0. (Ou: la sortie d'un nombre fini signifierait que vous en négligez une infinité d'autres!) Toute solution devra défavoriser des valeurs plus élevées afin d'atteindre P (total ) = 1.
joeytwiddle
2
@Ypnypn La RAM de l'ordinateur n'est pas non plus une limite. Vous n'avez pas besoin de stocker votre sortie partielle n'importe où.
jimmy23013
4
@GiantTree - way too long to fit in an integer- Ceci n'est vrai que si vous supposez que cela integersignifie le inttype de données sur un arc 32/64 bits, ce qui n'est pas nécessairement une hypothèse valide. "Entier" a commencé comme un terme mathématique , qui n'a pas de contraintes de taille.
Fake Name
5
Quiconque utilise un générateur de nombres pseudo-aléatoires pour prendre ses décisions sur la sortie exclura presque tous les entiers et imposera une limite supérieure à la taille des entiers pouvant être produits (en supposant que le PRNG a une période finie). Cela peut-il être ignoré dans les réponses ou une réponse valide nécessite-t-elle un véritable générateur de nombres aléatoires?
trichoplax

Réponses:

12

CJam, 16 14 13 octets

0{Kmr(+esmr}g

Cela fonctionnera très longtemps, car il utilise l'horodatage actuel (de l'ordre de 10 12 ) pour déterminer si la boucle doit se terminer. J'utilise ceci comme mémoire, car c'est le plus court, mais il y a deux alternatives de 14 octets, qui ont leurs propres mérites:

0{esmr(+esmr}g

Celui-ci n'est pas limité par la période du PRNG, car la plage de tous les nombres aléatoires dépend de l'horodatage actuel. Par conséquent, cela devrait être en mesure de produire n'importe quel nombre, bien que la probabilité de nombres négatifs, voire de petits nombres positifs, disparaisse.

Vous trouverez ci-dessous une version équivalente qui utilise 3e5au lieu de l'horodatage. Et 20pour la première plage (comme la soumission de 13 octets). C'est beaucoup plus rapide et respecte également toutes les règles. C'est en quelque sorte le cas limite pour obtenir la probabilité de 50% pour les nombres au-delà de 1 000 000 tout en conservant un temps d'exécution raisonnable et une petite taille de code. L'explication et la justification mathématique se réfèrent à cette version:

0{Kmr(+3e5mr}g

Cela prend généralement quelques secondes. Vous pouvez remplacer le 5par un 2pour le faire fonctionner encore plus rapidement. Mais alors l'exigence sur la probabilité de 50% ne sera remplie que pour 1 000 au lieu de 1 000 000.

Je commence à 0. Ensuite, j'ai une boucle, dont je casse avec une probabilité 1 / (3 * 10 5 ). Dans cette boucle, j'ajoute un entier aléatoire entre -1 et 18 (inclus) à mon total cumulé. Il y a une probabilité finie (quoique faible) que chaque entier soit sorti, les entiers positifs étant beaucoup plus susceptibles que les négatifs (je ne pense pas que vous en verrez un négatif dans votre vie). Sortir avec une si faible probabilité et incrémenter la plupart du temps (et ajouter bien plus que soustraire) garantit que nous dépasserons généralement 1 000 000.

0              "Push a 0.";
 {          }g "Do while...";
  Kmr          "Get a random integer in 0..19.";
     (         "Decrement to give -1..18.";
      +        "Add.";
       3e5mr   "Get a random integer in 0..299,999. Aborts if this is 0.";

Quelques justifications mathématiques:

  • À chaque étape, nous ajoutons 8,5 en moyenne.
  • Pour atteindre 1 000 000, nous avons besoin de 117 647 de ces étapes.
  • La probabilité que nous fassions moins que ce nombre d'étapes est

    sum(n=0..117,646) (299,999/300,000)^n * 1/300,000
    

    qui évalue à 0.324402. Par conséquent, dans environ les deux tiers des cas, nous ferons plus de 117 647 pas, et facilement chacun 1 000 000.

  • (Notez que ce n'est pas la probabilité exacte, car il y aura une certaine fluctuation autour de ces 8,5 moyens, mais pour atteindre 50%, nous devons aller bien au-delà de 117 646 à environ 210 000 pas.)
  • En cas de doute, nous pouvons facilement faire exploser le dénominateur de la probabilité de terminaison, 9e9sans ajouter d’octets (mais des années d’exécution).

... ou 11 octets?

Enfin, il existe une version à 11 octets, qui n'est pas non plus limitée par la période du PRNG, mais qui manquera de mémoire à peu près à chaque fois. Il ne génère qu'un seul nombre aléatoire (basé sur l'horodatage) à chaque itération, et l'utilise à la fois pour l'incrémentation et la fin. Les résultats de chaque itération restent sur la pile et ne sont résumés qu'à la fin. Merci à Dennis pour cette idée:

{esmr(}h]:+
Martin Ender
la source
J'ai ajouté un commentaire à la question pour voir si les règles nécessitent un véritable générateur de nombres aléatoires, mais je suppose que vous apprécierez la pédanterie. Votre source aléatoire est-elle ici pseudo aléatoire? Cela limiterait la taille de l'ensemble des sorties possibles à au plus la période de votre PRNG, non?
trichoplax
(+1 indépendamment pour l'élégance simple)
trichoplax
Oui, je suppose tout pour l'instant. Je suis curieux de voir si quelqu'un poste une réponse sans ce problème ...
trichoplax
Je vois que l'OP a déclaré que vous pouvez supposer que votre générateur de nombres aléatoires est un véritable générateur de nombres aléatoires, que ce soit ou non - donc c'est redondant maintenant ... :)
trichoplax
La somme de Kmrdans une période est probablement toujours un grand nombre positif supérieur à la période. Et il ne peut pas produire tous les nombres possibles dans ce cas.
jimmy23013
11

Java, 133 149

void f(){String s=x(2)<1?"-":"";for(s+=x(9)+1;x(50)>0;s+=x(10));System.out.print(x(9)<1?0:s);}int x(int i){return new java.util.Random().nextInt(i);}

Exemples de sorties

-8288612864831065123773
0
660850844164689214
-92190983694570102879284616600593698307556468079819964903404819
3264

Non golfé

void f() {
    String s = x(2)<1 ? "-" : "";       // start with optional negative sign
    s+=x(9)+1;                          // add a random non-zero digit
    for(; x(50)>0; )                    // with a 98% probability...
        s+=x(10)                        // append a random digit
    System.out.print(x(9)<1 ? 0 : s);   // 10% chance of printing 0 instead
}

int x(int i) {
    return new java.util.Random().nextInt(i);
}

Ancienne réponse (avant le changement de règle)

void f(){if(Math.random()<.5)System.out.print('-');do System.out.print(new java.util.Random().nextInt(10));while(Math.random()>.02);}
Ypnypn
la source
Vous avez tous les deux raison, mais la question indique que la probabilité doit être d' au moins 50% et non de l'ordre de +/- 1.000.000
GiantTree
@Optimizer Redone.
Ypnypn
Si vous utilisez des littéraux binaires, vous n'avez pas besoin d'imprimer le -.
TheNumberOne
4

Mathematica - 47

Round@RandomVariate@NormalDistribution[0,15*^5]

Fondamentalement, il suffit de générer un nombre aléatoire en utilisant une distribution normale avec une variance égale à 1500000. Cela produira un entier entre -10 ^ 6 et 10 ^ 6 avec une probabilité de 49,5015%.

bruissement
la source
"Cela produira un entier entre -10 ^ 6 et 10 ^ 6 avec une probabilité de 50,4985%." - ce n'est pas tout à fait suffisant. Avez-vous mal lu la spécification? Peut-être vouliez-vous utiliser 10 ^ 7 comme variance?
John Dvorak
@JanDvorak Mauvaise probabilité, désolé. Maintenant c'est la bonne.
swish
L'implémentation de ceci dans Mathematica couvre-t-elle vraiment tous les entiers? Je n'ai pas accès à la source mais je suppose que non ...
trichoplax
@githubphagocyte Cela dépend de la précision actuelle.
swish
4
Ce que je veux dire, c'est que la spécification d' une précision spécifique exclura les nombres supérieurs à cela. La seule façon dont cela pourrait fonctionner est de pouvoir spécifier une précision illimitée.
trichoplax
4

Python 2, 75 69 octets

from random import*;s=0;j=randrange
while j(12):s=s*9+j(-8,9)
print s

Il est trivial de vérifier que la boucle while au milieu peut générer tous les entiers (bien que biaisée vers zéro). "12" est choisi de telle sorte qu'il y ait environ la moitié des nombres dépassant ± 10 6 .


Solution plus ancienne:

Python 2, 44 octets

Basé sur la solution Mathematica .

from random import*;print int(gauss(0,8**7))

Ne fonctionne pas vraiment car Python floatn'a qu'une précision limitée.

kennytm
la source
Cela ne pourra pas générer tous les entiers, car le générateur de nombres pseudo-aléatoires a une quantité finie d'état interne. Selon la documentation Python utilise le Mersenne Twister, donc l'état est assez grand. Mais il n'est pas infini, il ne peut donc produire qu'un sous-ensemble fini de tous les entiers.
starblue
@starblue: De l'OP: "Vous pouvez supposer que le générateur de nombres aléatoires de votre langue est un véritable générateur de nombres aléatoires même si ce n'est pas le cas."
kennytm
3

Rubis, 70

f=->{m=10**6
r=rand -m..m
r<1?(r>-5e5??-:'')+r.to_s+f[][/\d+/]:r.to_s}

Pour rendre possible la génération de très grands nombres, je renvoie le nombre en tant que String d'un lambda. Si ce n'est pas autorisé, comptez 8 caractères supplémentaires (pour puts f[]) pour en faire un programme au lieu d'une fonction.

Explication

Générez un nombre entre -1,000,000et 1,000,000. Si le nombre est1 ou supérieur, le nombre est renvoyé sous la forme d'un String.

Si le nombre est inférieur à 1, la fonction est appelée récursivement pour renvoyer un nombre en dehors de la plage de nombres. Pour vous assurer que des nombres négatifs peuvent également être générés, un -est préfixé au résultatString si le nombre initial est supérieur à -500,000.

J'espère avoir bien compris le défi!

britishtea
la source
3

R, 38

library(Rmpfr)
round(rnorm(1,2e6,1e6))

Tirages de la distribution gaussienne avec une moyenne de 2 000 000, choisis au hasard et un écart-type de 1 000 000, de sorte qu'environ 2/3 des tirages se situeront entre 1 000 000 et 3 000 000. La distribution est illimitée donc en théorie cela peut générer n'importe quel entier. Le package Rmpfr remplace les R intégrés dans les flotteurs doubles avec une précision arbitraire.

shadowtalker
la source
Oui, j'ai réalisé que j'avais mal lu la spécification. Et j'imagine qu'il a les mêmes limitations sur la précision de la machine avec Mathematica
shadowtalker
Hmm dans ce cas, je ne suis pas sûr. Je vais devoir y réfléchir; considérez cette réponse "en attente" pour l'instant
shadowtalker
@ MartinBüttner corrigé je pense
shadowtalker
Intéressant. Je ne pense pas que vous ayez besoin de toute la sample(c(1,-1),1)réflexion. Un simple centrage sur 1e6 devrait suffire.
Martin Ender
@ MartinBüttner oh ça n'a pas besoin d'être à 50% aux deux extrémités? Ce n'était pas clair
shadowtalker
2

Perl, 53 caractères

print"-"if rand>.5;do{print int rand 10}while rand>.1

Je ne vois certainement aucune raison de travailler avec des entiers lors de l'impression d'un :)

A la même probabilité d'imprimer un nombre avec ou sans un "-".

Imprime un nombre à 1 chiffre 10% du temps, un nombre à 2 chiffres 9% du temps, un nombre à 3 chiffres 8,1% du temps, un nombre à 4 chiffres 7,29% du temps, un nombre à 5 chiffres 6,56% du temps, un nombre à 6 chiffres 5,9% du temps, etc. Toute longueur est possible, avec une probabilité décroissante. Les nombres d'un à cinq chiffres représentent environ 41,5% des cas de sortie, et le nombre 1 000 000 (ou -1 000 000) seulement 6 millionièmes de pour cent, de sorte que le nombre de sortie sera en dehors de la plage de -1 000 000 à 1 000 000 environ 54,6 % du temps.

"0" et "-0" sont des sorties possibles, ce qui, je l'espère, n'est pas un problème.

Hobbs
la source
Est-ce que cela n'imprime pas des "nombres" comme -00000000167? Ce n'est pas vraiment un entier.
isaacg
1
@isaacg Je ne vois pas pourquoi ce n'est pas un entier.
Optimizer
2
@Optimizer C'est le cas, mais l'OP a explicitement interdit de mener 0.
Martin Ender
Vous pouvez générer un premier chiffre aléatoire non nul avant la boucle, de -9 à +9. print int(rand(20)-10)||1. J'ai besoin d'un moyen de générer 0 en sortie, cependant. Peut-être || mourir 0, si la poubelle de fin après le zéro est autorisée. Sinon, il faut un court chemin pour imprimer le zéro et sortir sans autre sortie si int(rand(20)-10)==0.
Peter Cordes
@PeterCordes a convenu, c'est une approche décente, mais je n'ai pas envie de l'écrire et je ne pense pas que ce serait compétitif dans le temps. N'hésitez pas à le soumettre par vous-même :)
hobbs
2

Perl, 114 caractères

use Math::BigInt;sub r{$x=Math::BigInt->new(0);while(rand(99)!=0){$x->badd(rand(2**99)-2**98);}print($x->bstr());}

Panne:

use Math::BigInt;               -- include BigIntegers
  sub r{                        -- Define subroutine "r"
    $x=Math::BigInt->new(0);    -- Create BigInteger $x with initial value "0"
      while(rand(99)!=0){       -- Loop around until rand(99) equals "0" (may be a long time)
        $x->badd(               -- Add a value to that BigInt
          rand(2**99)-2**98);   -- Generate a random number between -2^98 and +2^98-1
        }print($x->bstr());}    -- print the value of the BigInt

La probabilité d'obtenir une valeur comprise entre -1 000 000 et 1 000 000 tend vers zéro MAIS c'est possible.

Remarque: Ce sous-programme peut s'exécuter pendant une longue période et une erreur avec un "Out of Memory!" erreur, mais il génère techniquement n'importe quel entier comme indiqué dans la question.

Perl, 25

sub r{rand(2**99)-2**98;}

Génère un entier aléatoire dans la plage de +/- 2 ^ 99.

Panne

sub r{                    -- Define subroutine "r"
     rand(2**99)          -- Generate a random integer between 0 and 2^99
                -2**98;}  -- Subtract 2^98 to get negative values as well

Testé avec 1 million d'échantillons:

~5 are inside the range of +/-1.000.000
~999.995 are outside that range
= a probability of ~99,99% of generating an integer outside that range.
Compare that number to the probability of 2.000.000 in 2^99: It is approx. the same.

Cela répond à toutes les règles:

  • 1 entier
  • n'importe quel entier est possible
  • au moins 50% (dans mon cas 99,99%) de tous les entiers générés sont en dehors de la plage de +/- 1.000.000.

Cela fonctionne parce que le générateur de nombres aléatoires sous-jacent définit une probabilité égale à chaque bit généré, faisant ainsi cela sur les entiers générés également.
Chaque entier a une probabilité de 1/2 ^ 99 d'être généré.

Éditer:

J'ai dû augmenter l'exposant pour que des entiers plus grands soient générés. J'ai choisi 99 car il maintient le code aussi court que possible.

GiantTree
la source
N'avons-nous pas convenu qu'il ne devrait pas y avoir de limites supérieure / inférieure? Par exemple, l'entier 2 ^ 31 + 1 a une probabilité de 0, enfreignant la règle 2
Optimizer
@Optimizer pour moi, un entier est défini comme dans de nombreux langages de programmation: un nombre dans les limites de -2^31et +2^31-1(32bits). Vous pouvez facilement augmenter les exposants si vous souhaitez générer des entiers plus grands, mais cela peut échouer en fonction de l'implémentation de Perl.
GiantTree
Je viens de voir que cet entier ridiculement grand doit également être généré. Je vais éditer mon code rapidement.
GiantTree
@ MartinBüttner J'ai fait de mon mieux pour répondre aux spécifications de la question. Il n'est tout simplement pas possible pour moi (du moins pas sans aide) de générer des entiers infiniment grands. Le plus grand entier de Perl est d'environ 1,7e308, ce qui est une limite que je ne peux pas contrôler.
GiantTree
@ MartinBüttner Les deux sont possibles mais par exemple. la chaîne déborderait après 2 Go de données, ce qui la rendrait à nouveau finie. Il est difficile de dire qu'un nombre doit être infiniment grand s'il y a des problèmes de mémoire. Je proposerai bientôt une approche différente en utilisant BigInts. De plus, l'entier ne déborde pas à 1.7e308, il est juste converti en infite ( 1.#INFpour être exact)
GiantTree
2

C #, 126 107 octets

string F(){var a=new System.Random();var b=a.Next(-1E6,1E6+1)+"";while(a.Next(1)>0)b+=a.Next(10);return b;}

Non golfé:

string F()
{
    System.Random rand = new System.Random();
    string rtn = rand.Next(-1E6, 1E6 + 1) + "";
    while (rand.Next(1) > 0)
         rtn += a.Next(10);
    return rtn;
}

La chance de générer un nombre de n chiffres est 1/2 ^ (n-10), ce qui est supérieur à 0 pour tous les n positifs et 1/2 pour n = 11.Crée également des zéros non significatifs, qui ne semblent pas interdits dans la question d'origine ni dans aucun de ses commentaires.

LegionMammal978
la source
Lors de l'utilisation using System;, vous n'avez pas besoin de System.Randomdeux fois, mais juste Random, non?
Charlie
@Charlie Ceci est une fonction, donc je ne peux pas utiliser d' usinginstructions. De toute façon, cela ne sauverait qu'un seul caractère.
LegionMammal978
1
Vous pouvez enregistrer 1 caractère en supprimant l'espace à -1E6, 1E6+1.
ProgramFOX
2

Perl, 62 octets

print $n=int rand(20)-10;while($n&&rand>.1){print int rand 10}

J'ai eu la même idée que @Hobbs, de générer un chiffre à la fois, mais son code ne satisfaisait pas à l'exigence supplémentaire sans zéros non significatifs. La génération du premier chiffre au lieu du simple signe a résolu cela. Et à moins qu'il n'y ait un moyen plus court de quitter si nous imprimons un zéro, ou un moyen plus court de générer le premier -9 à 9, cela devrait le faire pour la taille.

Dans une boucle shell: while perl -e '...'; do echo;done |less

Je pense que c'est l'un des plus courts qui ne nécessite pas de RAM infinie pour satisfaire le problème. En prime, la sortie n'est pas fortement biaisée vers quoi que ce soit et l'exécution est très rapide.

J'ai essayé d'utiliser bit à bit et d'enregistrer un caractère dans la condition while, mais je pense que cela finit par être vrai plus souvent, donc la boucle se termine plus tôt. Aurait besoin de plus de caractères pour ajuster d'autres choses pour contrer cela, pour maintenir la probabilité de générer des abs (sortie)> 1M.

Peter Cordes
la source
Bien, vous avez évincé des choses auxquelles je n'aurais pas pensé :)
hobbs
1

Javascript (73)

Cette solution utilise que vous pouvez construire un nombre avec la base n en multipliant le nombre précédent par n et en ajoutant un chiffre dans la base n . Nous en avons un supplémentaire ..?..:..pour pouvoir créer tous les entiers négatifs. Le code suivant doit être testé dans une console de navigateur.

b=Math.round;c=Math.random;x=0;while(b(c()*99)){x*=b(c())?2:-2;x+=b(c())}

La probabilité d'obtenir un entier> = 2^1(ou <= -(2^1)) est égale à la chance que la boucle soit exécutée 2 fois. La chance que cela se produise est (98/99)^2. La chance d'obtenir un nombre supérieur à 2^20(ou <= -(2^20)) est donc de (98/99)^21 = 0.80881%. C'est tout en théorie cependant, et en supposant que Math.random est vraiment aléatoire. Ce n'est évidemment pas le cas.


Extrait testant ce code. Également d'une manière plus lisible.

Sumurai8
la source
1
L'OP a maintenant confirmé que vous pouvez supposer que votre PRNG est vraiment aléatoire, même s'il ne l'est pas.
trichoplax
1

GolfScript, 20 octets

0{)8.?rand}do.2&(*4/

Ouais, celui-ci est aussi un peu lent.

Comparé à des langages comme CJam et Pyth, GolfScript souffre d'un mot-clé de génération de nombres aléatoires ( rand). Pour surmonter ce handicap, j'avais besoin de trouver un moyen de ne l'utiliser qu'une seule fois.

Ce code fonctionne en choisissant à plusieurs reprises un nombre aléatoire entre 0 et 8 8 -1 = 16 777 215 inclus, et en incrémentant un compteur jusqu'à ce que le nombre aléatoire se trouve être 0. La valeur du compteur résultant a une distribution géométrique avec une médiane d' environ -1 / log 2 (1 - 1/8 8 ) ,6 11 629 080, il satisfait donc au test "plus de 1 000 000 au moins 50% du temps".

Hélas, le nombre aléatoire ainsi généré est toujours strictement positif. Ainsi, la .2&(*4/partie supplémentaire est nécessaire pour la laisser devenir négative ou nulle. Il fonctionne en extrayant le deuxième bit le plus bas du nombre (qui est donc soit 0 ou 2), en le décrémentant pour le rendre -1 ou 1, en le multipliant par le nombre d'origine et en divisant le résultat par 4 (pour se débarrasser de les deux bits les plus bas, qui sont maintenant corrélés avec le signe, et aussi pour permettre au résultat de devenir nul). Même après la division par 4, la valeur absolue du nombre aléatoire a toujours une médiane de -1 / log 2 (1 - 1/8 8 ) / 4 ≈ 2 907 270, il passe donc toujours le test de 50%.

Ilmari Karonen
la source
1

JavaScript, 81 octets

Ce code remplit toutes les règles:

  • Sortie tout entier avec une probabilité positive
  • Des entiers de sortie en dehors de la plage de +/- 1000000 avec une probabilité d'au moins 50%
  • Pas de leader 0dans la sortie

En prime, l'algorithme s'exécute avec une complexité temporelle de O (log 10 n) , il renvoie donc l'entier presque instantanément.

for(s="",r=Math.random;r()>.1;s+=10*r()|0);r(s=s.replace(/^0*/,"")||0)<.5?"-"+s:s

Cela suppose un environnement REPL. Essayez d'exécuter le code ci-dessus dans la console de votre navigateur ou utilisez l'extrait de pile ci-dessous:

D.onclick = function() {
  for(s="", r=Math.random;r()>.1; s+=10*r()|0);
  P.innerHTML += (r(s=s.replace(/^0*/,"") || 0) <.5 ?"-" + s : s) + "<br>"
}
<button id=D>Generate a random number</button><pre id=P></pre>

Algorithme :

  • Continuez à ajouter des chiffres aléatoires à la chaîne sjusqu'à ce que a Math.random() > 0.1.
  • Basé sur Math.random() > 0.5, rendez le nombre négatif (en ajoutant la chaîne savec -).

Cet algorithme n'a pas de distribution uniforme sur tous les entiers. Les nombres entiers avec un nombre de chiffres plus élevé sont moins probables que les nombres inférieurs. Dans chaque boucle d'itération, il y a 10% de chances que je m'arrête au chiffre actuel. Je dois juste m'assurer que je m'arrête après 6 chiffres plus de 50% du temps.

Cette équation de @nutki explique la valeur maximale du pourcentage de chance d'arrêt basée sur la condition ci-dessus:

1 - 50%^(1/6) ≈ 0.11

Ainsi, 0,1 est bien dans la plage pour satisfaire aux trois règles de la question.

Optimiseur
la source
Il y a quelques choses qui me confondent dans cette réponse. Avez-vous supposé que Math.random () génère une distribution uniforme de nombres aléatoires, car la spécification indique qu'elle dépend de l'implémentation. En supposant qu'il s'agit d'une distribution uniforme, P (Math.random ()> 0,1) = 0,9, il y a donc une énorme probabilité qu'elle se termine entre chaque itération. Une implémentation de votre algorithme exécuté sur Firefox 34.0 Ubuntu me donne une probabilité de ~ 0.47 (<0.5) chaque fois que je le teste: jsfiddle.net/WK_of_Angmar/dh8gq4pb
Wk_of_Angmar
De plus, comment avez-vous réussi à calculer une complexité temporelle pour un algorithme sans entrée?
Wk_of_Angmar
1

TI-BASIC, 14 octets

1-2int(2rand:randNorm(AnsE6,9

Semblable à la réponse R de @ ssdecontrol, celle-ci s'appuie sur la distribution gaussienne avec une moyenne de -1 000 000 ou 1 000 000, choisie au hasard, et l'écart-type 9. La distribution n'est pas bornée, donc en théorie, cela peut générer n'importe quel entier.

Explication :

1-2int(2rand     - get a random integer 0 or 1, then multiply by 2 and subtract 1
:                - this gives the number 1 or -1 (with equal probability) to Ans
randNorm(AnsE6,9 - displays Gaussian distribution with mean (Ans * 1,000,000) and std. dev. 9
Timtech
la source
Mais peut-il générer "2" ou "-2"?
kennytm
Oui bien sûr. tibasicdev.wikidot.com/randnorm
Timtech
1
OK lire le code à tort (pensée :signifie «imprimer» en raison de la façon dont l'explication est présentée). Mais peut-il générer des nombres de plus de 20 chiffres?
kennytm
Tout entier arbitraire est-il possible en sortie? N'est-ce pas limité par la gamme de randNorm?
Optimizer
"La distribution est illimitée donc en théorie cela peut générer n'importe quel entier." Il n'y a pas de plage.
Timtech
1

Bash, 66

LANG=C sed -r '/^-?(0|[1-9][0-9]*)$/q;s/.*/5000000/;q'</dev/random

Il imprime presque toujours 5000000. Mais s'il trouve un numéro valide dans /dev/random, il imprimera ce numéro à la place.

Et celui-ci est plus rapide:

LANG=C sed -r '/^-?(0|[1-9][0-9]*)$/q;s/.*/5000000/;q'</dev/urandom
jimmy23013
la source
1
@Optimizer Il est censé être lent. C'est parce que c'est une vraie source aléatoire. Mais vous pouvez le tester avec /dev/urandomce qui est moins aléatoire.
jimmy23013
@Optimizer Comment cela prendrait-il une saisie manuelle? C'est lire un fichier, mais tout est un fichier.
Nit
@Optimizer Je ne comprends tout simplement pas le point que vous recherchez.
Nit
lire /dev/urandomdans un script shell est fondamentalement la même chose que d'appeler rand()dans d'autres langues. Bien que si vous utilisez vraiment bash, pas POSIX sh, vous pouvez obtenir des nombres aléatoires à partir de echo $RANDOM. wiki.ubuntu.com/DashAsBinSh donne hexdump /dev/urandomcomme équivalent pour bare-POSIX-minimum /bin/dash.
Peter Cordes
1

C ++, 95 octets

void f(){int d=-18,s=-1;while(s<9){d=(rand()%19+d+9)%10;cout<<d;s=9-rand()%10*min(d*d+s+1,1);}}

Étendu:

void f() {
    int d=-18,s=-1;
    while(s<9) {
        d=(rand()%19+d+9)%10;
        cout<<d;
        s=9-rand()%10*min(d*d+s+1,1);
    }
}

Explication:

La fonction continue d'imprimer des chiffres aléatoires consécutifs jusqu'à ce qu'un commutateur à valeur aléatoire prenne la valeur requise pour arrêter la fonction. d est la variable qui conserve la valeur du chiffre suivant à imprimer. s est la variable de commutation qui prend des valeurs entières aléatoires dans l'intervalle [0, 9], si s == 9 alors plus aucun chiffre n'est imprimé et la fonction se termine.

Les variables d et s sont initialisées afin de donner un traitement particulier au premier chiffre (en le prenant dans l'intervalle [-9, 9] et si le premier chiffre est nul alors la fonction doit se terminer pour éviter les zéros non significatifs). La valeur de d peut être affectée comme d = rand ()% 10 mais le premier chiffre ne peut pas être négatif. d est assigné à la place comme d = (rand ()% 19 + d + 9)% 10 et initialisé à -18 de sorte que la première valeur de d sera comprise entre [-9, 9] et les valeurs suivantes seront toujours comprises entre [0 , 9].

La variable s varie aléatoirement de [0, 9], et si s est égal à 9, la fonction se termine, donc après l'impression du premier chiffre, le suivant sera imprimé avec une probabilité de 90% (en supposant que rand () est vraiment aléatoire, et afin de satisfaire à la troisième condition). s peut être facilement attribué comme s = rand ()% 10, cependant, il y a une exception, si le premier chiffre est zéro, la fonction doit se terminer. Afin de gérer une telle exception, s a été attribué à s = ​​9-rand ()% 10 * min (d * d + s + 1,1) et initialisé à -1. Si le premier chiffre est zéro, le min renverra 0 et s sera égal à 9-0 = 9. L'affectation de la variable s sera toujours comprise entre [0, 9], donc l'exception ne peut se produire qu'au premier chiffre.

Caractéristiques (en supposant que rand () est vraiment aléatoire)

  • L'entier est imprimé chiffre par chiffre, avec une probabilité fixe de 90% d'imprimer un autre chiffre après avoir imprimé le dernier.

  • 0 est l'entier avec la plus grande chance d'être imprimé, avec une probabilité d'environ 5,2%.

  • La probabilité d'imprimer un entier sur l'intervalle [-10 ^ 6, 10 ^ 6] est d'environ 44% (le calcul n'est pas écrit ici).

  • Les entiers positifs et négatifs sont imprimés avec la même probabilité (~ 47,4%).

  • Tous les chiffres ne sont pas imprimés avec la même probabilité. Par exemple: au milieu de l'impression de l'entier, si le dernier chiffre était 5, le chiffre 3 aura une chance légèrement inférieure d'être imprimé ensuite. En général, si le dernier chiffre était d, le chiffre (d + 18)% 10 aura une chance légèrement inférieure d'être imprimé ensuite.

Exemples de sorties (10 exécutions)

-548856139437
7358950092214
507
912709491283845942316784
-68
-6
-87614261
0
-5139524
7

Process returned 0 (0x0)   execution time : 0.928 s
Press any key to continue.
Daniel Turizo
la source
1

Bash, 42 octets

printf "%d\n" 0x$(xxd -p -l5 /dev/random)
/ dev / random sur OSX est juste des octets aléatoires, et xxd -p -l5convertit 5 des caractères ascii en hexadécimal, et le printftransforme en format décimal.

Camden
la source
0

Pyth , 11 octets

WOyG~ZtOT)Z

Remarque: ce programme se bloquera probablement avec une erreur de mémoire sur n'importe quel ordinateur réel. Pour le tester, essayez de le remplacer Gpar une chaîne plus courte, comme dans ce code, qui génère des nombres en moyenne autour de 28000:

pyth -c 'WOy"abcdefghijklm"~ZtOUT)Z'

Ce code boucle, en ajoutant un nombre aléatoire de -1 à 8 Z, avec une probabilité de 2 ^ -26 de quitter la boucle à chaque répétition. La probabilité 2 ^ -26 est atteinte en sélectionnant un élément aléatoire ( O) de l'ensemble de tous les sous-ensembles ( y) de l'alphabet ( G).

Détails techniques et justification:

La probabilité 2 ^ -26 est dérivée de deux faits:, ylorsqu'elle est appelée sur des séquences, est la fonction power-set, an construit la liste de tous les sous-ensembles de l'entrée. Depuis l'entrée,, Gest de 26 caractères de long, ce bloc d'alimentation, yGa 2 ^ 26 entrées. OyGsélectionne un élément aléatoire parmi ces 2 ^ 26 entrées. Exactement l'une de ces entrées, la chaîne vide, sera évaluée comme fausse lorsqu'elle est passée à W, la boucle while. Par conséquent, il y a une probabilité de 2 ^ -26 de sortir de la boucle à chaque fois.

Dans tout nombre fixe de cycles de boucle K, la probabilité d'obtenir le nombre K * 3,5 + m et d'obtenir K * 3,5 - m est égale, car chaque séquence d'additifs qui atteint un total peut être inversée, -1 -> 8, 0 -> 7, etc., pour réaliser l'autre. De plus, les nombres plus proches de K * 3,5 sont nettement plus probables que les nombres plus éloignés. Ainsi, si K> 2000000 / 3,5 = 571428,5, la probabilité d'obtenir un nombre supérieur à 1000000 est supérieure à 75%, car certains des résultats supérieurs à ce nombre peuvent être mis en correspondance un à un avec tous les résultats inférieurs à ce nombre, et la moitié inférieure supérieure, peuvent être mis dans une correspondance un à un avec ceux de moins de 1000000. La probabilité d'obtenir au moins 571429 boucles est (1-2 ^ -26) ^ 571429, ce qui n'est pas moins de (1-2 ^ -26 * 571429), le nombre attendu de sorties de boucle au cours des 571429 premiers essais, soit 99,1%. Ainsi, sur 99,1% ou plus des essais, il y a 75% ou plus de chances d'obtenir au moins 1000000, donc il y a plus de 50% de chances de dépasser 1000000.

Ce code repose sur un comportement de l' Oendroit où un bogue a été introduit accidentellement il y a 3 jours et a été corrigé aujourd'hui. Il devrait fonctionner sur n'importe quelle version de Pyth 3 avant le 22 décembre ou après aujourd'hui. Le code suivant est équivalent et a toujours fonctionné:

WOyG~ZtOUT)Z
isaacg
la source
Qu'est-il arrivé au compilateur en ligne?
Optimizer
@Optimizer Problèmes avec le site Web, je vais y travailler.
isaacg
Ah cool. Je voulais travailler sur la traduction Pyth de ma réponse CJam hier et j'ai trouvé qu'elle donne 404.
Optimizer
0

Java, 113 octets

void g(){String a=Math.random()>0?"10":"01";for(;Math.random()>0;)a+=(int)(Math.random()*2);System.out.print(a);}

Ce programme imprime un nombre binaire sur le flux de sortie standard. Vous devrez peut-être attendre un certain temps car la probabilité qu'il termine le nombre (ou qu'il soit positif) est d'environ 0. L'idée que la valeur absolue d'un nombre généré est inférieure à 1 million est amusante, mais possible.

Non golfé:

void g(){
    String a=Math.random()>0?"10":"01";             //Make sure there are no trailing zeroes.
    for(;Math.random()>0;)a+=(int)(Math.random()*2);//Add digits
    System.out.print(a);                            //Print
}

Exemple de sortie: sera publié lorsqu'un nombre sera généré.

Le numéro un
la source
0

Java (JDK) , 140 127 octets

()->{int i;var o=System.out;for(o.print(i=(int)(19*Math.random())-10);i!=0&Math.random()<.9;)o.print((int)(11*Math.random()));}

-13 bytes en insérant plus de logique dans l'en-tête de la boucle - grâce à @ceilingcat

Essayez-le en ligne!

Sara J
la source