◄◄ اتــاق تــجــزیــه و تــرکــیــبــات ►►

[elector girl]

این سوال بنده

impossible is impossible

تو سوالم یکی از جوابا رو گذاشتم اینم شکلش

خب حالت ديگه اي هم داره؟!

[chessmathter]

جوابشم میدونم ولی اثباتش و نه به 92 حالت میشه این کارو کرد.!!!

[elector girl]

جوابشم میدونم ولی اثباتش و نه به 92 حالت میشه این کارو کرد.!!!

92 حالت؟!!!!!!!!!!!!!!! مگه ميشه؟!!!!!! چه جوري؟!!!!!

[chessmathter]

92 حالت؟!!!!!!!!!!!!!!! مگه ميشه؟!!!!!! چه جوري؟!!!!!

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

[elector girl]

من هر چقدر فكر كردم ديدم با آناليز به جايي نمي رسه! يعني تا 6 وزير رو ميشه با آناليز و حذف خونه ها رفت ولي بيش تر از اون نشد!
از راه همين ساختن تابعي كه گفتي رفتم 4 تا حالت ديگه پيدا كردم ولي مسلمه كه نميشه تا 92 حالت رو ازين راه پيدا كرد! ولي نوشتن الگوريتمش سادست. با برنامه نويسي هم در مياد!
اگه الگوريتم قبوله توضيحش بدم!

[chessmathter]

من هر چقدر فكر كردم ديدم با آناليز به جايي نمي رسه! يعني تا 6 وزير رو ميشه با آناليز و حذف خونه ها رفت ولي بيش تر از اون نشد!
از راه همين ساختن تابعي كه گفتي رفتم 4 تا حالت ديگه پيدا كردم ولي مسلمه كه نميشه تا 92 حالت رو ازين راه پيدا كرد! ولي نوشتن الگوريتمش سادست. با برنامه نويسي هم در مياد!
اگه الگوريتم قبوله توضيحش بدم!

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

برای مشاهده محتوا ، لطفا وارد شوید یا ثبت نام کنید

[elector girl]

انگليسيم كه خوبه!
من چند تا الگوريتم ديگه هم پيدا كردم.
اينم سورس برنامش به زبان C

برای مشاهده محتوا ، لطفا وارد شوید یا ثبت نام کنید

[elector girl]

اينم يه جورايي ترجمه شده ي راه حلشه! واسه اونايي كه حوصله متن زبان اصلي ندارن!
صورت مسئله : هشت وزير را در هشت خانه شطرنج (8*8) طوري قرار دهيد كه هيچكدام يكديگر را تهديد نكنند. وزير در خانه هاي شطرنج به صورت عرضي،طولي و قطري مي تواند حركت كند. اين مسئله قابل تعميم به مسئله N وزير در يك شطرنج N*N است.

تاريخچه: اين مسئله در سالي 1848 توسط شطرنج بازي به نام Max Bezzel عنوان شد و رياضي دانان بسياري ازجمله Gauss و Georg Cantor بر روي اين مسئله كار كرده و در نهايت آنرا به N وزير تعميم دادند. اولين راه حل توسط Franz Nauck در سال 1850 ارائه شد كه به همان مسئله N وزير تعميم داده شد. پس از آن Gunther راه حلي با استفاده از دترمينان ارائه داد كه J.W.L. Glaisher آنرا كامل نمود.
در سال 1979 ، Edsger Dijkstra با استفاده از الگوريتم عقب گرد اول عمق اين مسئله را حل كرد.

راه حل: براي حل اين مسئله كه داراي 92 جواب است ، بايد تكنيكهايي جهت كاهش حالات ،روش Brute Force يا امتحان تك تك جواب ها انجام شود. تعداد همه حالاتي كه مي تواند در روش Brute Force چك شود برابر 16,777,216 يا هشت به توان هشت است!
يكي از روش هاي حل اين مسئله براي n>=4 يا n=1 استفاده از روش مكاشفه اي (heuristic) است:
1- عدد n را بر عدد 12 تقسيم كن و باقي مانده را يادداشت كن
2- به ترتيب اعداد زوج 2 تا n را در ليستي بنويس
3- اگر باقي مانده 3 يا 9 بود ، عدد 2 را به انتهاي ليست انتقال بده.
4- به ليست اعداد فرد 1 تا N را به ترتيب اضافه كن، اما اگر باقي مانده 8 بود اعداد را دو به دو باهم عوض كند (مثلا 1و3و5و7و9 تبديل به 3و1و7و5و9 ميشه)
5- اگر باقي مانده 2 بود جاي 1 و3 را با هم عوض كن و 5 را به انتهاي ليست ببر
6- اگر باقي مانده 3 يا 9 بود ، اعداد 1 و 3 را به انتهاي ليست ببر.
7- حال با استفاده از ليست بدست آمده وزير ها در صفحه شطرنج چيده مي شوند، بطوريكه جاي وزير ستون اول ،اولين عدد ليست ،جاي وزير ستون دوم ، دومين عدد ليست و ...
اين الگوريتم يك راه حل براي حل اين مسئله است، براي بدست آوردن همه حالات از روشهاي ديگري مي توان استفاده كرد.
روش حل مسئله 12 راه حل يكتا دارد كه با در نظر گيري تقارن و چرخش به 92 حالت قابل تبديل است.

[chessmathter]

فقط چند توضیح اضافه اول اینکه راه حلی برای پیدا کردن تعداد جواب ها نداده و فقط الگوریتمی رو گفته که با اون تمام جواب ها رو میشه پیدا کرد.!!(باور کنید این 2 تا با هم فرق میکنن.!) البته راه حل دترمینالیش یا راه حل های ارایه شده توسط 'Franz Nauck وغیره رو نگفته.!!(توسایت)
بعدشم گرفتن تقارن و ثابت ندونستن صفحه یعنی این 2 جواب و یکی میگیریم





بعدشم یه جدول گذاشه که بالای با حساب ثابت نگرفتن صفحه است پایین با حساب ثابت گرفتن.!

نکته جالب اینه که تعداد جواب ها برای 6*6 کمتر از 5*5.!!!

math is beautiful.!!!

[elector girl]

عجب معمايي بود . . . !

خيلي خوشم اومد! جدا خيلي جالب بود . . .