atilla snowman
چهارشنبه 30 مرداد 1387, 13:23 عصر
سلام دوستان
من به یک مساله بر خوردم که ذهنمو مشغول کرد ولی بی جواب موند.
این مساله اینه:
(لطفا با دقت بخونید)
ما یک مولد عدد رندم داریم که یا 0 و یا 1 بر میگردونه. این مولد به احتمال p یک برمیگردونه و به احتمال یک منهای p صفر که p هم بین صفر و یکه و البته ما p رو نمیدونیم و فقط اطمینان داریم که عدد ثابتیه.
میخوایم با استفاده از این مولد یک مولد عدد رندم بسازیم که یا یک یا صفر رو با احتمال مساوی یعنی یک دوم برمیگردونه.
راه حل بدی که سریعا به ذهن میرسه اینه که به صورت متوالی و به تعداد زیاد مولدی که داریم رو فراخوانی کنیم و با نتایجی که به دست میاد p رو تقریت بزنیم که چندان به درد نمیخورد و احتمالا نیازی به آن نباشد. یا مولد رو به تعداد دلخواه مثلا به تعداد 10 بار به کار میندازیم و 10 تا تولیدیش رو جمع میکنیم. اگه بیت آخر حاصل جمع این ده تا عدد یک بود یک و اگه صفر بود صفر برگردونیم.
این راه حلها بدند و من دنبال بهترش میگردم.
اگه چیزی به ذهنتون میرسه لطفا بگید و اگه تونستید تحلیل زمانی هم بکنید.
با تشکر
من به یک مساله بر خوردم که ذهنمو مشغول کرد ولی بی جواب موند.
این مساله اینه:
(لطفا با دقت بخونید)
ما یک مولد عدد رندم داریم که یا 0 و یا 1 بر میگردونه. این مولد به احتمال p یک برمیگردونه و به احتمال یک منهای p صفر که p هم بین صفر و یکه و البته ما p رو نمیدونیم و فقط اطمینان داریم که عدد ثابتیه.
میخوایم با استفاده از این مولد یک مولد عدد رندم بسازیم که یا یک یا صفر رو با احتمال مساوی یعنی یک دوم برمیگردونه.
راه حل بدی که سریعا به ذهن میرسه اینه که به صورت متوالی و به تعداد زیاد مولدی که داریم رو فراخوانی کنیم و با نتایجی که به دست میاد p رو تقریت بزنیم که چندان به درد نمیخورد و احتمالا نیازی به آن نباشد. یا مولد رو به تعداد دلخواه مثلا به تعداد 10 بار به کار میندازیم و 10 تا تولیدیش رو جمع میکنیم. اگه بیت آخر حاصل جمع این ده تا عدد یک بود یک و اگه صفر بود صفر برگردونیم.
این راه حلها بدند و من دنبال بهترش میگردم.
اگه چیزی به ذهنتون میرسه لطفا بگید و اگه تونستید تحلیل زمانی هم بکنید.
با تشکر