• اگر سمپادی هستی همین الان عضو شو :
    ثبت نام عضویت

سوال اول مسابقه کامپیوتری ها: حرکات اسب در صفحه شظرنج

  • شروع کننده موضوع
  • #1

daneshvar.amrollahi

کاربر حرفه‌ای
ارسال‌ها
327
امتیاز
130
نام مرکز سمپاد
راهنمایی حلی۲/دبیرستان حلی۱۰/دبیرستان علامه طباطبایی
شهر
تهران
سال فارغ التحصیلی
1397
مدال المپیاد
کامپیوتر
مکانی برای بحث درمورد سوال زیر:


حرکات اسب در صفحه شظرنج - گراف و الگوریتم - ۱۵ امتیازی

برنامه ای بنوسید که با گرفتن یک عدد n، مشخص کند که آیا می توان با شروع از خانه ای دلخواه در یک صفحه شظرنج n*n، تنها با حرکات اسب و عدم ورود به خانه ی تکراری (مراجعه شده)، به همه ی خانه ها راه یافت یا خیر؟ (خیلی به اردر برنامه توجه نکنید - الگوریتم برنامه مورد نظر است)

تاپیک مربوطه: http://www.sampadia.com/forum/index.php/topic,106140.0.html

مدت زمان پاسخ گویی به سوال: ۴ روز

*ویرایش:
۱ - ارائه ی راه حل به کمک هر مبحثی (ترکیبیات، گراف، الگوریتم یا ...) بلامانع است و در این زمینه هیچ محدودیتی ندارید!

۲- امتیاز این سوال از ۱۰ به ۱۵ تغییر یافت. ۵ نمره ی دیگر مربوط به کد سوال است. یعنی هر که بتواند کد این سوال را بنویسد، از امتیاز کامل ۱۵ برخوردار خواهد شد. در غیر این صورت با ارائه راه حل تئوری، می تواند ۱۰ امتیاز کسب کند.


×علی[میم] : با تشکر ویژه بابت استارتی که به مسابقه زدی !!!!!
 

Anita H

کاربر فوق‌حرفه‌ای
ارسال‌ها
571
امتیاز
2,987
نام مرکز سمپاد
حلّی ۲
شهر
تهران
سال فارغ التحصیلی
1396
مدال المپیاد
کامپیوتری بودم
دانشگاه
شریف
رشته دانشگاه
کامپیوتر
پاسخ : سوال اول مسابقه کامپیوتری ها: حرکات اسب در صفحه ش

فرض کن صفحه ی شطرنج یه گراف باشه که خونه های اون متناظر با راسهای گراف هستن و دو راس(خونه) به هم یال دارن اگر و فقط اگر بشه با مهره ی اسب و با یه حرکت از اون دو تا خونه به همدیگه رفت!‌(پیچیده گفتم :-? )
حالا از یه خونه شروع میکنیم dfs میزنیم میریم جلو
(الآن باس توضیح بدم چرا الگوریتم درسته؟ واضحه دیگه :-")
اردرش هم احتمالن ان دو هست چون از هر خونه ی ارایه فقط یه بار میگذریم

ویرایش: آقا غلط کردم، سوالو اشتباه فهمیده بودم کلن، اردر این الگوریتم n^4 هست یحتمل :-"
 
  • شروع کننده موضوع
  • #3

daneshvar.amrollahi

کاربر حرفه‌ای
ارسال‌ها
327
امتیاز
130
نام مرکز سمپاد
راهنمایی حلی۲/دبیرستان حلی۱۰/دبیرستان علامه طباطبایی
شهر
تهران
سال فارغ التحصیلی
1397
مدال المپیاد
کامپیوتر
پاسخ : سوال اول مسابقه کامپیوتری ها: حرکات اسب در صفحه ش

به نقل از amoo§majid :
فرض کن صفحه ی شطرنج یه گراف باشه که خونه های اون متناظر با راسهای گراف هستن و دو راس(خونه) به هم یال دارن اگر و فقط اگر بشه با مهره ی اسب و با یه حرکت از اون دو تا خونه به همدیگه رفت!‌(پیچیده گفتم :-? )
حالا از یه خونه شروع میکنیم dfs میزنیم میریم جلو
(الآن باس توضیح بدم چرا الگوریتم درسته؟ واضحه دیگه :-")
اردرش هم احتمالن ان دو هست چون از هر خونه ی ارایه فقط یه بار میگذریم

آره میدونم توضیحش سخته. اصلا ماهیت dfs همینه مگه نه؟‌:D اگر بتونید دقیق تر بگید چه بهتر...

روی اردرش بیشتر فکر کن. اگر واقعا اردر n^2 باشه، یعنی اگر کدش نوشته بشه و تا 10000 بهش ورودی بدیم، زیر ۱ ثانیه جواب میده. چون تا ۱۰ به توان ۸ عملیات زیر ۱ ثانیه میتونه انجام بشه. آیا همچنین چیزی امکان داره؟
 

rezaezio

کاربر فوق‌حرفه‌ای
ارسال‌ها
1,167
امتیاز
1,956
نام مرکز سمپاد
حلّیِ 2
شهر
تهران
مدال المپیاد
برنز و طلای کامپیوتر !
دانشگاه
شریف
رشته دانشگاه
نرم افزار
پاسخ : سوال اول مسابقه کامپیوتری ها: حرکات اسب در صفحه ش

به نقل از amoo§majid :
فرض کن صفحه ی شطرنج یه گراف باشه که خونه های اون متناظر با راسهای گراف هستن و دو راس(خونه) به هم یال دارن اگر و فقط اگر بشه با مهره ی اسب و با یه حرکت از اون دو تا خونه به همدیگه رفت!‌(پیچیده گفتم :-? )
حالا از یه خونه شروع میکنیم dfs میزنیم میریم جلو
(الآن باس توضیح بدم چرا الگوریتم درسته؟ واضحه دیگه :-")
اردرش هم احتمالن ان دو هست چون از هر خونه ی ارایه فقط یه بار میگذریم
ببین تو مساله رو به گراف تبدیل کردی، حالا توی این گراف دنبال مسیر همیلتونی میگردی، که الگوریتم چند جمله‌ای نداریم براش در حال حاضر !
مشکل راهت اینه که با dfs زدن و جلو رفتن نمیشه دور همیلتونی پیدا کرد ! :-?

نکته : منظورم این نبود که مساله مورد نظر تاپیک الگوریتم چندجمله ای نداره !! سوتفاهم نشه :-""
 
  • شروع کننده موضوع
  • #5

daneshvar.amrollahi

کاربر حرفه‌ای
ارسال‌ها
327
امتیاز
130
نام مرکز سمپاد
راهنمایی حلی۲/دبیرستان حلی۱۰/دبیرستان علامه طباطبایی
شهر
تهران
سال فارغ التحصیلی
1397
مدال المپیاد
کامپیوتر
پاسخ : سوال اول مسابقه کامپیوتری ها: حرکات اسب در صفحه ش

به نقل از Damon :
ببین تو مساله رو به گراف تبدیل کردی، حالا توی این گراف دنبال مسیر همیلتونی میگردی، که الگوریتم چند جمله‌ای نداریم براش در حال حاضر !
مشکل راهت اینه که با dfs زدن و جلو رفتن نمیشه دور همیلتونی پیدا کرد ! :-?

خود دور همیلتونی رو نمی خوایم! یعنی این که اول به کدوم خونه بره و بعدش به کجا و ... .
فقط میخواهیم ببینیم آیا این گراف دور هملیتونی دارد یا نه ( که با dfs زدن میشه حل کرد ). شاید راه های دیگری هم داشته باشد...
 

rezaezio

کاربر فوق‌حرفه‌ای
ارسال‌ها
1,167
امتیاز
1,956
نام مرکز سمپاد
حلّیِ 2
شهر
تهران
مدال المپیاد
برنز و طلای کامپیوتر !
دانشگاه
شریف
رشته دانشگاه
نرم افزار
پاسخ : سوال اول مسابقه کامپیوتری ها: حرکات اسب در صفحه ش

به نقل از DaneshvarA :
خود دور همیلتونی رو نمی خوایم! یعنی این که اول به کدوم خونه بره و بعدش به کجا و ... .
فقط میخواهیم ببینیم آیا این گراف دور هملیتونی دارد یا نه ( که با dfs زدن میشه حل کرد ). شاید راه های دیگری هم داشته باشد...
بررسی وجود دور همیلتونی تو یک گراف دلخواه هم الگوریتم چند جمله ای نداره، داره ؟! :O
+ این مساله جواب داره از (O(1 ! ;;)
 
  • شروع کننده موضوع
  • #7

daneshvar.amrollahi

کاربر حرفه‌ای
ارسال‌ها
327
امتیاز
130
نام مرکز سمپاد
راهنمایی حلی۲/دبیرستان حلی۱۰/دبیرستان علامه طباطبایی
شهر
تهران
سال فارغ التحصیلی
1397
مدال المپیاد
کامپیوتر
پاسخ : سوال اول مسابقه کامپیوتری ها: حرکات اسب در صفحه ش

به نقل از Damon :
بررسی وجود دور همیلتونی تو یک گراف دلخواه هم الگوریتم چند جمله ای نداره، داره ؟! :O
+ این مساله جواب داره از (O(1 ! ;;)

یعنی یه الگوریتمی هست که دور هملیتونی توی گراف پیدا می کنه (از اردر ۱) ؟

آره دیگه در واقع انگار داریم می پرسیم: گراف صفحه شظرنج n*n، همیلتونی هستش یا نه...

الگوریتم چند جمله ای چیه؟ یه توضیح می دیدید؟

*ویرایش: متن سوال رو اصلاح کردم. میتونید دوباره بخونید : هر کسی میتونه با هر الگوریتم و ابزاری، اینجا پاسخ بنویسه! ممکنه چند تا راه حل داشته باشیم!
 

rezaezio

کاربر فوق‌حرفه‌ای
ارسال‌ها
1,167
امتیاز
1,956
نام مرکز سمپاد
حلّیِ 2
شهر
تهران
مدال المپیاد
برنز و طلای کامپیوتر !
دانشگاه
شریف
رشته دانشگاه
نرم افزار
پاسخ : سوال اول مسابقه کامپیوتری ها: حرکات اسب در صفحه ش

به نقل از DaneshvarA :
یعنی یه الگوریتمی هست که دور هملیتونی توی گراف پیدا می کنه (از اردر ۱) ؟

آره دیگه در واقع انگار داریم می پرسیم: گراف صفحه شظرنج n*n، همیلتونی هستش یا نه...

الگوریتم چند جمله ای چیه؟ یه توضیح می دیدید؟
نه باو !
توی یه گراف عمومی، مساله پیدا کردن دور همیلتونی و یا حتی بررسی وجود دور همیلتونی، در زمان چند جمله‌ای تا حالا حل نشده !!!!
ولی گفتم که واسه مساله‌ی تاپیک، یعنی بررسی وجود دور همیلتونی در گراف خاص صفحه شطرنج، میشه راه گفت از (O(1 !!!!

الگوریتم چند جمله‌ای یعنی الگوریتمی که اردرش، چند جمله‌ای بر حسب n باشه ! مثلا (O(n ^ 2 ، یا (O(n ^ 3
ولی بعضی الگوریتم ها اُردرشون نمایی هست ! مثلا از اُردر دو به توان n ! ویا اُردر n فاکتوریل !!!!

++ فک کنم تاپیکُ ریختیم به هم ! :-" اگه چیزیو نفهمیدی خصوصی بگو :-"

×علی[میم] : بسیار درخواست میشه ، خصوصی نرین ، عمومی بحث کنین یخ ملت باز شه !!!!
 
  • شروع کننده موضوع
  • #9

daneshvar.amrollahi

کاربر حرفه‌ای
ارسال‌ها
327
امتیاز
130
نام مرکز سمپاد
راهنمایی حلی۲/دبیرستان حلی۱۰/دبیرستان علامه طباطبایی
شهر
تهران
سال فارغ التحصیلی
1397
مدال المپیاد
کامپیوتر
پاسخ : سوال اول مسابقه کامپیوتری ها: حرکات اسب در صفحه ش

به نقل از Damon :
نه باو !
توی یه گراف عمومی، مساله پیدا کردن دور همیلتونی و یا حتی بررسی وجود دور همیلتونی، در زمان چند جمله‌ای تا حالا حل نشده !!!!
ولی گفتم که واسه مساله‌ی تاپیک، یعنی بررسی وجود دور همیلتونی در گراف خاص صفحه شطرنج، میشه راه گفت از (O(1 !!!!

الگوریتم چند جمله‌ای یعنی الگوریتمی که اردرش، چند جمله‌ای بر حسب n باشه ! مثلا (O(n ^ 2 ، یا (O(n ^ 3
ولی بعضی الگوریتم ها اُردرشون نمایی هست ! مثلا از اُردر دو به توان n ! ویا اُردر n فاکتوریل !!!!

++ فک کنم تاپیکُ ریختیم به هم ! :-" اگه چیزیو نفهمیدی خصوصی بگو :-"

مشکلی نیست. بحث های عمومی هستند و به درد همه می خورن! تاپیک به هم نریخته.

صورت سوال هم که گراف کلی نیست . گراف صفحه شطرنج موردنظر هستش. اگر برای جواب این سوال، کسی الگوریتمی از (O(1 گفتش (با توضیحات) احتمالا میشه بهترین جواب!
 

Anita H

کاربر فوق‌حرفه‌ای
ارسال‌ها
571
امتیاز
2,987
نام مرکز سمپاد
حلّی ۲
شهر
تهران
سال فارغ التحصیلی
1396
مدال المپیاد
کامپیوتری بودم
دانشگاه
شریف
رشته دانشگاه
کامپیوتر


آقا من جدا دارم گیج میزنم
لزومی نداره دنبال دور همیلتونی بگردیم :-"
اگر بشه به ازای هر خونه از صفحه ی شطرنج یه مسیر همیلتونی پیدا کرد که ابتداش اون خونه باشه، حله
(یعنی گراف برای این که شرایط مسئله رو داشته باشه لزومن باید دور همیلتونی داشته باشه؟)

+یکی منو از سردرگمی دربیاره

خطاب به پایینی: باو مشکل من اصلن اردر 1 و این حرفا نیست، مشکل من اون قسمتی از حرفه دیمنه که میگه باید دنبال دور همیلتونی بگردیم.
 
  • شروع کننده موضوع
  • #11

daneshvar.amrollahi

کاربر حرفه‌ای
ارسال‌ها
327
امتیاز
130
نام مرکز سمپاد
راهنمایی حلی۲/دبیرستان حلی۱۰/دبیرستان علامه طباطبایی
شهر
تهران
سال فارغ التحصیلی
1397
مدال المپیاد
کامپیوتر
پاسخ : سوال اول مسابقه کامپیوتری ها: حرکات اسب در صفحه ش

به نقل از amoo§majid :
آقا من جدا دارم گیج میزنم
لزومی نداره دنبال دور همیلتونی بگردیم :-"
اگر بشه به ازای هر خونه از صفحه ی شطرنج یه مسیر همیلتونی پیدا کرد که ابتداش اون خونه باشه، حله
(یعنی گراف برای این که شرایط مسئله رو داشته باشه لزومن باید دور همیلتونی داشته باشه؟)

+یکی منو از سردرگمی دربیاره

یه راهش همون dfs هستش که گفتید. اما آقای سلطانی میگن برای گراف این سوال، میشه با اردر ۱ فهمید هملیتونی هستش یا نه که اگر باشه، یعنی میشه به همه ی خونه ها رفت.
 

rezaezio

کاربر فوق‌حرفه‌ای
ارسال‌ها
1,167
امتیاز
1,956
نام مرکز سمپاد
حلّیِ 2
شهر
تهران
مدال المپیاد
برنز و طلای کامپیوتر !
دانشگاه
شریف
رشته دانشگاه
نرم افزار
پاسخ : سوال اول مسابقه کامپیوتری ها: حرکات اسب در صفحه ش

ببین آقا الان یه گراف ساختیم، که راس هاش خونه های صفحه شطرنج هستن و دو راس به هم یال دارن اگر و فقط اگر با یه حرکت اسب بتونیم بین خانه های این دو راس حرکت کرد !

حالا توی این گراف دنبال چی هستیم ؟ مگه دنبال مسیر همیلتونی نمیگردیم ؟ آیا میشه تو یه گراف ساده مسیر همیلتونی در زمان چند جمله‌ای پیدا کرد ؟
 

Anita H

کاربر فوق‌حرفه‌ای
ارسال‌ها
571
امتیاز
2,987
نام مرکز سمپاد
حلّی ۲
شهر
تهران
سال فارغ التحصیلی
1396
مدال المپیاد
کامپیوتری بودم
دانشگاه
شریف
رشته دانشگاه
کامپیوتر
پاسخ : سوال اول مسابقه کامپیوتری ها: حرکات اسب در صفحه ش

به نقل از Damon :
ببین آقا الان یه گراف ساختیم، که راس هاش خونه های صفحه شطرنج هستن و دو راس به هم یال دارن اگر و فقط اگر با یه حرکت اسب بتونیم بین خانه های این دو راس حرکت کرد !

حالا توی این گراف دنبال چی هستیم ؟ مگه دنبال مسیر همیلتونی نمیگردیم ؟ آیا میشه تو یه گراف ساده مسیر همیلتونی در زمان چند جمله‌ای پیدا کرد ؟
آره!
نه ممکن نیست

پ.ن: خب اول نوشته بودی دنبال دور همیلتونی بگردیم :-"
 
  • شروع کننده موضوع
  • #14

daneshvar.amrollahi

کاربر حرفه‌ای
ارسال‌ها
327
امتیاز
130
نام مرکز سمپاد
راهنمایی حلی۲/دبیرستان حلی۱۰/دبیرستان علامه طباطبایی
شهر
تهران
سال فارغ التحصیلی
1397
مدال المپیاد
کامپیوتر
پاسخ : سوال اول مسابقه کامپیوتری ها: حرکات اسب در صفحه ش

میدونم مسابقه به اتمام نرسید و این تنها سوالش بود!

مهلتش که تموم شده!

بیاید اینم کدش! :D

http://paste.ubuntu.com/8096669/
 

Anita H

کاربر فوق‌حرفه‌ای
ارسال‌ها
571
امتیاز
2,987
نام مرکز سمپاد
حلّی ۲
شهر
تهران
سال فارغ التحصیلی
1396
مدال المپیاد
کامپیوتری بودم
دانشگاه
شریف
رشته دانشگاه
کامپیوتر
پاسخ : سوال اول مسابقه کامپیوتری ها: حرکات اسب در صفحه ش

به نقل از daneshvar.a :
میدونم مسابقه به اتمام نرسید و این تنها سوالش بود!

مهلتش که تموم شده!

بیاید اینم کدش! :D

http://paste.ubuntu.com/8096669/

الآن این فقط دنبال مسیر همیلتونی ای نمیگرده که از خونه ی (۰و۰) شروع شده باشه؟
 
  • شروع کننده موضوع
  • #16

daneshvar.amrollahi

کاربر حرفه‌ای
ارسال‌ها
327
امتیاز
130
نام مرکز سمپاد
راهنمایی حلی۲/دبیرستان حلی۱۰/دبیرستان علامه طباطبایی
شهر
تهران
سال فارغ التحصیلی
1397
مدال المپیاد
کامپیوتر
پاسخ : سوال اول مسابقه کامپیوتری ها: حرکات اسب در صفحه ش

به نقل از amoo.majid :

الآن این فقط دنبال مسیر همیلتونی ای نمیگرده که از خونه ی (۰و۰) شروع شده باشه؟

چرا فکر کنم. میگید پیداکردن مسیر هملیتونی الگوریتم دیگه ای داره؟
من با این dfs نوشتم! اگر ایرادی داره بگید! :D

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