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

آمار پرسش:

  • پرسیده شده: 2014-06-15 05:30:46 -0500
  • مشاهده شده: 275 بار
  • بروز شده: 2014-07-19 20:22:38 -0500

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

بازی بر روی تخته

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

یافتن کوتاه ترین دور در گراف ساده

ایجاد شدن ۳۰ دسته با مجموع ۶۰ سنگریزه هنگام تقسیم کردن ۱۰۰ سنگریزه

راهنمایی برای برنامه نویسی

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

مجموع ارقام ! 100

مرجع فارسی برای الگوریتم های هندسی و 2sat

حدس زدن کارت پنجم با انتخاب ترتیب دادن ۴ کارت

نظریه اعداد لازم برای المپیاد کامپیوتری ها

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

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

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

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

علائم ریاضی:

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

بدست‌آوردن زوج سنگ برای بردن بازی به شرط برداشتن ۱ تا k سنگ‌ریزه از یک توده‌ی n سنگ‌ریزه‌ای در هر مرحله

2

دو نفر بازی زیر را انجام می دهند :

در ابتدا N سنگ ریزه(که Nعددی فرد است)موجود است . در هر حرکت بازی کنی که نوبت حرکت با او است می تواند 1و2و3و. . .وk سنگ ریزه بردارد. به این صورت یکی در میان دو بازی کن حرکت می کنند تا همه ی سنگ ریزه ها برداشته شود. در این لحظه تعداد سنگ ریزه هایی که هر یک برداشته اند شمرده می شود و هر کدام از ان ها که مجموعا تعداد زوجی سنگ ریزه برداشته بود برنده ی بازی به حساب می اید .(با توجه به این که N فرد است حتما یک نفر برنده می شود.)

برنامه ای بنویسید که با در یافت Nوk مشخص کند که کدام یک از دو بازیکن استراتژی برد دارند.(فرض کنید N حد اکثر 100و k حداکثر 20 باشد.)

برنامه-نویسی بازیها
2014-06-15 05:30:46 -0500
س 131 ● 2 ● 10
پاک‌کردن   ویرایش سوال
نظرات

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

2014-06-15 06:07:52 -0500 کلاه قرمزی

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

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

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

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

1 پاسخ

1

اگر این بازی را A بنامیم بازی‌های B و C و D را مشابه A به صورت زیر تعریف می‌کنیم:

B: تعداد سنگ‌ریزه‌ها زوج است نفر اول می‌خواهد تعداد سنگ‌ریزه‌هایش زوج باشد ولی نفر دوم می‌خواهد تعداد سنگ‌ریزه‌هایش فرد باشد

C: تعداد سنگ‌ریزه‌ها زوج است نفر اول می‌خواهد تعداد سنگ‌ریزه‌هایش فرد باشد ولی نفر دوم می‌خواهد تعداد سنگ‌ریزه‌هایش زوج باشد

D: تعداد سنگ‌ریزه‌ها فرد است هر دو می‌خواهند تعداد مهره‌هایشان فرد شود

حال هر ۴ مساله را به طور موازی با برنامه‌ریزی پویا حل می‌کنیم:

برای هر یک آرایه‌ای به طول $n$ در نظر می‌گیریم که مثلا $A[i]$ برابر یک است اگر نفر اول استراتژی برد داشته باشد و در غیراین‌صورت برابر صفر خواهد بود (در این صورت نفر دوم استراتژی برد دارد)

حال برای حل $A[n]$ فرض کنیم نفر اول $i$ سنگ‌ریزه بردارد آن‌گاه:

۱-اگر $i$ زوج باشد نفر دوم در صورتی استراتژی برد دارد که $A[n-i]=1$ باشد و درغیراین‌صورت نفر اول استراتژی برد خواهد داشت

۲-اگر $i$ فرد باشد نفر دوم در صورتی استراتژی برد دارد که $B[n-i]=1$ باشد و درغیراین‌صورت نفر اول استراتژی برد خواهد داشت

یا مثلا برای حل $B[n]$ اگر نفر اول $i$ سنگ‌ریزه بردارد آن‌گاه:

۱-اگر $i$ زوج باشد نفر دوم در صورتی استراتژی برد دارد که $C[n-i]=1$ باشد

۲-اگر $i$ فرد باشد نفر دوم در صورتی استراتژی برد دارد که $D[n-i]=1$ باشد

به طریق مشابه می‌توان قاعده‌های مربوط به حل $C[n]$ و $D[n]$ را هم بدست آورد. به ازای هر یک از مقادیر $i=1..k$ بررسی می‌کنیم که اگر نفر اول $i$ سنگ‌ریزه بردارد آیا راهی وجود دارد که نفر مقابل استراتژی برد نداشته باشد در این صورت استراتژی برد وجود دارد و در غیراین‌صورت وجود نخواهد داشت

نکته۱: برای پیاده‌سازی باید یا از تکنیک Memoization استفاده کرد (توصیه من اینه) یا به ازای مقادیر مختلف $n$ به طور هم‌زمان هر ۴ مساله را حل کرد

نکته۲: با این که در مسایل B و C به نظر میرسه همیشه برنده می‌تونه وجود نداشته باشه اما واقعیت اینه که اگر نفر اول استراتژی برد نداشت دومی حتما داره!

2014-07-19 20:22:38 -0500
شهریارو 49 ● 2
پاک‌کردن   ویرایش پاسخ

پاسخ شما

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

پیش‌نمایش:

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