שאלה במבני נתונים

[אופסשםמשתמש]

שאלה במבני נתונים

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

 

[טיורינג]

יכול להיות שאני מפספס משהו

אבל למה זה לא יעיל לעשות את זה במערך עצמו? הסיבוכיות של find היא O(1) וגם הסיבוכיות של ה-reverse הזה, לא? או שחייבים לעשות את זה ב logn?

 

[mE and Me]

reverse לא יהיה logn במערך

כי זה לא רק ה-reverse הטריוויאלי של i<->j אלא גם i+1<->j-1 וככה הלאה עד שמגיעים לממוצע שלהם (הופכים את סדר המערך שביניהם).

 

[אופסשםמשתמש]

אלוהים יעזור לי

ויש לי עוד תרגיל שאני לא מצליח לפתור ועוד 24 שעות המבחן, בבקשה מישהו ?

 

[טיורינג]

אה, ידעתי שפיספסתי משהו

לא שמתי לב שצריך להחליף את כל הערכים בניהם...

 

[אופסשםמשתמש]

כולנו נמות

אבל אני מוקדם יותר , אם לא תעזרו לי בתרגיל

ועוד שאלה, טיפה מורכבת, אבל תנסו לעקוב.. נניח אני רוצה להכניס איברים בסדר מסויים.. נניח יש לי צומת עם המילה "שלום" ועוד צומת עם המילה "מפגר" ברשימה מקושרת.. זה נראה כמחרוזת ככה "שלוםמפגר" אני רוצה להכניס בתו ה5 את המילה "_אני_" כדי שיהיא כתוב "שלום_אני_מפגר" אז אם המילים שלום ומפגר ברשימה מקושרת, אני שומר בכל צומת את האורך של המילה ורץ על הצמתים עד שאני יודע איפה להכניס.. הכל טוב ויפה, אבל אני צריך לעשות את ההכנסה הזאת בlog אז צריך איזה רשימת דילוגים או עץ רק אני לא יודע לפי מה לסדר את המילים. חשבתי למספר אותם או משהו, אבל אם אני מוסיף מילה באמצע אני צריך לרוץ על כל המילים אחריה ולעדכן את המספר שלהם.. וזה עקום למספר , כי המשתנים מוגבלים.. מישהו יש לו כיוון ?

 

[אופסשםמשתמש]

תשכחו מזה, אין סיכוי

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

 

[vinney]

תוכל להביא את הפתרונות?

 

[mE and Me]

מצטרף לבקשה

וגם לי יש מבחן מועד ב' במבני נתונים ביום ראשון, ככה שאתה [פותח השרשור] בחברה טובה

חוץ מזה, "צרת רבים - חצי נחמה"

 

[אופסשםמשתמש]

כן

אוקי לתרגיל הראשון עם התמונה, מצאתי פתרון ולפי הפתרון הבנתי, שאם שואלים אותי משהו כזה אני הולך למועד ב'.. אלוהים יעזור, זה איזה 2 עצים מוזרים.. http://webcourse.cs.technion.ac.il/234218/Spring2005/hw/WCFiles/dry2_sol.pdf תרגיל 5, אם מישהו מבין, אשמח להסבר מה הם רוצים מהחיים שלי

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

 

[vinney]

לגבי התרגיל השני

זה גם מה שעבר לי בראש, אבל לא ניסחתי את זה, אם אתה רוצה, אני אחשוב על זה כשיהיה לי משעמם

לגבי התרגיל הראשון, באמת נראה כמו סוג של התעללות שמתאים לטכניון

 

[אופסשםמשתמש]

אם הבנת את הראשון

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

 

[yossiea]

רגע...

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

 

[אופסשםמשתמש]

כן יותר יקר

 

[אופסשםמשתמש]

LOL אגב

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

 

[vinney]

עם זה אני לא מסכים

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

 

[אופסשםמשתמש]

עצוב מאוד

השאלות האלה מופיעות גם במבחן , וגם בתרגיל בית של סמסטר הבא

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

לכל פקולטה בטכניון יש שם, אצלינו זה פקולטת הפקטורים, המרצים נותנים סתם מבחן בלתי פתיר (ברצינות אף אחד לא פותר ממש את כל המבחן) ואז יש ממוצע 40, בא להם לנרמל הכל סביב 65, נותנים באחוזים פקטור שינרמל סביב 65 והמרצה קיבל מה שהוא רוצה.. כן אני מסכים זה חרא !! של שיטה.. אבל ככה זה בחיים

(או בטכניון)

 

[vinney]

ברור שזה יותר יקר

כשאתה מסובב מערך סיבוב ציר, אתה צריך לעבור (במקרה הגרוע ביותר) על N/2 איברים.

 

[yossiea]

איך בכל זאת...

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

 

[vinney]

יש פתרון

פה