פורסם 2009 בנובמבר 1816 שנים שלום לכולם. קיבלנו שאלה שאני לא מצליח לפתור כל כך.נתונה מטריצה mat מסוג INT שמספריה כבר ממוינים. ז"א בכל שורה ובכל עמודה המספרים ממוינים בסדר עולה - מהקטן לגדול. בכל שורה בנפרד ובכל עמודה בנפרד אין מספר שמופיע יותר מפעם אחת. הפעולה מחזירה את מספר הפעמים שהמספר X מופיע במטריצה.הפעולה הולכת ככה:public static int matrizh (int [] [] mat ,int x)int count =0;for (int i=0; i<mat.length ; i++)for (int j=0;j<mat.length ; j++)if (mat[i] [j] ==x counter ++;return counter;עכשיו השאלה היא :הצע דרך לשיפור יעילות הפעולה בסדר גודל . אין צורך לכתוב אלא רק להציע.יש למישהו רעיון?אגב עוד שאלה קטנה, כשרשום MAT.LENTGH אז מאיפה הוא לוקח את האורך מהשורות או מהמעודות (כבר שחכתי)...תודה לכולם!
פורסם 2009 בנובמבר 1816 שנים אתה אמור לרשום mat.GetLength(X) כאשר אם X זה 0 אז זה שורות ואם X זה 1 אז עמודות.אם כל מספר מופיע פעם אחת אתה יכול לנצל את זה שהמערך ממוין, במידה והגעת למספר גדול מהמספר שאתה מחפש אתה פשוט קופץ לסיבוב הבא של הלולאה החיצונית עם break
פורסם 2009 בנובמבר 1816 שנים geniaXP - מה שאמרת נכון אם זה מערך דו-מימדי, כלומר [,]int. במקרה הנתון זה מערך של מערכים.הפתרון שלך אמנם מייעל את העסק, אבל לא בסדר גודל (סיבוכיות). לדוגמה, אם כל האיברים במערך קטנים מ-X אז עדיין תעבור על כל המערך.קודם כל, תחשוב מה הסיבוכיות של המימוש הנוכחי, כדי שיהיה לך למה להשוות.עכשיו, תתחיל מבעיה יותר פשוטה - במקום מטריצה תיקח מערך פשוט ממויין, ותמצא דרך יעילה לספור כמה פעמים מופיע בו x. אחרי שתצליח את זה תחשוב איך מרחיבים את הבעיה.ולגבי השאלה הנוספת: המטריצה הזו פשוט מערך של מערכים - אין לה מושג של שורות ושל עמודות (זה כבר עניין של תצוגה, ואם אתה מדפיס מטריצה כזו אז אפשר גם ככה וגם ככה). mat.length זה פשוט האורך של המערך הזה. כל איבר ב-mat הוא מערך בפני עצמו, ויש לו אורך משלו. בעקרון, הלולאה של j הייתה צריכה להיות משהו כזה:for (int j = 0 ; j < mat[i].length ; j++)כי ייתכן שהמטריצה לא מלבנית.
פורסם 2009 בנובמבר 1816 שנים מחבר האמת שבשאלה היה רשום מטריצה ריבועית ומשום מה השמטתי את הפרט הזה. עדיין לא הבנתי ממש את הlentgh פה...לגבי מערך פשוט ממויין אני יודע איך לעשות זאת בדרך יעילה. זה כתוב בספר, צריך לחלק כל פעם את המערך ואז זה לא בעיה. אבל איך אפשר לעשות את זה במטריצה?וכשהם אומרים סדר גודל אז הם מתכוונים כיאלו שבמקום שזה יהיה O(n^2)זה יהיה משהו יותר קטן. לא קשור כמה n גדול . ולכן גם אם תעשה לולאת while שתעצר באמצע ולא תעבור על כל המערך זה לא ישפר את סדר הגודל , נכון?
פורסם 2009 בנובמבר 1816 שנים מה לא הבנת? המטריצה הזו היא לא מערך דו מימדי. היא מערך של מערכים.כלומר, היא מערך של אובייקטים שכל אחד מהם הוא מערך של int. ה-length שך mat הוא פשוט האורך של המערך הראשי. אם אתה רוצה את האורך של אחד מתתי המערכים אז אתה צריך לגשת ל-mat[i ].length.לגבי סדר הגודל - בדיוק.תזכור שהפתרון של המטריצה, בסופו של דבר, סופר את ה-xים בכל שורה בנפרד וסוכם את הכל ביחד (הוא רק לא עושה את זה בסדר כזה). אם ייעלת את סדר הגודל לכל שורה בנפרד, ייעלת אותו לכל המטריצה (אבל כנראה יש דרך עוד יותר יעילה מזה).
פורסם 2009 בנובמבר 1816 שנים מחבר מה זאת אומרת מערך של מערכים.מה זה אובייקטים בכלל? אתה מדבר בשפה גבוה ואני לא מצליח להבין כל כך...אולי אתה מתכוון שכיאלו הם היכנסו 2 מערכים פשוטים נפרדים של קשורים אחד לשני?
פורסם 2009 בנובמבר 1816 שנים לא 2 מערכים.נניח שהמטריצה שלך היא בגודל n על n. זה אומר ש-mat הוא n מערכים, שכל אחד מהם הוא מערך בגודל n.כמו שאמרתי קודם, אין משמעות לאורך ולרוחב, כי זה עניין של בחירה שרירותית (אתה יכול להתייחס לאינדקס הראשון כאורך ולשני כרוחב, או להיפך).אבל אם לא למדת על אובייקטים, אז עדיף שלא להתעמק בזה עדיין.
פורסם 2009 בנובמבר 1816 שנים מחבר אם לדוגמא יש לי מטריצה כזו:12 10 8 423 20 12 925 24 11 10אז מה הlentgh שלה?
פורסם 2009 בנובמבר 1816 שנים שוב, זה עניין שרירותי - אתה יכול להחליט שהאינדקס הראשון הוא השורות והשני הוא העמודות (ואז זו מטריצה שמימדיה הם 3 על 4, כלומר mat.length == 3), ואתה יכול להחליט שהאינדקס השני הוא השורות והראשון הוא העמודות (ואז זו מטריצה שמימדיה הם 4 על 3, כלומר mat.length == 4).
פורסם 2009 בנובמבר 1816 שנים מחבר ואי אני לא ממש מבין את זה...האמת שהשאלה עוד ממשיכה, הם נותנים עוד פעולה: public static int cout2(int[][] mat, int x) { int counter = 0; int n = mat.Length; for (int i = 0; i < mat.Length; i++) { for (int j = 0; j < n; j++) if (mat[i][j] == x) counter++; n = j - 1; } return counter; }ואז יש שאלה האם השינוי שערכנו באלגוריתם COUT2 גרר ייעול האלגוריתם? נמק והוכח. בתשובתך התייחס למקרה הכולל וכן למקרים פרטניים.בתכלס אם אתה מבצע נוסחה של ייעלות יבשה בCOUT1 זה יוצא 3n^2+3n+3ובcout2 3n^2+4n+4 ואפילו אם תיקח n קטן (אפילו 1) תמיד cout1 יהיה יותר יעיל , כל שכן בn גדול.אבל אני בכלל לא מבין איך לרוץ על הפעולה הזאת.. אתה יכול אולי לתת לי דוגמא קצרה של מערך\ים שאיתו אני אנסה לרוץ על הפעולה...?
פורסם 2009 בנובמבר 1816 שנים אני תמה לגבי זה, כי cout2 פשוט לא מבצע את האלגוריתם נכון (הם במטריצה יש רק x אחד בפינה האחרונה האחרונה, הוא לא יגיע אליו ולא יספור אותו).
פורסם 2009 בנובמבר 1816 שנים exztהאם למדתם רקורסיה וחיפוש בינארי?אם כן תחשוב איך זה יכול להשתלב בבעיה שלך.
פורסם 2009 בנובמבר 1916 שנים geniaXP - מה שאמרת נכון אם זה מערך דו-מימדי, כלומר [,]int. במקרה הנתון זה מערך של מערכים.הפתרון שלך אמנם מייעל את העסק, אבל לא בסדר גודל (סיבוכיות). לדוגמה, אם כל האיברים במערך קטנים מ-X אז עדיין תעבור על כל המערך.קודם כל, תחשוב מה הסיבוכיות של המימוש הנוכחי, כדי שיהיה לך למה להשוות.עכשיו, תתחיל מבעיה יותר פשוטה - במקום מטריצה תיקח מערך פשוט ממויין, ותמצא דרך יעילה לספור כמה פעמים מופיע בו x. אחרי שתצליח את זה תחשוב איך מרחיבים את הבעיה.אז אפשר לעשות חיפוש בינארי
פורסם 2009 בנובמבר 1916 שנים נכון, וזה הייעול שאני מציע.בעקרון אפשר לעשות חיפוש בינארי על כל שורה בנפרד, ואז לשפר מסיבוכיות של n^2 ל-nlogn.אבל אני מניח שהם מחפשים משהו יותר חכם מזה (אפשר לעשות איזה חיפוש בינארי משולב על השורות והעמודות או משהו כזה).
פורסם 2009 בנובמבר 1916 שנים שניצל בקורס המבוא שלי שיפור מ N^2 ל NLOGN נחשב שיפור בסדר גודל .ואם אני לא טועה אי אפשר לפתור את זה בפחות מזה כי המטריצה הזאת לא ממוינת .
ארכיון
דיון זה הועבר לארכיון ולא ניתן להוסיף בו תגובות חדשות.