אתה משתמש בדפדפן מיושן. יתכן והאתר הנוכחי יוצג באופן שגוי, כמו כן אתרים אחרים ברשת.
אנא שדרג את הדפדפן או השתמש בדפדפן חילופי.
אנא שדרג את הדפדפן או השתמש בדפדפן חילופי.
עזרה במבני נתונים
- פותח הנושא benda2109
- פורסם בתאריך
תשובות
1) אפשר למיין מספרים טבעיים החסומים מלמעלה ע"י counting sort בזמן לינארי . ברגע שקיבלת n מספרים אז n בחזקת 100 הוא גודל חסום וידוע 2) תחשוב על המקרה שאתה מנסה להכניס סדרה שהיא כבר ממויינת לעץ חיפוש בינארי. כמה זמן תקח הכנסה ? 3) תבנה מערך חדש בגודל המתאים. תאתחל שלושה פוינטרים להתחלה של שלושת המערכים. אם המספר שב A יותר קטן מ B אז תכתוב במערך החדש את המספר של A ותקדם את הפוינטר של A מקום קדימה (וגם את הפוינטר של המערך החדש) אחרת תעשה אותו דבר עם B 4) אם תרשום שורש n בצורה n בחזקת חצי ותזכור שקבועים נופלים בחישוב אסימפטוטי אז זה יהיה ברור
1) אפשר למיין מספרים טבעיים החסומים מלמעלה ע"י counting sort בזמן לינארי . ברגע שקיבלת n מספרים אז n בחזקת 100 הוא גודל חסום וידוע 2) תחשוב על המקרה שאתה מנסה להכניס סדרה שהיא כבר ממויינת לעץ חיפוש בינארי. כמה זמן תקח הכנסה ? 3) תבנה מערך חדש בגודל המתאים. תאתחל שלושה פוינטרים להתחלה של שלושת המערכים. אם המספר שב A יותר קטן מ B אז תכתוב במערך החדש את המספר של A ותקדם את הפוינטר של A מקום קדימה (וגם את הפוינטר של המערך החדש) אחרת תעשה אותו דבר עם B 4) אם תרשום שורש n בצורה n בחזקת חצי ותזכור שקבועים נופלים בחישוב אסימפטוטי אז זה יהיה ברור
בקשר ל-1
הגודל של המערך לא נחשב בדיוק כחסום כי הוא תלוי ב-n, והסיבוכיות של counting sort היא כמובן (O(n+k כשk הוא תחום המספרים, כך שבמקרה הזה הסיבוכיות בקאונטינג סורט תיהיה (O(n^100 לכל n. אני חושב שהפיתרון פה הוא להמיר את המספרים לבסיס n ואז להשתמש בradix-sort, כלומר למיין את המספרים לפי הספרות. כך הסיבוכיות תיהיה (O(100n - מיון לפי כל סיפרה יקח זמן לינארי בעזרת counting sort, ויש 100 ספרות למספר בבסיס n. סה"כ זה עדיין זמן לינארי.
הגודל של המערך לא נחשב בדיוק כחסום כי הוא תלוי ב-n, והסיבוכיות של counting sort היא כמובן (O(n+k כשk הוא תחום המספרים, כך שבמקרה הזה הסיבוכיות בקאונטינג סורט תיהיה (O(n^100 לכל n. אני חושב שהפיתרון פה הוא להמיר את המספרים לבסיס n ואז להשתמש בradix-sort, כלומר למיין את המספרים לפי הספרות. כך הסיבוכיות תיהיה (O(100n - מיון לפי כל סיפרה יקח זמן לינארי בעזרת counting sort, ויש 100 ספרות למספר בבסיס n. סה"כ זה עדיין זמן לינארי.
immortalus
New member
נוסחאות עצים
א) לא יודע מה איתכם, לנו הוכיחו כי עץ AVL מינימאלי הוא עץ פיבונאצי'. משמע מספר הצמתים נתונים ע"י מספרי פובונאצ'י של העומק. ב) נסה להשתמש ב-א'...
א) לא יודע מה איתכם, לנו הוכיחו כי עץ AVL מינימאלי הוא עץ פיבונאצי'. משמע מספר הצמתים נתונים ע"י מספרי פובונאצ'י של העומק. ב) נסה להשתמש ב-א'...
immortalus
New member
הגננת
א) הפתרון הדי טריביאלי פה הוא מערך עם תא לכל ילד שבתא הזה נספור כמה ילדים בחרו בו. יש לך מערך אחד של בחירות הילדים - כלומר לכל אינדקס רשומים 3 מספרים סידוריים (מספר סידורי לכל ילד 1..n) אתה רץ על המערך ולכל מספר סידורי שאתה נתקל בו אתה מעלה מונה במערך אחר שם יש תא לכל ילד = מונה. בסוף הריצה על מערך הבחירות (כמובן בזמן ליניארי) אתה יכול למצוא מקסימום במערך המונים בזמן ליניארי וזה יהיה הילד החברותי ביותר. ב) לא ברורה הכוונה... מה ז"א יכול לראות?! מסדרים בשלשות? לפי גובה?! WTF? ג) שוב, הכוונה לא ברורה, מצטער.. ד) לא יודע אם למדתם גרפים, אבל אני הייתי בונה פה גרף שלכל ילד מתאים צומת, ויש קשת מצומת i לצומת j אם הם חברים. (הגרף כנראה מכוון כי לא נתון שהיחס הוא הדדי). עכשיו הייתי מריץ עליו אלגוריתם למציאת שורש לעץ (2 הרצות של DFS) סה"כ: בניית גרף ב-(O(n וכל DFS רץ ב-(O(n אז אתה מקבל אלגוריתם ליניארי, כלומר בין היתר (o(n²..
א) הפתרון הדי טריביאלי פה הוא מערך עם תא לכל ילד שבתא הזה נספור כמה ילדים בחרו בו. יש לך מערך אחד של בחירות הילדים - כלומר לכל אינדקס רשומים 3 מספרים סידוריים (מספר סידורי לכל ילד 1..n) אתה רץ על המערך ולכל מספר סידורי שאתה נתקל בו אתה מעלה מונה במערך אחר שם יש תא לכל ילד = מונה. בסוף הריצה על מערך הבחירות (כמובן בזמן ליניארי) אתה יכול למצוא מקסימום במערך המונים בזמן ליניארי וזה יהיה הילד החברותי ביותר. ב) לא ברורה הכוונה... מה ז"א יכול לראות?! מסדרים בשלשות? לפי גובה?! WTF? ג) שוב, הכוונה לא ברורה, מצטער.. ד) לא יודע אם למדתם גרפים, אבל אני הייתי בונה פה גרף שלכל ילד מתאים צומת, ויש קשת מצומת i לצומת j אם הם חברים. (הגרף כנראה מכוון כי לא נתון שהיחס הוא הדדי). עכשיו הייתי מריץ עליו אלגוריתם למציאת שורש לעץ (2 הרצות של DFS) סה"כ: בניית גרף ב-(O(n וכל DFS רץ ב-(O(n אז אתה מקבל אלגוריתם ליניארי, כלומר בין היתר (o(n²..
קודם כל המון תודה
שנית... אני גם לא מבין את הכוונה בב' ובג' לגביי א- זה גם מה שאני חשבתי. לגביי ד'- קודם כל שאלה כללית. הרי ברור שמבקשים למצוא אם הגרף קשיר. השאלה מה נותן לי תשובה לגביי מחלקות קשירות? BFS או DFS? אני לא מבין איך אתה מגיע לזמן ריבועי. הרי בניית גרף O של N. וDFS או BFS זה O של E+V. וE הוא לכל היותר 3/2V (סכום דרגות בגרף שווה ל2 E). או שפספסתי משהו
שנית... אני גם לא מבין את הכוונה בב' ובג' לגביי א- זה גם מה שאני חשבתי. לגביי ד'- קודם כל שאלה כללית. הרי ברור שמבקשים למצוא אם הגרף קשיר. השאלה מה נותן לי תשובה לגביי מחלקות קשירות? BFS או DFS? אני לא מבין איך אתה מגיע לזמן ריבועי. הרי בניית גרף O של N. וDFS או BFS זה O של E+V. וE הוא לכל היותר 3/2V (סכום דרגות בגרף שווה ל2 E). או שפספסתי משהו
immortalus
New member
לגבי ד'
מה שאתה בעצם מחפש, לאחר בניית הגרף, זה צומת שהוא שורש - כלומר צומת שקיים ממנו מסלול מכוון לכל צומת אחר בגרף. הסיבה לכך היא די טריביאלית - אם קיים צומת כזו הרי שהילד אותו מייצג הצומת יפעיל 'תגובת שרשרת' שתקרא לכל שאר הילדים. נשאלת השאלה איך למצא גרף כזה? וכבן קיים אלגוריתם DFS. האלגוריתם נותן לכל צומת זמן תחילת הטיפול בו וזמן הסיום. בנוסף הוא יוצר לך יער של עצים. אם חוזר עץ יחיד, הרי שמצאנו שורש. אחרת, הרצה של האלגוריתם על שורש העץ האחרון ביער שחזר יחזיר לך עץ או יער, כשהוא יחזיר עץ אם ורק אם הצומת הוא שורש. אתה יכול לקרוא על זה, כולל הוכחת נכונות כאן: http://webcourse.cs.technion.ac.il/234247/Spring2008/ho/WCFiles/recitation%203%20-%20DFS%20and%20topological%20sorting.doc לקראת סוף עמוד 3. יש לך n צמתים, צומת לכל ילד, ו-3 קשתות שיוצאות מכל ילד ולכן יש לך 3n קשתות. סה"כ DFS רץ ב- (O(V+E) = O(4n) = O(n זה בין היתר גם (O(n^2 (באופן טריביאלי)
מה שאתה בעצם מחפש, לאחר בניית הגרף, זה צומת שהוא שורש - כלומר צומת שקיים ממנו מסלול מכוון לכל צומת אחר בגרף. הסיבה לכך היא די טריביאלית - אם קיים צומת כזו הרי שהילד אותו מייצג הצומת יפעיל 'תגובת שרשרת' שתקרא לכל שאר הילדים. נשאלת השאלה איך למצא גרף כזה? וכבן קיים אלגוריתם DFS. האלגוריתם נותן לכל צומת זמן תחילת הטיפול בו וזמן הסיום. בנוסף הוא יוצר לך יער של עצים. אם חוזר עץ יחיד, הרי שמצאנו שורש. אחרת, הרצה של האלגוריתם על שורש העץ האחרון ביער שחזר יחזיר לך עץ או יער, כשהוא יחזיר עץ אם ורק אם הצומת הוא שורש. אתה יכול לקרוא על זה, כולל הוכחת נכונות כאן: http://webcourse.cs.technion.ac.il/234247/Spring2008/ho/WCFiles/recitation%203%20-%20DFS%20and%20topological%20sorting.doc לקראת סוף עמוד 3. יש לך n צמתים, צומת לכל ילד, ו-3 קשתות שיוצאות מכל ילד ולכן יש לך 3n קשתות. סה"כ DFS רץ ב- (O(V+E) = O(4n) = O(n זה בין היתר גם (O(n^2 (באופן טריביאלי)
נסיון להבין את ב' וג'
אני חושב שהכוונה כאן היא לטור שבו כולם עומדים אחד אחרי השני, כך שאתה יכול לראות רק את אלה שעומדים לפניך. אם אכן זו הכוונה, הפתרון לב' יהיה מתורת הגרפים, נצייר גרף שבו קיימת קשת מכוונת מכל ילד לכל אחד מחבריו, כעת נריץ אלגוריתם שימצא האם הגרף הוא א-ציקלי (DFS לדוגמא). אם אכן הגרף הוא אציקלי, אז ניתן לעשות לו מיון טופולוגי, בזמן לינארי. ולסדר את הטור, ע"פ סדר המיון. אם הגרף לא א-ציקלי, לא ניתן לעשות לו מיון טופולוגי, ולכן לא ניתן לסדר אותו בטור כזה. לגבי ג', התשובה ברורה, בגרף א-ציקלי, חייב להיות לפחות צומת אחד שאין לו קשתות יוצאות. ואם לכל ילד יש 3 חברים, אז לכל הצמתים יש 3 קשתות יוצאות, ולכן הגרף לא א-ציקלי. הסבר נוסף, אם יש לנו טור, מישהו יהיה חייב להיות בראש הטור. אותו ילד שיעמוד בראש הטור לא יוכל לראות אף אחד מחבריו, לכן, אם יהיו לו 3 חברים, הוא לא יוכל לראות אף אחד מהם. ולכן לא נוכל לסדר טור כזה.
אני חושב שהכוונה כאן היא לטור שבו כולם עומדים אחד אחרי השני, כך שאתה יכול לראות רק את אלה שעומדים לפניך. אם אכן זו הכוונה, הפתרון לב' יהיה מתורת הגרפים, נצייר גרף שבו קיימת קשת מכוונת מכל ילד לכל אחד מחבריו, כעת נריץ אלגוריתם שימצא האם הגרף הוא א-ציקלי (DFS לדוגמא). אם אכן הגרף הוא אציקלי, אז ניתן לעשות לו מיון טופולוגי, בזמן לינארי. ולסדר את הטור, ע"פ סדר המיון. אם הגרף לא א-ציקלי, לא ניתן לעשות לו מיון טופולוגי, ולכן לא ניתן לסדר אותו בטור כזה. לגבי ג', התשובה ברורה, בגרף א-ציקלי, חייב להיות לפחות צומת אחד שאין לו קשתות יוצאות. ואם לכל ילד יש 3 חברים, אז לכל הצמתים יש 3 קשתות יוצאות, ולכן הגרף לא א-ציקלי. הסבר נוסף, אם יש לנו טור, מישהו יהיה חייב להיות בראש הטור. אותו ילד שיעמוד בראש הטור לא יוכל לראות אף אחד מחבריו, לכן, אם יהיו לו 3 חברים, הוא לא יוכל לראות אף אחד מהם. ולכן לא נוכל לסדר טור כזה.
Copyright©1996-2021,Tapuz Media Ltd. Forum software by XenForo® © 2010-2020 XenForo Ltd.