چرخش ماتریس

[doost4]

سلام . می خوام یه برنامه ای رو بنویسم که ماتریس n x n رو 45 -90 - 135 و 180 درجه بچرخونه . مثلا چرخش 45 درجه ماتریس 3x3 به صورت زیر هست :


3 2 1
4 9 8
5 6 7

4 3 2
5 9 1
6 7 8


حالا چرخش 45 برای ماتریس 5x5 به صورت زیر هست :


5 4 3 2 1
6 19 18 17 16
7 20 25 24 15
8 21 22 23 14
9 10 11 12 13

7 6 5 4 3
8 20 19 18 2
9 21 25 17 1
10 22 23 24 16
11 12 13 14 15




اگر دقت کنید برای 5*5 حلقه داخلی (رنگ آبی) یه دونه به صورت پاد ساعتگرد به سمت چپ شیفت می کنه و حلقه بیرونی (صورتی) 2 تا به صورت پاد ساعتگرد شیفت میکنه . حالا اگه بیش از 2 حلقه داشتیم حلقه های بیرونی همینطور به صورت 3 - 4 و ... شیفت می کنن.

تا اینجا این برای 45 بود . اگه برای 90 بخوایم باید تعداد شیفت ها رو یکی اضافه کنیم یعنی برای 3*3 به جای یک بار 2 بار شیفت کنیم و ...

سوال من اینجاست که هیچ الگوریتم خاصی برای n x n پیدا نکردم ! برای 5*5 نوشتم برای 7*7 هم نوشتم اما حالت کلی پیدا نکردم . آیا برای حالت کلی باید در ماتریس خاصی ضرب شه یا الگوریتمی رو میشه پیدا کرد ؟

[shahmohammadi]

با سلام.
در كجا مشكل دارين.
اينكه بايد خودش مربع ها (همون قرمز و آبي ها) رو پيدا كنه.
يا اينكه در هر لايه اي كه پيدا مي كنين چقدر بايد بر اساس اون زاويه داده شده خونه ها رو حركت بديد.
يا اينكه اينو هم مي تونيد پيدا كنين و نمي دونين چطوري حركت بدين.
اگه بگيد در كدوم بخش از الگوريتم براي n*n دچار مشكل مي شين مي تونيم كمكتون كنيم.

[doost4]

با سلام.
در كجا مشكل دارين.
اينكه بايد خودش مربع ها (همون قرمز و آبي ها) رو پيدا كنه.
يا اينكه در هر لايه اي كه پيدا مي كنين چقدر بايد بر اساس اون زاويه داده شده خونه ها رو حركت بديد.
يا اينكه اينو هم مي تونيد پيدا كنين و نمي دونين چطوري حركت بدين.
اگه بگيد در كدوم بخش از الگوريتم براي n*n دچار مشكل مي شين مي تونيم كمكتون كنيم.


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

[doost4]

الان که روش فک کردم برای 90 رو نوشتم . اما برای 45 که می نویسم حلقه بیرونی (5*5) رو فقط یه بار می چرخونه . در صورتی که حلقه داخلی رو باید 1 بار و حلقه بیرونی رو 2 بار بچرخونه . کدی هم که نوشتم به صورت زیر هست :

void rotate45()
{
int z=n/2;


maze1[z][z]=maze[z][z];
for( k= 0; k<=z-1;k++ )
{
for( i = k; i <n-1-k; i++ )
maze1[k][i]=maze[k][i+1];

for( i = k+1; i <n-k; i++ )
maze1[i-1][n-1-k]=maze[i][n-1-k];

for( i = k; i <n-1-k; i++ )
maze1[i+1][k]=maze[i][k];

for( i = k+1; i<n-k; i++ )
maze1[n-1-k][i]=maze[n-1-k][i-1];
}

}


به نظر شما اشکال کار کجاست ؟

[shahmohammadi]

نیازی نیست برای هر زاویه یه تابع جدا بنویسیم.می تونیم یه تابع بنویسیم که خودش زاویه رو بگیره و بر حسب اون زاویه هر حلقه رو بچرخونه.
برنامه باید خودش بتونه تشخیص بده که وقتی در یه حلقه ای هست اون حلقه رو چند بار باید بچرخونه.
اگر در حلقه k*k باشیم و تعداد کل خونه ها هم که در این حلقه برابر 4k-4 هست، برای چرخش 360 درجه باید 4k-4 بار بچرخه (تا برگرده سرجای اولش).حالا اینکه برای زاویه مورد نظر چقدر باید بچرخه از یه تناسب ساده به دست می آد. که فرمول کلی تعداد چرخش بعد از محاسبه به این صورت در می آد:
d=(angle*(4k-4))/360
که در اون d تعداد چرخش هاست که برای k های مختلف عدد متفاوتی می آد.

for(k=n;k>1;k-=2)
{
d=(angle*(4*k-4))/360;
for(i=1;i<=d;i++)
{
//**************//
}
}
الگوریتم بالا لایه ها(آبی قرمز ها) رو از بزرگ به کوچیک پیمایش می کنه . که در اون k برابر با طول یک ضلع حلقه(لایه) هست. برای هر حلقه تعداد چرخش ها رو پیدا می کنه و به تعداد چرخش ها حلقه ی i رو اجرا می کنه. با هر بار اجرای حلقه i شما یک بار تمام عناصر حلقه رو می چرخونید.
کد چرخوندنش رو در بالا خالی گذاشتم تا زیاد پیچیده نشه.
اما برای چرخوندن می تونیم از یه آرایه کمکی دیگه استفاده نکنیم. با همون روش شما چهار تا حلقه باید بنویسیم که هر کدوم یکی از اضلاع رو جرکت می ده.

[shahmohammadi]

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

برای پیمایش ضلع بالا می دونیم که در حلقه اول از 0,0 تا 0,8 می ریم؛ در لایه دوم از 1,1 تا 1,7 می ریم و... . برنامه باید خودش انا رو تشخیص بده برای این منظور در حلقه ی خارجی مون متغیر دیگری رو قرار می دیم به نام t تا از 0 شروع بشه و هر بار یکی بهش اضافه شه. در این صورت برای پیمایش حلقه اولی به صورت زیر تغییر می کنه:
for(k=n,t=0;k>1;k-=2,t++)
و برای حرکت ضلع بالایی در اون قسمتی که //**************// رو نوشتم به این صورت مینویسم:
temp=a[t][t];
for(j=1;j<k;j++)
{
a[t][t+j-1]=a[t][t+j];
}
برای هر ضلع یه چنین کدی می نویسیم که اندیس هاش متفاوت هستند و در آخر اون مقادیری که در متغیر های کمکی اند رو جاگذاری می کنیم سر جاشون. اگه نتونستین پیمایش بقیه اضلاع رو بدست بیارین باز اطلاع بدین.