شما وارد حساب خود نشده و یا ثبت نام نکرده اید. لطفا وارد شوید یا ثبت نام کنید تا بتوانید از تمامی امکانات انجمن استفاده کنید.


تبليغات
سامانه ي پيامکي آز پي ان يو مقالات ISI
فروشگاه اينترنتي آز پي ان يو خريد شارژ آز پي ان يو

الگوریتم و سورس کد مسئله هشت وزیر ( ۸ وزیر )زمان کنونی: ۱۶-۹-۱۳۹۵، ۱۱:۱۹ :عصر
کاربرانِ درحال بازدید از این موضوع: 1 مهمان
نویسنده: Administrator
آخرین ارسال: sitfa
پاسخ: 42
بازدید: 6170

ارسال پاسخ 
 
امتیاز موضوع:
  • 45 رأی - میانگین امتیازات: 3.82
  • 1
  • 2
  • 3
  • 4
  • 5

الگوریتم و سورس کد مسئله هشت وزیر ( ۸ وزیر )

۱-۹-۱۳۹۰, ۰۱:۵۳ :عصر (آخرین ویرایش در این ارسال: ۱۹-۷-۱۳۹۱ ۰۹:۴۴ :عصر، توسط Administrator.)
ارسال: #1
الگوریتم و سورس کد مسئله هشت وزیر ( ۸ وزیر )
مساله هشت وزیر از جمله مسائل پرمخاطب مباحث طراحی الگوریتم است. ۸ مهره وزیر رو روی صفحه شطرنج چنان بچینید که نتونن همدیگه رو تهدید کنن.

برای افرادی که با بازی شطرنج آشنایی ندارن:
مهمان ها نمي توانند تصاوير را ببينند و دیدن لینک ها برای شما امکان پذیر نیست. لطفا ثبت نام کنید یا وارد حساب خود شوید تا بتوانید لینک ها را ببینید.


وزیر مهره ای از مهره های بازی شطرنجه که می تونه در تمامی ۸ جهت هر تعداد خانه – تا زمانی که مهره ای مانع نباشه – حرکت کنه و اگه در یکی از این خانه ها مهره حریف قرار داشته باشه تهدیدش کنه.

مساله هشت وزیر : ما مساله رو در حالت کلی در نظر می گیریم. یعنی زمانی که ابعاد صفحه شطرنج n در n و تعداد مهره ها n هستش. ( n > 3 ) روشهای مختلفی برای پیدا کردن جواب وجود داره. یکی از این روشها چیدن تصادفی مهره ها روی صفحه شطرنجه! به عبارت دیگه n مهره رو به صورت تصادفی در خانه های مختلف صفحه قرار می دیم و بررسی می کنیم که آیا شرط مساله رو برآورده می کنن یا نه؟ این روش بسیار سریع ما رو به جواب می رسونه. اما ایرادی که داره نمی شه مطمئن بود بشه به همه حالتهای چینش دست پیدا کرد. در صفحه ۸ در ۸ شطرنج این مساله ۹۲ جواب مختلف داره. شما ممکنه روش تصادفی رو هزار بار به کار ببرید، اما نتونید همه ۹۲ حالت ممکنه رو به دست بیارید. این روش زمانی مفیده که پیدا کردن یه جواب برای ما کافی باشه.

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

برای پیاده سازی چنین الگوریتمی و تشخیص اینکه چه خانه هایی از سطر امن هستن روشهای مختلفی وجود داره. ساده ترینشون اینه که هر بار تمامی خانه هایی رو که امکان تهدید شدن از اونها وجود داره بررسی کنیم تا از قرار نداشتن مهره وزیر در اونها مطمئن باشیم. اما این روش اصلا کارا و بهینه نیست.

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

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

کدی که به زبان ++C درباره این مساله نوشته شده با استفاده از روش سوم تعداد جوابهای ممکن – و نه خود جوابها – برای مقادیر مختلف n رو مشخص می کنه. به عنوان مثال اگر n رو ۸ وارد کنید خروجی برنامه ۹۲ خواهد بود. توصیه می کنم برای nهای بزرگ برنامه رو امتحان نکنید! اگر n رو ۱۶ وارد کنید بعد از گذشتن زمان زیادی عدد ۱۴۷۷۲۵۱۲ روی صفحه نمایش چاپ می شه. یعنی در صفحه شطرنج ۱۶ در ۱۶ حدود ۱۵ میلیون حالت مختلف برای چیدمان صحیح وجود داره!!

در ادامه میتونید الگوریتم، تحلیل و سورس کد این مسئله را ( با زبان های مختلف ) را دانلود کنید

فایل‌(های) پیوست شده
نام فایل : 8 وزیر
دفعات دانلود : 64
حجم فایل : 503 bytes
ارسال کننده فایل : Administrator
نوع فایل : .


فایل‌(های) پیوست شده
نام فایل : 8 وزیر
دفعات دانلود : 51
حجم فایل : 200 bytes
ارسال کننده فایل : Administrator
نوع فایل : .
مردم شهری که همه در آن می لنگند
به کسی که راست می رود میخندند !
مشاهده‌ی وب‌سایت کاربر یافتن تمامی ارسال‌های این کاربر
نقل قول این ارسال در یک پاسخ
 سپاس شده توسط STAR ، nasrin67 ، maryam_esmaili
۱-۹-۱۳۹۰, ۰۲:۰۸ :عصر (آخرین ویرایش در این ارسال: ۱-۹-۱۳۹۰ ۰۲:۳۸ :عصر، توسط STAR.)
ارسال: #2
RE: الگوریتم و سورس کد مسئله هشت وزیر ( ۸ وزیر )
8 پازل رو هم میشه بذارید؟ با الگوریتم A*
--
ترجیحا به نسرین 67 هم ندینمهمان ها نمي توانند تصاوير را ببينند و دیدن لینک ها برای شما امکان پذیر نیست. لطفا ثبت نام کنید یا وارد حساب خود شوید تا بتوانید لینک ها را ببینید.
خیلی دلتنگت شده ام،اما نمیدانم خیلی را چگونه بنویسم که "خیلی" خوانده شود...
یافتن تمامی ارسال‌های این کاربر
نقل قول این ارسال در یک پاسخ
 سپاس شده توسط nasrin67
۱-۹-۱۳۹۰, ۰۲:۴۲ :عصر
ارسال: #3
RE: الگوریتم و سورس کد مسئله هشت وزیر ( ۸ وزیر )
دروغ میگه بزارینش هر کی زودتر دانلود کرد مال اونهمهمان ها نمي توانند تصاوير را ببينند و دیدن لینک ها برای شما امکان پذیر نیست. لطفا ثبت نام کنید یا وارد حساب خود شوید تا بتوانید لینک ها را ببینید.

لطفا شب هم بزارین که کاربر فارسان نباشه آخه شبا کمتر میادمهمان ها نمي توانند تصاوير را ببينند و دیدن لینک ها برای شما امکان پذیر نیست. لطفا ثبت نام کنید یا وارد حساب خود شوید تا بتوانید لینک ها را ببینید.
پروردگارا تو تکراری ترین “حضور” روزگار منی و من عجیب به آغوش تو از آن سوی فاصله ها خو گرفته ام !
مشاهده‌ی وب‌سایت کاربر یافتن تمامی ارسال‌های این کاربر
نقل قول این ارسال در یک پاسخ
 سپاس شده توسط STAR
۱-۹-۱۳۹۰, ۰۲:۴۶ :عصر
ارسال: #4
RE: الگوریتم و سورس کد مسئله هشت وزیر ( ۸ وزیر )
حالا کی بذارمش مهمان ها نمي توانند تصاوير را ببينند و دیدن لینک ها برای شما امکان پذیر نیست. لطفا ثبت نام کنید یا وارد حساب خود شوید تا بتوانید لینک ها را ببینید.
مردم شهری که همه در آن می لنگند
به کسی که راست می رود میخندند !
مشاهده‌ی وب‌سایت کاربر یافتن تمامی ارسال‌های این کاربر
نقل قول این ارسال در یک پاسخ
 سپاس شده توسط nasrin67
۱-۹-۱۳۹۰, ۰۲:۴۷ :عصر
ارسال: #5
RE: الگوریتم و سورس کد مسئله هشت وزیر ( ۸ وزیر )
(۱-۹-۱۳۹۰ ۰۲:۴۲ :عصر)nasrin67 نوشته شده توسط: دیدن لینک ها برای شما امکان پذیر نیست. لطفا ثبت نام کنید یا وارد حساب خود شوید تا بتوانید لینک ها را ببینید.
دروغ میگه بزارینش هر کی زودتر دانلود کرد مال اونهمهمان ها نمي توانند تصاوير را ببينند و دیدن لینک ها برای شما امکان پذیر نیست. لطفا ثبت نام کنید یا وارد حساب خود شوید تا بتوانید لینک ها را ببینید.

لطفا شب هم بزارین که کاربر فارسان نباشه آخه شبا کمتر میادمهمان ها نمي توانند تصاوير را ببينند و دیدن لینک ها برای شما امکان پذیر نیست. لطفا ثبت نام کنید یا وارد حساب خود شوید تا بتوانید لینک ها را ببینید.
رو رو برم!!!! مهمان ها نمي توانند تصاوير را ببينند و دیدن لینک ها برای شما امکان پذیر نیست. لطفا ثبت نام کنید یا وارد حساب خود شوید تا بتوانید لینک ها را ببینید.

دیگه هیچ درخواستی نداری؟ تعارف نکنیا... راحت باش عزیزم! مهمان ها نمي توانند تصاوير را ببينند و دیدن لینک ها برای شما امکان پذیر نیست. لطفا ثبت نام کنید یا وارد حساب خود شوید تا بتوانید لینک ها را ببینید.
خیلی دلتنگت شده ام،اما نمیدانم خیلی را چگونه بنویسم که "خیلی" خوانده شود...
یافتن تمامی ارسال‌های این کاربر
نقل قول این ارسال در یک پاسخ
 سپاس شده توسط nasrin67
۱-۹-۱۳۹۰, ۰۲:۴۷ :عصر
ارسال: #6
RE: الگوریتم و سورس کد مسئله هشت وزیر ( ۸ وزیر )
بزارینش بلاخره با هم به توافق میرسیم یعنی برا من باشهمهمان ها نمي توانند تصاوير را ببينند و دیدن لینک ها برای شما امکان پذیر نیست. لطفا ثبت نام کنید یا وارد حساب خود شوید تا بتوانید لینک ها را ببینید.
پروردگارا تو تکراری ترین “حضور” روزگار منی و من عجیب به آغوش تو از آن سوی فاصله ها خو گرفته ام !
مشاهده‌ی وب‌سایت کاربر یافتن تمامی ارسال‌های این کاربر
نقل قول این ارسال در یک پاسخ
۱-۹-۱۳۹۰, ۰۲:۴۸ :عصر
ارسال: #7
RE: الگوریتم و سورس کد مسئله هشت وزیر ( ۸ وزیر )
مهمان ها نمي توانند تصاوير را ببينند و دیدن لینک ها برای شما امکان پذیر نیست. لطفا ثبت نام کنید یا وارد حساب خود شوید تا بتوانید لینک ها را ببینید.



فایل‌(های) پیوست شده
نام فایل : 8 Puzzle Download
دفعات دانلود : 45
حجم فایل : 356.4 KB
ارسال کننده فایل : Administrator
نوع فایل : .
مردم شهری که همه در آن می لنگند
به کسی که راست می رود میخندند !
مشاهده‌ی وب‌سایت کاربر یافتن تمامی ارسال‌های این کاربر
نقل قول این ارسال در یک پاسخ
 سپاس شده توسط STAR ، nasrin67
۱-۹-۱۳۹۰, ۰۲:۴۸ :عصر
ارسال: #8
RE: الگوریتم و سورس کد مسئله هشت وزیر ( ۸ وزیر )
تا شما بذاریدش من به مهندس قاسمی بگم بچه ها دارن دانلودش می کنن.
من: سلام حاله شما خوبه مهندس؟!
مهندس: سلام، تشکر شما چطورید؟!
.....
گيرم كه در باورتان به خاك نشستم
و ساقه‌هاي جوانم از ضربه‌هاي تبرهاتان زخم دار است
مشاهده‌ی وب‌سایت کاربر یافتن تمامی ارسال‌های این کاربر
نقل قول این ارسال در یک پاسخ
 سپاس شده توسط STAR ، nasrin67 ، MostafA
۱-۹-۱۳۹۰, ۰۲:۴۸ :عصر
ارسال: #9
RE: الگوریتم و سورس کد مسئله هشت وزیر ( ۸ وزیر )
(۱-۹-۱۳۹۰ ۰۲:۴۶ :عصر)Administrator نوشته شده توسط: دیدن لینک ها برای شما امکان پذیر نیست. لطفا ثبت نام کنید یا وارد حساب خود شوید تا بتوانید لینک ها را ببینید.
حالا کی بذارمش مهمان ها نمي توانند تصاوير را ببينند و دیدن لینک ها برای شما امکان پذیر نیست. لطفا ثبت نام کنید یا وارد حساب خود شوید تا بتوانید لینک ها را ببینید.
لطفا همین حالا بذارید.
نسرین دم در باهات کار دارن، برو ببین کیهمهمان ها نمي توانند تصاوير را ببينند و دیدن لینک ها برای شما امکان پذیر نیست. لطفا ثبت نام کنید یا وارد حساب خود شوید تا بتوانید لینک ها را ببینید.
خیلی دلتنگت شده ام،اما نمیدانم خیلی را چگونه بنویسم که "خیلی" خوانده شود...
یافتن تمامی ارسال‌های این کاربر
نقل قول این ارسال در یک پاسخ
۱-۹-۱۳۹۰, ۰۲:۵۱ :عصر
ارسال: #10
RE: الگوریتم و سورس کد مسئله هشت وزیر ( ۸ وزیر )
(۱-۹-۱۳۹۰ ۰۲:۴۸ :عصر)farsan نوشته شده توسط: دیدن لینک ها برای شما امکان پذیر نیست. لطفا ثبت نام کنید یا وارد حساب خود شوید تا بتوانید لینک ها را ببینید.
(۱-۹-۱۳۹۰ ۰۲:۴۶ :عصر)Administrator نوشته شده توسط: دیدن لینک ها برای شما امکان پذیر نیست. لطفا ثبت نام کنید یا وارد حساب خود شوید تا بتوانید لینک ها را ببینید.
حالا کی بذارمش مهمان ها نمي توانند تصاوير را ببينند و دیدن لینک ها برای شما امکان پذیر نیست. لطفا ثبت نام کنید یا وارد حساب خود شوید تا بتوانید لینک ها را ببینید.
لطفا همین حالا بذارید.
نسرین دم در باهات کار دارن، برو ببین کیهمهمان ها نمي توانند تصاوير را ببينند و دیدن لینک ها برای شما امکان پذیر نیست. لطفا ثبت نام کنید یا وارد حساب خود شوید تا بتوانید لینک ها را ببینید.
کسی با من کار ندارهمهمان ها نمي توانند تصاوير را ببينند و دیدن لینک ها برای شما امکان پذیر نیست. لطفا ثبت نام کنید یا وارد حساب خود شوید تا بتوانید لینک ها را ببینید.

من دانلودش کردممهمان ها نمي توانند تصاوير را ببينند و دیدن لینک ها برای شما امکان پذیر نیست. لطفا ثبت نام کنید یا وارد حساب خود شوید تا بتوانید لینک ها را ببینید.
پروردگارا تو تکراری ترین “حضور” روزگار منی و من عجیب به آغوش تو از آن سوی فاصله ها خو گرفته ام !
مشاهده‌ی وب‌سایت کاربر یافتن تمامی ارسال‌های این کاربر
نقل قول این ارسال در یک پاسخ
ارسال پاسخ 


کسانی که از این موضوع بازدید کرده اند . . . ( آز پی ان یو )
12 کاربر زیر موضوع را خوانده اند:
Administrator (۲۰-۱۰-۱۳۹۴, ۰۱:۱۸ :عصر)، Masoud Ebrahimi (۱۴-۱۰-۱۳۹۲, ۰۹:۵۷ :عصر)، mahdi hashemi (۲۸-۷-۱۳۹۲, ۰۴:۳۱ :عصر)، rascal1364 (۲۱-۸-۱۳۹۲, ۰۳:۱۶ :عصر)، arash4644 (۲۲-۱۱-۱۳۹۲, ۱۰:۲۱ :صبح)، NegarRiazi (۳۰-۷-۱۳۹۳, ۰۶:۳۰ :صبح)، tabatabaei (۳-۹-۱۳۹۳, ۰۳:۴۷ :عصر)، y.darooghe@gmail.com (۹-۱۱-۱۳۹۳, ۰۸:۵۳ :عصر)، afkari (۲-۲-۱۳۹۴, ۱۲:۰۱ :عصر)، Nabegh (۵-۳-۱۳۹۴, ۰۷:۵۷ :صبح)، shary (۱۹-۳-۱۳۹۴, ۰۱:۱۶ :عصر)، sitfa (۱۹-۱۰-۱۳۹۴, ۰۱:۰۳ :عصر)

پرش به انجمن:


کاربرانِ درحال بازدید از این موضوع: 1 مهمان


آپلودسنتر آز پي ان يو تالار گفتمان آز پي ان يو
تبلیغات نیازمندی های استان چهارمحال و بختیاری