اولین باره که به کاهو میای؟ راهنمای سایت رو حتما بخون!

ورود ثبت‌نام راهنما درباره‌ی کاهو
پرسش‌ها برچسب‌ها کاربر‌ها سوال بپرسید!

آمار پرسش:

  • پرسیده شده: 2014-05-09 08:18:59 -0500
  • مشاهده شده: 1,303 بار
  • بروز شده: 2014-06-04 03:08:47 -0500

پرسش‌های مشابه:

دنباله و جادوگر - دوره ی 24 - مرحله ی 2

مسئله تالار ها -سوال مرحله ۲

سوال ۱ روز دوم مرحله ۲ دوره ۲۳: رشته‌ی نزدیک

بازی رنگی - سوال ۱ - مرحله ۲ - ۱۳۹۳

وزنه‌ها و ماشین جادویی - سوال ۲ - مرحله ۲ - ۱۳۹۳

گاوی خسیس - سوال ۳ - مرحله ۲ - ۱۳۹۳

انتقال مهره‌های گاوی - سوال ۴ - مرحله ۲ - ۱۳۹۳

آشپزباشی:‌ مرتب کردن پشته با برعکس کردن یک دنباله متوالی از ابتدای آن

تعداد مثلث های پوشاننده

الگوریتمی برای کمینه کردن تعداد دفعات بازشدن کشوها

نکاتی در مورد نوشتن پاسخ:

در این قسمت می‌تونی به یک پرسش پاسخ بدی. اگه می‌خوای در مورد پرسش بحث و اظهار نظر کنی از قسمت «ثبت نظر» استفاده کن.
پاسخت رو دقیق و کامل بنویس، از عکس استفاده کن و اگه لازمه به منابع (کتاب یا سایت) ارجاع بده.
اگه پرسش یا پاسخ‌ها مفید هستند حتما بهشون رای بده تا پرسش‌ها و پاسخ‌های خوب مشخص بشن.

استفاده از ویرایشگر:

توی قسمت پیش‌نمایش می‌تونی ببینی متنی که نوشتی چجوری روی سایت دیده میشه.
خیلی مهم: برای اینکه به خط بعد بری باید دوتا Enter بزنی.
می‌تونی از تگ‌های معمولی و ساده‌ی html هم استفاده کنی.
با دکمه‌هایی که بالای ویرایش‌گر قرار دارند کلی کار می‌شه کرد. از عکس‌گذاشتن بگیر تا لیست شماره‌دار. حتما امتحان‌شون کن.

علائم ریاضی:

برای نوشتن علائم ریاضی می‌تونی از Mathjax استفاده کنی. راهنمای Mathjax رو از سایت math.stackexchange بخون.
برای نوشتن عبارت ریاضی وسط جمله، اون عبارت رو بین دوتا $ قرار بده.
برای نوشتن عبارت ریاضی تو یه خط جدید اون رو بین دوتا $$ قرار بده.

یافتن کوچکترین پیچ و مهره با مقایسه آنها

6

n پیچ و n مهره که از نظر ظاهری شبیه هستند داریم. میدانیم هر پیچ تنها به یک مهره میخورد (با آن هم اندازه است) و هیچ دو پیچی هم اندازه نیستند.

عمل «آزمون» یعنی برداشتن یک پیچ و یک مهره و امتحان کردن آنها. در این صورت یا می فهمیم پیچ بزرگتر از مهره است، یا مهره بزرگتر از پیچ است، یا هم اندازه هستند. توجه کنید که نمیتوانیم مستقیما دو پیچ، یا دو مهره را مقایسه کنیم.

روشی ارایه کنید که با حداکثر $2n-2$ آزمون همواره بتوانیم کوچکترین پیچ و کوچکترین مهره را پیدا کنیم.

مرحله۲ ۱۳۷۷ روز۲ مقایسه الگوریتم
2014-05-09 08:18:59 -0500
کلاه قرمزی 3097 ● 21 ● 34 ● 57
پاک‌کردن   ویرایش سوال
نظرات

سلام میدونستید انجمن علمی نخبگان دانشگاه صنعتی شریف مسابقه تخصصی مهارت سنجی برنامه نویسی و داده کاوی گذاشته است آدرس سایتش www.fanavard.com

2015-08-06 09:45:26 -0500 امیر شکری

سلام میگم یک سر به سایت www.fanavard.ir بزنید. مسابقات برنامه نویسی شون شروع شده. گواهی رسمی از طرف دانشگاه شریف می ده. 50 تا سکه هم جایزشه

2016-10-27 08:38:41 -0500 امیر شکری

3 پاسخ

7

اول یه پیچ و یه مهره بر میداریم
اگر پیچ بزرگتر بود یعنی حتما یک پیچ کوچکتر از این مهره وجود دارد(چون یه پیچی باید به این مهره بخوره)پس این پیچ کوچیکترین پیچ نیست. این پیچ رو میزاریم کنار و با دیگری ادامه میدهیم.
اگر مهره بزرگتر بود هم مثل بالا یعنی این مهره کوچیکترین مهره نیست و اون رو میزاریم کنار و با دیگری ادامه میدهیم.
اگر هم اندازه بودند یکیشان را نگه میداریم(مثلا مهره را)و با دیگری ادامه میدهیم. در هر مرحله که این پیچ کنار گذاشته شد مهره اش را نیز کنار میگذاریم و اگر در آخر همین پیچ ماند یعنی آن مهره نیز کوچکترین مهره است.
هر دفعه یک پیچ یا مهره(اگر پیچ مانده بود، مهره و بالعکس) بر میداریم و دوباره همین کار ها را انجام میدهیم.
در هر مرحله حتما یک پیچ یا مهره کنار گذاشته میشود و بعد از 2n - 2 مرحله به یک پیچ و یک مهره میرسیم که این ها کوچکترین هستند.
تو هیچ مرحله ای هم کوچیکترین مهره یا پیچ رو کنار نمیزاریم چون چیزی از اونا کوچیکتر وجود نداره.

2014-05-31 11:14:10 -0500
پویان 2066 ● 11 ● 18 ● 40
پاک‌کردن   ویرایش پاسخ
3

پویان ما نمی دونیم که هر پیچ برای کدوم مهره است برای همین نمی تونیم در هر مرحله که پیچی کنار گذاشته شد مهره اش را نیز کنار بگذاریم. ولی راهش همین طوریه : هر بار یک پیچ با یک مهره رو مقایسه می کنیم اونی که بزرگتر بود رو حذف میکنیم(چون پیچ یا مهره کوچک تری وجود دارد)و اگر که با هم مساوی شدند پیچ را با یک مهره دیگر مقایسه میکنیم و اگر مهره دوم کوچکتر بود هردو را خذف و در غیر اینصورت مهره دوم را حذف میکنیم و در مراحل بعدی تا زمانی که مهره کوچکتر پبدا شود هر مهره را با این پیچ مقایسه می کنیم در ضمن اگر همه ی مهره ها با این پیچ مقایسه و حذف شوند این پیچ و مهره پیچ و مهره مورد نظر است ،در هر مرحله یک پیچ یا مهره در حال حذف شدن است و در حالت آخر نیز در یک مرحله دو پیچ و مهره حذف میشوند.حال بعد از n-1+i حرکت (i>=0)کوچکترین پیچ یا مهره پیدا میشود(هرکدام که زود تر اتفاق بیافتد).بدون اینکه به کلیت مسله لطمه ای وارد شود فرض کنید اول مهره پیدا شود در این صورت باید پیچی هم اندازه ی آن وجود داشته باشد.که تا بحال آن را مقایسه نکرده ایم از بین n-i پیچ باقی مانده هرکدام که به مهره خورد پیچ مورد نظر است.

2014-05-31 21:23:25 -0500
عطا 1110 ● 7 ● 12 ● 29
پاک‌کردن   ویرایش پاسخ
نظرات

من گفتم اگه مقایسه کردیم و برابر بودن یکیشون رو نگه میداریم(چون ممکنه کوچیکترین باشن)و با اون یکی ادامه میدیم حالا هروقت اینی که داریم باهاش ادامه میدیم حذف شد اونی که نگه داشته بودیم(و با این برابره)رو حذف میکنیم

2014-06-01 01:41:35 -0500 پویان

من فکر کردم برای هر مرحله ای میگی آخه گفته بودی در هر مرحله این کار رو میکنیم حواسم نبود که ادامه جمله قبله :D

2014-06-01 01:47:14 -0500 عطا

سلام من فقط میدونم که عده ای این این سوال رو با ایده ی استقرا حل میکنن ولی ایده اصلی این سوال استقرا نیست بلکه این سوال راه حل صریح داره ممنون

2014-06-01 11:24:19 -0500 هه هه هه
2

اول همه ی پیچ ها رو از 1 تا n به صف می کنیم و همهی مهره ها رو هم همینطور. مهره ی 1 رو برمی داریم و همینطور با پیچ ها امتحانش می کنیم تا یه پیچی پیدا کنیم که ازش کوچکتره. (مثلا پیچ i ام) چون پیچ i کوچکتره و یه مهره ای هم داره که بهش می خوره و از مهره ی 1 کوچکتره پس مهره 1 رو می اندازیم دور و مهره ی 2 رو برمی داریم و از ادامه (پیچ i و بعدش پیچ i +1 و به همین ترتیب) همین کارا رو امتحان می کنیم. اولین مهره ای که هیچ پیچ کوچکتری نداشت ( و قطعا یه پیچ اندازه داشته که با خودش امتحان کردیم، چون کوچکترین مهره ست و کوچکترین پیج رو داره و فقط خودش می تونه ازش بگذره) رو به این ترتیب پیدا می کنیم، کل این عملیات حداکثر 2n تا طول می کشه و دو حرکت آخر کاملا به درد نخورن، چون اگه کل 2n حرکت بگذره یعنی به عنوان آخرین حرکت آخرین مهره رو با آخرین پیچ امتحان کردیم در حالی که چون اون مهره هه ازهمه ی مهره های دیگه کوچکتر بوده و با همه ی پیچ ها تا اینجا براش بزرگ بودن یعنی پیچ آخری اندازشه و اون دو تا کوچکترین هان.

2014-06-01 13:47:10 -0500
هشئذذ 459 ● 6
پاک‌کردن   ویرایش پاسخ
نظرات

الان من و عطا دقیقا همین جوابو ندادیم؟؟؟

2014-06-01 14:44:01 -0500 پویان

پاسخ شما

فقط در صورتی که پاسخی برای این پرسش دارید، آن را اینجا بنویسید و برای بحث کردن از قسمت «ثبت‌ نظر» استفاده کنید. شما می‌توانید قبل از وارد شدن به سایت پاسخ خود را بنویسید. این پاسخ ذخیره می‌شود و زمانی که شما وارد سایت شدید یا ثبت‌نام کردید منتشر می‌شود.

پیش‌نمایش:

کلیه‌ی حقوق این سایت متعلق به کمیته‌ی ملی المپیاد کامپیوتر است.