רשימה מעגלית
- פותח הנושא yhaim
- פורסם בתאריך
חכם בלילה המקורי
New member
כמו מעגל החיים
בהתחלה אתה נולד באמצע אתה מבוגר בסוף אתה מת האם יש גילגול נשמות?
בהתחלה אתה נולד באמצע אתה מבוגר בסוף אתה מת האם יש גילגול נשמות?
ניסיון לתשובה
ע"י רקורסיה: תוכנית לדוגמא: בהנחה שהנקסט של האיבר האחרון מצביע על NULL וכשהפונקציה נקראת אז הפרמטר שיינתן יהיה האיבר הראשון void reverse(node *p) { if (node->next==NULL) cout << p->data; else { reverse(p->next); cout << p->data; } } התוכנית סורקת את הרשימה עד שהיא מגיעה לאיבר האחרון, ברגע שהיא מגיעה לאיבר האחרון התכנית מתחילה להדפיס את האיברים, כאשר האיבר האחרון שיודפס יהיה האיבר הראשון
ע"י רקורסיה: תוכנית לדוגמא: בהנחה שהנקסט של האיבר האחרון מצביע על NULL וכשהפונקציה נקראת אז הפרמטר שיינתן יהיה האיבר הראשון void reverse(node *p) { if (node->next==NULL) cout << p->data; else { reverse(p->next); cout << p->data; } } התוכנית סורקת את הרשימה עד שהיא מגיעה לאיבר האחרון, ברגע שהיא מגיעה לאיבר האחרון התכנית מתחילה להדפיס את האיברים, כאשר האיבר האחרון שיודפס יהיה האיבר הראשון
אני אתמול בעיקרון חשבתי על משהו כזה
של למצוא את המקסימום ברשימה (O(N) כמובן, ואז להפוך את הרשימה למספר בבסיס max+1 (להוסיף את האיבר הנוכחי, להתקדם הלאה ולכפול בmax+1 את מה שיש לנו ולהוסיף את האיבר הבא וכן הלאה עד הסוף) ואחרי שסיימנו פשוט "לחזור אחורה" באמצעות פעולות של mod וdiv (באופן דומה לאלגוריתם שבודק את כמות הספרות במספר). זמן הריצה יהיה O
העניין הוא שכמות הזכרון לא ממש קבועה אלא בכמות לוגריתמית של זכרון... אוף...
של למצוא את המקסימום ברשימה (O(N) כמובן, ואז להפוך את הרשימה למספר בבסיס max+1 (להוסיף את האיבר הנוכחי, להתקדם הלאה ולכפול בmax+1 את מה שיש לנו ולהוסיף את האיבר הבא וכן הלאה עד הסוף) ואחרי שסיימנו פשוט "לחזור אחורה" באמצעות פעולות של mod וdiv (באופן דומה לאלגוריתם שבודק את כמות הספרות במספר). זמן הריצה יהיה O
העניין הוא שכמות הזכרון לא ממש קבועה אלא בכמות לוגריתמית של זכרון... אוף...תשובה
גודל הרשימה הוא N . נחלק אותה ל K תתי רשימות שבכל אחד M אברים ( N=K*M ) . יש להגיע להתחלה של כל תת רשימה ( כאשר מתחילים מהתת רשימה האחרונה )ואז להפעיל שם את האלגוריתם של eresh רק על התת רשימה הזו. כלומר להגיע לסוף התת רשימה , להדפיס את האיבר, ללכת להתחלת התת רשימה , להגיע לסופ התת רשימה פחות איבר אחד להדפיסו וכך עד שמדפיסים את האיבר הראשון בתת רשימה. הסיבוכיות של הדפסת תת רשימה היא S1=(M+1)*N/2 הסיבוכיות של להגיע כל פעם להתחלת תת רשימה היא S2=(K-1)*N/2 סה"כ סיבוכיות היא S=S1+S2=(K+M)*N/2 נציב K=N/M S=(N/K+K)*N/2 על ידי גזירה אפשר להראות שמינימום מתקבל אם
גודל הרשימה הוא N . נחלק אותה ל K תתי רשימות שבכל אחד M אברים ( N=K*M ) . יש להגיע להתחלה של כל תת רשימה ( כאשר מתחילים מהתת רשימה האחרונה )ואז להפעיל שם את האלגוריתם של eresh רק על התת רשימה הזו. כלומר להגיע לסוף התת רשימה , להדפיס את האיבר, ללכת להתחלת התת רשימה , להגיע לסופ התת רשימה פחות איבר אחד להדפיסו וכך עד שמדפיסים את האיבר הראשון בתת רשימה. הסיבוכיות של הדפסת תת רשימה היא S1=(M+1)*N/2 הסיבוכיות של להגיע כל פעם להתחלת תת רשימה היא S2=(K-1)*N/2 סה"כ סיבוכיות היא S=S1+S2=(K+M)*N/2 נציב K=N/M S=(N/K+K)*N/2 על ידי גזירה אפשר להראות שמינימום מתקבל אם
K=sqrt(N) ואז S=N*(N/sqrt(N)+sqrt(N))/2=N*(sqrt(N)+sqrt(N))/2=N*sqrt(N)
Copyright©1996-2021,Tapuz Media Ltd. Forum software by XenForo® © 2010-2020 XenForo Ltd.