שלום לכולם

קיבלתי את השאלה הזו באופ

ישבתי עליה אולי 5 שעות ולא הצלחתי למצוא את הפתרון

אשמח אם תעזרו לי.

בעיקרון הבנתי שהמערך בנוי בצורה "מקופלת" ממוינת נסיתי איכשהו לנסות לשלב את זה

בעזרת חיפוש בינארי ובכל מיני דרכים אחרות אך לא הצלחתי..

תודה לעוזרים..

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

הפונקציה find כמובן תקרא לפונקציה הזו.

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

תודה על התגובה..

אבל לא הצלחתי להבין את תשובתך

איך אני אדע באיזה תת מטריצה לחפש את המספר?

איך אני בודק באיזה תת מטריצה נמצא המספר?

אין לי אפשרות להשתמש בלולאות

אני צריך לעבור על כל תת מטריצה? זה לא הגיוני

יכול להינתן לי מטריצה בגודל 8 על 8

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

תסתכל לדוגמה על המטריצה בגודל 4x4 שנתונה בשאלה כדוגמה למטריצה ממוינת.

נניח שאני מחפש את המספר 20.

אז אני אעבור על ארבעת הרביעים, ועבור כל רביע אני אשווה בין האיבר השמאלי העליון והאיבר הימני התחתון למספר שאני מחפש.

אם 20 שווה לאחד מהם, אז כמובן מצאתי ואני יכול להחזיר true.

אם הוא ביניהם, זה אומר שאם המספר 20 נמצא במטריצה, הוא בהכרח נמצא ברביע הזה.

ואכן, המספרים בפינות של הרביע השלישי הם 13 ו-24, ו-20 נמצא ביניהם (ואכן 20 נמצא ברביע הזה).

כמובן, אם המספר לא יכול להיות באף רביע, נחזיר false.

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

הפיתרון דומה לבעיה של אריה במדבר.

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

ואז שליחה לפונ' את אותו מערך בחצי גודל.

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

תסתכל לדוגמה על המטריצה בגודל 4x4 שנתונה בשאלה כדוגמה למטריצה ממוינת.

נניח שאני מחפש את המספר 20.

אז אני אעבור על ארבעת הרביעים, ועבור כל רביע אני אשווה בין האיבר השמאלי העליון והאיבר הימני התחתון למספר שאני מחפש.

אם 20 שווה לאחד מהם, אז כמובן מצאתי ואני יכול להחזיר true.

אם הוא ביניהם, זה אומר שאם המספר 20 נמצא במטריצה, הוא בהכרח נמצא ברביע הזה.

ואכן, המספרים בפינות של הרביע השלישי הם 13 ו-24, ו-20 נמצא ביניהם (ואכן 20 נמצא ברביע הזה).

כמובן, אם המספר לא יכול להיות באף רביע, נחזיר false.

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

כל מה שכתבת אני מבין..

אני פשוט לא מצליח לממש את זה בשפה.

כלומר איך אני אכתוב לעבור על איבר השמאלי העליון והאיבר הימני התחתון ב4 תת מטריצות?

אם היו לי 8 תת מטריצות? או יותר?

אני פשוט לא מצליח לכתוב את התוכנית

כל מה שהסברת הבנתי פשוט אני לא מצליח להבין איך לכתוב את זה(אני לא מצפה שתרשום לי את הפתרון ברור)

תודה לך על ההסבר.

אבל זו כל הפואנטה ברקורסיה. אתה לא צריך לכתוב את זה עבור 16 תת מטריצות, אלא רק עבור 4.

בוא קח אלגוריתם קצת יותר פשוט. הפונקציה שלך מקבלת מטריצה כלשהי ומספר x.

קודם כל, תשווה את x לשני האיברים שבפינות השמאלית העליונה והימנית התחתונה.

אם הוא שווה לאחד מהם, אז תחזיר true (כי בבירור x נמצא במטריצה).

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

אם הוא ביניהם, זה אומר שהוא (אולי) נמצא באחת מתתי המטריצות.

אז קרא לפונקציה באופן רקורסיבי עבור כל אחת מתתי המטריצות, ותחזיר את ה-or של התוצאות. אם הוא נמצא באחת מתתי המטריצות, אז הקריאה לפונקציה עבור תת המטריצה הזו אמורה להחזיר true.

קפיש?

אני קורא לפונקציה הזו באופן רקורסיבי או לפונקצית עזר?

איך אני קורא כל פעם לתת מטריצה אחרת?

תקרא את ההודעה הראשונה שלי.

אוקיי תודה רבה לך.

תראה מה שעשית בודק באיזה רביע נמצא מספר מסוים ומחזיר לי את מספר הרביע

איך אני מריץ רקורסיה על על הרביע הזה על מנת למצוא מספר

ז"א אני יכול לעשות 4 if-ים ולשלוח לפוקנציה עם הערכים למשל

אם זה ברביע 1: אז row=0 col=0

אם רביע 2 אז: row=2 col=0

רביע 3: row=0 col=2 וכ'ו.. ואז שיעשה רקורסיה

אבל אם יש לי מטריצה בגודל 8 על 8 או 16 על 16 איך אני פותר את הבעיה הזו

והאם עשית מה שאתה חשבת עליו מקודם בכלל?(בדקתי את מה שעשית זה עובד)

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

ועוד משהו באיזו סיבוכיות זה יהיה?

תודה.

הנה הקוד:

public static boolean find (int x, int [ ][ ] arr) {
  if ( (x == arr[0][0] ) || (x == arr[arr.length-1] [ arr.length-1] ) )
      return true;
   if ( (x <arr[0][0] ) || (x > arr[arr.length-1] [ arr.length-1] ) ) 
    return false;

    int row=0,col=0,sum=1;
         int i= kok(arr,x,row,col,sum);
         if (i>0) {
              System.out.println(i);
         return true;
        }
         return false;
        }

        public static int kok( int [ ][ ] arr, int x, int row, int col, int sum) {

          if( ( arr[row][col] <= x) && ( arr[row+1][col+1] >=x) )
          {

            return sum;
          }
          else
             if( row!= arr.length-2)
                return (0+ kok(arr,x,row+2,col,sum+1) );
             else
             {
               row=0;
               return (0+kok(arr,x,row,col+2,sum+1) );
              }
            }

לא הבנתי מה אתה עושה שם. מה הקטע עם הסכום? הפונקציה שלך רק צריכה להחזיר אמת או שקר.

ולא הבנת אותי נכון. תשכח מהפונקציה find שאמרו לך לממש.

תממש את הפונקציה הזו:

boolean find(int x, int[][] arr, int row, int col, int size)

ש-size מציין את גודל תת המטריצה, ו-row,col מציינים את האינדקסים של הפינה השמאלית העליונה של תת המטריצה הנוכחית.

קריאה רקורסיבית צריכה להקטין את size פי 2 (כי אתה עובר ממטריצה בגודל 16 על 16, לדוגמה, למטריצה בגודל 8 על 8 ), ותחשוב איזה ערכים של row ו-col אתה צריך לתת.

הקטע עם הסכום זה בעצם מחזיר לי את הרביע שבו (אולי) נמצא המספר

אני לא הצלחתי להבין מה זה size? איך זה עוזר לי?

גודל תת מטריצה אתה מתכוון 2*2 אז 4?

לא חושב שהבנתי אותך עם הsize.

מה זה משנה? מה שנוח לך לעבוד איתו.

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