פורומים באוניברסיטת בן-גוריון בנגב

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

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

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

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

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

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

אם באמת לילד שבחר 3 חברים אין אפשרות לראות את שלושתם בטור אז מה המטרה בסעיף ג?כי כאן מדברים על כך שלכולם יש 3 חברים

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

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

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

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

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

פורומים באוניברסיטת בן-גוריון בנגב

קיץ 2004

קיץ 2004

Re: קיץ 2004

Re: קיץ 2004

Re: קיץ 2004

Re: קיץ 2004

מי מחובר