| כותב |
|
מור
אורח
הצטרף / הצטרפה: 01 October 2003
משתמש: אונליין
הודעות: 12647
|
| נשלח בתאריך: 04 April 2007 בשעה 21:23 | | IP רשוּם
|
|
|
|
שלום,
קודם כל ממש כל הכבוד על הפורום הזה ועל כל האתר בכלל!הספקתי להסתכל קצת והתרשמתי ממש- גם מהחומר וגם מהנכונות לעזור בבעיות שיש לנו בתרגילים!
יש לי 2 שאלות-
1.א.אני צריכה לממש פולינום מדרגה n-1 בעזרת רשימה מקושרת.אני יודעת שפולינום זה ביטוי אלגברי. אבל מה זה אומר מדרגה n-1?..ואיך אני אמורה לממש אותו כך שיהיה מושפע מפעולות שנרצה לבצע עליו?...
ב.אם אפשר יהיה לתת כיוון לאלגוריתם שמבצע הכפלת הפולינום בקבוע כלשהו ואלגוריתם שמבצע הכפלת הפולינום בפולינום אחר מדרגה 1,אשמח ממש...
2.א.איך אפשר לממש מחסנית בעזרת 2 תורים?הרי לפי מה שקראתי באתר-תור עובד לפי-מה שנכנס ראשון יוצא ראשון.ומחסנית-מה שנכנס ראשון יוצא אחרון..איך הם יכולים להתקשר יחד?..
ב.איך ניתן לממש 2 מחסניות באמצעות מערך אחד,כך שהפעולות pop ןpush יתבצעו בO(1).(דורשים שתתקיים גלישה באחת המחסניות אמ"ם המספר הכולל של האיברים ב2 המחסניות הוא n(.
סליחה שיצא קצת ארוך ושוב תודה רבה על העזרה!!
מור.
|
| חזרה לתחילת העמוד |
|
| |
צחי@
משתמש חבר
הצטרף / הצטרפה: 02 January 2007
מדינה: Israel
משתמש: מנותק/ת
הודעות: 209
|
| נשלח בתאריך: 05 April 2007 בשעה 21:29 | | IP רשוּם
|
|
|
|
פולינום מדרגה n-1 הוא פולינום שהחזקה הגבוהה ביותר בו היא n-1, כלומר פולינום מהצורה:
קוד:
P(X) = C(n-1) * X^(n-1) + C(n-2) * X^(n-2) + ... + C(2) * X^2 + C(1) * X^1 + C(0)
|
|
|
אם את מחפשת איך לשמור את הפולינום כרשימה אז אם תבחני את המבנה של הפולינום תראי שה-X-ים כבר מוגדרים עם יחס סדר - מה שנשאר זה לשמור בכל איבר ברשימה את המקדם של החזקה המתאימה.
- הכפלה בקבוע או בפולינום מדרגה 1 ? מכפילים באותה הדרך שכופלים איברים מחוברים במתמטיקה - זה אותו אלגוריתם - תחילה כופלים ולאחר מכן מסכמים את האיברים מאותה החזקה. שימי לב שייתכן שתצטרכי להוסיף איברים לרשימה (במקרה של כפל בפולינום מדרגה 1 ומעלה).
|
| חזרה לתחילת העמוד |
|
| |
מור
אורח
הצטרף / הצטרפה: 01 October 2003
משתמש: אונליין
הודעות: 12647
|
| נשלח בתאריך: 06 April 2007 בשעה 11:24 | | IP רשוּם
|
|
|
|
תודה צחי!
אם הבנתי אותך נכון-אם n שלי הוא 5- אז הדרגה הכי גבוהה שתהיה לי(=שזה אומר חזקה)-היא 4 .אז למה לשמור רק את המקדם?לא צריך לשמור גם את המעריך של כל איבר.(במידה ויש)
כשכופחם ייתכן שייצאו לי 2 איברים מאותה דרגה . למשל )2X-5(*(7X+8).
לחבר את האיברים בעלי אותה הדרגה?
ומה עושים עם האופרטורים?-הם מצטרפים למקדם?
אני חושבת שעדיין לא התרגלתי לשאלות במבנה נתונים...כשאומרים לי לממש- זה אומר שאני יכולה להמציא לאיבר שלי איזה נתונים שאני רוצה ע"מ שתהיה לי גישה עליהם ושאני אוכל לפעול עליו?......
תודה רבה!
מור.
|
| חזרה לתחילת העמוד |
|
| |
צחי@
משתמש חבר
הצטרף / הצטרפה: 02 January 2007
מדינה: Israel
משתמש: מנותק/ת
הודעות: 209
|
| נשלח בתאריך: 06 April 2007 בשעה 13:52 | | IP רשוּם
|
|
|
|
איברים מאותה דרגה ניתן לצמצם לאיבר בודד - ולכן מספיק לשמור על יחס סדר נכון בתוך הרשימה לפי גודל המעריך ולא צריך לזכור מהו המעריך. אם זה יותר נוח - אפשר לשמור את המקדמים בסדר הפוך - תחילה את המקדם של X^0, לאחר מכן של X^1 וכו' - זה עניין של מימוש.
על איזה אופרטורים את מדברת ? +,- ?
אם כן אז הם מצטרפים מן הסתם למקדמים - אם המקדם שלילי אז זה -.
לגבי מבנה הנתונים - אם ביקשו ממך רשימה אז זה מבנה מאוד מסויים - את יכולה להחליט איזה משתנים יהיו בכל איבר וכל אספקט מימושי אחר כמובן- כל עוד הוא עונה על חוקיות של רשימה.
|
| חזרה לתחילת העמוד |
|
| |
מור
אורח
הצטרף / הצטרפה: 01 October 2003
משתמש: אונליין
הודעות: 12647
|
| נשלח בתאריך: 06 April 2007 בשעה 15:44 | | IP רשוּם
|
|
|
|
נכון....אם אני אשמור אותם לפי הסדר אז ברמת אין צורך לשמור את המעריכים.
תודה רבה!!
יש לי שאלה נוספת, אם אפשר-
נתון לי מערך בין N מספרים.נרצה להחליף כל מספר עם ערך שגדול ממנו וישב קרוב ביתר מימינו במערך. עבור הערכים עבורם לא קיים ערך כזה, יש לכתוב 0 בפלט.
לדוג'- עבור הקלט:4 3 5 2 3 1
הפלט יהיה: 0 4 0 5 5 3
צריך לתאר אלגוריתם שבמעבר אחד(!!!) על הקלט פותר את הבעיה הנתונה.
אני חשבתי לעבור על הקלט וישר להכניס אותו למחסנית- ואז להוציא 3 איברים- לטפל בהם-לבחור מביניהם את המ"ס שעוד אצטרך אותו(ע"יי דרך מסויימת) ואז להוציא 2-ואז לבחור מביניהם +הקודם את האחד שימשיך הלאה- ןלהוציא שוב שתיים וכך הלאה....
אבל הבנתי שזה נקרא לעבור יותר מפעם אחת....(אמרו לי שכשהופכים את הקלט- זה בדיוק כמו לעבור יותר מפעם אחת)
מה עוד אפשר לעשות עם מחסנית כדי שתעזור לי בתרגיל?
תודה ממש!
מור.
|
| חזרה לתחילת העמוד |
|
| |
צחי@
משתמש חבר
הצטרף / הצטרפה: 02 January 2007
מדינה: Israel
משתמש: מנותק/ת
הודעות: 209
|
| נשלח בתאריך: 06 April 2007 בשעה 19:55 | | IP רשוּם
|
|
|
|
לי נראה שתשתמשי במחסנית להחזיק אינדקסים של איברים שעדיין לא מצאת להם מחליף,
לדוגמה:
איטרציה תוכן מחסנית מערך
0 - 4 3 5 2 3 1
1 0(האינדקס של 1) 4 3 5 2 3 1
2 1 4 3 5 2 3 3
3 1,2 4 3 5 2 3 3
4 3 4 3 5 5 5 3
5 3,4 4 3 5 5 5 3
6 ; 3,5 4 4 5 5 5 3
7 - 0 4 0 5 5 3
כלומר, בכל איטרציה מקדמים אינדקס i בתוך הרשימה במקום אחד, ומשווים את הערך של התא במערך עליו מצביע האינדקס עם הערך עליו מצביע האינדקס j שבראש המחסנית, אם
A[j]<A[i] אז עושים POP ומבצעים השמה A[j]<--A[i] .
חוזרים על התהליך עד שהתנאי A[j]<A[i] לא מתקיים עבור האינדקס j בראש המחסנית, ואז מקדמים את i לאיבר הבא.
כאשר i מגיע לסוף המערך, עושים POP לכל האינדקסים שנשארו במחסנית ושמים בהם 0.
|
| חזרה לתחילת העמוד |
|
| |
shoshan
מנהל האתר
הצטרף / הצטרפה: 16 July 2005
מדינה: Israel
משתמש: מנותק/ת
הודעות: 4637
|
| נשלח בתאריך: 06 April 2007 בשעה 21:22 | | IP רשוּם
|
|
|
|
פעם אחרת לא יזיק לנושא חדש לפתוח נושא חדש :)
__________________
עד מתי רשעים יעלוזו?
עַל כֵּן אֶמְאַס וְנִחַמְתִּי עַל עָפָר וָאֵפֶר.
|
| חזרה לתחילת העמוד |
|
| |
מור
אורח
הצטרף / הצטרפה: 01 October 2003
משתמש: אונליין
הודעות: 12647
|
| נשלח בתאריך: 07 April 2007 בשעה 21:17 | | IP רשוּם
|
|
|
|
היי צחי!
האינדקסים I ו J מאותחלים שניהם להצביע על האיבר הראשון ואז מתבצעת השאלה האם a[j] <a[i] אם כן עושים POP אם לא שומרים את האינדקס של האיבר הראשון במחסנית?ומה קורה עם I וJ ?איך מקדמים אותם?וממשיכים עם אותה שאלה?
|
| חזרה לתחילת העמוד |
|
| |
shoshan
מנהל האתר
הצטרף / הצטרפה: 16 July 2005
מדינה: Israel
משתמש: מנותק/ת
הודעות: 4637
|
| נשלח בתאריך: 07 April 2007 בשעה 21:50 | | IP רשוּם
|
|
|
|
נו...הוא כבר נתן לך 90% מהפתרון...את כל הקטע של החשיבה...תמשיכי בעבודה השחורה (:
__________________
עד מתי רשעים יעלוזו?
עַל כֵּן אֶמְאַס וְנִחַמְתִּי עַל עָפָר וָאֵפֶר.
|
| חזרה לתחילת העמוד |
|
| |
מור
אורח
הצטרף / הצטרפה: 01 October 2003
משתמש: אונליין
הודעות: 12647
|
| נשלח בתאריך: 08 April 2007 בשעה 11:09 | | IP רשוּם
|
|
|
|
האמת- צודק....
הייתי צריכה לשבת על זה קצת ובניתי את האלגוריתם...
צחי- תודה רבה!עזרת לי מאוד!
שיהיה חג שמח לכולם!
|
| חזרה לתחילת העמוד |
|
| |
צחי@
משתמש חבר
הצטרף / הצטרפה: 02 January 2007
מדינה: Israel
משתמש: מנותק/ת
הודעות: 209
|
| נשלח בתאריך: 08 April 2007 בשעה 11:43 | | IP רשוּם
|
|
|
|
אין על מה - בכיף. חג שמח !
|
| חזרה לתחילת העמוד |
|
| |
מאיה
אורח
הצטרף / הצטרפה: 01 October 2003
משתמש: אונליין
הודעות: 12647
|
| נשלח בתאריך: 10 April 2007 בשעה 10:26 | | IP רשוּם
|
|
|
|
שלום,
האם הפתרון המוצע (להחלפה של האיברים באיבר הגדול להם מימין) לא חורג מהדרישה שהאלגוריתם ירוץ ב - O(n)?
הרי אנחנו בעצם משתמשים במחסנית כדי לרוץ חזרה על תאים במערך שכבר עברנו עליהם...
תודה
|
| חזרה לתחילת העמוד |
|
| |
צחי@
משתמש חבר
הצטרף / הצטרפה: 02 January 2007
מדינה: Israel
משתמש: מנותק/ת
הודעות: 209
|
| נשלח בתאריך: 10 April 2007 בשעה 10:46 | | IP רשוּם
|
|
|
|
לא - זה עדיין O של n.
הוכחה: מס' פעולות ה-PUSH - לכל היותר n. מס' פעולות ה-POP - לכל היותר n.
+מעבר על n איברים:
|
| חזרה לתחילת העמוד |
|
| |
עדו
אורח
הצטרף / הצטרפה: 01 October 2003
משתמש: אונליין
הודעות: 12647
|
| נשלח בתאריך: 12 April 2007 בשעה 11:03 | | IP רשוּם
|
|
|
|
צר לי
אבל הדרישה היא לא O)N(
אלא מעבר פעם אחת על המערך
ולא זו הדרך לפיתרון
רמז: תנסו מהסוף להתחלה...
|
| חזרה לתחילת העמוד |
|
| |
shoshan
מנהל האתר
הצטרף / הצטרפה: 16 July 2005
מדינה: Israel
משתמש: מנותק/ת
הודעות: 4637
|
| נשלח בתאריך: 12 April 2007 בשעה 11:55 | | IP רשוּם
|
|
|
|
אם עוברים מהסוף עדיין צריך להשתמש במחסנית ולאחסן בה את כל האיברים שבמקומם שמנו 0 (והראשון הוא האיבר האחרון).
לכאורה זה נראה (בגלל הדוגמא) כאילו במעבר מהסוף להתחלה המספר ששמים בבמספרים הקטנים הוא האחרון שראינו, אבל עדיין יש אפשרות בצורך לחזור מספרים אחדים אחורה ברשימת המספרים הגדולים.
וזה כן מעבר אחד...אם באמת תסתכל על זה שלא עוברים על המחסנית כל פעם, אלא רק לאורך כל המעבר על המערך מוציאים ממנהאת כל האיברים...
__________________
עד מתי רשעים יעלוזו?
עַל כֵּן אֶמְאַס וְנִחַמְתִּי עַל עָפָר וָאֵפֶר.
|
| חזרה לתחילת העמוד |
|
| |
עדו
אורח
הצטרף / הצטרפה: 01 October 2003
משתמש: אונליין
הודעות: 12647
|
| נשלח בתאריך: 12 April 2007 בשעה 14:10 | | IP רשוּם
|
|
|
|
זה כל כך פשוט
ולא לשמור אינדקסים אלא את המספרים עצמם...
אם תרשום לך את המעבר לאורך המערך ומחסנית ותנסה לראות מה אתה עושה בעצם בכל שלב תמצא פיתרון הרבה יותר קל...
|
| חזרה לתחילת העמוד |
|
| |
shoshan
מנהל האתר
הצטרף / הצטרפה: 16 July 2005
מדינה: Israel
משתמש: מנותק/ת
הודעות: 4637
|
| נשלח בתאריך: 12 April 2007 בשעה 14:35 | | IP רשוּם
|
|
|
|
ברור ששומרים את המספרים, במערך שמנו אפסים (:
אבל כמו שאמרתי, הדוגמא מטעה...כן יש צורך לזכור את כל המספרים הגדולים עד כה...
זה נראה כאילו אפשר לבדוק מהסוף להתחלה מקסימום, כל פעם שמוצאים שמים באינדקס שלו 0 ושומרים אותו ואז עבור כל האיברים הבאים שקטנים ממנו שמים אותו,
אבל זה לא נכון.
__________________
עד מתי רשעים יעלוזו?
עַל כֵּן אֶמְאַס וְנִחַמְתִּי עַל עָפָר וָאֵפֶר.
|
| חזרה לתחילת העמוד |
|
| |
עדו
אורח
הצטרף / הצטרפה: 01 October 2003
משתמש: אונליין
הודעות: 12647
|
| נשלח בתאריך: 12 April 2007 בשעה 15:35 | | IP רשוּם
|
|
|
|
לא אמרתי לשמור רק אותו
מדובר במחסנית יש בה עוד ערכים ואנו לא שוכחים את השאר
בדקתי, זה עובד בודאות ויותר פשוט מהפיתרון של צחי
|
| חזרה לתחילת העמוד |
|
| |
shoshan
מנהל האתר
הצטרף / הצטרפה: 16 July 2005
מדינה: Israel
משתמש: מנותק/ת
הודעות: 4637
|
| נשלח בתאריך: 12 April 2007 בשעה 17:28 | | IP רשוּם
|
|
|
|
טוב.
(אני די בטוח שלזה התכוונו אבל טוב שדאגת לוודא)
אם למישהו (או מישהי) יש עוד תרגיל מעניין מעיין זה הוא מוזמן (או היא מוזמנת) לשלוח אותו
בנושא חדש ונשמח (או לפחות אני מאוד אשמח) להעיף מבט.
__________________
עד מתי רשעים יעלוזו?
עַל כֵּן אֶמְאַס וְנִחַמְתִּי עַל עָפָר וָאֵפֶר.
|
| חזרה לתחילת העמוד |
|
| |
נושאים פעילים
רשימת משתמשים
חיפוש
עזרה
הרשמה
התחברות
UnderWarrior Forums : 
מדעי המחשב
