נושא: בעיה אלגוריתמית נוספת

נשלח בתאריך: 29 October 2005 בשעה 08:16 | IP רשוּם

שלום, חבר שלי היה באולימפיאדה הארצית במדעי המחשב ואת השאלה הזו הוא ממש לא הצליח והוא שאל המון אנשים ואף אחד מהם לא הצליח.

אולי מישהו כאן יצליח כי אני יודע שיש כאן הרבה אנשים חכמים וטובים בכל הקשור לאלגוריתמיקה ובמדעי המחשב.

כתוב תכנית אשר הקלט שלה הוא מספר שלם 5 £ N £ 1000 ,N , ואחריו תמורה אקראית (סידור אקראי) של המספרים  1, 2, .., N; והפלט שלה זוגיות מספר הזוגות הלא-סדורים בתמורה הנתונה. זוג לא-סדור של מספרים הוא זוג מספרים אשר אינם מסודרים בתמורה אחד ביחס לשני, כלומר – הגדול שבהם נמצא בתמורה משמאל לקטן שבהם.

על תכניתך לבצע את החישוב בזמן קצר ככל האפשר, ובפרט – קטן בהרבה מ- O(N²) (שהוא הזמן הנגזר מסדר גודל של N מעברים על תת-סדרות בסדר גודל של N).

למשל, עבור התמורה:    4  3  1  6  2  5   יהיה הפלט "זוגי", עקב 8 זוגות מספרים לא-סדורים:  5,2   5,1   2,1   6,1   5,3   6,3   5,4   6,4.

נשלח בתאריך: 29 October 2005 בשעה 12:11 | IP רשוּם

1. נשתמש במערך arrNumbers כדי לגשת במהירות לאיבר המתאים ברשימה. הדפס את כל האיברים ברשימה המופיעים אחרי האיבר שאליו הגענו, בפורמט הרצוי לפי הדרישות.
2. הסר את האיבר a מהרשימה המקושרת  - (O(1

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