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