3

This code is used to get random numbers with a certain probability: 8 is returned if r is between 0 and 0.8; 2 is returned if r is between 0.8 and 1.

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

int main()
{
    srand(time(NULL));
    double r = rand() / (double)RAND_MAX;
    double sum = 8 + 2;
    if (r < 8 / sum) {
        printf("80% \n");
    } else {
        printf("20% \n");
    }  
}

but if I have more than two numbers, say n, how can I handle it? Can I handle it with multiple if-else statements? Or what else?

LorenzoDonati4Ukraine-OnStrike
  • 6,875
  • 4
  • 37
  • 56
Nidal
  • 1,717
  • 1
  • 27
  • 42
  • Just interested: why you asign 2 + 8? Why not just 10? – dhein Aug 25 '13 at 01:40
  • 1
    @Zaibis To make the logic clearer, maybe, shorter isn't always better – Thomas Aug 25 '13 at 01:41
  • um, well it depends. If you could have many such values, looping over an array may be best, or if the values are determined by some formula, just a loop with the values. Or if it's a few fixed values, you could use a series of if/else. I don't really see the point of this question; what are you hoping to find out? – Dave Aug 25 '13 at 01:44
  • Can you give an example of input (e.g: [8,2]) and output (e.g: [80%, 20%]) that you wish to have for your N problem please? You don't even need the if/else in the example you gave... – fabien Aug 25 '13 at 01:45
  • @Dave I want to distribute rand scope to multiple choices according to its weigh, for example if we have the choices :5,3,2,1 then I want 50% to 5, 30% to 3, 20% to 2, 10% to 1 – Nidal Aug 25 '13 at 01:47
  • you can accomplish that with a simple loop. I'd put it in a function which takes an array parameter (of the values) to keep it reusable. It sounds like you're quite new to this, so I'd recommend looking up arrays, looping and pointers. – Dave Aug 25 '13 at 01:50
  • Many programming languages have these things called "arrays" and "loops". – Lee Daniel Crocker Aug 25 '13 at 05:03
  • @pjs below has a better answer; since it also references the simpler solutions in mine, it would be better for other users if you switched the accepted answer to his. – necromancer Aug 25 '13 at 16:39

2 Answers2

3

Simple

  1. Create an array of probabilities (sum to 1.0), in O(n) time
  2. Generate a random number between 0.0 and 1.0
  3. Iterate through the array, in O(n) time:
    • if the random number < the probability of the element, stop
    • otherwise decrement the random number by the probability and move to next element
  4. The answer is the number corresponding to the element you stopped at

Complex

  1. Create an array of cumulative probabilities and store them in an array, in O(n) time (this array should have increasing values)
  2. Generate a random number between 0.0 and 1.0
  3. Do a binary search to find the smallest element that is >= the random number, in O(log(n)) time.
  4. The answer is the number corresponding to the element you stopped at

I have not included the necessary corner cases to address. I am sure you can do it yourself.

necromancer
  • 23,916
  • 22
  • 68
  • 115
1

In addition to randomstring's proposals, you could consider building an Alias Table -- O(n log n) to construct the table, O(1) per value to generate.

Community
  • 1
  • 1
pjs
  • 18,696
  • 4
  • 27
  • 56