[algogeeks] X-AmazoN
You are provided with a bit generator which generates 1 and 0 with equal probabilities i.e. (1/2). You are required to design a function which generates numbers form 1-1000 with equal probabilities i.e. (1/1000). -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] X-AmazoN
int a=(int)rand()%1001; //1-1000 int b=(int)rand()%2; // 0-1 On Fri, Jul 15, 2011 at 3:01 PM, SkRiPt KiDdIe anuragmsi...@gmail.comwrote: You are provided with a bit generator which generates 1 and 0 with equal probabilities i.e. (1/2). You are required to design a function which generates numbers form 1-1000 with equal probabilities i.e. (1/1000). -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- **Regards SAGAR PAREEK COMPUTER SCIENCE AND ENGINEERING NIT ALLAHABAD -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] X-AmazoN
@sagar did you read the question before posting On Fri, Jul 15, 2011 at 3:17 PM, sagar pareek sagarpar...@gmail.com wrote: int a=(int)rand()%1001; //1-1000 int b=(int)rand()%2; // 0-1 On Fri, Jul 15, 2011 at 3:01 PM, SkRiPt KiDdIe anuragmsi...@gmail.comwrote: You are provided with a bit generator which generates 1 and 0 with equal probabilities i.e. (1/2). You are required to design a function which generates numbers form 1-1000 with equal probabilities i.e. (1/1000). -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- **Regards SAGAR PAREEK COMPUTER SCIENCE AND ENGINEERING NIT ALLAHABAD -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Sunny Aggrawal B-Tech IV year,CSI Indian Institute Of Technology,Roorkee -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] X-AmazoN
oh sorry... On Fri, Jul 15, 2011 at 3:21 PM, sunny agrawal sunny816.i...@gmail.comwrote: @sagar did you read the question before posting On Fri, Jul 15, 2011 at 3:17 PM, sagar pareek sagarpar...@gmail.comwrote: int a=(int)rand()%1001; //1-1000 int b=(int)rand()%2; // 0-1 On Fri, Jul 15, 2011 at 3:01 PM, SkRiPt KiDdIe anuragmsi...@gmail.comwrote: You are provided with a bit generator which generates 1 and 0 with equal probabilities i.e. (1/2). You are required to design a function which generates numbers form 1-1000 with equal probabilities i.e. (1/1000). -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- **Regards SAGAR PAREEK COMPUTER SCIENCE AND ENGINEERING NIT ALLAHABAD -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Sunny Aggrawal B-Tech IV year,CSI Indian Institute Of Technology,Roorkee -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- **Regards SAGAR PAREEK COMPUTER SCIENCE AND ENGINEERING NIT ALLAHABAD -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] X-AmazoN
If rand() generates equi-probable numbers within range [1 - n] and n is a multiple of 1000 then your above code will be correct. You should utilize the bit-generator function. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] X-AmazoN
Read Dave solution https://groups.google.com/forum/#!msg/algogeeks/nE3REQZ-YBc/Y02NVHYBhdkJ On Fri, Jul 15, 2011 at 3:23 PM, SkRiPt KiDdIe anuragmsi...@gmail.comwrote: If rand() generates equi-probable numbers within range [1 - n] and n is a multiple of 1000 then your above code will be correct. You should utilize the bit-generator function. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Varun Pahwa B.Tech (IT) 7th Sem. Indian Institute of Information Technology Allahabad. Ph : 09793899112 Official Email :: rit2008...@iiita.ac.in Another Email :: varunpahwa.ii...@gmail.com People who fail to plan are those who plan to fail. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] X-AmazoN
its correct. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] X-AmazoN
int bit_generator(); // function which returns 1 and 0 with equal probabilities
int generator()
{
int generated_num[10],i,n;
for(i=0;i10;i++)
{
generated_num[i]=bit_generator();
}
n=generated_num[0];
i=1;
while(i10)
{
n*=10;
n+=generated_num[i];
i++;
}
if(n==0 || n1000)
generator();
else
return n;
}
No. of possible outcomes = 1000 i.e. 1 to 1000
Since each outcome is equally likely, so probability of each generated
no. is 1/1000.
There are some issues with this algo, since we are calling generator()
again and again untill the no. is from 1-1000, but we can discuss on
these issues...
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] X-AmazoN
I don't think so that probability would be exact 1/1000 . suppose number is ( a9 a8 a7 a6 a5 a4 a3 a2 a1 a0) where a0 is least and a9 is most significant bit then you can generate each of the bit ai using given bit generator but if but at a time (a9 , a8 , a7 , a6 , a5 , a3 ) and any other bit are set together then number would exceed given limit 1000 which we don't want . so dave's solution generate numbers with probability 1/(2^n) where n is ceil(log2(b-a+1)) so 1/2^10 = 1/1024 -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] X-AmazoN
nos [1001,1023] are neglected as if their probabilities are set to zero and recalculated.As nos [1,1000] are only considered and as they are generated with equal probabilities i.e. 1/1024. I feel the above solution to be correct. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] X-AmazoN
but suppose you have to generate numbers between [1,513] then also it would generate numbers them each with probability 1/1024 which could make a big difference and I feel the above solution to be incorrect . May be we could think of a better one . -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] X-AmazoN
@rishab, here it generates numbers which are powers of 2 until n gets to 0
int bit_generator(); // function which returns 1 and 0 with equal
probabilities
int generator(int n)
{
int generated_num[10],i;
int lg = (int)floor(log(n));
n -= pow(lg,2);
int m = 0;
i=0;
if(n==0)return 0;
while(ilg)
{
m*=10;
m+=bit_generator();
i++;
}
return m + generator(n);
}
surender
On Fri, Jul 15, 2011 at 10:58 PM, Rishabh Maurya poofiefoo...@gmail.comwrote:
but suppose you have to generate numbers between [1,513] then also it would
generate numbers them each with probability 1/1024 which could make a big
difference and I feel the above solution to be incorrect . May be we could
think of a better one .
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] X-AmazoN
@Surender Your solution in correct one . -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
