بابا و دخترش

بابا و دختراش

Saturday, June 03, 2006

جواب معمای اول:


خوب بلاخره آخرین نفری هم که بایستی معما رو جواب می داد آمد و راه حل اش رو گفت.البته هاله اونجوری که خودش گفته برخلاف من و بقیه جواب معما رو از قبل می دونسته. خود من هم اولین بار این معما رو توی یک جلسه مصاحبه 4 ساعته توی گوگل شنیدم ( البته 30 دقیقه بیشتر برای حل اش وقت نداشتم) اما راه حل:
دوتا استراتژی می شه انتخاب کرد. اول اینکه طبقات رو به فواصل مساوی pتقسیم کرد و اونها رو یکی یکی امتحان کرد. اگر در طبقه p1 گوی نشکست طبقه p2 رو همنطور بالاتر رو آزمایش می کنیم ولی اگر درطبقه pi گوی مورد نظر شکست باید همه طبقات از مرحله قبلی رو یکی یکی بیایم بالا و گوی رو آزمایش کنیم که در این صورت در بدترین حالت تعداد آزمایش ها برابر خواهد شدبا :

n=100, T=n/p+(p-1)
که در این صورت به شکل زیر می رسیم که نشون می دهه برای p=9 یا 10 کمترین تعداد آزمایش رو خواهیم داشت که عبارت است از T=19

اما استراتژی دوم می گه که می تونیم فواصل هر طبقه رو در هر مرحله کمتر و کمتر کنیم تا تعداد آزمایش ها در هر مرحله ثابت بمونه مثلا در مرحله اول به طبقه p می ریم ولی مرحله دوم به p+(p-1) و مرحله سوم p+(p-1)+(p-2)و الی آخر در این صورت نهایتا خواهیم داشت
n=p+(p-1)+(p-2)+...=p(p-1)/2 => p^2-p-2n=0 , n=100
همونجوری که هاله گفته راه حل درست اش 14 مرحله آزمایشه
خوب این از معمای اول. اگر علاقهمندید بگید تا بازهم معما براتون بگم.

0 Comments:

Post a Comment

Links to this post:

Create a Link

<< Home

| مطلب را به بالاترین بفرستید: Balatarin


My blog is worth $11,855.34.
How much is your blog worth?