מבחן 2009 מועד א', שאלה 2 ב'

מנהל: TA_Isana

שלח תגובה
מור דקל
הודעות: 17
הצטרף: 15:32 22/10/2009

מבחן 2009 מועד א', שאלה 2 ב'

שליחה על ידי מור דקל » 09:40 26/06/2010

אני יודעת שהיה משהו מאוד דומה בתרגול מספר 11, אבל בגלל שלא זכרתי את זה, כתבתי פתרון די נאיבי, אשר רץ בo(n):

על מנת שכל הקטעים יהיו זרים, צריף להתקיים: a1 < b1 < a2 < b2 < ... < an < bn.

נאתחל את ans ל true, ואת i ל n.
כל עוד (i>1) וגם (ans=true) בצע:
אם לא מתקיים (גם bi>ai וגם a i > b i-1)
ans=false
i--
החזר את ans.

האם פתרון נאיבי שכזה היה מתקבל? האם בכלל מותר לי להניח שניתן "לנדוד" בין ערכי הa והb , לפי הסדר?
תודה

מור דקל
הודעות: 17
הצטרף: 15:32 22/10/2009

Re: מבחן 2009 מועד א', שאלה 2 ב'

שליחה על ידי מור דקל » 09:42 26/06/2010

אמ..... זה ביטל לי את ההזחה! בכל מקרה, i-- מחוץ לif, וההחזרה מחוץ לwhile

בר כהן
הודעות: 146
הצטרף: 18:24 22/10/2009

Re: מבחן 2009 מועד א', שאלה 2 ב'

שליחה על ידי בר כהן » 12:10 26/06/2010

קיבלת בשאלה הזאת קבוצה של נקודות, אם היא הייתה מסודרת כבר, אז באמת זה כל מה שהיית צריכה לעשות.
אבל את לא יכולה להניח שהיא כבר ממויינת ולכן הבעייתיות, בהצלחה :)

שלח תגובה

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