עזרה בכתיבת תוכנית ב C++ , קבצים ופקודות ביטים

[SeaMonster]

יש לי תמשימה הבאה:

עבודה בקבצים ופקודות ביטים.

בקובץ million.txt (באתר, בספריה misc) מיליון מספרים שונים מטפוס int בתחום

[0-999999] מסודרים בסדר אקראי.

על פי תאור הקובץ קל לראות שכל מספר בתחום מופיע בקובץ רק פעם אחת.

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

כתוב תוכנית שמוצאת את המספר החסר.

על התוכנית לעמוד במגבלות הבאות:

a. מותר לקרוא את הקובץ רק פעם אחת.

b. אסור לשמור את כל המספרים שבקובץ או את חלקם במערך בזכרון.

c. אסור להשתמש במערכים שסך כל הזכרון שהם תופסים עולה על 130000 בתים.

d. על התוכנית להגיע למספר החסר תוך פחות מ 10 שניות.

יש למישהו רעיון?

-תודה

[שניצל]

יש דרכים מתמטיות כדי לפתור את הבעיה (פונקציות מסויימות על הקלט שייתנו לך מידע על המספר החסר).

[Armageddon26]

אתה יכול ליצור מערך בוליאני בגודל מיליון.

בהתחלה תאפס את כולו ל-FALSE.

לכל מספר X בקובץ הטקסט:

הפוך את הערך ה-X במערך הבוליאני לTRUE.

באופן הזה כולם יהיו TRUE חוץ מאחד שהוא FALSE.

תרוץ על כל המספרים במערך הבוליאני ותמצא את זה שFALSE, זה מי שנעלם...

לא יודע לגבי כמה שניות (זה תלוי במעבד כמובן) אבל אתה רץ על המערך המקורי (בערך מיליון פעלולות) ושוב על המערך הבוליאני (בערך עוד מיליון) אז סה"כ זאת משימה לינארית.

[Zelig]

בעצם הפתרון תלוי בסיבוכיות הזכרון המותרת.

אם O(n) אז הפתרון עם מערך של מליון bool-ים הוא תקין.

אם O(1) (ונראה לי שלזה בעצם כיוון כותב השאלה) אז הפתרון הנ"ל לא תקין.

[SeaMonster]

על המערך בגודל מיליון תאים חשבתי מייד איך שקראתי תשאלה , הבעייה היא שאין שימוש בביטים בפיתרון הזה וגם יש בעייה של גלישה , מודיע לי על Stack Overflow

[שניצל]

אי אפשר להגדיר מערך מקומי בגודל 1000000. אתה חייב להגדיר אותו דינמית (באמצעות new) או להשתמש באחד הקלאסים המובנים לדברים כאלה, כגון bitset או <vector<bool

בכל מקרה, תחשוב על פתרון מתמטי (לדוגמה - מה קורה אם אתה סוכם את כל המספרים?)

[Zelig]

רמזים:

http://discuss.joelonsoftware.com/default.asp?interview.11.742412.38

[Armageddon26]

אם n הוא אורך הקלט (במקרה הזה מיליון) אז הפיתרון חייב להיות לפחות לינארי O(n) כי אם לא תעבור על כל המספרים לא תוכל לדעת מה חסר.

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

השאלה היא אם מותר לך להשתמש בעוד מיליון ביטים.

אני הבנתי שכן כי רשמת שרק אסור לשמור את כל המספרים שבקובץ או את חלקם במערך בזכרון ואנחנו לא שומרים אותם.

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

[שניצל]

ברור שהפתרון חייב להיות בסיבוכיות זמן (O(n (לפחות), Zelig דיבר על סיבוכיות הזכרון.

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

בלינק ש-Zelig נתן יש רעיונות לפתרון (זו לא בדיוק אותה שאלה, אבל זה מספיק דומה). אני אישית חשבתי על הפתרון השני שמוצע שם (הוא לדעתי הכי פשוט ואלגנטי).

[SeaMonster]

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

אבל יש הגבלה חדשה שהמרצה שלי החליט להוסיף אחרי ששלחתי לו את הפתרון , אסור להשתמש במערכים שסך כל הזכרון שהם תופסים עולה על 130000 בתים.

ז"א שהפיתרון הנ"ל כבר לא מתקבל.

גם העניין שחייבים להשתמש בפקודות ביטים:

1s Complement ~ 1

Shift Left << 2

Shift Right >> 3

AND & 4

XOR ^ 5

OR | 6

הצצתי בלינק ש Zelig הביא, ותאמת אני לא מבין תשפה (java?) שבה האלגוריתם כתוב.

[שניצל]

יש כמה פתרונות בלינק שהובא, בכל מיני שפות (הראשון בפייתון, השני ב-C, וכו'). בכל מקרה, לפי ההסבר האחרון שלך זו לא המטרה.

תחשוב איך אפשר לממש מערך של ביטים בצורה חסכונית מבחינת מקום (תזכור ש-byte הוא בעצם 8 ביט).

[Armageddon26]

1) 130,000 בתים הם 1,040,000 ביטים והפיתרון עם המערך הבוליאני יעבוד (הוא לוקח 1,000,000) ביטים.

2) כמו שנאמר, בלינק הוצע פיתרון עדיף - עם O(1) זיכרון נוסף (כלומר כמות קבועה שלא תלוי בגודל הקלט).

הרעיון הכללי:

נסמן ב-X את המספר שלא קיים וב-Y את המספר שמופיע פעמיים.

סכום ערכי המערך הוא סכום המספרים מ1 עד 999,999 פחות X ועוד Y.

לכן אם נסכם את האיברים נדע את ההפרש בין X ל-Y. (סכום המספרים מ-1 עד 999,999 הוא 1,000,000*999,999 חלקי 2 ).

באופן דומה, סכום ריבועי הערכים הוא סכום ריבועי הערכים של המספרים מ-1 עד 999,999 פחות X*X ועוד Y*Y.

יש לנו 2 משוואות פשוטות עם שני נעלמים ומכאן כבר הכל ברור.

אני ממליץ לך לעשות כמו שמישהו הראה באתר:

sum = sum + a[i] -i;
   sumSquare = sumSquare + a[i]*a[i] - i*i;

SUM מראה את X-Y ו-SUMSQUARE מראה את הפרש ריבועיהם.

תסביר למחשב איך לפתור את המשוואה הריבועית וסיימת.

בהצלחה!

[שניצל]

1) 130,000 בתים הם 1,040,000 ביטים והפיתרון עם המערך הבוליאני יעבוד (הוא לוקח 1,000,000) ביטים.

תיאורטית כן, מעשית לא. מערך בוליאני עדיין יתפוס 32000000 ביט (כי כל bool הוא למעשה int).

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

[Zelig]

1) 130,000 בתים הם 1,040,000 ביטים והפיתרון עם המערך הבוליאני יעבוד (הוא לוקח 1,000,000) ביטים.

2) כמו שנאמר, בלינק הוצע פיתרון עדיף - עם O(1) זיכרון נוסף (כלומר כמות קבועה שלא תלוי בגודל הקלט).

הרעיון הכללי:

נסמן ב-X את המספר שלא קיים וב-Y את המספר שמופיע פעמיים.

סכום ערכי המערך הוא סכום המספרים מ1 עד 999,999 פחות X ועוד Y.

לכן אם נסכם את האיברים נדע את ההפרש בין X ל-Y. (סכום המספרים מ-1 עד 999,999 הוא 1,000,000*999,999 חלקי 2 ).

באופן דומה, סכום ריבועי הערכים הוא סכום ריבועי הערכים של המספרים מ-1 עד 999,999 פחות X*X ועוד Y*Y.

יש לנו 2 משוואות פשוטות עם שני נעלמים ומכאן כבר הכל ברור.

אני ממליץ לך לעשות כמו שמישהו הראה באתר:

sum = sum + a[i] -i;
   sumSquare = sumSquare + a[i]*a[i] - i*i;

SUM מראה את X-Y ו-SUMSQUARE מראה את הפרש ריבועיהם.

תסביר למחשב איך לפתור את המשוואה הריבועית וסיימת.

בהצלחה!

זהירות! בפתרון זה יש שגיאת overflow, בתלות בטיפוסים ובארכיטקטורה. הקומפיילר לא יזהיר אותך על זה וזו שגיאה שקשה לראות בקוד.

בהנחה שint הוא 32 סיביות והחשבון נעשה ב-int-ים (כל המשתנים הם int) אז הערך של המכפלה יגלוש מעבר ל-32 סיביות!

[שניצל]

^^ בהחלט. צריך לדאוג להשתמש ב-long long (שהוא 64 ביט).