1

Recently I came across an interesting C puzzle: We have a network with N nodes and M edges. Each node contains some number of packets. Initially, node i contains ai number of packets. At every time step, each packet randomly chooses one of it's neighboring neighbor and moves to it. We have to find out number of packets at every node after K time steps.

The main problem i'm facing in this problem is how to use probability. The word "randomly" is quite confusing and doesn't suggest any logic to me. Can anyone please help?

username_4567
  • 4,737
  • 12
  • 56
  • 92
  • If a node has three neighbours, one should be chosen randomly. That's what it seems to me. – Some programmer dude Oct 12 '12 at 21:35
  • You are apparently supposed to write a little simulation in C. Have a look at the C library functions rand and srand. http://linux.die.net/man/3/rand . In every step of the simulation redistribute the packets according to the rules (only neighbors) at random, output what changed and repeat many times. – Bernd Elkemann Oct 12 '12 at 21:38
  • This is nowt to do with the C programming language. It is put mathematics. Perhaps that would be a better forum. Gotta a feeling that it is NP problem that is related to colouring or the TSP. – Ed Heal Oct 12 '12 at 21:38
  • ... Also try to understand the problem before writing code. – Ed Heal Oct 12 '12 at 21:39
  • If you don't know how to use randmon numbers in C, you might want to take a look at this: http://stackoverflow.com/questions/822323/how-to-generate-a-random-number-in-c – Pablo Oct 12 '12 at 22:04
  • @Ed Heal It is not NP complete problem. I wanted to know about how to put randomness factor in code. I never wrote programs for such cases. – username_4567 Oct 12 '12 at 22:23
  • @username_4567 - This might be handy to read http://en.wikipedia.org/wiki/NP_complete. Also think about Oracles or Monto Carlo – Ed Heal Oct 12 '12 at 22:34

1 Answers1

0

The simplest approach is to use the srand() and rand() functions.

srand() initializes the random number generator. Typical usage is:

srand(time(NULL));

which set a seed based on the current time. It's not securely random, but it avoids getting the same results every time you run the program (unless you run it twice in very quick succession). You should call srand() only once during the execution of your program, before any calls to rand().

The rand() function returns a random number in the range 0 to RAND_MAX; the value of RAND_MAX can vary from one system to another. You can manipulate the result to get random numbers in a desired range; for example, rand() % 2 gives you a random number with the value 0 or 1.

Section 13 of the comp.lang.c FAQ covers this well.

Note that rand() typically doesn't generate very high-quality random numbers. For your purposes, that's probably ok. If it isn't, there are other system-specific ways to generate better random numbers.

Keith Thompson
  • 254,901
  • 44
  • 429
  • 631