Description

מבוא:
מטריצה היא מבנה דו-מימדי המכיל אוסף של מספרים.
– המימוש הקלאסי של מטריצה הוא מערך דו-מימדי בגודל𝑚 × 𝑛 .
– הפעולות הבסיסיות הדרושות לעבודה עם מטריצה הן:
● (𝑔𝑒𝑡(𝑖, 𝑗 המחזירה את האיבר שנמצא במקום (𝑖, 𝑗).
● (𝑠𝑒𝑡(𝑖, 𝑗, 𝑥 המעדכנת את האיבר הנמצא במקום (𝑖, 𝑗)להיות𝑥 .
– סיבוכיות הזמן של שתי פעולות אלה הוא (1)𝑂.
סיבוכיות המקום של המבנה הוא (𝑂(𝑚 · 𝑛.
אולם, כאשר מטריצה היא בעלת מבנה מיוחד, ניתן להציע מימוש חכם יותר ובכך לשפר את הסיבוכיות.
מטרות:
במעבדה זו נכיר מימושים של מטריצה מיוחדת- מטריצה אלכסונית
תיאור: מטריצה ריבועית בה הערכים בכל אלכסון שווים, נקראת מטריצה אלכסונית. למשל המטריצה הבאההיא מטריצה אלכסונית 4 ×𝑛 4.×שים𝑛 לב שמספר האלכסונים במטריצה זו הוא 7.

סיבוכיות המימוש סטנדרטי:
● בזמן .
● ((𝑠𝑒𝑡𝑔𝑒𝑡(𝑖,(𝑗𝑖,,𝑥𝑗 (בזמן1()𝑂(𝑂𝑛 כי צריך לעדכן את כל איברי האלכסון.
נציע מימוש חלופי באמצעות מערך חד-מימדי בגודל 1 −𝑛 2:
● נשים לב כי מספר האלכסונים השונים במערך הוא . עבור כל אלכסון נקצה תא אחד במערך. למשל,
עבור ((𝑗𝑖,,𝑥𝑗המטריצה),𝑠𝑒𝑡𝑔𝑒𝑡(𝑖המופיעה (1()לעיל1,𝑂(𝑂נחזיק מערך בגודל 17 −ובו𝑛 2האיברים: 7652134.
● סיבוכיות היא .● סיבוכיות היא .
כך שחסכנו גם במקום וגם בזמן!
המשימה היחידה היא לתרגם נכון את האינדקסים של המטריצה הנתונה אל המטריצה החד-מימדית ובחזרה.
1) כתבו ממשק בשםMatrix עם הפעולות הבאות והקבועMAX_SIZE שערכו 100.
double get(int i, int j)
Precondition: 1 ≤ i,j ≤ n
Postcondition: returns the value of the element at position (i,j).
void set(int i, int j, double x) Precondition: 1 ≤ i,j ≤ n.
Postcondition: update the value of the element at position (i,j) to x.
void transpose( )
Postcondition: replace the current matrix wıth its transpose.
Matrix getTranspose( )
Postcondition: returns a new matrix which equals to the transpose of the current matrix.
2) כתבו מחלקה בשםDiagonalMatrix המממשת את הממשק הנ”ל כמטריצה אלכסונית (כלומר, אם משנים
איבר במטריצה, אז כל האיברים באותו אלכסון גם משתנים) ומכילה את הבנאים הבאים:
DiagonalMatrix(int size)
Precondition: size>0
Postcondition: Initializes a size*size diagonal matrix using an array of length 2*size-1.
DiagonalMatrix( )
Initializes an MAX_SIZE * MAX_SIZE diagonal matrix
בנוסף, המחלקה מכילה את השיטה הבאה:
String toString( )
Postcondition: Returns the matrix in its natural n*n form as a string (with between entries of the same row and between rows).
במקרה שתנאי ה-precondition לא מתקיים (למשל מספר שורה קטן מ-1 או גדול ממספר השורות) יש לזרוק חריגת
זמן ריצה מתאימה.
יש לממש את השיטהtranspose בסיבוכיות זמן של (1) 𝑂, ו-getTranspose ב-(𝑂(𝑠𝑖𝑧𝑒
סדר העבודה ופרטים טכניים
● שליפת הפרויקט מתוךGITHUB :
○ אם אין לכם גישה לפרויקט שהורדתם מGITHUB במעבדה הראשונה יש לבצע שליפהמחדש לפי ההוראות במעבדה הראשונה.
○ אם יש לכם גישה לפרויקט שהורדתם מGITHUB במעבדה הראשונה אז בצעו:
■ קליק על שם הפרויקט.
■ עכבר ימני
Team–>Pull ■ File–>Import->Git->Projects From Git->Existing Local Repository ■
פורמט קובץ ההגשה ובדיקתו:
בשםZIP פורמט : יש להגיש קובץ43_lab02_123456789_987654321.zip
(כמובן, יש להחליף את המספרים עם מספרי ת.ז. של המגישים).
על הקובץ להכיל את כל קבצי הJAVA שכתבתם. שימו לב: הקובץ לא יכיל את התיקיה שבה הקבציםנמצאים, רק את הקבצים עצמם (אם לא ברור מה ההבדל, ראו סרטון הדגמה מטה).
ניתן ליצור את הקובץ בשרת המכללה ע”י הפקודה הבאה:
zip ~/43_lab02_123456789_987654321.zip *.java
שיש לתת כאשר אתם נמצאים בתיקייהsrc של הפרויקט. הקובץ יווצר בתיקיית הבית שלכם.
בדיקה: בדקו את הקובץ שיצרתם בתוכנת הבדיקה בקישור:
https://csweb.telhai.ac.il/
ראו סרטון הדגמה של השימוש בתוכנת הבדיקה.
חשוב !!!
בדיקת ההגשות תבוצע ברובה ע”י תוכנית הבדיקה האוטומטית הנ”ל. תוצאת הבדיקה תהייהבעיקרון זהה לתוצאת הבדיקה הנ”ל שאתם אמורים לערוך בעצמכם . כלומר, אם ביצעתם אתהבדיקה באתר החוג, לא תקבלו הפתעות בדיעבד. אחרת, ייתכן שתרגיל שעבדתם עליו קשה ייפסלבגלל פורמט הגשה שגוי וכו’. דבר שהיה ניתן לתקנו בקלות אם הייתם מבצעים את הבדיקה. היותואין הפתעות בדיעבד, לא תינתן אפשרות של תיקונים, הגשות חוזרות וכד’.
הגשה שלא מגיעה לשלב הקומפילציה תקבל ציון 0.
הגשה שלא מתקמפלת תקבל ציון נמוך מ- 40 לפי סוג הבעיה.
הגשה שמתקמפלת תקבל ציון 40 ומעלה בהתאם לתוצאות הריצה, ותוצאת הבדיקה הידנית שלהקוד (חוץ ממקרה של העתקה).
תכנית הבדיקה האוטומטית מכילה תוכנה חכמה המגלה העתקות. מקרים של העתקות יטופלובחומרה.