חידה לא קלה

עמוד
מוצגות 13 תגובות – 16 עד 28 (מתוך 28 סה״כ)
  • מאת
    תגובות
  • #79181
    סוסי
    משתתף

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

    #79182
    TheWizard
    משתתף

    כותרת: נכון…
    לכן אם המספר הלפני-אחרון הוא אי-זוגי, צריך להוסיף אליו ואל האחרון 1 (אני מאוד מקווה שעשיתי ככה במבחן…), ואם המספר האחרון הוא אי-זוגי ושאר המספרים הם אפס, לא ניתן לאפס את הסדרה — אבל את זה כבר בודקים בהתחלה (סכום המספרים זוגי)

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

    כותרת: סיביות זה לא קשור לשפה…
    זה קשור למספרים בינאריים – ייצוג של מספר באמצעות הספרות 0 ו 1 בלבד. "סיבית"(bit) זה ספרה בודדת בתוך מספר בינארי.

    הסבר הכי בנאלי על מספרים בינאריים:
    http://home.swbell.net/ruthven/robotics/binary.html
    הסבר טוב וקצת יותר מעמיק(כולל פעולות מתמטיות ולוגיות על מספרים בינריים, אבל עם טיפה שטויות על שפת אסמבלי
    http://webster.cs.ucr.edu/Page_AoAWin/HTML/DataRepresentation.html
    http://webster.cs.ucr.edu/Page_AoAWin/HTML/DataRepresentationa2.html
    http://webster.cs.ucr.edu/Page_AoAWin/HTML/DataRepresentationa3.html
    http://webster.cs.ucr.edu/Page_AoAWin/HTML/DataRepresentationa4.html

    נכון, הקטע קוד שלי היה בסי…
    בכל מקרה, הוא מתבסס על העובדה שאם ניקח מספר כלשהוא, ונבצע פעולת AND(בסי מסמנים עם &) לוגי עם המספר מינוס אחד, למעשה נהפוך את הסיבית )הראשונה מצד ימין ששווה 1 ל אפס.

    למשל:
    19 = 10011
    18 = 10010
    18&19 = 10010

    20 = 10100
    19 = 10011
    19&20 = 10000

    אז כל שצריך לעשות, זה לבצע את הפעולה הנ"ל כדי לכבות סיבית אחר סיבית.

    #79184
    סוסי
    משתתף

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

    #79185
    TheWizard
    משתתף

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

    #79186
    Yoni
    משתתף

    כותרת: ככה אני פתרתי:
    את השאלה השנייה כמו שדניאל אמר, ממש 2 שורות.

    int CheckNumber(int N)//0
    {
    int X = 3 * N;//0
    return (X &= (X – 1)) && (X &= (X – 1)) && !(X &= (X – 1));//0
    }

    את השאלה השלישית בדרך הזו:
    תוך כדי קליטת האיברים לתוך המערך שמרתי את הזוגיות של הסכום שלהם (ה-XOR של ה-LSB שלהם). אם בסוף יצא אפס, המערך פתיר.
    איפסתי את כל האיברים חוץ מהראשון על-ידי:
    Add(1, X, -Array[X]);//0
    ואז איפסתי את האיבר הראשון (בהנחה שהוא עדיין לא מאופס), שהוא בטוח זוגי, על-ידי:
    D = Array[0] / 2;//0
    Add(1, 2, -D);//0
    Add(2, 3, D);//0
    Add(1, 3, -D);//0

    (הוספתי בסוף כל שורה //0 כדי שיהיה קריא בפורום.)

    #79187
    יובל
    משתתף

    כותרת: "הפתרון לא צריך להיות כל-כך מורכב"-למי אתה מתכוו?
    כי גם אחרי שקראתי את התשובה כולה לא הצלחתי להבין למי אתה מתכוון

    וצריך גם להציג את הדרך לפתרון, לא רק אם זה אפשרי או לא

    #79188
    יובל
    משתתף

    כותרת: זה לא קשור לזוגיות זה קשור לשתי קבוצות של מספרים

    #79189
    יובל
    משתתף

    כותרת: זה לא קשור לזוגיות זה קשור לשתי קבוצות של מספרים
    תסתכלו על השורה 11 7 3 9
    סכום המספרים זוגי ועדיין אי אפשר לפתור

    #79196
    Yoni
    משתתף

    כותרת: מה נשמע יובל?
    אמרנו 11 7 3 9…
    עם האלגוריתם שלי:
    Add(1, 2, -3);//0
    Add(1, 3, -7);//0
    Add(1, 4, -11);//0
    Add(1, 2, 6);//0
    Add(2, 3, -6);//0
    Add(1, 3, 6);//0
    והכל אפס. מה רע?

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

    כותרת: ליוני, ההבדל בין האלגוריתמים
    האלגוריתם שלך הרבה יותר חסכוני בקריאות לADD – על כל איבר מלבד הראשון מתבצע פעולת ADD בודדת. לעומת זאת האלגוריתם של רומי(Thewizard) משתמש ב3 קריאות לADD על כל איבר. עם זאת, בשיטה שלך חסרון אחד מאוד גדול – גודל המספרים בהם ניתן להשתמש. מאחר וכל האיברים באותו גודל(נניח 16 סיביות ), הם יכולים להכיל רק טווח ערכים מסוים. בסוף הלולאה על כל האיברים באלגוריתם שלך, האיבר הראשון למעשה יכיל את ההפך מסכום כל המספרים. המערך יכול להכיל עד אלף מספרים, מכאן שהאלגוריתם שלך מגביל את הערך הממוצע של כל האיברים במערך לתחום 32 עד מינוס 32.
    טווח הערכים באלגוריתם של רומי גדול בהרבה(ערך ממוצע של 20,000 למשל הוא סביר בהחלט).

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

    שני האלגוריתמים אחלה, כל אחד מתאים לסדרת תנאים שונים.

    #79202
    Yoni
    משתתף

    כותרת: לא נראה לי שזה משנה…
    כל עוד המספר הראשון נשאר זוגי, גם אם הוא עובר מעבר למקסימום/מינימום הערכים שלו הוא ישאר זוגי…
    למשל: (נניח 16 סיביות)
    -32760 – 10 = 32766
    וכן
    32766 + 10 = -32760

    #79203
    Yoni
    משתתף

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

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