שאלה במבנה נתונים

[amirxbox]

שאלה במבנה נתונים

יש לי מטריצה בגודל N^2 על N^2 . אני רוצה לחלק אותה לריבועים כך ש בהנתן מיקום I,J (האינדקסים מ 1 ועד N^2) אני אדע לאיזה ריבוע בדיוק לגשת (יש N^2 ריבועים ממוספרים מ 1 ועד N^2 משמאל לימין). לדוגמא אם N=2 עבור 1,1 התשובה תהיה 1. עבור 1,3 התשובה תהיה 2. עבור 4,4 התשובה 4. יש מצב בכלל לעשות זאת בזמן קבוע לא תלוי ב N הצלחתי רק בזמן התלוי ב N.

 

[vinney]

מה זאת אומרת?

תמספר את כל הריבועים שלך לפי הסדר, ותהיה לך פונקציה חח"ע ממס' הריבוע בסדר לזוג אינדקסים (והפוך). זה נורא פשוט, הרי עושים את זה כל הזמן במחשבים כשרוצים לגשת לאיבר במערך דו מימדי.

 

[ron369]

והנה הפונקציה עצמה

אם המטריצה היא A עם n שורות וm עמודות, אזי הפונקציה היא: row*(m-1)+ + col, כאשר row זו השורה, וcol זו העמודה. נכון?

 

[vinney]

כן, רק תן לאנשים לחשוב קצת לבד ../images/Emo13.gif

 

[ron369]

יאללה, תמחק את השרשור ../images/Emo13.gif

(מההודעה שלי ומטרה) (צודק, מצטער. בוקר טוב, אגב

)

 

[amirxbox]

לא מסתדר

למשל N=2 המטריצה היא N^2 על N^2 . כלומר 4*4. המטריצה מחולקת ל 4 ריבועים שבכל אחד מהם 4 תאים סה"כ 16 תאים. נקח את התא ה 3,1 (ROW=3, COL=1) הריבוע המתאים במטריצה זו הוא 3 ולפי הנוסחא שלך יוצא 10.

 

[ron369]

טוב, אז תחשוב איך לתקן אותה ../images/Emo13.gif

 

[vinney]

איך אתה מחלק לריבועים ?

אם לא תספר לנו לא נדע, הנחנו שהחלוקה זה לפי תאי המערך...

 

[amirxbox]

מצורף ציור לדוגמא עבור

4 על 4 . ניסיתי להסביר את עצמי בהודעה הראשונה העלתי תמונה להיות יותר ברור. למי שמעניין למה בכלל אני צריך את ההתאמה בין תא לריבוע זה הדבר האחרון שחסר לי בדרך לפתרון תרגיל ראשון בדף הבא: הוספתי 3 לוחות בוליאנים על כל איתחול לוח סודוקו כל אחד יבדוק חוקיות אחרת בלוח וישמור מונה ברגע שסכום המונים יהיה 3 כפול N^2 אז הלוח VALID.

 

[vinney]

אז מה הבעיה?

אם החלוקה היא לריבועים זהים (ז"א N ריבועים בגודל N בכל מימד), אז זה טריויאלי, במה הסתבכת? חלוקה+מודולו נותנים לך את הריבוע+תא בריבוע בכל מימד, וקיבלת פונקציה לינארית מאינדקס רגיל לאינדקס לפי ריבועים...

 

[amirxbox]

לא מסתדר לי

תודה על העזרה , תאמין לי ישבתי על זה שעות בסוף התייאשתי ופתרתי תרגיל אחר. עדיין לא מובן לי. המטריצה היא N*N. שאני מקבל I, J הדבר היחיד שכרגע חשוב לי זה לאיזה ריבוע הוא שייך מ 1 עד N, בדקתי בפתרונות של מבוא לJAVA ששם כתבנו תוכנית שפתרה סודוקו והינו צריכים משהו עם רעיון דומה וגם בפתרון הרישמי הם שאלו 2*N שאלות כדי לדעת באיזה ריבוע מדובר ברגע שנותנים אינדקסים I,J. בכל אופן יש מצב שתסביר יותר מהי החלוקה וכו לא כל כך הבנתי אותך, מצטער על ההטרדה.

 

[vinney]

תראה

תגיד לי אם הבנתי לא נכון את השאלה יש לך מטריצה N^2*N^2 תאים, שהיא גם N*N ריבועים (מה שאומר שכל ריבוע זה N*N תאים). אתה מקבל I,J כתובת של תא, אתה צריך לתרגם אותה לK,M כתובת של ריבוע, כדי לדעת באיזה ריבוע התא נמצא (כדי לדעת מה המספר הבודד של הריבוע, יש לך כבר את הפונקציה של רון, כך שמעבר מK,M למספר בודד אתה כבר יודע לעשות). I/N+1 נותן לך את הK, וJ/N+1 נותן לך את הM. אם אתה רוצה לדעת את הכתובת של התא בתוך הריבוע K,M, אז I%N נותן לך את המימד הראשון, וJ%N את השני. זה הכל

(ההנחה שלי היא שכל המספורים מתחילים מ0, אם זה מ1 - צריך להוסיף 1).

 

[amirxbox]

אני צריך את המספר הבודד של הריבוע

והנוסחא שרון נתן לא עובדת. הסבר נוסף - אין לי שום צורך בכתובת התא בתוך הריבוע אלא בהנתן I, J במערך דו מימדי ריבועי מסדר N^2 על N^2 אני צריך פונקציה שתקבל את ה I, J ותחזיר מספר הריבוע (יכול להיות מ 1 עד N^2 ) לפי הדוגמא שהעלתי בציור.

 

[vinney]

מה זאת אומרת נוסחא של רון

לא עובדת? תגדיר "לא עובדת". יחד עם הנוסחא הזאת יש לך את הפתרון המלא, מה כבר אתה עוד יכול לבקש?

 

[amirxbox]

כנראה שלא הבנת אותי לגמרי

זה פשוט לא פותר את מה ששאלתי . תשמע אני גם בכלל לא בטוח שזה אפשרי אבל בכל מקרה מה שענית עליו לא קשור למה ששאלתי וגם מה שרון ענה עליו, קשה לי מאוד להסביר ככה דרך בכתב. אם למשל אני מקבל I= 3 ו J=3 הטרנספורמציה שאמורה לחשב באיזה ריבוע אני אמורה להחזיר 4 . לפי הנוסחא שרון הביא התוצאה היא מעבר ל N^2 יוצא 6 בעוד שהריבוע האחרון הוא 4. אין לי מושג איך לתקן אותה.

 

[vinney]

לפי הנוסחא של רון יצא לך בדיוק 4

N שלך זה מ0 ל3, ז"א הK=1 והM=1, 1 לפי הנוסחא של רון - 2*1+1, שזה 3.. אתה מתחיל את הספירה מ1 ולא מ0, אז תוסיף 1. קיבלת 4. תקרא בדיוק את מה שכתבתי לך.

 

[amirxbox]

אם הבנתי נכון אז יצא לי ככה

בהנחה שהריבועים מ 0 עד N^2 ו התאים ימוספרו מ 0 עד N^2 , קילתי נוסחא כזאת n*(i div n) + jdivn= ואכן זה עובד תודה לכם.

 

[amirxbox]

תודה רבה רון וויני ../images/Emo13.gif

מצטער שהייתי קצת קשה הבנה. יש לי הרגשה שאני אאלץ להטריד אותכם עוד הרבה עם העבודה הזאת שנתנו לנו.

 

[ron369]

בבקשה, למרות שויני עשה כמעט הכל

אבל אתה צריך לחשוב, ולהבין איך זה עובד. אתה מבין איך זה עובד?

 

[vinney]

בבקשה, תבוא כל יום ../images/Emo13.gif

הכי חשוב - ראש פתוח. לא יבקשו ממך להמציא מחדש את הגלגל, בסך הכל התרגילים פתירים, רק צריך טיפה לצאת מהקופסא לפעמים כדי לפתור אותם.