آسان داک ASANDOC.sellfile.ir

فروشگاه جامع کتوب , تحقیقات , مقالات , پروژه های دانشجویی ,app موبایل

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

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

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

برای افرادی که با بازی شطرنج آشنایی ندارن:

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

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

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

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

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

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

کدی که به زبان ++C درباره این مساله نوشته شده با استفاده از روش سوم تعداد جوابهای ممکن – و نه خود جوابها – برای مقادیر مختلف n رو مشخص می کنه. به عنوان مثال اگر n رو 8 وارد کنید خروجی برنامه 92 خواهد بود. توصیه می کنم برای nهای بزرگ برنامه رو امتحان نکنید! اگر n رو 16 وارد کنید بعد از گذشتن زمان زیادی عدد 14772512 روی صفحه نمایش چاپ می شه. یعنی در صفحه شطرنج 16 در 16 حدود ۱۵ میلیون حالت مختلف برای چیدمان صحیح وجود داره!!


اشتراک بگذارید:


پرداخت اینترنتی - دانلود سریع - اطمینان از خرید

پرداخت هزینه و دریافت فایل

مبلغ قابل پرداخت 2,000 تومان
عملیات پرداخت با همکاری بانک انجام می شود
کدتخفیف:

درصورتیکه برای خرید اینترنتی نیاز به راهنمایی دارید اینجا کلیک کنید


فایل هایی که پس از پرداخت می توانید دانلود کنید

نام فایلحجم فایل
8vazir_1757800_5608.zip333.6k





دانلود پروژه ماشین حساب مهندسی با زبان ویژوال بیسیک

دانلود پروژه ماشین حساب مهندسی با زبان ویژوال بیسیک عنوان پروژه  :  ماشین حساب مهندسی با زبان ویژوال بیسیک قالب بندی :  VB6 شرح مختصر : پروژه ماشین حساب یکی از برنامه هایی است که زیاد در گوشی های موبایل زیاد مورد استفاده قرار می گیرد ولی معمولا ماشین حساب های پیش فرض ، امکانات لازم برای انجام امور مهندسی و محاسبات پیچیده را ندارند به همین علت برخی کاربران به یک ماشین حساب جداگانه نیاز پیدا می کنند.  این پروژه یک ماشین حساب زیبا ...

توضیحات بیشتر - دانلود 2,000 تومان

دانلود پروژه طراحی سایت نوبت دهی آنلاین پزشکی‎

دانلود پروژه طراحی سایت نوبت دهی آنلاین پزشکی‎ عنوان پایان نامه :  طراحی سایت نوبت دهی آنلاین پزشکی‎  قالب بندی :  PDF شرح مختصر :  از آنجایی که ترافیک شهرها و همچنین جابجایی بیماران به شهرهای بزرگ برای معالجه امری وقت گیر و مشکل  می باشد ، سیستم نوبت دهی آنلاین پزشکان می تواند جهت سهولت و تسریع در کارها استفاده شود و به بیماران اجازه دهد در هر جایی از کشور و برای هر پزشکی که بخواهند بتوانند نوبت رزرو نمایند و در ز ...

توضیحات بیشتر - دانلود 2,000 تومان

دانلود پروژه طراحي سايت اتحاديه مدارس به زبان ASP.NET‎

دانلود پروژه طراحي سايت اتحاديه مدارس به زبان ASP.NET‎ قالب بندی :  ASPX, C#, PDF شرح مختصر :  این پروزه می تواند بصورت یک اتحادیه از مدرسه ها در تمامی سطوح  استفاده شود.در پروزه امکان اضافه کردن نام مدرسه با تمام خصوصیات اش توسط مدیر سایت وجود دارد .مدرسه ها می توانند دراین سایت نام معلم هایشان ، کلاسهایشان و دروس مربوط به هر سطوح را وارد کنند. در سایت  دانش آموز می تواند با انجام یک جستجو به هر نحوی که دوست دارد مدرسه ی مورد نظرا ...

توضیحات بیشتر - دانلود 2,500 تومان

دانلود پروژه برنامه نویسی و طراحی یک فروشگاه اینترنتی با زبان PHP (آماده ارائه)

دانلود پروژه برنامه نویسی و طراحی یک فروشگاه اینترنتی با زبان PHP (آماده ارائه) قالب بندی :  PHP شرح مختصر :  در پروژه حاضر یک فروشگاه اینترنتی با امکانات کامل در اختیار شما قرار گرفته است که با زبان برنامه نویسی PHP و بانک اطلاعاتی MySQL نوشته شده است. قابلیت های این پروژه عبارتند از : پنل مدیریت، سورس ساده و روان، دسته بندی محصولات، استفاده از سبد خرید، قابلیت توسعه، طراحی زیبا و کاربر پسند و … جهت استفاده ابتدا یک دیتا بیس ایجاد و سپس فایل shop_sc.sql را د ...

توضیحات بیشتر - دانلود 2,500 تومان

دانلود پروژه مهندسی نرم افزار سیستم داروخانه

دانلود پروژه مهندسی نرم افزار سیستم داروخانه عنوان مقاله : سیستم داروخانه  – UML قالب بندی : word 2003 ، PDF ، power point، rational rose شرح مختصر : معرفی سیستم:  سیستم داروخانه صورت مسئله : یک سیستم دریافت نسخه و تحویل دارو هدف :  کنترل و مدیریت مراجعه کنندگان ، دارو و امور مالی نیازهای عملیاتی : ۱-  سخت افزار : به طور همزمان چندین کاربر بتوانند از آن استفاده نمایند. سیستم باید قابلیت تغییرات مکانی را داشته باشد ...

توضیحات بیشتر - دانلود 3,000 تومان

الگوریتم ژنتیک در متلب

الگوریتم ژنتیک در متلب بی شک با بحث هوش مصنوعی و الگوریتم های تکاملی و بحث های وابسته به آن آشنا هستید. در این پست 2 فایل آموزشی الگوریتم ژنتیک را برای شما عزیزان بر روی وبسایت مهندس قرار داده ایم. از الگوریتم ژنتیک در حل بسیاری از مسائل استفاده می شود و از جمله الگوریتم های پرکاربرد به شمار می آید. برخی از عناوین این فایلهای آموزشی: مقدمه تاریخچه مروری بر مفاهیم بنیادی – مفاهیم پایه — علم ژنتیک — صفت ...

توضیحات بیشتر - دانلود 2,000 تومان