پاورپوینت آشنایی با الگوریتم های زمان بندی

اختصاصی از کوشا فایل پاورپوینت آشنایی با الگوریتم های زمان بندی دانلود با لینک مستقیم و پرسرعت .

این پاورپوینت شامل 49 اسلاید از مبحث آشنایی با الگوریتم های زمانبندی می باشد. این محصول هم اکنون با پرداخت تنها 2500 تومان قابل دانلود خواهد بود.

روشی جدید برای الگوریتم زمانبندی CPU با گردش بنوبت ژنتیکی

اختصاصی از کوشا فایل روشی جدید برای الگوریتم زمانبندی CPU با گردش بنوبت ژنتیکی دانلود با لینک مستقیم و پرسرعت .

روشی جدید برای الگوریتم زمانبندی CPU با گردش بنوبت ژنتیکی

45 صفحه در قالب word

به همراه 45 اسلاید آماده ارائه در قالب پاورپوینت

فهرست مطالب

مقدمه ..................................1

فصل اول

چکیده..................................................................2

تاریخچه الگوریتم ژنتیک.....................................3

اهداف ......................................................3

ساختار الگوریتم‏های ژنتیکی................................4

عملگرهای الگوریتم  ژنتیک...............5

روند کلی الگوریتم‏های ژنتیکی............................9

روند کلی بهینه سازی و حل مسائل در الگوریتم ژنتیک :.....................11

شرط پایان الگوریتم..........................................12

    فصل دوم

توضیح الگوریتم ژنتیک  در 12 قدم.......................18

قدم اول :  بدست آوردن تابع هدف (Cost Function) با n متغیر…………...18

قدم دوم : تعیین طول کروموزوم. ................20

قدم سوم : تولید جمعیت اولیه. .......................21

قدم چهارم: تبدیل هر ژن  از کروموزوم به اعدادی در بازه دامنه همان متغیر...............23

قدم پنجم :........................................25

قدم ششم : :.................................................26

قدم هفتم : تعیین تعداد کروموزوم شرکت کننده در عمل پیوند .:.........27

قدم هشتم : انتخاب کروموزومهایی که در عمل پیوند شرکت می کنند .................27

قدم نهم :  پیوند (crossover) . ..........................31

قدم دهم : جهش (mutation)   .................................36

قدم یازدهم : حفظ بهترین کروموزوم 36………………..

قدم دوازدهم : 37………………

فصل سوم

روش پژوهش....................................40

نتایج و بحث:.......................................41

نتیجه گیری و کارهای آینده..............................................50

نتیجه گیری‌ کلی.................................................51

قدر دانی................................................51

منابع.................................................43

مقدمه

یک موضوع جالب در سیستم عامل, زمانبندی CPU است.این زمانبندی به تخصیص CPU مربوط است که فراینده ها را در سیستمی کامپیوتری اجرا میکند.زمانبندی CPU وظیفه ی اصلی سیستم عامل است[1].زمانبندی باید بدرستی برای نگه داشتن بیطرفی و جلوگیری از فرایندهایی که هرگز CPU را تخصیص نمیدهد انجام شود(فرایند گرسنگی).زمانبندی CPU ضروری است , بخصوص در سیستم شبکه ی کامپیوتری که از گروهی از ایستگاههای کاری و سرویس دهندهها تشکیل میشود.سپس,در این سیستم عامل جدید ,کامپیوتر چند وظیفه ای ,یک هدف است و این به الگوریتم برای زمانبندی CPU متکی است.بهمین دلیل CPU بخش موثر یا مهم یک کامپیوتر است.[1].علاوه بر این ,در این عصر به کمک VLSL (در مقیاس بسیار بزرگ مدار مجتمع)ممکن است پردازنده هایی با قدرت بالا تولید کنند.این قدرت شگفت انگیز بایداستفاده شود تا بی فایده نباشد.همزمان با قدرت محاسبه ی پردازنده, در برنامه های کاربردی افزایش وجود دارد که آن قدرت را استفاده میکند. یک معیار که باید بوسیله ی برنامه انجام شود ,به حداقل رساندن میانگین زمان انتظار برای همه ی فرایندها در بدست آوردن تخصیص CPU است.الگوریتمهای مختلفی برای زمانبندی CPU وجود دارد:یکی از آنها گردش بنوبت(RR) است.مفهوم اساسی در RR استفاده از اشتراک گذاری زمان است[3].هر فرایند همان زمان CPU را بدست می آورد یعنی زمان کوانتومی, که بعنوان محدودیت در زمان پردازش ,بطور کلی در محدوده ی 1-100 میلی ثانیه عمل میکند.بعد از اینکه زمان کوانتومی برای فرایندی بپایان رسید,فرایند از اجرای آن متوقف میشود و در صف آماده گذارده میشوند.سپس ,فرایند بعدی انتخاب میشودتا اجرا شود.این مراحل چندین بار اجرا خواهند شد تا زمانیکه همه ی فرایندها بطور کامل بوسیله ی CPU بکار روند.اگر چه محدوده ی مقدار برای زمان کوانتومی وجود دارد,هنوز هیچ استانداردی وجود ندارد. ضمنا اگر زمان کوانتومی بسیار زیاد باشد,زمان مورد نیاز برای پاسخ / انتظار (چقدر زمان مورد نیاز است که آن بکار گرفته شود) کاملا زیاد است.علاوه براین, اگر خیلی کم باشد برای CPU مخارج کلی بوجود می آورد.جستجو برای بهترین زمان کوانتومی هدف دارد که به حداقل رساندن میانگین زمان انتظار برای گروهی از فرایندهاست.امیدواریم که هر فرایند بتواند کارش را در زمان معقول انجام دهد.تسریع کننده  یک فرایند اثرات کارش را در بسیاری از فرایندها بپایان میرساند که میتواند بوسیله ی CPU بکار گرفته شود.این کار به توان عملیاتی بهتری از CPU میرسد برای اینکه همیشه مشغول است و هرگز غیرفعال نیست.براساس مقدمه ی بالا فکر میکنیم برای پیدا کردن بهترین کوانتوم برای بدست آوردن میانگین بهتری از زمان انتظار,مدت زمان صرف شده و حداقل تعویض بستر لازم است.الگوریتم ژنتیکی را پیشنهاد میکنیم که با گردش بنوبت سنتی ترکیب میشود.

به زبان ساده تر

   محدوده کاری الگوریتم ژنتیک  بسیار وسیع می باشد و هر روز با پیشرفت روزافزون علوم و تکنولوژی استفاده از این روش در بهینه سازی و حل مسائل بسیار گسترش یافته است. الگوریتم ژنتیک   یکی از زیر مجموعه های محاسبات تکامل یافته می باشد که رابطه مستقیمی با مبحث هوش مصنوعی دارد در واقع الگوریتم ژنتیک  یکی از زیر مجموعه های هوش مصنوعی می باشد.  الگوریتم ژنتیک را می­توان یک روش جستجوی کلی نامید که از قوانین تکامل بیولوژیک طبیعی تقلید می­کند .الگوریتم ژنتیک برروی یکسری از جواب­های مساله به امید بدست آوردن جوابهای بهتر قانون بقای بهترین را اعمال می کند. درهر نسل به کمک فرآیند انتخابی متناسب با ارزش جواب­ها و تولید مثل جواب-های انتخاب شده به کمک عملگرهایی که از ژنتیک طبیعی تقلید شده­اند ,تقریب­های بهتری از جواب نهایی بدست می­آید. این فرایند باعث می­شود که نسلهای جدید با شرایط مساله سازگارتر باشد.

تاریخچه

   حساب تکاملی ,برای اولین بار در سال 1960 توسط آقای ریچنبرگ ارائه شد که تحقیق وی در مورد استراتژی تکامل بود.بعدها نظریه او توسط محققان زیادی مورد بررسی قرار گرفت تا اینکه الگوریتم ژنتیک  (GA  ) توسط جان هولند(John Holland ) و در سال 1975 در دانشگاه میشیگان ,ارائه شد.

در سال 1992 نیز جان کوزا (John Koza ) از الگوریتم ژنتیک  (GA  ) برای حل و بهینه سازی مسائل مهندسی پیشرفته استفاده کرد و توانست برای اولین بار روند الگوریتم ژنتیک  (GA  )  را به زبان کامپیوتر در آورد و برای آن یک زبان برنامه نویسی ابداع کندکه به این روش برنامه نویسی ,برنامه نویسی ژنتیک (GP ) گویندو نرم افزاری که توسط وی ابداع گردید به نرم افزار LISP مشهور است که هم اکنون نیز این نرم افزار کاربرد زیادی در حل و بهینه سازی مسائل مهندسی پیدا کرده است .

اهداف

تحقیقاتمان اهدافی بشرح زیر دارد:

1. طراحی و پیاده سازی سیستم که میتواند بهترین کوانتوم را برای رسیدن به میانگین بهینه ی زمان انتظار تولید کند.
2. بمنظور بررسی پارامترهای GA که میتواند بهترین راه حل را ارائه کند.
3. تحقیقات قبلی

ساختار الگوریتم‏های ژنتیکی

به طور کلی, الگوریتم‏های ژنتیکی از اجزاء زیر تشکیل می‏شوند:

 کروموزوم[1]

در الگوریتم‏های ژنتیکی, هر کروموزوم نشان دهنده یک نقطه در فضای جستجو و یک راه‏حل ممکن برای مسئله مورد نظر است. خود کروموزوم‏ها (راه حل‏ها) از تعداد ثابتی ژن[2] (متغیر) تشکیل می‏شوند. برای نمایش کروموزوم‏ها, معمولاً از کدگذاری‏های دودویی (رشته‏های بیتی) استفاده می‏شود.

جمعیت[3]

مجموعه‏ای از کروموزوم‏ها یک جمعیت را تشکیل می‏دهند. با تاثیر عملگرهای ژنتیکی  بر روی هر جمعیت, جمعیت جدیدی با همان تعداد کروموزوم تشکیل می‏شود.

تابع برازندگی[4]

به منظور حل هر مسئله با استفاده از الگوریتم‏های ژنتیکی, ابتدا باید یک تابع برازندگی برای آن مسئله ابداع شود. برای هر کروموزوم, این تابع عددی غیر منفی را برمی‏گرداند که نشان دهنده شایستگی یا توانایی فردی آن کروموزوم است.

عملگرهای الگوریتم  ژنتیک

در الگوریتم‏های ژنتیکی, در طی مرحله تولید مثل[5] ازعملگرهای ژنتیکی استفاده می‏شود. با تاثیر این عملگرها بر روی یک جمعیت, نسل[6] بعدی آن جمعیت تولید می‏شود. عملگرهای انتخاب[7] , آمیزش[8]  و جهش[9] معمولاً بیشترین کاربرد را در الگوریتم‏های ژنتیکی دارند.

عملگر انتخاب  (Selection ):

این عملگر از بین کروموزوم‏های موجود در یک جمعیت, تعدادی کروموزوم را برای  تولید مثل انتخاب می‏کند. کروموزوم‏های برازنده‏تر شانس بیشتری دارند تا برای تولید مثل انتخاب شوند.

روش های انتخاب :

• : Elitist Selection (انتخاب نخبگان)
  • مناسب‌ترین عضو هر اجتماع انتخاب می‌شود. با توجه به مقدار شایستگی که از تابع ارزیاب دریافت کرده است.
• نمونه‏برداری به روش چرخ رولت

در این روش, به هر فرد قطعه‏ای از یک چرخ رولت مدور اختصاص داده می‏شود. اندازه این قطعه متناسب با برازندگی آن فرد است. چرخ N بار چرخانده می‏شود که N تعداد افراد در جمعیت است. در هر چرخش, فرد زیر نشانگر چرخ انتخاب می‏شود و در مخزن والدین نسل بعد قرار می‏گیرد. این روش می‏تواند به صورت زیر پیاده‏سازی شود:

• نرخ انتظار کل افراد جمعیت را جمع کنید و حاصل آن را T بنامید.
• مراحل زیر را N بار تکرار کنید:

یک عدد تصادفی r بین 0 و T  انتخاب کنید.

در میان افراد جمعیت بگردید و نرخ‏های انتظار( مقدار شایستگی) آنها را با هم جمع کنید تا این که مجموع بزرگتر یا مساوی r شود. فردی که نرخ انتظارش باعث بیشتر شدن جمع از این حد می‏شود, به عنوان فرد برگزیده انتخاب می‏شود.

ممکن است هنگام انتقال از فایل ورد به داخل سایت بعضی متون به هم بریزد یا بعضی نمادها و اشکال درج نشود ولی در فایل دانلودی همه چیز مرتب و کامل است

متن کامل را می توانید در ادامه دانلود نمائید

چون فقط تکه هایی از متن برای نمونه در این صفحه درج شده است ولی در فایل دانلودی متن کامل همراه با تمام ضمائم (پیوست ها) با فرمت ورد word که قابل ویرایش و کپی کردن می باشند موجود است

دانلود پایان نامه کامل بررسی جامع الگوریتم های مسیریابی در شبکه های موردی (تعداد صفحات112 )

اختصاصی از کوشا فایل دانلود پایان نامه کامل بررسی جامع الگوریتم های مسیریابی در شبکه های موردی (تعداد صفحات112 ) دانلود با لینک مستقیم و پرسرعت .

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

فهرست :

چکیده

مقدمه

فصل اول : کلیات

هدف

پیشینه کار و تحقیق

روش کار و تحقیق

فصل دوم : معرفی شبکه های موردی

شبکه موردی چیست

معرفی انواع شبکه های موردی

مزایای شبکه های موردی

کاربردهای شبکه های موردی

محدودیت های شبکه های موردی

خصوصیات شبکه های موردی

فصل سوم : مسیریابی شبکه های موردی

چگونگی مسیریابی در شبکه های موردی

انواع پروتکل های مسیریابی

پروتکل های پیشگیرانه proactive

پروتکلdsdv

پروتکلwrp

پروتکلcsgr

پروتکلstar

پروتکل های واکنش دار reaction

پروتکل ssr

پروتکل dsr

پروتکل tora

پروتکل aodv

پروتکل rdmar

پروتکل های پیوندیHybrid

پروتکل zrp

پروتکل zhls

پروتکل های موقعیتیLocation

پروتکل dream

پروتکل lar

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

سلسله مراتبی

الگوریتم مسیریابی مبتنی بر مورچه متحرکmabr

الگوریتم Sdr اتخاذ شده

الگوریتم hopent

مسطح

الگوریتم مسیریابی مبتنی بر لانه مورچه

الگوریتم موریانه

الگوریتم مسیریابی اورژانس احتمالاتیpera.

الگوریتم مسیریابی فوری ویژهeara

الگوریتم مورچه aodv

مسیریابی شبکه های حسگر

روش های مسیریابی شبکه های حسگر

مسیریابی مسطح

روش سیل آسا

روش شایعه پراکنی

روش اسپینspin

روش انتشار هدایت کننده

مسیریابی سلسله مراتبی

پروتکل LEACH

پروتکل SEP

پروتکل PEGASIS

پروتکل TEEN و APTEEN

پروتکل SOP

پروتکل Sensor Aggregates Routing

پروتکل VGA

پروتکل HPAR

پروتکل TTDD

مسیریابی مبتنی بر مکان

پروتکل GAF

پروتکل GEAR

فصل چهارم : امنیت شبکه های موردی

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

حملات مبتنی بر Modification

حملات مبتنی بر Impersonation

حمله سوراخ کرم

حمله هجوم

نیازمندی های امنیتی شبکه های موردی

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

پروتکل ARAN

پروتکل Ariadne

پروتکل saodv

پروتکل srp

پروتکل sead

پروتکل spaar

فصل پنجم : بحث و نتیجه گیری

نتیجه گیری

پیشنهادات

منابع و ماخذ

فهرست منابع فارسی

چکیده انگلیسی

دانلود مقاله الگوریتم EZW

اختصاصی از کوشا فایل دانلود مقاله الگوریتم EZW دانلود با لینک مستقیم و پرسرعت .

الگوریتم EZW در سال 1993 توسط shapiro ابداع شد نام کامل این واژه   به معنای کدینگ تدریجی با استفاده از درخت ضرایب ویولت است. این الگوریتم ضرایب ویولت را به عنوان مجموعه ای از درختهای جهت یابی مکانی در نظر می گیرد هر درخت شامل ضرایبی از تمام زیرباندهای فرکانسی و مکانی است که به یک ناحیه مشخص از تصویر اختصاص دارند. الگوریتم ابتدا ضرایب ویولت با دامنه بزرگتر را کددهی می کند در صورتیکه دامنه یک ضریب بزرگتر یا مساوی آستانه مشخص باشد ضریب به عنوان ضریب معنی دار   در نظر گرفته می شود و در غیر اینصورت بی معنی  می باشد یک درخت نیز در صورتی معنی دار است که بزرگترین ضریب آن از نظر دامنه بزرگتر یا مساوی با آستانه مورد نظر باشد و در غیراینصورت درخت بی معنی است.
مقدار آستانه در هر مرحله از الگوریتم نصف می شود و بدین ترتیب ضرایب بزرگتر زودتر فرستاده می شوند در هر مرحله، ابتدا معنی دار بودن ضرایب مربوط به زیر باند فرکانسی پایین تر ارزیابی می شود اگر مجموعه بی معنی باشد یک علامت درخت صفر استفاده می شود تا نشان دهد که تمامی ضرایب مجموعه صفر می باشند در غیراینصورت مجموعه به چهارزیرمجموعه برای ارزیابی بیشتر شکسته می شود و پس از اینکه تمامی مجموعه ها و ضرایب مورد ارزیابی قرار گرفته اند این مرحله به پایان می رسد کدینگ EZW براساس این فرضیه استوار است که چگالی طیف توان در اکثر تصاویر طبیعی به سرعت کاهش می یابد بدین معنی که اگر یک ضریب در زیر باند فرکانسی پایین تر کوچک باشد به احتمال زیاد ضرایب مربوط به فرزندان آن در زیر باندهای بالاتر نیز کوچک هستند به بیان دیگر اگر یک ضریب والد بی معنی باشد به احتمال زیاد فرزندان آن نیز بی معنی هستند اگر آستانه ها توانهایی از دو باشند میتوان کدینگ EZW را به عنوان یک کدینگ bit-plane در نظر گرفت در این روش در یک زمان، یک رشته بیت که از MSB شروع می شود کددهی می شود با کدینگ تدریجی رشته بیت ها و ارزیابی درختها از زیرباندهای فرکانسی کمتر به زیرباندهای فرکانسی بیشتر در هر رشته بیت میتوان به کدینگ جاسازی   دست یافت.
الگوریتم EZW بر پایه 4 اصل استوار است [3]
1- جدا کردن سلسله مراتبی زیرباندها با استفاده از تبدیل ویولت گسسته
1-1-2) تبدیل ویولت گسسته
تبدیل ویولت سلسله مراتبی که در EZW و SPIHT مورد استفاده قرار می گیرد نظیر یک سیستم تجزیه زیرباند سلسله مراتبی است که در آن فاصله زیرباندها در مبنای فرکانس بصورت لگاریتمی است.
در شکل 2-2 یک مثال از تجزیه دو سطحی ویولت روی یک تصویر دو بعدی نشان داده شده است. تصویر ابتدا با بکارگیری فیلترهای افقی و عمودی به چهار زیرباند تجزیه می‌شود. در تصویر (c ) 2-2 هر ضریب مربوط به ناحیه تقریبی 2×2 پیکسل در تصویر ورودی است. پس از اولین مرحله تجزیه سه زیر باند LH1 , HL1 و HH1 بعنوان زیرباندهای فرکانس بالایی در نظر گرفته می شوند که به ترتیب دارای سه موقعیت عمودی، افقی و قطری می باشند اگر Wv  , Wh  به ترتیب فرکانسهای افقی و عمودی باشند، پهنای باند فرکانسی برای هر زیر باند در اولین سطح تجزیه ویولت در جدول
1-2 آمده است[4]

شامل 32 صفحه فایل word

الگوریتم و سورس کد مسئله هشت وزیر ( 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 حدود ۱۵ میلیون حالت مختلف برای چیدمان صحیح وجود داره!!

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