חידה

[טיקטי1]

חידה

למי שמזהה השאלה הזאת הופיעה באולימפיאדת מדעי המחשב השנה: נתונה שורה באורך N, N>3<1000, של מספרים שלמים חיוביים כלשהם. מעוניינים להמיר את כל מספרי השורה ל-0, באמצעות שימוש חוזר ונשנה בפונקציה Add. הפונקציה Add מקבלת שלושה פרמטרים – מקומות סידוריים של שני מספרים בשורה, וערך שלם, חיובי או שלילי. הפונקציה מוסיפה לשני המספרים (שמקומותיהם הסידוריים נתונים) את הערך השלם. ניתן לזמן את הפונקציה שוב ושוב, ובכל פעם – עם שני מקומות סידוריים (שונים זה מזה) כרצונך, וכל ערך שלם כרצונך. למשל, עבור השורה הבאה של 8 מספרים: 12 2 3 9 11 2 14 3 זימון של Add(3,7,10( יגדיל את המספר השלישי בשורה ל-13 ואת השביעי ל-24. זימון של Add(3,5,-10) יקטין את המספר השלישי בשורה ל- 7- ואת החמישי ל-1. זימון כגון Add(5,5,-10) איננו חוקי כיון ששני המקומות המצוינים בו שווים (שניהם 5). כתוב תכנית אשר הקלט שלה הוא N, ואחריו שורה של N מספרים שלמים חיוביים, והפלט שלה הוא הודעה האם ניתן או לא ניתן להמיר את השורה לשורה של 0-ים באמצעות סדרת זימונים של Add. אם ההודעה היא כן – הצג בפלט את סדרת הזימונים (כל זימון יתואר בפלט על-ידי ערכי שלושת הפרמטרים שלו). בהצלחה לכולם! החידה נלקחה מ- http://www.codeguru.co.il/forum/ShowMessage.asp?id=729&Fnumber=3&SunId=0

 

[אמיר96]

נסיון

ראשית, נאפס את האיבר הראשון בעזרת השני, השני בעזרת השלישי וכך הלאה. נגיע לכך שכל המספרים מאופסים, פרט לאחרון. נחלק את המספר האחרון ב N (נסמן D). נמצא את השארית בחלוקה בN (נסמן R). נוסיף ל R איברים D+1 מול האיבר האחרון. נוסיף לשאר האיברים D מול האיבר האחרון. האיבר האחרון התאפס. כעת נאפס אחד מול השני את הזוגות השווים. את אלה שנשארים (כי לא נותרו איברים שווים לאפס מולם) נאפס בעזרת האיבר האחרון. שוב, הגענו לכך שכל האיברים מאופסים פרט לאחרון. חוזרים על כך עד שכולם מתאפסים, או עד שנשאר רק 1 (או -1)באיבר האחרון. במקרה זה אי אפשר לאפס את כולם.

 

[BigMax]

אפשר פשוט יותר

איפסת את כולם חוץ מאחד. נקבע שערכו P והוא נמצא במקום הN אז במקרה שP זוגי אתה עושה (Add (1, N, -P/2 (Add (1, 2, P/2 (Add (2, N, -P/2 וגמרנו עכשיו מה קורה אם P לא זוגי (שאגב בשיטה שלך אתה נשאר עם 1 בסוף במקרה שP לא היה זוגי), זאת שאלה טובה... אבל אני הולך לישון

 

[נשר בלי כנפיים]

ולסיכום

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

 

[BigMax]

ואללה

איזה שיתוף פעולה...

 

[אמיר96]

הרבה יותר פשוט ../images/Emo127.gif

 

[טיקטי1]

שאלה

לא הבנתי את השורה הבאה- "נאפס את האיבר הראשון בעזרת השני, השני בעזרת השלישי וכך הלאה. נגיע לכך שכל המספרים מאופסים" כלומר למה אתה בטוח שהם יתאפסו? מה קורה עים השורה הבאה: 1,3,15 ? והנה הפתרון שלי (תבדקו לי אותו בבקשה (יש כמה פתרונות ואני לא יודע אים זה נכון)): אים סכום כל האיברים אי זוגי מחזירים שהמערך לא פתיר אים לא הופכים את כל איברי המערך לזוגיים ואז מחלקים אותם לשתי קבוצות ומתחילים לזמן את הפונקציה add כשההפרש הוא 2 על האיברים בקבוצה שהסכום שלה נמוך יותר עד שמגיעים למצב שבו ההפרש בין הקבוצות הוא 0 או 2 (אלה האפשרויות היחידות) ואז מתחילים לחסר בין איברי הקבוצה עד שאו שנשאר 0 בכל התאים (אים ההפרש בין הקבוצות כשמפסיקים את החיבור הוא 0) או לאיבר אחד שהוא 2 (אים ההפרש בין הקבוצות כשמפסיקים לחבר הוא 2) ואז מוסיפים לשני איברים אחרים 2 ופותרים עד שכל איברי המערך הם 0

 

[טיקטי1]

תתעלם מהשאלה שלי ../images/Emo3.gif

זה בגלל השעה

ו-

יפה מאד