אלגוריתם שבלול

[baranchik]

אלגוריתם שבלול

אני צריך ליצור צורה של שבלול, לפי מספר מסויים שאני קולט, למשל : קלט = 5 פלט = 10 11 12 1 9 16 13 2 8 15 14 3 7 6 5 4 עכשיו מצאתי אלגוריתם קצת ארוך, יש למישהו פתרון יותר אלגנטי? ניסיתי למצוא קשרים וזה לא כל כך הצליח...

 

[vinney]

תגדיר "קצת ארוך"

 

[baranchik]

לולאה לכל צלע בתוך לולאה ראשית :|

 

[baranchik]

קלט = 4

 

[ron369]

אתה יכול ליצור מטריצה NXN מימדית?

 

[baranchik]

אין לי בעיה עם הפתרון

התעניינתי אם יש למשישהו פתרון מתמטי לזה, שיהיה יותר אלגנטי. הנה איך שאני עשיתי:

int stop,i,j,count=1,mat[n][n]; stop = n/2; if (n%2!=0) stop++; for (i=0;i<stop;i++) { for (j=i;j<=n-1-i;j++) { mat[j]=count; count++; } for (j=i+1;j<=n-1-i;j++) { mat[n-1-i][j]=count; count++; } for (j=n-i-2;j>=i;j--) { mat[j][n-1-i]=count; count++; } for (j=n-i-2;j>i;j--) { mat[j]=count; count++; } } for (i=0;i<n;i++) { for (j=0;j<n;j++) printf("%3d", mat[j]); printf("\n"); }​

 

[ron369]

ובכן,

אתה בטח יכול לעשות את זה מתימטית. למשל, נסה לחשוב על האלכסון. אם נתונים לנו האיברים בתוכו, בבירור, ובקלות, אפשר "להשלים" את שאר המטריצה (וכל איבר אחר בה). נכון? אז צמצמנו קצת את הבעיה. בנוסף, מטעמי סימטריות, נניח שעלינו למצוא רק את חציו. עוד צמצום קל. ועכשיו, נשים לב למשהוא פשוט ונחמד. אם נניח שנתון לנו איבר ברבע העליון ימני, (i,j), אזי כל האיברים בריבוע (תת-מטריצה) X, המתקבלים כך: i עד n-i, וj-1 עד n-j (אם לא התבלבלתי), עדיין "ריקים". משמע, מכיוון שבכל הריבוע כולו יש n^2 איברים, ובתת-מטריצה יש row X * col X איברים, נוכל לחשב (בזמן קבוע, פחות או יותר) את ערכו של האיבר ה"פינתי" ב-X. מכך, בקלות, אפשר לחשב את השאר. זה ברור? נראה לי שלא העברתי את זה בצורה כ"כ ברורה. הטריק הבסיסי הוא להגיע למצב עם "ריבוע פנימי ריק", לחשב את מספר האיברים שבו, מכך את מספר האיברים שמחוצה לו, ומכך את הערך של נקודת הפינה בו - הנקודה הבאה בתוך הריבוע שבה יושם ערך (הפינה הספציפית תלויה בריבוע הספציפי). ניתן לשנות מעט את השיטה שהראיתי, ולהופכה ליותר נוחה.