אני צריכה עזרה בפתרון שאלות תכנות

[פיונה11]

אני צריכה עזרה בפתרון שאלות תכנות

ששואלים בראיונות. ניסיתי לפתור ולא הצלחתי החידות הן- 1 ·נתונה רשימה מקושרת, בעזרת זיכרון נוסף בעלות O(1), בדוק האם קיים ברשימה מעגל. בהנחה שהשאלה מתכוונת לשאלה אם יש רשימה מעגלית, חשבתי להשתמש בשני מצביעים ,שאחד רץ בקפיצות של 2 ואחד בשל 1 ,ואם הם נפגשים , אז מדובר ברשימה מעגלית ואם מגיעים ל NUL אז לא. האם זה בזכרון של N ? 2.·בהינתן שני משתנים מסוג integer, החלף את תכנם ללא שימוש במשתנה עזר. א. בעזרת פעולות חיבור וחיסור. ב. בעזרת XOR. ידוע לי איך לעשות זאת עם משתנה עזר ,אבל בלי לא הצלחתי.. 3.· נתונות N מילים בא"ב הלועזי באורך M כל אחת. בהינתן מילה באורך M, מצא דרך לבדוק בסיבוכיות זמן של O(1) האם קיימת פרמוטציה שלה במאגר. תודה מראש!!!

 

[DNile]

1. כמה זכרון נוסף את משתמשת

עבור רשימה של 5 איברים? עבור רשימה של 10 איברים? עבור רשימה של 20 איברים? 2.

a = a - b b = b + a a = b - a a = a xor b b = a xor b a = a xor b​

3. בטוחה שביקשו סיבוכיות O של 1?

 

[פיונה11]

לגבי שאלה 1 נראה לי שזה לא משנה

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

 

[DNile]

נו,

אז אם אין קשר בין מספר האיברים לכמות הזכרון, אז זה O של 1.

 

[פיונה11]

תודה, רק רציתי להיות בטוחה.. שאלה

נוספת שנתקעתי בה- א.בהינתן בייט (8 ביטים) של אפסים ואחדים , מצא דרך להחזיר בעלות זמן של O של 1 את מס' האחדים בו. (רמז: להשתמש בזיכרון כאוות נפשך) ב. פתור את הבעיה כאשר נתונים 4 בייטים. לפי הרמז נראה שצריך להשתמש איכשהו ברקורסיה, לא? באיזה עוד אפשרויות ניתן להשתמש כאשר לא מגבילים אותנו מבחינת זיכרון?

 

[Desslok of Gamilon]

טבלת חיפוש ל byte אחד (8 ביטים) יש 256 אפשרויות שונות, או ערכים שונים. תחשבי מראש כמה "1"-ים יש בכל אפשרות כלשהי, ותשימי את התוצאה בטבלה (בגודל 256 כניסות). כששואלים אותך לגבי בייט ספציפי, פשוט תיגשי ישירות למקום המתאים בטבלה ותשלפי משם את התוצאה.

 

[פיונה11]

תודה! האם העיבוד המוקדם כלומר

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

 

[Desslok of Gamilon]

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

 

[MegaMango]

לגבי הפיתרון של שאלה 2

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

 

[MegaMango]

אה, ולגבי שאלה שלוש..

אם אנחנו לא יכולים לבצע אפילו M פעולות.. אתם הולכים לסקול אותי בגלל זה P: לעשות מערך בגודל N בחזקת M של בוליאנים ולבדוק האם הביט במקום של המילה דלוק או כבוי P: בסך הכל(אני חושב) כל פיתרון אחר דורש לפחות לעבור על המחרוזת עצמה... יכול להיות שזה מה שרוצים שנענה בסך הכל..זו שאלה תיאורטית ומדגישים בסיבוכיות זמן ריצה ולא זיכרון...

 

[MegaMango]

התבלבלתי,

לא N בחזקת M אלא מס' האותיות שבא"ב הלועזי בחזקת M (חשבתי שמדברים על שפה שיש בה N אותיות)

 

[ron369]

ואיך תבדוק את זה בO(1)?

 

[MegaMango]

זה הרעיון..

כמו שעושים מערך בגודל n, למשל arr[n] ורוצים לבדוק האם arr[n] הוא 1 או 0, אני מציע לעשות מערך גדול מאוד שכל תא בו מייצג צירוף אחר. עבור הצירופים שקיימים במאגר, arr[word] יהיה 1 ועבור אלה שלא, יהיה 0. פשוט צריך לבדוק האם המערך במקום של המילה שקיבלנו (נתייחס לתוכן של ה- char * כאל ההתקדמות מהנק' arr) if(arr[word]) return true; return false

 

[MegaMango]

ממ..למרות שבפועל

המחשב יצטרך להיכנס לarr + מספר בגודל M ביטים, אני לא חושב שמתייחסים לזה כ o(m). זה כמו להתייחס ל n+n לא כo(1) אלא כחסם של מספר פעולות הביטים שהמחשב עושה בחיבור ה-n.

 

[vinney]

זה לא מדויק

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

 

[MegaMango]

ויי חשבתי שהפיתרון שלי

יותר מדי מעורער מכדי להיות מציאותי >.>

 

[ron369]

אבל M לא חסום מלמעלה!

ועדיין יש לך בדיוק או (גדול) של lg(2^m) = m, אם אני לא טועה (ואין לי כוח לבדוק את זה עכשיו).

 

[vinney]

אמרתי שאתה חייב לחסום את M

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

 

[ron369]

לפי איך שאני מבין את זה,

הסיבוכיות של עיבוד מספר היא לוגריתמית, ולכן אפשר "להתעלם" ממנה. האם אני טועה? האם פה מופיע הלוגריתם של M, או M עצמו, בחישוב הסיבוכיות? (אני פשוט מכיר את החידה, ולא שמעתי על פתרון שלה ב-O(1), אלא בO(m))

 

[vinney]

M עצמו, אם הוא לא חסום

הפתרון המעשי הוא בO של 1 (כי M תמיד חסום).