פורסם 2009 ביוני 2216 שנים שלום לכולם קיבלתי את השאלה הזו באופ ישבתי עליה אולי 5 שעות ולא הצלחתי למצוא את הפתרון אשמח אם תעזרו לי. בעיקרון הבנתי שהמערך בנוי בצורה "מקופלת" ממוינת נסיתי איכשהו לנסות לשלב את זה בעזרת חיפוש בינארי ובכל מיני דרכים אחרות אך לא הצלחתי.. תודה לעוזרים..
פורסם 2009 ביוני 2216 שנים קודם כל, כתוב פונקציית עזר, שבה תעביר כארגומנט מספרים המציינים באיזה תת-מטריצה אתה מחפש כרגע, ומה הגודל שלה.הפונקציה find כמובן תקרא לפונקציה הזו.עכשיו, תבדוק באיזה מהרבעים של המטריצה הנוכחית המספר הנתון יכול להימצא. תזכור שהאיבר הגדול ביותר במטריצה תמיד יהיה בפינה הימנית תחתונה, והקטן ביותר יהיה בפינה השמאלית העליונה. אחרי שמצאת, תקרא בצורה רקורסיבית לפונקציה על תת המטריצה שמצאת.
פורסם 2009 ביוני 2316 שנים מחבר תודה על התגובה..אבל לא הצלחתי להבין את תשובתךאיך אני אדע באיזה תת מטריצה לחפש את המספר?איך אני בודק באיזה תת מטריצה נמצא המספר?אין לי אפשרות להשתמש בלולאותאני צריך לעבור על כל תת מטריצה? זה לא הגיונייכול להינתן לי מטריצה בגודל 8 על 8
פורסם 2009 ביוני 2316 שנים לא צריך לעבור על כל תת מטריצה, מספיק לעבור על האיברים שבפינות.תסתכל לדוגמה על המטריצה בגודל 4x4 שנתונה בשאלה כדוגמה למטריצה ממוינת.נניח שאני מחפש את המספר 20.אז אני אעבור על ארבעת הרביעים, ועבור כל רביע אני אשווה בין האיבר השמאלי העליון והאיבר הימני התחתון למספר שאני מחפש.אם 20 שווה לאחד מהם, אז כמובן מצאתי ואני יכול להחזיר true.אם הוא ביניהם, זה אומר שאם המספר 20 נמצא במטריצה, הוא בהכרח נמצא ברביע הזה.ואכן, המספרים בפינות של הרביע השלישי הם 13 ו-24, ו-20 נמצא ביניהם (ואכן 20 נמצא ברביע הזה).כמובן, אם המספר לא יכול להיות באף רביע, נחזיר false.כמובן יש עוד ייעולים קטנים (אם לדוגמה המספר שאנחנו מחפשים קטן מהמספר השמאלי העליון ברביע הראשון, אז הוא בבירור לא נמצא באף אחד מהרביעים).
פורסם 2009 ביוני 2316 שנים הפיתרון דומה לבעיה של אריה במדבר.פיתרון רקורסיבי לבעיות האלו הוא בדרך כלל פיתרון של חיפוש במיקום כלשהו - בדיקה אם הוא גדול\קטן או שווה למספר המבוקשואז שליחה לפונ' את אותו מערך בחצי גודל.
פורסם 2009 ביוני 2316 שנים מחבר לא צריך לעבור על כל תת מטריצה, מספיק לעבור על האיברים שבפינות.תסתכל לדוגמה על המטריצה בגודל 4x4 שנתונה בשאלה כדוגמה למטריצה ממוינת.נניח שאני מחפש את המספר 20.אז אני אעבור על ארבעת הרביעים, ועבור כל רביע אני אשווה בין האיבר השמאלי העליון והאיבר הימני התחתון למספר שאני מחפש.אם 20 שווה לאחד מהם, אז כמובן מצאתי ואני יכול להחזיר true.אם הוא ביניהם, זה אומר שאם המספר 20 נמצא במטריצה, הוא בהכרח נמצא ברביע הזה.ואכן, המספרים בפינות של הרביע השלישי הם 13 ו-24, ו-20 נמצא ביניהם (ואכן 20 נמצא ברביע הזה).כמובן, אם המספר לא יכול להיות באף רביע, נחזיר false.כמובן יש עוד ייעולים קטנים (אם לדוגמה המספר שאנחנו מחפשים קטן מהמספר השמאלי העליון ברביע הראשון, אז הוא בבירור לא נמצא באף אחד מהרביעים).כל מה שכתבת אני מבין..אני פשוט לא מצליח לממש את זה בשפה.כלומר איך אני אכתוב לעבור על איבר השמאלי העליון והאיבר הימני התחתון ב4 תת מטריצות?אם היו לי 8 תת מטריצות? או יותר?אני פשוט לא מצליח לכתוב את התוכניתכל מה שהסברת הבנתי פשוט אני לא מצליח להבין איך לכתוב את זה(אני לא מצפה שתרשום לי את הפתרון ברור)תודה לך על ההסבר.
פורסם 2009 ביוני 2316 שנים אבל זו כל הפואנטה ברקורסיה. אתה לא צריך לכתוב את זה עבור 16 תת מטריצות, אלא רק עבור 4.בוא קח אלגוריתם קצת יותר פשוט. הפונקציה שלך מקבלת מטריצה כלשהי ומספר x.קודם כל, תשווה את x לשני האיברים שבפינות השמאלית העליונה והימנית התחתונה.אם הוא שווה לאחד מהם, אז תחזיר true (כי בבירור x נמצא במטריצה).אם הוא קטן מהשמאלי העליון או גדול מהימני התחתון, אז בבירור הוא לא נמצא במטריצה (כי האיבר השמאלי העליון הוא הקטן ביותר, והימני התחתון הוא הגדול ביותר). לכן תחזיר false.אם הוא ביניהם, זה אומר שהוא (אולי) נמצא באחת מתתי המטריצות.אז קרא לפונקציה באופן רקורסיבי עבור כל אחת מתתי המטריצות, ותחזיר את ה-or של התוצאות. אם הוא נמצא באחת מתתי המטריצות, אז הקריאה לפונקציה עבור תת המטריצה הזו אמורה להחזיר true.קפיש?
פורסם 2009 ביוני 2316 שנים מחבר אני קורא לפונקציה הזו באופן רקורסיבי או לפונקצית עזר?איך אני קורא כל פעם לתת מטריצה אחרת?
פורסם 2009 ביוני 2316 שנים מחבר תראה מה שעשית בודק באיזה רביע נמצא מספר מסוים ומחזיר לי את מספר הרביעאיך אני מריץ רקורסיה על על הרביע הזה על מנת למצוא מספרז"א אני יכול לעשות 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) ); } }
פורסם 2009 ביוני 2316 שנים לא הבנתי מה אתה עושה שם. מה הקטע עם הסכום? הפונקציה שלך רק צריכה להחזיר אמת או שקר.ולא הבנת אותי נכון. תשכח מהפונקציה find שאמרו לך לממש.תממש את הפונקציה הזו:boolean find(int x, int[][] arr, int row, int col, int size)ש-size מציין את גודל תת המטריצה, ו-row,col מציינים את האינדקסים של הפינה השמאלית העליונה של תת המטריצה הנוכחית.קריאה רקורסיבית צריכה להקטין את size פי 2 (כי אתה עובר ממטריצה בגודל 16 על 16, לדוגמה, למטריצה בגודל 8 על 8 ), ותחשוב איזה ערכים של row ו-col אתה צריך לתת.
פורסם 2009 ביוני 2316 שנים מחבר הקטע עם הסכום זה בעצם מחזיר לי את הרביע שבו (אולי) נמצא המספראני לא הצלחתי להבין מה זה size? איך זה עוזר לי?גודל תת מטריצה אתה מתכוון 2*2 אז 4?לא חושב שהבנתי אותך עם הsize.
פורסם 2009 ביוני 2316 שנים סתם כהערה, השאלה הזאת ניתנה לי במבחן בקורס הנ"ל. השתמשתי בפיתרון ששניצל הציע.
ארכיון
דיון זה הועבר לארכיון ולא ניתן להוסיף בו תגובות חדשות.