חידה לא קלה

[סוסי]

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

[TheWizard]

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

[דניאל ק]

כותרת: סיביות זה לא קשור לשפה…
זה קשור למספרים בינאריים – ייצוג של מספר באמצעות הספרות 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

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

[סוסי]

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

[TheWizard]

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

[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 כדי שיהיה קריא בפורום.)

[יובל]

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

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

[יובל]

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

[יובל]

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

[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
והכל אפס. מה רע?

[דניאל ק]

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

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

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

[Yoni]

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

[Yoni]

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

[מאת]

תגובות