دوستان سلام
در مسئله زیر من کد n وزیر به روش backtrack رو میتونم بنویسم و میدونم که منظور از جوابهایی که با چرخش یا انعکاس به یکدیگر تبدیل میشه چیه مثلا در حالت انعکاس میدونم که اگه همه درایه های بردار جواب رو از n کم کنیم جواب دیگه بدست میاد.
و اگه این شرط رو بگذاریم که واسه اولین وزیر محدوده قرار گرفتن بین سطرهای ۱ تا n/2 باشه دیگه جوب دوم رو به ما نمیده.
اما واسه ی چرخش نمیدونم رابطه شون چه جوری هست (با استفاده از شیفته؟ یا ترانهاده کردن؟ یا .... )
و اینکه چون روش عقبگرده کجا شرط رو قرار بدم که اون جوابها رو بررسی نکنه.
با استفاده از روش backtracking برنامه‌ای بنویسید که تمام جوابهای مسئله‌ی n-وزیر را بدست آورد اما ترتیبی دهید که جوابهایی که با چرخش یا انعکاس صفحه به یکدیگر تبدیل می‌شوند تنها یکبار بدست آیند.
(۰۱ تیر ۱۳۹۱ ۰۴:۲۹ ب.ظ)afagh1389 نوشته شده توسط: در مسئله زیر من کد n وزیر ... مثلا در حالت انعکاس میدونم که اگه همه درایه های بردار جواب رو از n کم کنیم جواب دیگه بدست میاد.من فکر می کنم انعکاس یعنی قرینه نسبت به خط افقی یا عمودی
ربطش با کم کردن از عدد n را نمی دانم!
انعکاس نسبت به خط عمودی:
برای ماتریس A و B
کد:
A[i][j]<==>B[i][9-j]و نسبت به افقی:
کد:
A[i][j]<==>B[9-i][j]خط مایل
کد:
A[i][j]<==>B[9-i][9-j]چرخش هم با عوض کردن جای سطر و ستون بدست می آیید.
با تشکر از پاسختون :
- - - - x | x - - - -
- x - - - | - - - x - انعکاس
- - - x - | - x - - -
x - - - - | - - - - x
- - x - - | - - x - -
توی اولی اگر وزیر اول در سطر ۴ قرار گرفته در شکل دوم در سطر اول قرار گرفته.۴+۱ =۵ =n
اگر وزیر دوم در سطر دوم قرار گرفته در شکل دوم در سطر سوم قرار گرفته . ۲+۳=۵ =n
اگه بتونید بیشتر راهنمایی کنید ممنون میشم.
(۰۱ تیر ۱۳۹۱ ۰۸:۲۴ ب.ظ)a.hooshmand نوشته شده توسط: چرخش هم با عوض کردن جای سطر و ستون بدست می آیید.آخه چرخش ۹۰ درجه داریم،۱۸۰ درجه و ۲۷۰ درجه .
مشکل من با پیاده سازی هست یعنی اینکه مثلا به یک جواب که رسید خوب بعد چی کار کنم آخه روش عقب گرده ، اگه به صورت یک درخت در نظر بگیریم من چه جوری بگم که این مسیر از درخت رو طی نکن.
فکر میکنم باید flag اون مسیر رو false کنیم اما ..........
کد:
- - - - x | x - - - -
- x - - - | - - - x - انعکاس
- - - x - | - x - - -
x - - - - | - - - - x
- - x - - | - - x - -مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
اگر وزیر اول رو به سطرهای ۱ تا n/2 و وزیر دوم رو به سطرهای n/2 تا n محدود کنیم، جوابهای منحصر به فرد بدست نمیاد؟
من اول فکر کردم مسئله قرار دادن تعدادی وزیر در خانه های ۸*۸ است.
(۰۲ تیر ۱۳۹۱ ۱۱:۲۲ ق.ظ)afagh1389 نوشته شده توسط: اگر وزیر اول رو به سطرهای ۱ تا n/2 و وزیر دوم رو به سطرهای n/2 تا n محدود کنیم، جوابهای منحصر به فرد بدست نمیاد؟
نه، مثلا این شکل انعکاسش باز هم در این شرط است.(۲ با شمرده می شود.)
داخل ۸*۸ من ۳ تای اولو نیگا می‌کردم منحصر بفرد بودن ، فکر میکنم ۱۲ تای اول منحصر به فرد باشن، برسی کنین
فکر کنم اینجوری باید بگیم سطر اول در یکی از ستونهای ۱ تا n/2
و یه سری شرط مشابه.
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
اینجا به زبانهای مختلف نوشته است در بعضی از برنامه ها مثل زبانهای PHP و Groovy و Ursala تکراری ها را هم حذف می کند
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
من زبان Groovy نمی دانم چی هست ولی در این IDE اینترنتی اجرا می شود!
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
Groovy:
Groovy is an object-oriented programming language for the Java platform. It is a dynamic language with features similar to those of Python, Ruby, Perl, and Smalltalk. It can be used as a scripting language for the Java Platform.
Groovy uses a Java-like bracket syntax. It is dynamically compiled to Java Virtual Machine (JVM) bytecode and interoperates with other Java code and libraries. Most Java code is also syntactically valid Groovy.
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
راستی حالا این برای چه چیزی هست؟
جزء سوالهای درس طراحی الگوریتم دوره لیسانسه.
سلام. میشه برای شمارنده هر سطر یه شرط اعمال کنید. مثلاً شکل زیر رو درنظر بگیرید:
۱ ۲ ۳ ۴ ۵ ۶ ۷ ۸
۱|*| | | | | | | |
۲| | | | |*| | | |
۳| | | | | | | | |
۴| | | | | | | | |
۵| | | | | | | | |
۶| | | | | | | | |
۷| | | | | | | | |
۸| | | | | | | | |
برای حذف مشابه ها باید یه سری خونه هارو بلاک کرد. برای شکل بالا میشه:
۱ ۲ ۳ ۴ ۵ ۶ ۷ ۸
۱|*|.| | | | | | |
۲|.|.|.|.|*| | | |
۳| |.| | | | | | |
۴| |.| | | | | | |
۵| | | | | | |.| |
۶| | | | | | |.| |
۷| | | | |.|.|.|.|
۸| | | | | | |.|.|
این بلاک ها هم وقتی یک سطر نیاز به برگشت داشت برای اون سطر ازبین میرن. فایدش هم حذف قرینه هاست. مثل دوتا حالت زیر:
۱ ۲ ۳ ۴ ۵ ۶ ۷ ۸
۱|*| | | | | | | |
۲| | | | |*| | | |
۳| | | | | | | |*|
۴| | | | | |*| | |
۵| | |*| | | | | |
۶| | | | | | |*| |
۷| |*| | | | | | |
۸| | | |*| | | | |
۱ ۲ ۳ ۴ ۵ ۶ ۷ ۸
۱|*| | | | | | | |
۲| | | | | | |*| |
۳| | | | |*| | | |
۴| | | | | | | |*|
۵| |+| | | | | | |
۶| | | |*| | | | |
۷| | | | | |*| | |
۸| | |*| | | | | |
که قرینه هم هستن. (+ در دومین صفحه نشون دهنده نقطه بلاک شدست که درصورت اعمال نشدن شرط شمرده میشه.) شرط شمارنده برای سطر اول از ۱ تا ۴ برای ۸×۸ میشه. یعنی فقط نصفشونو چک میکنیم. بقیشون مشابهن. دلیلشم که خودتون گفتید برای حالت انعکاس.