tamim vazneha

[sfs]

hala agar masaleye ghabl ra hal kardid mikhaham bedanam behtarin karani ke baraye 4 bar vazn kardan miyabid chand ast (yani had aksar tedad vaznehayi ke mitavan ba 4 bar vazn kardan sekeye taghalobi ra peida kard
agar kasi tamimi az in masalera midanad lotfan barayam ersal konad)

 

[Goharshady]

دوست عزیز، لطف کنید فارسی بنویسید
یک تعمیم بهتر می تواند این باشد که اگر n سکه داشته باشیم ، چمد بار وزن کردن لازم است
در صورت حل این تعمیم ، حالت خاصی که شما خواستید هم حل می شود.

 

[sfs]

bebakhshid dar type farsi kheili kondam vali
ama dar mored tamim nemidonam aslan mishe tamim dad ya na man baraye 4 bar vazn kardan karan 30 be dast avordam vali har kari mikonam nemitonam tamim bedam

 

[Goharshady]

اولین نکته این است که نمی توان از بین 13 سکه با 3 بار به جواب رسید.(چرا؟همین پایین را ببین)و حداقل 4 بار وزن کردن می خواهد.
در بین n سکه با مقایسه اول می توانیم یا

یا

سکه را حذف کنیم (یعنی با اطمینان بگوییم که تقلبی نیستند.)
حال فرض کنیم 20 سکه داشته باشیم،آن را به 4 دسته 5 تایی تقسیم می کنیم. ابتدا 2 تا دسته ی 5 تایی را با هم مقایسه می کنیم اگر یکسان بودند ،سکه تقلبی در بین 10 سکه دیگر است که با حداکثر 3 بار وزن کردن به دست می آید(با توجه به این که از بین 12 تا هم می توان با 3 بار وزن کردن پیدا کرد) و در غیر اینضورت سکه تقلبی در بین همین 10 سکه اولیه است که باز با حداکثر 3 بار وزن کردن به دست می آید.
برای عدد های بزرگتر به دسته هایی با این اندازه ها تقسیم می کنیم:
21={5,5,5,6}
22={5,5,6,6}
23={6,6,6,5}
24={6,6,6,6}
یعنی با 24 سکه و 4 بار وزن کردن می توان به جواب رسید ولی:
25={6,6,6,7}
و

برابر 13 است. با توجه به این که 13 ، چهار بار وزن کردن می خواست،برای وزن کردن 25 به 4+1=5 بار وزن کردن نیاز داریم.
این راه حل پاسخ تعمیم کلی تری که خودم مطرح کردم را نیز می دهد
کمی دقت کنید!!
جواب سوال شما 24 است.

 

[Goharshady]

bebakhshid dar type farsi kheili kondam vali
ama dar mored tamim nemidonam aslan mishe tamim dad ya na man baraye 4 bar vazn kardan karan 30 be dast avordam vali har kari mikonam nemitonam tamim bedam

چه جوری 30 تا رو با چهار بار وزن کردن به دست آوردی؟

 

[Goharshady]

برای تایپ فارسی از

استفاده کن.
http://www.google.com/transliterate/persian

 

[Goharshady]

http://www.irysc.com/modules/Forums/images/smiles/53.gif[/IMG]sfs

]bebakhshid dar type farsi kheili kondam vali
ama dar mored tamim nemidonam aslan mishe tamim dad ya na man baraye 4 bar vazn kardan karan 30 be dast avordam vali har kari mikonam nemitonam tamim bedam

اگر بشه 30 تا رو با 4 بار وزن کردن به دست آورد قاعدتا باید بشه 15 تا رو با 3 بار وزن کردن به دست آورد که غیر ممکنه!

 

[sfs]

deghat konid ke ma nemikhahim tain konim vazn vazneye mored nazar bishtar az baghie ast ya kam tar faghat mikhahim peidayash konim masalan dar bein 13 seke taghalobi mitavan ba 3 bar vazn kardan vazneye taghalobi ra peida kard ama nemitavan goft vaznash bishtar ast ya kamtar

 

[Goharshady]

راست میگی
خب طبق همون الگوریتمی که من گفتم فقط به جای 4 برای 5 حساب می کنیم.

 

[Goharshady]

حالا که فکر می کنم میبینم کلا مسئله فرق می کنه
یعنی راه حل من به درد این مسئله نمی خوره
ببخشییییییییییییییییید