PDA

View Full Version : برنامه فرش كردن صفحه n*n



takstar
سه شنبه 17 اردیبهشت 1387, 20:42 عصر
سلام
از برنامه نويسان مي خواستم بنده را در نوشتن اين برنامه ياري كنند

برنامه به اين صورت است كه:

يك خانه n*n داريم كه اين خانه را بايد به خانه هاي 2*2 تقسيم كرده و آن را به صورت (L) مانند فرش كنيم كه از اين خانه 2*2 يك خانه خالي مي ماند و بايد اين يك خانه را با يك خانه هاي ديگر كه باقي مي ماند را طوري فرش كنيم كه در پايان از كل n*n فقط يك خانه خالي بماند (با استفاده از روش تقسيم و غلبه)

اميدوارم كه برنامه را متوجه شده باشيد و بتوانيد من را ياري كنيد.

amir_cpp
چهارشنبه 18 اردیبهشت 1387, 21:51 عصر
سلام.
ببخشید من این طوری اصلا متوجه نشدم :افسرده:، اگه می شه به صورت مصور توضیح بدین، یعنی برای این مثال یه عکس هم بزارین. ممنون. :لبخند:

takstar
سه شنبه 24 اردیبهشت 1387, 09:21 صبح
سلام

هيچ كسي نظري نداره؟

MRHagh
سه شنبه 24 اردیبهشت 1387, 11:48 صبح
شکل بیان شما در طرح مسئله نادرست است , همچنان که این بحث بیشتر به قسمت طراحی الگوریتم مربوط میشود :

صفحه ای به ابعاد n*n داریم که میخواهیم آنرا با موزاییک هایی به شکل L فرش کنیم , در بهترین حالت (اگر n زوج باشد ) یکی از خانه ها خالی خواهد ماند . میخواهیم نشان دهیم , اگر این خانه را بعنوان خانه دلخواه اختیار کنیم , باقی خانه ها (از کل صفحه) کاملا فرش خواهند شد . طوریکه موزاییک ها روی هم قرار نمیگیرند و از صفحه بیرون نمیزنند . بدیهیست که میتوان موزاییک ها را دوران داد .

برای حل این مسئله , اگر صفحه را به بخشهایی کوچکتری تقسیم کنیم , به نوعی دوباره با همین مسئله در ابعاد کوچکتر مواجه خواهیم شد و این یعنی , تقسیم و غلبه !
این روش که معمولا برای بدست آوردن الگوریتم های سریع در حل مسائل مورد استفاده قرار میگیرد , مسئله را به چند بخش کوچکتر و قابل حل تقسیم میکند . گونه مسائلی که بوسیله این روش حل میشوند , عموما از تکنیک های روش طراحی الگوریتم به روش استقراء استفاده میکنند , قابل ذکر است که در استقراء هم مسئلهء مورد بحث به مسئله ای به اندازه کوچکتر تقسیم خواهد شد .
بنابراین با استفاده از استقراء برای n=1 بدیهیست که با یک دوران به جواب میرسیم , اگر صفه n*n را به 4 قسمت تقسیم کنیم , با صفحاتی به ابعاد n/2*n/2 مواجه خواهیم بود که باز طبق استقراء , هرقسمت را میتوان طوری فرش کرد که خانه دلخواهی از آنها خالی بماند . اما خانه خالی مورد نظر ما , در یکی از 4 قسمت (مربع) ایجاد شده قرار دارد . پس دوباره با فرض این خانه خالی در این قست بعنوان خانه دلخواه , این قسمت را طوری با استقراء فرش میکنیم که این خانه خالی بماند . حال سه مربع دیگر را طوری فرش میکنیم که در هر مربع یک خانه موجود در محل تلاقی آنها خالی بماند که حال مجموعا در این محل سه خانه خالی خواهیم داشت که با یک موزاییک پر میشود و خانه دلخواه ما هم خالی میماند .
در تنظیم الگوریتم این برنامه فقط کافیست مراحل یاد شده به دقت بصورت بازگشتی پیاده سازی کنید .
این مرحله را خودتون به راحتی میتونید انجام بدید !
موفق باشید ...

takstar
سه شنبه 24 اردیبهشت 1387, 23:39 عصر
ازMRHAGH خيلي ممنونم به خاطر بهتر طرح كردن مسئله

اما من با روش تقسيم و غلبه آشنا هستم فقط مي خواستم من را در نوشتن همين برنامه بازگشتي كمك كنيد

لطفا اگر نظري داريد در تاپيك قرار دهيد

mehdimarzi92
چهارشنبه 31 اردیبهشت 1393, 00:15 صبح
عزیزان کسی میتونه برنامه بنویسه که پیکسل های یک تصویر رو به صورت عدد خروجی بده.خود سی شارپ مثل اینکه همچین امکانی توش هست.حالا دستمزد هم تا جاییکه بودجه ام یاری بده میپردازم.از همه بچه های این سایت ممنونم.