Vous disposez d'une fonction Rand5 (). Cette fonction renvoie des entiers parfaitement aléatoires (distribution égale) entre 1 et 5.

Fournissez la fonction Rand7 (), qui utilise Rand5 () pour produire des entiers parfaitement aléatoires entre 1 et 7.

Java - 61 caractères

int rand7(){int s=0,c=7;while(c-->0)s+=rand5();return s%7+1;}

Pilote de test pour validation:

class Rand {

    public static void main(String[] args) {
        int[] nums = new int[7];
        // get a lot of numbers
        for(int i = 0; i < 10000000; i++) nums[rand7()-1]++;
        // print the results
        for(int i = 0; i < 7; i++) System.out.println((i+1) + ": " + nums[i]);
    }

    // just for rand5()
    static java.util.Random r = new java.util.Random();

    static int rand5() {
        return r.nextInt(5)+1; // Random.nextInt(n) returns 0..n-1, so add 1
    }

    static int rand7(){int s=0,c=7;while(c-->0)s+=rand5();return s%7+1;}

}

Résultats

C:\Documents and Settings\glowcoder\My Documents>java Rand
1: 1429828
2: 1429347
3: 1428328
4: 1426486
5: 1426784
6: 1429853
7: 1429374

C:\Documents and Settings\glowcoder\My Documents>

Perl - 47 (au lieu de 52) caractères

sub rand7{($x=5*&rand5+&rand5-3)<24?int($x/3):&rand7} 

De plus, j'arrive à utiliser l'opérateur ternaire ET la récursivité. Meilleur jour de ma vie!

OK, 47 caractères si vous utilisez mod au lieu de div:

sub rand7{($x=5*&rand5+&rand5)<27?$x%7+1:&rand7} 

JavaScript, 42

Rand7=f=_=>(x=Rand5()+Rand5()*5-5)>7?f():x

Bonus ES5:

Rand7=eval.bind(0,'for(;x=Rand5()+Rand5()*5-5,x>7;);x')

Ruby - 54 caractères (basé sur la solution Dan McGrath, utilisant une boucle)

def rand7;x=8;while x>7 do x=rand5+5*rand5-5 end;x;end

Ruby - 45 caractères (même solution, en utilisant la récursivité)

def rand7;x=rand5+5*rand5-5;x>7 ?rand7: x;end

En Python:

def Rand7():
  while True:
    x = (Rand5() - 1) * 5 + (Rand5() - 1)
    if x < 21: return x/3 + 1

En Common Lisp 70 caractères:

(defun rand7()(let((n(-(+(rand5)(* 5(rand5)))5)))(if(> n 7)(rand7)n)))

Les parenthèses prennent plus de place que je ne le souhaiterais.

En c / c ++ en utilisant l' échantillonnage de rejet

int rand7(){int x=8;while(x>7)x=rand5()+5*rand5()-5;return x;}

62 caractères.

Traduction en PHP, de la réponse publiée par Dan McGrath.

function Rand7(){$x=8;while($x>7)$x=rand5()+5*rand5()-5;return $x;}

67 caractères.

R, 34 caractères

En R (un langage construit pour le calcul statistique), une solution délibérément trompeuse:

# Construct a Rand5 function
Rand5 <- function() sample(seq(5),1)
# And the golf
Rand7=function(r=Rand5())sample(1:(r/r+6),1)
# Or (same character count)
Rand7=function(r=Rand5())sample.int(r/r+6,1)
# Or even shorter(thanks to @Spacedman)
Rand7=function()sample(7)[Rand5()]

Grâce à une évaluation paresseuse des arguments, j'ai supprimé le point-virgule et les accolades.

Sortie sur 10 ^ 6 répliques:

> test <- replicate(10^6,Rand7())
> table(test)
test
     1      2      3      4      5      6      7 
142987 142547 143133 142719 142897 142869 142848 

library(ggplot2)
qplot(test)

scala, 47, 40 59 caractères:

def rand7:Int={val r=5*(rand5-1)+rand5
if(r<8)r else rand7}

avec 2 entrées de rand5:

\ 1 2 3 4 5 
1 1 2 3 4 5  
2 6 7 8 ..
3 11 ..
4 ..
5

Je multiplie le premier-1 par 5 et j'ajoute le second. La plupart des résultats sont ignorés et conduisent à un nouveau calcul. Le résultat devrait être une distribution égale des valeurs de 1 à 25, dont je ne choisis que les 7 premières. Je pourrais accepter les 21 premiers avec la construction d'un modulo, mais cela conduirait à un code plus long.

code historique qui a échoué, mais pas très clairement. Merci à Ilmari Karonen de l'avoir signalé:

def rand7=(1 to 7).map(_=>rand5).sum%7+1

Merci à Yoshiteru Takeshita pour cette approche scala-2.8.0 qui a rendu la «somme» si facile. Ma solution avant:

def rand7=((0/:(1 to 7))((a,_)=>a+rand5-1))%7+1

rand5:

val rnd = util.Random 
def rand5 = rnd.nextInt (5) + 1

C ++

int Rand4()
{
    int r = Rand5();
    return r > 4 ? Rand4() : r;
}

inline int Rand8()
{    
    return (Rand4() - 1) << 2 + Rand4();
}

int Rand7()
{
    int r = Rand8();
    return r > 7 ? Rand7() : r;
}

C ++ (109)

Golfé

int Rand4(){int r=Rand5();return r>4?Rand4():r;}int Rand7(){int r=Rand4()-1<<2+Rand4();return r>7?Rand7():r;}

Traduction en Javascript, de la réponse postée par Dan McGrath.

function Rand7(){x=8;while(x>7)x=rand5()+5*rand5()-5;return x}

62 caractères

JavaScript, 85

function Rand7(){for(x=0,i=1;i<8;x^=i*((k=Rand5())%2),i*=1+(k<5));return x?x:Rand7()}

Je sais qu'il y a une réponse plus courte, mais je voulais montrer le test de ce puzzle. Il s'avère que seule la réponse de Clyde Lobo utilisant l'échantillonnage de rejet de Dan McGrath est correcte (entre les réponses JS).

С ++

int Rand7()
{
    int r = Rand5();
    int n = 5;
    do {
        r = (r - 1) * 5 + Rand5();
        int m = n * 5 / 7 * 7;
        if (r <= m) {
            return r % 7 + 1;
        }
        r -= m;
        n = n * 5 - m;
    } while (1);
}

Distribution des nombres (1000000 entiers):

142935 142751 142652 143299 142969 142691 142703

Le nombre moyen d'appels à Rand5 () pour chaque entier généré est d'environ 2,2 (2 à 10+).

1 2      3      4     5    6   7 8  9 10
0 840180 112222 44433 2212 886 0 60 6 1

En Java (ou C / C ++ je suppose)

• en utilisant la formule de génération d'Alexandru, en 65 caractères:

  int rand7(){int x=rand5()*5+rand5()-6;return x>20?rand7():x/3+1;}
  

• utilisant la formule de génération de Dan McGrath, en 60 caractères

  int rand7(){int x=rand5()+5*rand5()-5;return x>7?rand7():x;}
  

Clojure - 58 caractères

(defn rand7[](#(if(<% 8)%(rand7))(+(rand5)(*(rand5)5)-5)))

Python, 56 37 caractères

Une autre solution qui peut être erronée, en Python:

rand7 = lambda: sum(rand5() for i in range(7)) % 7 + 1

Cela semble trop simple, mais quand j'essaye:

counter = [0] * 7
for i in range(100000):
     counter[rand7()] += 1

J'obtiens une distribution raisonnablement uniforme (toutes entre 14000 et 14500).

D'accord, maintenant que quelqu'un a voté pour ce poste: cette solution est-elle vraiment correcte? J'ai plus posté ceci ici pour inciter les gens à le critiquer. Eh bien, si c'est correct, ma version golfée serait:

rand7=lambda:eval("+rand5()"*7)%7+1

ce qui donne 37 caractères.

Java, 65 caractères:

int rand7(){int r;do{r=rand5()+5*rand5()-5;}while(r>7);return r;}

Python, 70 caractères

def rand7():
 while True:
  n=5*(rand5()-1)+(rand5()-1)
  if n<21:return n%7+1

mais complètement correct sur la base du raisonnement ici .

Perl, 43 caractères, échantillonnage itératif de rejet

sub rand7{1while($_=5*&rand5-rand5)>6;$_+1}

Cela donne un avertissement Ambiguous use of -rand5 resolved as -&rand5(), mais fonctionne correctement. L'ajout d'une &seconde au deuxième rand5appel le corrige au prix d'un coup. (Inversement, l'autre &peut également être supprimé s'il rand5 a été défini avec un ()prototype.)

Ps. La version suivante de 46 caractères est environ trois fois plus rapide:

sub rand7{1while($_=5*&rand5-rand5)>20;$_%7+1}

Java - 66 caractères

int rand7(){int s;while((s=rand5()*5+rand5())<10);return(s%7+1);}

Plus longue que la routine précédente, mais je pense que celle-ci renvoie des nombres uniformément distribués en moins de temps.

PostScript (46)

Cela utilise un codage de jeton binaire, par conséquent, voici un hexdump:

00000000  2f 72 61 6e 64 37 7b 38  7b 92 38 37 92 61 7b 92  |/rand7{8{.87.a{.|
00000010  40 7d 69 66 92 75 32 7b  72 61 6e 64 35 7d 92 83  |@}if.u2{rand5}..|
00000020  35 92 6c 92 01 35 92 a9  7d 92 65 7d 92 33        |5.l..5..}.e}.3|
0000002e

Pour l'essayer, vous pouvez également le télécharger .

Voici le code non golfé et commenté, ainsi que le code de test.

% This is the actual rand7 procedure.
/rand7{
  8{                      % potentialResult
    % only if the random number is less than or equal to 7, we're done
    dup 7 le{             % result
      exit                % result
    }if                   % potentialResult
    pop                   % -/-
    2{rand5}repeat        % randomNumber1 randomNumber2
    5 mul add 5 sub       % randomNumber1 + 5*randomNumber2 - 5 = potentialResult
  }loop
}def

%Now, some testing code.

% For testing, we use the built-in rand operator; 
% Doesn't really give a 100% even distribution as it returns numbers
% from 0 to 2^31-1, which is of course not divisible by 5.
/rand5 {
  rand 5 mod 1 add
}def

% For testing, we initialize a dict that counts the number of times any number
% has been returned. Of course, we start the count at 0 for every number.
<<1 1 7{0}for>>begin

% Now we're calling the function quite a number of times 
% and increment the counters accordingly.
1000000 {
  rand7 dup load 1 add def
}repeat

% Print the results
currentdict{
  2 array astore ==
}forall

int result = 0;

for (int i = 0; i++; i<7)
    if (((rand(5) + rand(5)) % 2) //check if odd
        result += 1;

return result + 1;

R (30 caractères)

Définissez rand7:

rand7=function(n)sample(7,n,T)

Parce que R a été écrit avec une analyse statistique à l'esprit, cette tâche est triviale, et j'utilise la fonction intégrée sampleavec remplacement défini sur TRUE.

Exemple de sortie:

> rand7(20)
 [1] 4 3 6 1 2 4 3 2 3 2 5 1 4 6 4 2 4 6 6 1
> rand7(20)
 [1] 1 2 5 2 6 4 6 1 7 1 1 3 7 6 4 7 4 2 1 2
> rand7(20)
 [1] 6 7 1 3 3 1 5 4 3 4 2 1 5 4 4 4 7 7 1 5

Sensationnel

rand7={if(b==null)b=rand5();(b=(rand5()+b)%7+1)}

exemple de distribution sur 35 000 itérations:

[1:5030, 2:4909, 3:5017, 4:4942, 5:5118, 6:4956, 7:5028]

Est-ce mauvais que ce soit avec état?

Mathematica, 30

Rand7=Rand5[]~Sum~{7}~Mod~7+1&

Que dis-tu de ça?

int Rand7()
{
    return Rand5()+ Rand5()/2;
}

Java - 54

int m=0;int rand7(){return(m=m*5&-1>>>1|rand5())%7+1;}

Test de distribution: [1000915, 999689, 999169, 998227, 1001653, 1000419, 999928]

Algorithme:

• Conserver une variable globale
• multipliez par 5, donc il y a 5 places libres à l'extrémité la moins significative
• Tronquer le bit de signe pour le rendre positif (pas nécessaire si les numéros non signés étaient pris en charge)
• Modulo 7 est la réponse

> Les nombres ne sont plus non corrélés entre eux, mais individuellement parfaitement aléatoires.

Rubis (43 octets)

def rand7;(0..7).reduce{|i|i+rand5}%7+1;end

La solution de cemper93 portée sur Ruby est trois octets plus courte;) (34 octets)

def rand7;eval("+rand5"*7)%7+1;end

Code C / C ++ le code principal n'a qu'une seule ligne!

static unsigned int gi = 0;

int rand7()
{
    return (((rand() % 5 + 1) + (gi++ % 7)) % 7) + 1;
}

//call this seed before rand7
//maybe it's not best seed, if yo have any good idea tell me please
//and thanks JiminP again, he remind me to do this
void srand7()
{
    int i, n = time(0);
    for (i = 0; i < n % 7; i++)
        rand7();
}

Le srand7 () est la graine de rand7, doit appeler cette fonction avant rand7, tout comme appeler srand avant rand en C.

C'est un très bon choix, car il n'appelle rand () qu'une seule fois, et aucune boucle, aucune dépense de mémoire supplémentaire.

Permettez-moi de l'expliquer: considérons un tableau entier de taille 5:

1st get one number from 1 2 3 4 5 by rand5
2nd get one number from 2 3 4 5 6
3rd get one number from 3 4 5 6 7
4th get one number from 4 5 6 7 1
5th get one number from 5 6 7 1 2
5th get one number from 6 7 1 2 3
7th get one number from 7 1 2 3 4

Nous avons donc obtenu le TABLEAU, chacun de 1-7 apparaît 5 fois dedans, et a tous les 35 nombres, donc la probabilité de chaque nombre est 5/35 = 1/7. Et la prochaine fois,

8th get one number from 1 2 3 4 5
9th get one number from 2 3 4 5 6
......

Après suffisamment de temps, nous pouvons obtenir la distribution uniforme de 1-7.

Ainsi, nous pouvons allouer un tableau pour restaurer les cinq éléments de 1-7 par boucle vers la gauche et obtenir un numéro du tableau à chaque fois par rand5. Au lieu de cela, nous pouvons générer les sept tableaux avant et les utiliser de manière circulaire. Le code est également simple, a de nombreux codes courts peuvent le faire.

Mais, nous pouvons utiliser les propriétés de l'opération%, donc le tableau 1-7 lignes est équivalent à (rand5 + i)% 7, c'est-à-dire: a = rand ()% 5 + 1 est rand5 en langage C, b = gi ++ % 7 génère toutes les permutations du tableau ci-dessus, et 0 - 6 remplace 1 - 7 c = (a + b)% 7 + 1, génère 1 - 7 uniformément. Enfin, nous avons obtenu ce code:

(((rand() % 5 + 1) + (gi++ % 7)) % 7) + 1 

Mais, nous ne pouvons pas obtenir 6 et 7 au premier appel, nous avons donc besoin d'une graine, certains comme srand pour rand en C / C ++, pour perturber la permutation pour le premier appel formel.

Voici le code complet à tester:

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

static unsigned int gi = 0;

//a = rand() % 5 + 1 is rand5 in C language,
//b = gi++ % 7 generates all permutations,
//c = (a + b) % 7 + 1, generates 1 - 7 uniformly.
//Dont forget call srand7 before rand7
int rand7()
{
   return (((rand() % 5 + 1) + (gi++ % 7)) % 7) + 1;
}

//call this seed before rand7
//maybe it's not best seed, if yo have any good idea tell me please
//and thanks JiminP again, he remind me to do this
void srand7()
{
    int i, n = time(0);
    for (i = 0; i < n % 7; i++)
        rand7();
}

void main(void)
{
    unsigned int result[10] = {0};
    int k;

    srand((unsigned int)time(0)); //initialize the seed for rand
    srand7() //initialize the rand7

    for (k = 0; k < 100000; k++)
        result[rand7() - 1]++;

    for (k = 0; k < 7; k++)
        printf("%d : %.05f\n", k + 1, (float)result[k]/100000);
}