| כותב |
|
turj
אורח
הצטרף / הצטרפה: 01 October 2003
משתמש: אונליין
הודעות: 12647
|
| נשלח בתאריך: 28 August 2006 בשעה 22:10 | | IP רשוּם
|
|
|
|
יש לי בעייה קטנה, הייתי רוצה לשמוע את דעתכם בעניין.
נתונה רשימה מקושרת חד כיוונית [ניתן להתקדם רק קדימה].
צריך להדפיס על המסך את האיבר ה N ברשימה מהסוף.
הדרך היחידה שאני חשבתי עליה היא לקחת שני פוינטרים, לשים אחד בהתחלה, את השני במקום N מההתחלה. ואז ללכת N צעדים עם שני הפוינטרים, ואז אחד הפוינטרים יעמוד בדיוק על האיבר ה N מהסוף.
אני בטוח שיש דרכים יותר יעילות לפתור את הבעייה, בואו נראה את היצירתיות שלכם..
[לא בהכרח יותר יעילות, אני מתכוון אולי במקום להשתמש בשני פוינטרים אפשר איכשהו להשתמש בפוינטר אחד ובמשתנה עזר, או כל רעיון יצירתי אחר]
|
| חזרה לתחילת העמוד |
|
| |
shoshan
מנהל האתר
הצטרף / הצטרפה: 16 July 2005
מדינה: Israel
משתמש: מנותק/ת
הודעות: 4637
|
| נשלח בתאריך: 28 August 2006 בשעה 22:52 | | IP רשוּם
|
|
|
|
אם הרשימה חד כיוונית איך אתה אמור ללכת מהסוף להתחלה עם הפויינטר השני ?
או שאני טועה ?
__________________
עד מתי רשעים יעלוזו?
עַל כֵּן אֶמְאַס וְנִחַמְתִּי עַל עָפָר וָאֵפֶר.
|
| חזרה לתחילת העמוד |
|
| |
turj
אורח
הצטרף / הצטרפה: 01 October 2003
משתמש: אונליין
הודעות: 12647
|
| נשלח בתאריך: 29 August 2006 בשעה 12:45 | | IP רשוּם
|
|
|
|
מצביע A נמצא N מקומות מההתחלה.
מצביע B נמצא בדיוק בהתחלה.
הם זזים ביחד, זאת אומרת מצביע B הולך צעד אחד ואז מצביע A הולך צעד אחד.
כאשר מצביע A מגיע לסוף הרשימה, הוא חוזר להתחלה [זה אפשרי, זה לא נקרא הליכה לאחור, הוא פשוט קופץ לעוגן הרשימה].
ובצורה הזו הם שניהם מתקדמים N צעדים.
בסוף יווצר מצב שמצביע A עומד N צעדים מהסוף.
אני בטוח שיש עוד פתרונות...
|
| חזרה לתחילת העמוד |
|
| |
אלצ'קו
אחראי פורומים
ג2ר פ33תי
הצטרף / הצטרפה: 20 January 2006
משתמש: מנותק/ת
הודעות: 609
|
| נשלח בתאריך: 29 August 2006 בשעה 13:04 | | IP רשוּם
|
|
|
|
למה אתה חושב שיש דרך יעילה יותר?
הסיבוכיות של הפעולה הזו היא O(n) (כי פונקציית העבודה שלך היא משהו
בסגנון a+2bn+c, כש-a,b,c קבועים).
אתה חושב שיש יותר טוב? ה"יותר טוב
מ-O(n)" הם בדרך כלל O(logn) או O(1). אתה רואה ברשימת המקושרת איזושהי
דרך לגישה אקראית (זו המשמעות הטכנית של O(1))? אתה רואה חזקות איפשהו
(זו המשמעות של לוג)?
כנראה שזו הדרך הכי טובה שתמצא.
ברמה הטכנית, ולא ברמת הסיבוכיות, יש מה לשפר: אם תשמור את גודל הרשימה
(שזה דבר הגיוני בפני עצמו), תוכל להשתמש רק במצביע אחד, שילך K-N צעדים,
כש-K הוא גודל הרשימה, ו-N הוא המיקום מהסוף.
|
| חזרה לתחילת העמוד |
|
| |
turj
אורח
הצטרף / הצטרפה: 01 October 2003
משתמש: אונליין
הודעות: 12647
|
| נשלח בתאריך: 29 August 2006 בשעה 13:08 | | IP רשוּם
|
|
|
|
כן, לספור כמה איברים ברשימה זאת האפשרות הראשונה שעלתה לי לראש, אבל אני רוצה משהו יותר יפה.
ואם תסתכל טוב במה שכתבתי:
" [לא בהכרח יותר יעילות, אני מתכוון אולי במקום להשתמש בשני פוינטרים אפשר
איכשהו להשתמש בפוינטר אחד ובמשתנה עזר, או כל רעיון יצירתי אחר] "
אז סתם, אני מחפש רעיון יצירתי אחר לפתור את הבעייה.
|
| חזרה לתחילת העמוד |
|
| |
ניר
מנהל האתר
הצטרף / הצטרפה: 12 January 2005
מדינה: Israel
משתמש: מנותק/ת
הודעות: 3296
|
| נשלח בתאריך: 29 August 2006 בשעה 13:47 | | IP רשוּם
|
|
|
|
לדעתי הפתרון שלך יפה..
__________________
מספר האייסיקיו שלי ו/או כתובת ה-MSN שלי אינם מהווים מוקד תמיכה
|
| חזרה לתחילת העמוד |
|
| |
אלצ'קו
אחראי פורומים
ג2ר פ33תי
הצטרף / הצטרפה: 20 January 2006
משתמש: מנותק/ת
הודעות: 609
|
| נשלח בתאריך: 29 August 2006 בשעה 14:04 | | IP רשוּם
|
|
|
|
turj כתב:
כן, לספור כמה איברים ברשימה זאת האפשרות הראשונה שעלתה לי לראש, אבל אני רוצה משהו יותר יפה.
ואם תסתכל טוב במה שכתבתי:
" [לא בהכרח יותר יעילות, אני מתכוון אולי במקום להשתמש בשני פוינטרים אפשר
איכשהו להשתמש בפוינטר אחד ובמשתנה עזר, או כל רעיון יצירתי אחר] "
אז סתם, אני מחפש רעיון יצירתי אחר לפתור את הבעייה.
|
|
|
כמו שניר אמר, הפיתרון שלך אחלה. כמו שאני אמרתי, אם הרשימה שלך שומרת גודל (לא אם תספור אותו לבד כחלק מהאלגוריתם!), אז כדאי להשתמש בו כדי לחסוך בערך חצי מזמן הפעולה.
|
| חזרה לתחילת העמוד |
|
| |
Fate
פורומיסט על
הצטרף / הצטרפה: 25 October 2005
משתמש: מנותק/ת
הודעות: 571
|
| נשלח בתאריך: 29 August 2006 בשעה 15:26 | | IP רשוּם
|
|
|
|
אפשר רקורסיבית, ללכת עד סוף הרשימה ולספור N עומק ביציאה חזרה מהרקורסיה...
זה אבל סיבוכיות קצת יותר גבוהה מהפיתרון שלך...
|
| חזרה לתחילת העמוד |
|
| |
לאו
אורח
הצטרף / הצטרפה: 01 October 2003
משתמש: אונליין
הודעות: 12647
|
| נשלח בתאריך: 29 August 2006 בשעה 17:59 | | IP רשוּם
|
|
|
|
א) יש ממשק פעולות המפשת תהליכים. קיימות פקודות "קודם ברשימה( L, p ) --> למצביע",
ופעולה "סוף-רשימה( L )" --> למצביע
==> האלגוריתם די פשוט:
p <-- סוף-רשימה
כל עוד לא סוף-רשימה בצע
p <-- קודם-ברשימה ( L, p )
הדפס ...
סוף לולאה
יעילות של האלגוריתם היא N*N
ב) האלגוריתם של turj בעל אותה עילות!! אפשר לארגן הזזת מצביע B בתוך תת-משימה
|
| חזרה לתחילת העמוד |
|
| |
אלצ'קו
אחראי פורומים
ג2ר פ33תי
הצטרף / הצטרפה: 20 January 2006
משתמש: מנותק/ת
הודעות: 609
|
| נשלח בתאריך: 29 August 2006 בשעה 18:54 | | IP רשוּם
|
|
|
|
לא. האלגוריתם של turj הולך N צעדים קדימה, ואחר-כך עוד K-N צעדים קדימה פעמיים. כלומר. פונקציית העבודה היא:
a + b*N + 2*b*(K-N) +c =
= a + b*N + 2*b*K - 2*b*N + c
= b*N - 2*n*N + a + c + 2*b*K
= a+c+2*b*K - b*N
כל החלק הימני קבוע, מה שמשאיר לנו ביטוי שתלוי לינארית ב-N. O(N). איך הגעת ל-N בריבוע השד יודע...
|
| חזרה לתחילת העמוד |
|
| |
Fate
פורומיסט על
הצטרף / הצטרפה: 25 October 2005
משתמש: מנותק/ת
הודעות: 571
|
| נשלח בתאריך: 29 August 2006 בשעה 21:54 | | IP רשוּם
|
|
|
|
לאו כתב:
א) יש ממשק פעולות המפשת תהליכים. קיימות פקודות "קודם ברשימה( L, p ) --> למצביע",
ופעולה "סוף-רשימה( L )" --> למצביע
==> האלגוריתם די פשוט:
p <-- סוף-רשימה
כל עוד לא סוף-רשימה בצע
p <-- קודם-ברשימה ( L, p )
הדפס ...
סוף לולאה
יעילות של האלגוריתם היא N*N
ב) האלגוריתם של turj בעל אותה עילות!! אפשר לארגן הזזת מצביע B בתוך תת-משימה |
|
|
אין קודם ברשימה, זה רשימה חד כיוונית....
אלא אם כן אתה רוצה לממש קודם ברשימה בסיבוכיות של O(N)...
ואז זה באמת NXN...שזה לא כלכך יעיל...
|
| חזרה לתחילת העמוד |
|
| |
turj
אורח
הצטרף / הצטרפה: 01 October 2003
משתמש: אונליין
הודעות: 12647
|
| נשלח בתאריך: 29 August 2006 בשעה 22:48 | | IP רשוּם
|
|
|
|
אוקיי, תודה על כל התגובות
FATE, הבאת רעיון שלא חשבתי עליו, שחיפשתי [עוד דרכים לפתרון]
אני מניח שאין עוד דרכים יצירתיות לפתרון הבעייה..
אז אני חושב שהנושא סגור
תודה 
|
| חזרה לתחילת העמוד |
|
| |
אלצ'קו
אחראי פורומים
ג2ר פ33תי
הצטרף / הצטרפה: 20 January 2006
משתמש: מנותק/ת
הודעות: 609
|
| נשלח בתאריך: 30 August 2006 בשעה 02:27 | | IP רשוּם
|
|
|
|
Fate כתב:
אפשר רקורסיבית, ללכת עד סוף הרשימה ולספור N עומק ביציאה חזרה מהרקורסיה...
זה אבל סיבוכיות קצת יותר גבוהה מהפיתרון שלך...
|
|
|
יש סיבה לבזבז זמן על רקורסיות?
|
| חזרה לתחילת העמוד |
|
| |
Fate
פורומיסט על
הצטרף / הצטרפה: 25 October 2005
משתמש: מנותק/ת
הודעות: 571
|
| נשלח בתאריך: 30 August 2006 בשעה 23:30 | | IP רשוּם
|
|
|
|
אלצ'קו כתב:
Fate כתב:
אפשר רקורסיבית, ללכת עד סוף הרשימה ולספור N עומק ביציאה חזרה מהרקורסיה...
זה אבל סיבוכיות קצת יותר גבוהה מהפיתרון שלך...
|
|
|
יש סיבה לבזבז זמן על רקורסיות?
|
|
|
כמו שאמרתי, הפתרון שלו הרבה יותר יעיל.
פשוט הוא חיפש עוד פתרונות\רעיונות של אנשים. אז זרקתי משהו....
|
| חזרה לתחילת העמוד |
|
| |
אלצ'קו
אחראי פורומים
ג2ר פ33תי
הצטרף / הצטרפה: 20 January 2006
משתמש: מנותק/ת
הודעות: 609
|
| נשלח בתאריך: 30 August 2006 בשעה 23:53 | | IP רשוּם
|
|
|
|
שוב, השאלה היא למה לא לממש את אותו רעיון, רק בלי רקורסיה?
|
| חזרה לתחילת העמוד |
|
| |
Fate
פורומיסט על
הצטרף / הצטרפה: 25 October 2005
משתמש: מנותק/ת
הודעות: 571
|
| נשלח בתאריך: 31 August 2006 בשעה 00:40 | | IP רשוּם
|
|
|
|
אפשר, אבל אז זה יהיה כתיבת משהו רקורסיבי בצורה איטרטיבית, וזה לרוב מגעיל...
אני יודע שתמיד אפשר לכתוב כל דבר רקורסיבי בצורה איטרטיבית יותר יעיל מבחינת זמן ריצה ומבחינת זיכרון.
אבל הקוד יהיה מגעיל
|
| חזרה לתחילת העמוד |
|
| |
אלצ'קו
אחראי פורומים
ג2ר פ33תי
הצטרף / הצטרפה: 20 January 2006
משתמש: מנותק/ת
הודעות: 609
|
| נשלח בתאריך: 31 August 2006 בשעה 00:51 | | IP רשוּם
|
|
|
|
במקרים מסובכים, כן. במקרים אחרים, לא.
רקורסיה זו בעצם לולאה ומחסנית + בזבוז זמן על העתקת פרמטרים וביצוע
קריאות והחזרות. במקרה של הרעיון שלך אפשר לוותר על הקריאות וההחזרות,
ופשוט לשמור במחסנית את כל המצביעים.
דוחפים את הראשון, את השני, את השלישי, וכך האלה, ואז מוציאים את n האיברים האחרונים במחסנית, והופל'ה - קיבלנו את האיבר ה-n מהסוף.
while (curnode.pnext)
{
mystack.push(curnode);
curnode = curnode.pnext;
}
for (i=1; i<n; i++) mystack.pop;
result = mystack.pop;
צריך לוודא שאין כאן טעות ב-1 לכיוון כזה או אחר, אבל מסובך? לא נראה לי...
|
| חזרה לתחילת העמוד |
|
| |
Fate
פורומיסט על
הצטרף / הצטרפה: 25 October 2005
משתמש: מנותק/ת
הודעות: 571
|
| נשלח בתאריך: 31 August 2006 בשעה 10:17 | | IP רשוּם
|
|
|
|
צודק,
לא כלכך מסובך, אבל עדיין צריך לממש מחסנית או להשתמש בעוד ספרייה קיימת ...
וכמו שאמרתי כל דבר רקורסיבי אפשר לכתוב יותר יעיל איטרטיבית, אבל לפעמים זה מגעיל..
|
| חזרה לתחילת העמוד |
|
| |
נושאים פעילים
רשימת משתמשים
חיפוש
עזרה
הרשמה
התחברות
UnderWarrior Forums : 
תיכנות
