חידה לא קלה

עמוד
מוצגות 15 תגובות – 1 עד 15 (מתוך 28 סה״כ)
  • מאת
    תגובות
  • #77381
    סוסי
    משתתף

    למי שמזהה השאלה הזאת הופיעה באולימפיאדת מדעי המחשב השנה:

    נתונה שורה באורך 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. אם ההודעה היא כן – הצג בפלט את סדרת הזימונים (כל זימון יתואר בפלט על-ידי ערכי שלושת הפרמטרים שלו).

    בהצלחה לכם!

    #79166
    Yoni
    משתתף

    כותרת: גם אני השתתפתי באולימפיאדה הזאת
    אבל אני יותר אהבתי את שאלה מספר 2:

    כתוב תוכנית שקולטת מספר ופולטת האם הוא ממוצע של 3 חזקות שונות של 2. (1 נחשב לחזקה של 2)
    לדוגמה:
    5 לא
    7 כן (כי זה ממוצע של 1,4,16)
    46 כן (כי זה ממוצע של 2,8,128)

    הגעתי פה לאלגוריתם שרץ ב-O(1) וממומש בפונקציה של 2 שורות =) תהנו.

    #79167
    TheWizard
    משתתף

    כותרת: נו וגם אני הייתי…
    שתי השאלות הראשונות היו מאוד קלות.
    בשאלה השנייה פשוט מכפילים את המספר פי 3, סופרים כמה סיביות יש, ואז אם זה בדיוק שלוש אז זה מתאים. אם יש משהו עוד יותר פשוט, אשמח לשמוע!

    הקטע זה השאלה השלישית. הצלחתי לפתור אותה, אבל בצורה ממש לא אפקטיבית… :(

    #79168
    סוסי
    משתתף

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

    #79170
    אורן בקר
    משתתף

    כותרת: השאלה השלישית
    תחשוב על זה שהפעולה ADD היא הפיכה, מה זה אומר בקשר לסידור ההתחלתי ולכל סידור שאפשר להגיע אליו ממנו? לאיזה צורה נורמלית אפשר להביא כל סידור התחלתי ואיך אפשר לנצל את זה שיש שלושה מספרים או יותר כדי לקבוע אם הצורה הנורמלית הזאת יכולה להפוך לשורת אפסים או לא?

    #79171
    יובל
    משתתף

    כותרת: פתרון
    ע"מ שתוכל לאפס את כל מספרי השורה, צריכות להיות שתי קבוצות של מספרים שסכומן שווה. לדוגמא, בשורה 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 משום שבהתחלה שני המערכים שווים ואז לא יתווספו איברים). לאחר ההוספה של מיקום האיבר למערך, יגדל המשתנה שמונה את סכום המערך בגודל האיבר (עוד משתנה שמוחזר מהפונקציה).
    ד. כאשר הערך החוזר מהפונקציה הוא אפס, מסתיימת הלולאה.
    ה. לאחר סיום הלולאה, אם סכום מערך א´ שווה לסכום מערך ב´ יש לבעיה פתרון, ולהיפך.
    ו. כעת, עוברים עם לולאה נוספת על שני המערכים.
    כל פעם מוצאים את הערך המקסימלי מבין שני המערכים (איחוד של שניהם), ומורידים את הערך שלו מהמערך השני (כמובן שאי אפשר את כל הערך שלו כי הוא מקסימלי, אז מורידים רק מה שאפשר).

    וככה עד לסוף עם הצגת ההוראות על המסך

    #79172
    יובל
    משתתף

    כותרת: מה היה התאריך של התחרות? ובאיזו תחרות מדובר?
    כי אני גם מתכנן להשתתף בה למרות שלא הייתי ביום היכרות שנערך באאוניברסיטת ת"א
    התחרות כבר התקיימה?

    #79173
    אורן בקר
    משתתף

    כותרת: אני לא חושב שהפתרון צריך להיות כ"כ מורכב
    פשוט תעשה XOR בין כל האיברים ותבדוק את ה LSB של התוצאה הסופית. אם היא 0 אז אפשר, אם היא 1 אז אי אפשר.

    #79174
    TheWizard
    משתתף

    כותרת: הפתרון שלי
    קודם כל – לספור סיביות כלומר לבדוק כמה סיביות דלוקות בייצוג הבינארי של המספר
    למשל במספר שייצוגו הבינארי הוא 10110010 יש 4 סיביות דלוקות

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

    #79175
    TheWizard
    משתתף

    כותרת: הפתרון שלי
    קודם כל – לספור סיביות כלומר לבדוק כמה סיביות דלוקות בייצוג הבינארי של המספר
    למשל במספר שייצוגו הבינארי הוא 10110010 יש 4 סיביות דלוקות

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

    #79176

    כותרת: אל ה the wizard
    הפתרון שלך אכן חכם, אני רק תוהה מה בדיוק אתה עושה עם המספרים האחרונים שנשארים לך, כי למשל למספר האחרון בשורה אין 2 מספרים אחריו.

    #79177
    דניאל ק
    משתתף

    כותרת: מה עושים בשביל שני האחרונים
    אפשר פשוט להשתמש בשני הראשונים…
    פשוט להסתכל על המערך כעל מאין מעגל…
    את הלפני אחרון נאפס בעזרת הראשון והאחרון, את האחרון בעזרת השניים הראשונים…

    אגב, בנוגע לבדיקת הסיביות – אפשר ב O(1) אם מנצלים את זה שהביטוי
    a&a-1 למעשה מאפס את הסיבית הראשונה שדלוקה מצד ימין, לכן הבדיקה יכולה להיות:
    if( (a&=a-1) != 0 &&
    (a&=a-1) != 0 &&
    (a&=a-1) == 0 )
    (אין ברירה – תעתיקו לnotepad כדי לראות את זה נורמלי).

    #79178
    TheWizard
    משתתף

    כותרת: ל´סתם מישהו´
    אם המספר נמצא במקום האחרון או הלפני-אחרון, אז לוקחים את שני המספרים הראשונים

    כשאני חושב על זה עכשיו, נראה לי שאולי השיטה שלי לא תעבוד בכמה מקרים מסוימים… אוי לא! :(

    #79179
    סוסי
    משתתף

    כותרת: שלום לך שוב דניאל
    שוב שלום לך דניאל, שמח לראות אותך כל הזמן מגיב על ההודעות שלי
    אני רק תוהה באיזה שפה אתם מדברים כשאתם מדברים על סיביות?
    זה סי או אסמבלי?

    #79180
    סוסי
    משתתף

    כותרת: ל The Wizard
    הרעיון יפה, אבל עד שתגיע למספר האחרון או הלפני האחרון המספר הראשון והשני כבר אמורים להיות מאופסים לא?
    אם תוסיף לאחד מהם 1 זה יעשה בעיות

מוצגות 15 תגובות – 1 עד 15 (מתוך 28 סה״כ)
  • יש להתחבר למערכת על מנת להגיב.