בתשובה לעוזי ו., 19/08/03 0:36
כמה הערות 401352
גדי אלכסנדרוביץ' • בתשובה לעוזי ו. יום א', 6/8/2006, 13:55
ג. מה האלגוריתם שאתה מציע?
רמז 401470
אלון עמית • בתשובה לגדי אלכסנדרוביץ' יום א', 6/8/2006, 20:50
תגובה 164969.
רמז 401571
גדי אלכסנדרוביץ' • בתשובה לאלון עמית יום ב', 7/8/2006, 10:30
חשבתי על זה, אבל לא כל כך ברור לי איך כותבים אלגוריתם שעושה את זה בלי להסתבך קצת. עד כמה שאני מבין, לא מספיק סתם לעבור באופן סדרתי על כל המספרים עד לגבול מסויים (למשל, אי אפשר להגיד "המספר שהמחלקים שלו הם 1 ו-‏4" כי חייבים ש-‏2 יהיה שם). כלומר, הנפה שלנו צריכה לעבור על מספרים ראשוניים, ולקחת מהם את כל החזקות האפשריות. כל זה לא נשמע כיף מדי - אפשרי, בוודאי, אבל לא אלגוריתם פשוט.

אני כנראה מפספס משהו.
רמז 401574
עוזי ו. • בתשובה לגדי אלכסנדרוביץ' יום ב', 7/8/2006, 10:44
המשימה היא לבנות מערך P בגודל N, שיחזיק במקום ה-n את סכום המחלקים של n. בשלב ראשון, הצב את המספר 1 בכל המקומות.

אחר-כך, הוסף 2 לכל המקומות מהצורה 2n (עד N, כמובן). ואז 3 לכל המקומות מהצורה 3n, ו- 4 לכל המקומות מהצורה 4n, וכן הלאה. בתוך N*logN פעולות, המערך מלא. את הזוגות של מספרים ידידים אפשר למצוא על-ידי בדיקה מתי P[P[n]]=n.
רמז 401575
גדי אלכסנדרוביץ' • בתשובה לעוזי ו. יום ב', 7/8/2006, 10:47
טוב, אני הולך להתבייש בפינה... הייתי צריך לחשוב על זה.
רמז 401576
ראובן • בתשובה לעוזי ו. יום ב', 7/8/2006, 10:49
אתה מציע בניה של מערך של מאה מיליון אלמנטים?
רמז 401577
ערן בילינסקי • בתשובה לראובן יום ב', 7/8/2006, 10:53
לדעתי אפשר להחליף את המערך ב-lazy evaluation שמסמלץ את הגישה למערך. אם אני לא טועה, אנחנו עדיין נשארים בגבולות הסיבוכיות הלא-אקספוננציאלית.
רמז 401578
ראובן • בתשובה לערן בילינסקי יום ב', 7/8/2006, 10:59
איך זה יעבוד?

בעניין הסיבוכיות, אין לי מושג, עוזי טען שתוכנית מחשב תוכל לבצע את הבדיקות ב5 דקות.
רמז 401592
גדי אלכסנדרוביץ' • בתשובה לראובן יום ב', 7/8/2006, 11:31
5 דקות זה כבר לא ייקח (במחשב שלי, שמועמס כבר כך, ובלי אופטימיזציות), אבל האלגוריתם בבירור יותר יעיל ברמה העקרונית.
רמז 401596
ראובן • בתשובה לגדי אלכסנדרוביץ' יום ב', 7/8/2006, 11:36
אז תן אומדן משלך- כמה זמן זה ייקח, וכמה זמן זה היה לוקח במחשב לא עמוס וקוד אופטימלי?
רמז 401602
גדי אלכסנדרוביץ' • בתשובה לראובן יום ב', 7/8/2006, 11:56
אין לי שום מושג. בשביל לתת אומדן אני צריך להריץ את התוכנה על המחשב הנ''ל ועם האופטימיזציות הנ''ל על טווחים קטנים יחסית ולראות את קצב הגידול.
רמז 401605
ראובן • בתשובה לגדי אלכסנדרוביץ' יום ב', 7/8/2006, 11:59
סדר גודל? חצי שעה? יום? שבוע?
רמז 401613
גדי אלכסנדרוביץ' • בתשובה לראובן יום ב', 7/8/2006, 12:11
שוב: אין לי מושג. המספר 100,000,000 הוא שרירותי למדי.

דוגמה אחרת: בתוכנה שהייתי צריך להריץ ושזמן הריצה שלה הוא אקספוננציאלי "מאוד", הרצה עבור הפרמטר 15 לקחה כמה שניות, עבור 16 יום, עבור 17 חודש ועבור 18 המון זמן. אני לא יכול לתת הערכה לדבר כזה בלי לבדוק את קצב הריצה עבור פרמטרים יותר קטנים - אבל אחרי שעשיתי את זה, הצלחתי להעריך את זמן הריצה בדיוק לא רע. לפחות אני צריך בסיס כלשהו.
רמז 401623
ראובן • בתשובה לגדי אלכסנדרוביץ' יום ב', 7/8/2006, 12:31
חשבתי שיש לך קוד רץ, לא? ב5 דקות, לאן הגעת?
אולי שווה לחשב את היחס: זמן ריצה פר ראשוני.
רמז 401628
גדי אלכסנדרוביץ' • בתשובה לראובן יום ב', 7/8/2006, 12:36
הקוד שכתבתי פועל בשני שלבים: קודם מחשב את כל המערך, ורק אחר כך עובר עליו ומוצא את המספרים המתאימים. אני לא הדפסתי מונה רץ שאומר לאן כבר הגעתי כי זה מאט את הריצה (שהפסקתי בינתיים).
רמז 401631
סמיילי • בתשובה לגדי אלכסנדרוביץ' יום ב', 7/8/2006, 12:43
בדיקה קצרה ב-pc די רגיל נתנה לי ב-‏102 שניות את כל הזוגות עד 100,000,000 (הזוג האחרון הוא 99,899,792 ו 93,837,808 סה"כ 467 זוגות אבל לא הורדתי כפילויות ולא הורדתי מספרים שהם הזוג של עצמם).
רמז 401633
גדי אלכסנדרוביץ' • בתשובה לסמיילי יום ב', 7/8/2006, 12:47
איזו שפה ואיזה קומפיילר?
רמז 401636
סמיילי • בתשובה לגדי אלכסנדרוביץ' יום ב', 7/8/2006, 12:55
שפת c++ (בעצם, לא ממש השתמשתתי ב++). הקומפיילר של מיקרוסופט.

אגב, כשאני מסנן את הזוגות הכפולים ואת אלה שהם הזוג של עצמם, אני מקבל 231 זוגות, כשהאחרון הוא 97,041,735 ו-‏97,945,785. זה גם מוריד את הזמן ב-‏2 שניות.
רמז 401638
הקשה המקשה • בתשובה לסמיילי יום ב', 7/8/2006, 12:57
מה זה מספרים שהם זוג של עצמם?
רמז 401640
סמיילי • בתשובה להקשה המקשה יום ב', 7/8/2006, 13:05
6
28
496
8,128
33,550,336
רמז 401641
האייל האלמוני • בתשובה להקשה המקשה יום ב', 7/8/2006, 13:05
כל מספר הוא ידיד של עצמו ולכן צריך לסנן את התשובות האלה.
רמז 401642
גדי אלכסנדרוביץ' • בתשובה להקשה המקשה יום ב', 7/8/2006, 13:05
מספרים מושלמים, כמו 6 (מספרים שסכום המחלקים שלהם שווה לעצמם).
רמז 401639
גדי אלכסנדרוביץ' • בתשובה לסמיילי יום ב', 7/8/2006, 13:04
טוב, אני בספק אם הבעיה היא בקומפיילר (גם אני ב-++C). עד 10,000,000 הוא דווקא עושה את זה די מהר. כנראה שב-‏100,000,000 אני כבר מתחיל להרגיש את ההשפעה של הזכרון הוירטואלי.
רמז 401634
ראובן • בתשובה לסמיילי יום ב', 7/8/2006, 12:49
אני המום! 102 שניות? זה יפה מאוד.
רמז 401585
גדי אלכסנדרוביץ' • בתשובה לערן בילינסקי יום ב', 7/8/2006, 11:19
תוכל לפרט קצת איך היית עושה את זה מבלי לקבל בעצם את האלגוריתם ה"מקורי" (שגם הוא לא אקספוננציאלי, כמובן)?
רמז 401594
גדי אלכסנדרוביץ' • בתשובה לגדי אלכסנדרוביץ' יום ב', 7/8/2006, 11:33
(אני מניח שהכוונה היא "אקספוננציאלי בגודל המספר N", לא "אקספוננציאלי בגודל הייצוג של N").
רמז 401601
ערן בילינסקי • בתשובה לגדי אלכסנדרוביץ' יום ב', 7/8/2006, 11:53
המ... מסתבר שאני בעצם מקבל את האלגוריתם ה"מקורי", לא? :)
רמז 401584
גדי אלכסנדרוביץ' • בתשובה לראובן יום ב', 7/8/2006, 11:17
מה הבעיה כאן? במימוש סטנדרטי כל תא במערך ידרוש 4 בייטים - בהחלט בגבולות הזכרון הוירטואלי הסביר. המחשב קצת יקרטע, אבל לדעתי ישרוד (אני מנסה את זה כרגע).
רמז 401590
ראובן • בתשובה לגדי אלכסנדרוביץ' יום ב', 7/8/2006, 11:30
אם תצליח לבצע את זה בפחות מ5 דקות על PC תעדכן אותי.
חזרה לעמוד הראשי המאמר המלא
מערכת האייל הקורא אינה אחראית לתוכן תגובות שנכתבו בידי קוראים
האייל הקורא RSS מאמרים | כתבו למערכת | אודות האתר | טרם התעדכנת | ארכיון | חיפוש | עזרה | תנאי שימוש © כל הזכויות שמורות