דף 1 מתוך 1

קיץ 2004

נשלח: 09:29 14/07/2010
על ידי zoran
שאלה 2 ב
"תאר אלגוריתם לינארי המסדר את הילדים בטור כך שכל אחד רואה את החברים הטובים
ביותר שציין ברשימה, או מכריז 'אי אפשר' במידה וסדר כזה לא קיים."
איזה טווח נחשב "לראות" את החברים"?נניח שלילד יש שלושה חברים אז בהכרח יהיה חבר אחד שלא צמוד אליו. כלומר לראות משמעו מרחק של לכל היותר ילד אחד ממנו?

Re: קיץ 2004

נשלח: 11:52 14/07/2010
על ידי TA_Yoni
אינני מכיר את השאלה, לכן הענה בהסתייגות.
לעניות דעתי מדובר רק בחברים שצמודים אליו. שים לם כי בשאלה הגננת "ביקשה מכל ילד רשימה של החברים הטובים ביותר שלו בגן (לכל היותר שלושה)" - יכול להיות ילד עם אפס חברים, חבר אחד וכו'

Re: קיץ 2004

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

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

Re: קיץ 2004

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

Re: קיץ 2004

נשלח: 21:23 15/07/2010
על ידי Brk
TA_Yoni כתב:הכוונה שלי ב "אני לא מכיר את השאלה" לא הייתה שלא קראתי את השאלה , אלא שלא ראיתי אותה קודם לכן ואינני מכיר את הפתרון שלה.
מתוך הסתכלות שנייה בשאלה, יכול להיות כי הכוונה ב"רואה" היא את כל מי שנמצא לפניו בטור (שוב בהסתייגות, בדומה לשאלה עם הנקודות מהעבודת הבית שלכם).
בכל מקרה, סעיף ג' באמת נראה לי טריוואלי.
יש מצב לסוגים כאלה של שאלות במבחן? זה נראה מאוד לא קשור
סעיף ג' הוא טרוואלי מספיק להסתכל על שלושת החברים בסוף הטור ולהגיע למסקנה שיש להם פחות משלושה חברים בסתירה לטענה שלכול ילד יש בדיוק שלושה! נכון יוני?