- This topic has 27 תגובות, 8 משתתפים, and was last updated לפני 21 שנים, 10 חודשים by
.
-
תגובות
-
למי שמזהה השאלה הזאת הופיעה באולימפיאדת מדעי המחשב השנה:
נתונה שורה באורך 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. אם ההודעה היא כן – הצג בפלט את סדרת הזימונים (כל זימון יתואר בפלט על-ידי ערכי שלושת הפרמטרים שלו).
בהצלחה לכם!
כותרת: גם אני השתתפתי באולימפיאדה הזאת
אבל אני יותר אהבתי את שאלה מספר 2:כתוב תוכנית שקולטת מספר ופולטת האם הוא ממוצע של 3 חזקות שונות של 2. (1 נחשב לחזקה של 2)
לדוגמה:
5 לא
7 כן (כי זה ממוצע של 1,4,16)
46 כן (כי זה ממוצע של 2,8,128)הגעתי פה לאלגוריתם שרץ ב-O(1) וממומש בפונקציה של 2 שורות
תהנו.כותרת: נו וגם אני הייתי…
שתי השאלות הראשונות היו מאוד קלות.
בשאלה השנייה פשוט מכפילים את המספר פי 3, סופרים כמה סיביות יש, ואז אם זה בדיוק שלוש אז זה מתאים. אם יש משהו עוד יותר פשוט, אשמח לשמוע!הקטע זה השאלה השלישית. הצלחתי לפתור אותה, אבל בצורה ממש לא אפקטיבית…
כותרת: וואי זה חכם
וואי אני חשבתי שאני מבין קצת במחשבים, נראה לי שאני מבזבז את הזמן שלי, אני כתבתי אלגוריתם שלם שבודק את זה.
לספור סיביות, מאיפה אני אמור לדעת מה כל זה אומר???
באיזה שפה כל זה נכתב?כותרת: השאלה השלישית
תחשוב על זה שהפעולה ADD היא הפיכה, מה זה אומר בקשר לסידור ההתחלתי ולכל סידור שאפשר להגיע אליו ממנו? לאיזה צורה נורמלית אפשר להביא כל סידור התחלתי ואיך אפשר לנצל את זה שיש שלושה מספרים או יותר כדי לקבוע אם הצורה הנורמלית הזאת יכולה להפוך לשורת אפסים או לא?כותרת: פתרון
ע"מ שתוכל לאפס את כל מספרי השורה, צריכות להיות שתי קבוצות של מספרים שסכומן שווה. לדוגמא, בשורה 2 5 7 3 4 1 יש 2 קבוצות:
2+5+4 מול 7+3+1 (יכול להיות גם 2+5+1+3 מול 7+4 אולם האפשרות הראשונה עדיפה).הצעדים:
א. כותבים פונקציה שמטרתה להחזיר את המיקום של האיבר הגדול ביותר בשורה ואת גודלו, ולהפוך את ערכו של אותו איבר במערך של השורה ל-0 (כדי שלא יהיה יותר המקסימום).
ב. מגדירים 4 משתנים: 2 מערכים בני n אברים (למעשה n-1, אבל לא צריך להיות קטנוניים), ועוד 2 משתנים שמאחסנים סכום כל מערך.
ג. כותבים לולאה while שקוראת כל פעם לפונקציה מסעיף א´. המיקום (המיקום של האיבר המקסימלי) שמוחזר מתווסף למערך א´ או למערך ב´ – לפי המערך הקטן יותר (צריך להשתמש במשפט else ולא במשפט elseif משום שבהתחלה שני המערכים שווים ואז לא יתווספו איברים). לאחר ההוספה של מיקום האיבר למערך, יגדל המשתנה שמונה את סכום המערך בגודל האיבר (עוד משתנה שמוחזר מהפונקציה).
ד. כאשר הערך החוזר מהפונקציה הוא אפס, מסתיימת הלולאה.
ה. לאחר סיום הלולאה, אם סכום מערך א´ שווה לסכום מערך ב´ יש לבעיה פתרון, ולהיפך.
ו. כעת, עוברים עם לולאה נוספת על שני המערכים.
כל פעם מוצאים את הערך המקסימלי מבין שני המערכים (איחוד של שניהם), ומורידים את הערך שלו מהמערך השני (כמובן שאי אפשר את כל הערך שלו כי הוא מקסימלי, אז מורידים רק מה שאפשר).וככה עד לסוף עם הצגת ההוראות על המסך
כותרת: מה היה התאריך של התחרות? ובאיזו תחרות מדובר?
כי אני גם מתכנן להשתתף בה למרות שלא הייתי ביום היכרות שנערך באאוניברסיטת ת"א
התחרות כבר התקיימה?כותרת: אני לא חושב שהפתרון צריך להיות כ"כ מורכב
פשוט תעשה XOR בין כל האיברים ותבדוק את ה LSB של התוצאה הסופית. אם היא 0 אז אפשר, אם היא 1 אז אי אפשר.כותרת: הפתרון שלי
קודם כל – לספור סיביות כלומר לבדוק כמה סיביות דלוקות בייצוג הבינארי של המספר
למשל במספר שייצוגו הבינארי הוא 10110010 יש 4 סיביות דלוקותכעת לצורה בה פתרתי את השאלה השלישית
אמנם אני קורא לפונקציה ADD הרבה יותר פעמים מאשר אפשר לעשות, אבל התכנית עצמה פשוטה ביותר
עוברים בלולאה על כל המספרים
עבור כל מספר במערך עושים את הדברים הבאים (אשר תמיד מביאים לאיפוס המספר הנוכחי) :
1. אם הוא אי-זוגי, מוסיפים לו ולמספר הבא 1
2. מוסיפים חצי מהמספר הנוכחי לשני המספרים הבאים
3. מחסירים חצי מהמספר הנוכחי מהמספר עצמו ומשני המספרים הבאים (הנוכחי והבא, ואז הנוכחי והשני הבא)
וזהוכותרת: הפתרון שלי
קודם כל – לספור סיביות כלומר לבדוק כמה סיביות דלוקות בייצוג הבינארי של המספר
למשל במספר שייצוגו הבינארי הוא 10110010 יש 4 סיביות דלוקותכעת לצורה בה פתרתי את השאלה השלישית
אמנם אני קורא לפונקציה ADD הרבה יותר פעמים מאשר אפשר לעשות, אבל התכנית עצמה פשוטה ביותר
עוברים בלולאה על כל המספרים
עבור כל מספר במערך עושים את הדברים הבאים (אשר תמיד מביאים לאיפוס המספר הנוכחי) :
1. אם הוא אי-זוגי, מוסיפים לו ולמספר הבא 1
2. מוסיפים חצי מהמספר הנוכחי לשני המספרים הבאים
3. מחסירים חצי מהמספר הנוכחי מהמספר עצמו ומשני המספרים הבאים (הנוכחי והבא, ואז הנוכחי והשני הבא)
וזהוכותרת: אל ה the wizard
הפתרון שלך אכן חכם, אני רק תוהה מה בדיוק אתה עושה עם המספרים האחרונים שנשארים לך, כי למשל למספר האחרון בשורה אין 2 מספרים אחריו.כותרת: מה עושים בשביל שני האחרונים
אפשר פשוט להשתמש בשני הראשונים…
פשוט להסתכל על המערך כעל מאין מעגל…
את הלפני אחרון נאפס בעזרת הראשון והאחרון, את האחרון בעזרת השניים הראשונים…אגב, בנוגע לבדיקת הסיביות – אפשר ב O(1) אם מנצלים את זה שהביטוי
a&a-1 למעשה מאפס את הסיבית הראשונה שדלוקה מצד ימין, לכן הבדיקה יכולה להיות:
if( (a&=a-1) != 0 &&
(a&=a-1) != 0 &&
(a&=a-1) == 0 )
(אין ברירה – תעתיקו לnotepad כדי לראות את זה נורמלי).כותרת: ל´סתם מישהו´
אם המספר נמצא במקום האחרון או הלפני-אחרון, אז לוקחים את שני המספרים הראשוניםכשאני חושב על זה עכשיו, נראה לי שאולי השיטה שלי לא תעבוד בכמה מקרים מסוימים… אוי לא!
כותרת: שלום לך שוב דניאל
שוב שלום לך דניאל, שמח לראות אותך כל הזמן מגיב על ההודעות שלי
אני רק תוהה באיזה שפה אתם מדברים כשאתם מדברים על סיביות?
זה סי או אסמבלי?
- יש להתחבר למערכת על מנת להגיב.