מציאת תת-מטריצה מרכזית שהיא מטריצת יחידה

נגדיר,

מטריצת היחידה (Identity matrix) מסדר n היא מטריצה (מערך דו-ממדי) ריבועית בגודל n×n (n שורות ו- n עמודות) שאלכסונה הראשי מורכב מאחדות וכל שאר המטריצה אפסים. לדוגמה, המטריצה A להלן היא מטריצת יחידה מסדר 3 (האלכסון הראשי מודגש), והמטריצה B להלן אינה מטריצת יחידה, אמנם אם האיבר [1][1] היה 1 ולא 2, והאיבר [1][3] היה 0 ולא 3, אז היא הייתה מטריצת יחידה מסדר 4.

		0	1	2
	0	1	0	0
A=	1	0	1	0
	2	0	0	1

		0	1	2	3
	0	1	0	0	0
B=	1	0	2	0	3
	2	0	0	1	0
	3	0	0	0	1

תת-מטריצה מרכזית של מטריצה ריבועית A היא תת המטריצה ריבועית שמרכזה מתלכד עם המרכז של A. לדוגמה,

	0	1	2	3	4	5	6
0
1
2
3				מרכז
4
5
6

המטריצה המסומנת במרכז, בגודל 3×3 היא תת-מטריצה מרכזית שמתלכדת עם המטריצה הגדולה בגודל 7×7.

בשאלה זו חשבו את הגודל המקסימלי של תת-מטריצה המרכזית של A שהיא מטריצת יחידה.

לדוגמה, עבור המטריצה A שלפניך:

	0	1	2	3	4	5	6
0	1	2	3	2	0	1	2
1	0	1	0	0	0	3	0
2	0	0	1	0	0	0	0
3	5	0	0	1	0	0	0
4	7	0	0	0	1	0	0
5	8	0	0	0	0	1	0
6	1	0	0	0	0	0	0

הגודל המקסימלי של תת-מטריצה מרכזית שהיא מטריצת יחידה הוא 3.

אם למשל A[1][5] היה שווה 0 (במקום 3) אזי הגודל המקסימלי של תת-מטריצה המרכזית שהיא מטריצת יחידה היה 5.

כתבו שתי שיטות רקורסיביות:

isIdentity המקבלת כפרמטרים מטריצה ריבועית mat ומספרים שלמים x ו- size. השיטה תחזיר את הערך true אם תת-מטריצה בגודל size שהפינה השמאלית העליונה שלה היא mat[x][x] היא מטריצת יחידה, ו-false אחרת.

לדוגמה, על המטריצה שהוצגה לעיל:

כאשר x=0 ו-size=1, השיטה תחזיר true.
כאשר x=1 ו-size שווה ל-1 או 2 או 3 או 4, השיטה תחזיר true.
כאשר x=4 ו-size שווה ל-1 או 2, השיטה תחזיר true, אבל אם size שווה ל-3 השיטה תחזיר false (עקב המטריצה שהפינה השמאלית העליונה שלה היא באיבר A[4][4] והיא בגודל 3 אינה מטריצת היחידה, כי האיבר הימני התחתון שלה הוא A[6][6] והוא שונה מ-1).

x ו-size לא חורגים מגבולות המטריצה.

maxMatrix המקבלת כפרמטר מטריצה ריבועית mat ומספר השורות והעמודות הוא אי-זוגי. השיטה תחזיר את הגודל המקסימלי של תת-מטריצה ריבועית של mat שהיא מטריצת יחידה.

לדוגמה, אם המטריצה לעיל הייתה מועברת כפרמטר לשיטה, היה מוחזר הערך 3. שימו לב, אמנם יש במטריצה חזו מטריצת יחידה גדולה יותר, שמתחילה גם באיבר A[2][2] והיא בגודל 4 (והפינה הימנית התחתונה שלה היא A[5][5]), אבל המרכז של המטריצה הזו אינו מתלכד עם המטריצה A, ולכן היא אינה תת-מטריצה מרכזית של A.

שימו לב, מותר להשתמש בשיטה isIdentity.

השיטות צריכות להיות רקורסיביות ללא שימוש בלולאות כלל. כך גם כל שיטות העזר (אם תכתבו) לא יכולות להכיל לולאות.

אילוצים:

x ו-size לא חורגים מגבולות המטריצה.
המטריצה אינה null ואינה ריקה.
המטריצה היא ריבועית.
אין לשנות את תוכן המטריצה (אפילו לא זמנית), ולא להשתמש במערכי עזר.

דוגמה 1:

קלט:

mat =
[[1, 2, 3, 2, 0, 1, 2],
 [0, 1, 0, 0, 0, 3, 0],
 [0, 0, 1, 0, 0, 0, 0],
 [5, 0, 0, 1, 0, 0, 0],
 [7, 0, 0, 0, 1, 0, 0],
 [8, 0, 0, 0, 0, 1, 0],
 [1, 0, 0, 0, 0, 0, 0]]

פלט:

נשמרLn 1, Col 1

קלט:

mat =
[[1, 2, 3, 2, 0, 1, 2],
 [0, 1, 0, 0, 0, 3, 0],
 [0, 0, 1, 0, 0, 0, 0],
 [5, 0, 0, 1, 0, 0, 0],
 [7, 0, 0, 0, 1, 0, 0],
 [8, 0, 0, 0, 0, 1, 0],
 [1, 0, 0, 0, 0, 0, 0]]

הפלט המבוקש: