מבנה נתונים: תורים ומחסנית

[ron369]

בסה"כ, אתה צריך למצוא את

כל ה"צירופים הלינאריים" של המכפלות של 2,3,5 כאשר התוצאה קטנה מ-N. מה הבעיה פה? אתה יכול לעשות פתרון חביב שבודק לכל מספר בין 1 ל-N אם הוא מתחלק כנדרש (סיבוכיות התוצאה היא NlgN). ואתה יכול לעשות את זה בצורה רקורסיבית חמודה כשבכל פעם אתה מוסיף מכפלה בכל אחד מהם, ובודק אם התוצאה קטנה מ-N, עם האינווארינטה שהגורם שנוסף אחרון הוא הכי גדול (כדי שלא תגיע לאותם מספרים כמה פעמים). אתה יכול עכשיו לקחת את הכל, ולשים את זה במערך, וככה למיין את הפלט (O(N) זמן ומקום). אם לא צריך למיין, זה יהיה "קצת יותר מהיר". במקרה שלך, עם המס' הראשוניים הספציפיים, ההבדל לא יהיה משמעותי. אבל, מי אנחנו מדמ"חניקים שנחליט מה משמעותי ומה לא. נשים לב שאם יש לנו את עץ הרקורסיה, אולי נוכל למיינו בזמן לינארי. ננסה למיין את העץ בזמן לינארי, בהנחה שהעץ לא קיצוני (שלרוב הצמתים יש כמות ממוצעת של בנים באותה רמה, וכולי', כלומר, ש: N>>מספר הראשוניים וגודלם (בצורה כללית), וכד'). עכשיו, הרעיון הוא שאם נמיין כל אחת מהרמות, הדבר ימיין פחות או יותר גם את הרמה הבאה. בפרט, נניח שהבנים של כל צומת ממוינים (לפי גודל או לפי הגורם הראשוני במכפלה, זה אותו הדבר). עכשיו צריך, איכשהו, למיין כל רמה. ואז, אחרי שכל אחת מהרמות ממויינת, ניתן בבירור לאחד אותן למערך בזמן לינארי במספר האיברים (בעצם, זה לא כזה ברור, אבל גם לא מסובך).

 

[ron369]

מצטער אם זה קצת מבולגן,

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

 

[shochat1]

תודה על זה עוד שאלה

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

 

[gil levi]

הסימון שלך לא נכון.

התכוונת: "נתונה לי קבוצה A של N מס' חיוביים. ויש לתאר אלגוריתם המקבל כקלט מס' T ומחזיר קבוצה חלקית של A, כך שסכום כל המס' שלה היא N בדיוק ובמקרה ולא קיימת קבוצה להחזיר תוצאה שלילית". האלגוריתם שלך לא ברור לי. אתה רוצה למצוא את כל הסכומים החלקיים האפשריים? בקשר לסיבוכיות: הבעיה שתארת זאת בעיית NPC שנקראת SUBSET-SUM. לא ידוע אם יש לה פתרון בזמן פולינומיאלי ואם תמצא פתרון בזמן פולינומיאלי אז בעצם הוכחת שP=NP. השאלה אם P=NP היא שאלה פתוחה ומי שיענה עליה יזכה בפרס של מליון דולר, כך שסביר שהאלגוריתם שלך לא רץ בזמן פולינומיאלי.

 

[shochat1]

וואלה צודק תיקון:

אם נתונה לי קבוצה A של n מס' חיוביים. ויש לתאר אלגוריתם המקבל כקלט מס' N ומחזיר קבוצה חלקית של A, כך שסכום כל המס' שלה היא N בדיוק ובמקרה ולא קיימת קבוצה להחזיר תוצאה שלילית. אני אגב לא חושב בזמן הריצה כ"כ מסובך זה צריך להיות משהו כמו O או nlogn דברים כאלו פשוטים

 

[gil levi]

אני די בטוח שלא.

תכתוב את האלגוריתם ונראה...

 

[shochat1]

אז ככה

for (i=0;i<=N;i++) if (sum==N) printf("success"); if (sum>N) printf ("failed")​

לא שכחתי שלפני צריך לבדוק שN>n לא מתקיים

 

[ron369]

ומה אם האיבר הראשון הוא 50*N?

 

[shochat1]

לא הבנתי

אבל נראה לי שאתה מדבר ברמה הרבה יותר גבוהה ממי שלמד עד רק שפת שפה C לא ברמה גבוהה מאוד והתחיל קורס 1 במבנה נתונים... בכל מקרה האיבר הראשון יכול להיות מספר ממש ולא משתנה...

 

[ron369]

כתבת בהודעה לפני ש-N מציין את האיבר

שנדרש לבדוק אם סכום איברים מהמערך שווה לו, לא?

 

[gil levi]

רגע,

מה זה sum ואיפה אתה משנה אותו? נראה לי שבפעם הראשונה אתה בודק אם האיבר הראשון ==N, אח"כ אם הראשון + השני ==N, אח"כ אם הראשון+השני+השלישי==N וכו'. אבל זה לא נכון, מה לגבי מקרה שבו הראשון + השלישי==N? אתה לא בודק אותו.

 

[shochat1]

לא משנה בכל מקרה

אבל תודה על עזרתכם כאן.... הגשתי את זה כבר היום

 

[ron369]

ולא הצלחת לפתור?

ואתה עוזב את זה ככה?! אחר"כ אנשים מתפלאים שהם מקבלים 50, סליחה שאני מתערב.

 

[gil levi]

יש בזה משהו

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

 

[ron369]

אני יודע ../images/Emo13.gif

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

 

[ron369]

ואחר"כ אני מתפלא שאני מקבל 66 במבחן

 

[gil levi]

לא נורא... יש מועדי ב'....

גם הציונים שלי לא היו בשמיים בסמסטר האחרון.