آمار پرسش:

• پرسیده شده: 2015-03-14 02:33:27 -0500
• مشاهده شده: 209 بار
• بروز شده: 2015-03-30 01:56:02 -0500

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

الگوریتم محاسبه لگاریتم-سوال مسابقه دانش آموزی صنعتی شریف

وبسایت مسابقه‌های برنامه نویسی

سه زندانی از کجا باید متوجه شوند که قبل از خودش دو نفر دیگر وارد اتاق شده اند یا نه !!

شبکه ی مربعی با یک دزد و حداقل تعداد پلیس

پوش محدب - کدینگ -سوال سخت -الگوریتمی (Convex Hull)

در های به هم پیوسته در اتاقی دایره ای شکل

جدول ۸*۸ !

مسابقه سوال 1........................

الگوریتم تا چه حدی برای المپیاد نیازه

مسابقه‌ی شماره ۸، BWC Round #8

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

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

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

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

علائم ریاضی:

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

محاسبه مجموع اعداد نصفه جدول با حداقل حرکات- سوال مسابقه حضوری شریف

2

یه نصفه جدول n* n داریم,(برای مثال در پایین یک نصفه جدول 5*5 میبینید) که میتوانید روی آن حرکت زیر را انجام دهید.

حرکت: انتخاب یکی از خانه ها و محاسبه مجموع اعدادی که در مستطیلی است که یک گوشه آن, خانه ی اول و گوشه ی مقابلش این خانه است.

مثلا با انتخاب خانه ای که 6 روی آن نوشته شده, 244 به دست می آید. (244=6+34+44+79+68+13)

با حداقل حرکات مجموع اعداد جدول را به دست آورید.(با اثبات حداقل بودن)

الگوریتمی شریف مسابقه

2015-03-14 02:33:27 -0500

پروفسور 296 ● 7 ● 13 ● 26

پاک‌کردن   ویرایش سوال

نظرات

حداقل n تا سوال رو می خواد چون هر کدوم از خونه های قطری باید در یک سوال پرسیده شوند

2015-03-14 12:02:37 -0500 عطا

n تا لازمه ولی به هیچ وجه کافی نیست. با این n تا حرکت مجموع رو نمیشه فهمید.

2015-03-14 15:35:54 -0500 پروفسور

ممنون به خاطر تبریک . آهان ببخشید الان متوجه سوال شدم !

2015-03-15 04:18:48 -0500 م ح م د

سوال قشنگیه:)

2015-03-15 04:32:35 -0500 حمیدرضاه

میشه 2n-1 ولی هنوز نتونستم حداقلیشو اثبات کنم :)

2015-03-15 07:12:15 -0500 حمیدرضاه

0

واضحه که هر حرکت از یه خونه متمایز زده میشه.( درغیر اینصورت میشه جواب با تعداد حرکت کمتری رو با حذف تکرارها بدست آورد)
بعد از هر حرکت باید تصمیم بگیری که مجموع مستطیل متناظرش رو جمع برنی یا تفریق کنی - برای راحتی حرکت هارو با جمع و تفریق نام گذاری می کنیم.

به این دقت کن که تو مجموع نهایی هر خونه دقیقا 1 بار ظاهر شده.
برای اینکه مجموع نهایی هر کدوم از اعداد روی قطر اصلی رو شامل بشه، باید 1 حرکت جمع به ازای هر عضو روی قطر اصلی انجام بدی. در غیر این صورت یه خونه رو کلا تو مجموع حساب نکردی!!
اگه دقت کنی هر عضو روی دومین قطر 2 بار تو مجموع فعلی حساب شده، پس از هر کدوم از این خونه ها باید 1 بار حرکت تفریق انجام بدی. در غیر این صورت یه خونه 2 بار تو مجموع حساب شده!!
تا حالا 2n-1 حرکت انجام دادی :دی
ثابت می کنیم که همین 2n-1 حرکت کافیه.
به ازای هر اندیس دلخواه، می تونی ببینی این خونه تو مستطیل متناظر با k خونه از قطر اصلی و k-1 خونه از قطر فرعی قرار می گیره.
پس k - ( k-1) = 1 بار تو مجموع ظاهر شده.

2015-03-30 01:55:17 -0500

رضا حسینی آشتیانی 21 ● 1

پاک‌کردن   ویرایش پاسخ

نظرات

من برای اثبات لزوم همین چیزی که شما گفتید رو گفتم و گفتن غلطه! با توجه به الگوریتمی که ما تعریف کردیم حتما باید خونه های قطر دوم رو هم انتخاب کنه. گفتن کی گفته حتما باید جمع باشه اصن چرا ضرب نباشه؟؟ در کل گفتن "اثبات" درستی نیست.

2015-03-30 06:30:40 -0500 پروفسور

اگه دقت کنی هر عضو روی دومین قطر 2 بار تو مجموع فعلی حساب شده، پس از هر کدوم از این خونه ها باید 1 بار حرکت تفریق انجام بدی. در غیر این صورت یه خونه 2 بار تو مجموع حساب شده!! این کاریه که ما میکنیم شاید یه راهی باشه که این کارو نکنه مثلا اینا رو جمع نکنه

2015-03-30 09:57:29 -0500 حمیدرضاه