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

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

آمار پرسش:

  • پرسیده شده: 2015-04-03 09:50:21 -0500
  • مشاهده شده: 397 بار
  • بروز شده: 2015-04-03 11:08:24 -0500

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

ارتفاع یکسان کوهنورد در دو روز کوهنوردی

پیداکردن همه ی تابع های پیوسته در 0 با برقراری رابطه $f(x + y) = f(x) + f(y) + xy(x + y)$

از تابع f(X)= x^2+4*x+3 به f(X)= x^2+10*x+9

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

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

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

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

علائم ریاضی:

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

یک جدول $n \times n$ - می خواهیم همه ی لامپ ها را روشن کنیم.

6

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

در هر مربع از یک جدول ‎$n \times n$‎ یک لامپ قرار دارد . در ابتدا هر کدام از لامپ ها خاموش هستند. اگر روی هر لامپ یک ضربه بزنیم ، آن لامپ و همه ی لامپ های هم ردیف و هم ستون با آن ، تغییر وضعیت می دهند . ثابت کنید می توانیم تمام لامپ ها را روشن کنیم و همچنین کمترین تعداد لامپ را پیدا کنید که با ضربه زدن روی آن ها ، می توان تمام لامپ ها را روشن کرد.

تابع
2015-04-03 09:50:21 -0500
حمید کاملی 2921 ● 30 ● 56 ● 83
پاک‌کردن   ویرایش سوال
نظرات

قبلا توسط علیرضا گذاشته شده . نام سوالی که علیرضا گذاشته بود : روشن کردن لامپ با استفاده از کمترین حرکت

2015-04-03 09:51:35 -0500 حمید کاملی

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

2015-08-06 07:20:57 -0500 امیر شکری

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

2016-10-27 07:40:05 -0500 امیر شکری

1 پاسخ

5

اگر n فرد باشه با انتخاب یک سطر کل جدول یک بار تغییر می کنه و این کمترین مقدار هست چون اگر یک گراف 2 بخشی بکشیم که یک طرف سطر ها و طرف دیگر ستون ها باشند و یال u,v باشد اگر و تنها اگر خانه ی تقاطع سطر u و ستون v انتخاب شده باشد آنگاه هر راس باید حداقل 1 یال داشته باشد پس باید حداقل n یال باشد

اگر n زوج باشه کل جدول رو باید انتخاب کنیم اثبات این که همه ی لامپ ها روشن میشن راحته اما اثبات کمینه بودن:برای این که تنها یه خونه تغییر کنه کافیه که همه ی هم سطر ها و هم ستون ها به علاوه ی خودش رو انتخاب کنیم پس می تونیم هر حالتی از 2 به توان n^2 حالت رو بسازیم و می دونیم که انتخاب کردن خونه ها هم همین تعداد حالت داره پس باید به ازای هر حالت از لامپ ها یک حالت از انتخاب ها هم باشه و برعکس پس تنها حالتی که می شه لامپ ها رو روشن کرد همین حالته

2015-04-03 11:07:55 -0500
عطا 1110 ● 7 ● 12 ● 29
پاک‌کردن   ویرایش پاسخ
نظرات

مرسی . +1 درسته . فقط کمی دقیق تر کاش توضیح می دادی . یک جواب خیلی دقیق و کامل روی وبلاگم براش گذاشتم. اگه این جواب رو متوجه نشدید می تونید به اون مراجعه کنید. البته کمی طولانی تره .

2015-04-03 13:37:03 -0500 حمید کاملی

+1 ممنون فثط اثبات قسمت n زوج رو نفهمیدم. ممنون میشم توضیح بدید.

2015-04-07 08:27:21 -0500 سی پلاس پلاس

کجاشونفهمیدید؟

2015-04-07 08:52:39 -0500 عطا

http://math-cs.blog.ir/page/%D9%85%D8%B3%D8%A7%D8%A8%D9%82%D9%87-%DB%8C-%D8%B1%DB%8C%D8%A7%D8%B6%DB%8C مساله ی شماره ی یک

2015-06-13 10:33:54 -0500 حمید کاملی

پاسخ شما

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

پیش‌نمایش:

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