◄◄ اتــاق اثبــات فــرمــول ها،قــضــایــا و احــکام هــنــدســه ►►

[CppBuilder2006]

f و g در مسیر پر شدن مربع در هر مرحله تغییر میکنن و به مراحل قبلی کاملا وابسته هستند. در ضمن در هر مرحله کارهای مشابهی نمیشه انجام داد. برای همین فکر نمی کنم جایی برای تابع بازگشتی از نظر ریاضی موجود باشه.مشکل این جاست که همه شکلها جهت دارن.میتونیم برای یه کار ابتدایی حتی جهت رو هم حذف کنیم. و دو شکل رو هم نهشت بدونیم اگر با یه انتقال بدون چرخش بر هم منطبق بشن.اینجوری فکر می کنم دیگه شکل L تقسیم نشه.باید از حالت های ساده تر شروع کرد کم کم پیش رفت.طرح من برای برنامه نویسی اینه که کامپیوتر در هر مرحله تعداد از نقاط گرید رو به هم وصل کنه و چک کنه که آیا تقسیم صورت گرفته یا نه.البته ابن برای یه مربع 8 در 8 هم انقدر طول می کشه که به درد نمی خوره.

[k1kz]

من برای بعضی حالتهای خاص یه رابطه بازگشتی بدست آوردم امشب براتون میذارم.
این راه شما هم قطعا به صورت نمایی هست من بعید میدونم راه حل در کلاس Pspace وجود داشته باشه احتمالا این مساله در کلاس NP -Hard قرار میگیره

>

[k1kz]

البته یه کار دیگه هم میشه کرد و اون اینکه معادله فروبنیوس رو با شرایط خاص بنویسیم و سعی کنیم که حلش کنیم اینطوری:


ولی به نظر شما چه شرایطی برای x ij ها میشه تعیین کرد که مجموعه آنها به هم پیوسته باشه؟

[CppBuilder2006]

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

[k1kz]

من توی yahoo answer عضو هستم.اونجا هم اکثرا مسائل دبیرستانی مطرح میشه و لی مسائل با کلاس هم خیلی دیدم ولی اونجا اینقدر شلوغه که اگه تا 5 دقیقه کسی سوال رو جواب نده دیگه سوال گم میشه و پیدا کردنش هم سخته. شما فروم مفید تر انگلیسی سراغ دارین؟

>

[CppBuilder2006]

نهplanetmath.org هست ولی ظاهرش خیلی بده برای همین خیلی جذاب نیست.

[k1kz]

فکر میکنم همه الگوریتمهای ما به صورت نمایی هستند
ولی جالبه که وقتی جواب رو پیدا میکنیم کنترل صحت اون جواب ,الگوریتم خیلی ساده و سریعی در زمان چند جمله ای داره درست مثل مسائلNP-Complete فکر کنم من اشتباه گفتم که این مساله NP-Hard میشه
من بیشتر علاقه دارم ببینیم کدوم الگوریتمهایی که اینجا مطرح شد سریعتره.
این که بفهمیم کدوم سریعتره باز هم یه مساله ترکیباتی خیلی پیچیده است!!
فرض میکنیم که ما یه مربع با تعداد تقسیم بندی nدرn داریم.که میخواهیم اونو به 5 قسمت مساوی تقسیم کنیم.احتمالا تنها جوابها به صورت مستطیلهایی به اضلاع n/5 وn هست ولی ما میخواهیم با الگوریتم خودمون همه جوابها رو کنترل کنیم
برای ساده ترین مساله ترکیباتی این رو بررسی کنیم که
تعداد تمام مسیر هایی که مربع رو به 5 قسمت تقسیم کنه چند تاست:
طول حداکثر کل مسیر پیموده شده میشهn+1)^2 )و همیشه حداکثر میشه با سه مسیر مربع رو به 5 قسمت تقسیم کنیم
اگه دست کم فرض کنیم مسیرها به طول حداکثر 2n باشه میتونیم بنویسیم تعداد کل 3مسیرهایی که به طول n تا 2n هستند برابر است با

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


>

[CppBuilder2006]

فکر می کنم درست باشه
ولی n باید بر 5 بخش پذیر باشه.

ولی هنوز این مسیرها یه خرده برام مبهمه باید روش فکر کنم!

[CppBuilder2006]

من با اینا یه خرده مشکل دارم:

همیشه حداکثر میشه با سه مسیر مربع رو به 5 قسمت تقسیم کنیم

چرا؟

طول حداکثر کل مسیر پیموده شده میشهn+1)^2 )

یعنی چی؟

فرض کنیم مسیرها به طول حداکثر 2n باشه

چرا این فرض رو بکنیم.

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

[k1kz]

خوب در مورد اولی فکر میکنم اگه سه خط داشته باشیم که از یک نقطه نگذرند حتما مربع رو به 7 قسمت تقسیم میکنند که میتونیم دو قسمت رو با هم ادغام کنیم.یعنی یک قسمت از یه خط رو به طوری که دو تا نشه پاک کنیم

در مورد دومی من اینطور حساب کردم که n+1 خط عمودی داریم که طول همشون n هست اینطوری:


.پس حداکثر طول قابل پیمایش میشه:
که من اشتباه حساب کرده بودم!!


در مورد سوم خوب اگه یه کم دست پایین بگیریم میشه فرض کرد فقط مسیرهای ما حداکثر یه گوشه مربع رو به گوشه دیگه وصل میکنن اگه دو گوشه مقابل رو در نظر بگیریم میشه 2nو اگه گوشه مجاور میشه n که من اینجا یه خورده دست پایین گرفتم و فرض کردم تمام مسیرهایی که از گوشه مقابل تا مجاور هستند رو با هم جمع میکنیم.

>