קיץ 2004

מנהל: TA_Isana

קיץ 2004

הודעהעל ידי zoran » 08:29 14/07/2010

שאלה 2 ב
"תאר אלגוריתם לינארי המסדר את הילדים בטור כך שכל אחד רואה את החברים הטובים
ביותר שציין ברשימה, או מכריז 'אי אפשר' במידה וסדר כזה לא קיים."
איזה טווח נחשב "לראות" את החברים"?נניח שלילד יש שלושה חברים אז בהכרח יהיה חבר אחד שלא צמוד אליו. כלומר לראות משמעו מרחק של לכל היותר ילד אחד ממנו?
zoran
 
הודעות: 30
הצטרף: 21:18 10/11/2009

Re: קיץ 2004

הודעהעל ידי TA_Yoni » 10:52 14/07/2010

אינני מכיר את השאלה, לכן הענה בהסתייגות.
לעניות דעתי מדובר רק בחברים שצמודים אליו. שים לם כי בשאלה הגננת "ביקשה מכל ילד רשימה של החברים הטובים ביותר שלו בגן (לכל היותר שלושה)" - יכול להיות ילד עם אפס חברים, חבר אחד וכו'
המתרגל יוני
TA_Yoni
 
הודעות: 236
הצטרף: 13:44 18/10/2009

Re: קיץ 2004

הודעהעל ידי zoran » 10:59 14/07/2010

"בגן ילדים הגננת ביקשה מכל ילד רשימה של החברים הטובים ביותר שלו בגן (לכל היותר שלושה).
א) ( 8 נק') תאר אלגוריתם לינארי העונה על השאלה, מי הילד החברותי ביותר בגן.
הילד החברותי ביותר הינו הילד שנבחר כחבר של מספר מקסימלי של ילדים בגן.
ב) ( 7 נק') תאר אלגוריתם לינארי המסדר את הילדים בטור כך שכל אחד רואה את החברים הטובים
ביותר שציין ברשימה, או מכריז 'אי אפשר' במידה וסדר כזה לא קיים.
ג) ( 7 נק') הוכח כי אם לכל הילדים יש בדיוק שלושה חברים, אזי סידור כזה אינו אפשרי.
ד) ( 8 נק') הגננת מצאה דרך לקרוא לכל הילדים מהחצר. היא תגיד לילד אחד לקרוא לכל החברים שלו
(מהרשימה) ואז להיכנס, כל חבר יקרא באופן רקורסיבי לחברים שלו שעדיין בחצר ויכנס וכו'.
שיענה לגננת האם ניתן בדרך זו להכניס את כל הילדים לגן, O(n2) הצע לגננת אלגוריתם בעלות
ובמידה וניתן, מאיזה ילד כדאי להתחיל."

אם באמת לילד שבחר 3 חברים אין אפשרות לראות את שלושתם בטור אז מה המטרה בסעיף ג?כי כאן מדברים על כך שלכולם יש 3 חברים
zoran
 
הודעות: 30
הצטרף: 21:18 10/11/2009

Re: קיץ 2004

הודעהעל ידי TA_Yoni » 15:49 14/07/2010

הכוונה שלי ב "אני לא מכיר את השאלה" לא הייתה שלא קראתי את השאלה , אלא שלא ראיתי אותה קודם לכן ואינני מכיר את הפתרון שלה.
מתוך הסתכלות שנייה בשאלה, יכול להיות כי הכוונה ב"רואה" היא את כל מי שנמצא לפניו בטור (שוב בהסתייגות, בדומה לשאלה עם הנקודות מהעבודת הבית שלכם).
בכל מקרה, סעיף ג' באמת נראה לי טריוואלי.
המתרגל יוני
TA_Yoni
 
הודעות: 236
הצטרף: 13:44 18/10/2009

Re: קיץ 2004

הודעהעל ידי Brk » 20:23 15/07/2010

TA_Yoni כתב:הכוונה שלי ב "אני לא מכיר את השאלה" לא הייתה שלא קראתי את השאלה , אלא שלא ראיתי אותה קודם לכן ואינני מכיר את הפתרון שלה.
מתוך הסתכלות שנייה בשאלה, יכול להיות כי הכוונה ב"רואה" היא את כל מי שנמצא לפניו בטור (שוב בהסתייגות, בדומה לשאלה עם הנקודות מהעבודת הבית שלכם).
בכל מקרה, סעיף ג' באמת נראה לי טריוואלי.

יש מצב לסוגים כאלה של שאלות במבחן? זה נראה מאוד לא קשור
סעיף ג' הוא טרוואלי מספיק להסתכל על שלושת החברים בסוף הטור ולהגיע למסקנה שיש להם פחות משלושה חברים בסתירה לטענה שלכול ילד יש בדיוק שלושה! נכון יוני?
Brk
 
הודעות: 87
הצטרף: 17:58 25/10/2009


חזור אל - מבני נתונים 2010

מי מחובר

משתמשים הגולשים בפורום זה: אין משתמשים רשומים ואורח אחד