אופסשםמשתמש
New member
../images/Emo41.gif רשימת דילוגים עזרה..
קבלו תרגיל : בשאלה זו נדון באיחוד / פיצול של רשימות דילוגים דטרמיניסטיות. בכל סעיף הציעו את הפתרון הטוב ביותר שתוכלו מבחינת סיבוכיות זמן, ונתחו את הסיבוכיות. א. בהינתן שתי רשימות דילוגים דטרמיניסטיות, הציעו אלגוריתם לאיחודן לרשימת דילוגים תקנית אחת, המכילה את איחוד המפתחות. ב. חיזרו על סעיף א', כאשר נתון שכל האיברים ברשימה הראשונה קטנים מהאיבר הקטן ביותר ברשימה השנייה. ג. בהינתן מספר k, תארו אלגוריתם לפיצול רשימת דילוגים קיימת לשתי רשימות דילוגים, כאשר באחת יהיו כל האיברים שקטנים או שווים ל- k , ובשנייה כל שאר האיברים. עכשיו לפתרונות שלי, הבעיה שהם דיי טריוואלים אבל נראה לי יעילים למדיי : א. לקחת את השורה הכי תחתונה, איפה שהמידע, לאחד אותה עם השורה הכי תחתונה של הרשימה השניה, בסיבוכיות N.. ולטפס למעלה וליצור מפתחות אחת לכל 3 צמתים (זה אמור להיות דטרמיניסטי). אבל הם כתבו "המכילה איחוד המפתחות" שלא כל כך ברור לי.. ב. הייתי לוקח את כל רשימה 1 מדביק מימינה את רשימה 2 והכל טוב ויפה.. אבל הבעיה היא אם הרשימת דילוגים מבחינת גובה לא אותו גובה .. אני לא בדיוק מצליח למצוא לזה פתרון אלגנטי.. ג. מחפשים את המספר K ברשימה, או מוצאים, אז כל מה שהיה מימין למסלול שלו רשימה אחת, ומה שמשמאל כולל אותו רשימה שניה. אם לא מוצאים את K .. אותו דבר בדיוק .. מה רע בפתרונות הדיי פשוטים האלה, כנראה שיש יותר הגיונים, אבל אני משום מה לא רואה אותם..
קבלו תרגיל : בשאלה זו נדון באיחוד / פיצול של רשימות דילוגים דטרמיניסטיות. בכל סעיף הציעו את הפתרון הטוב ביותר שתוכלו מבחינת סיבוכיות זמן, ונתחו את הסיבוכיות. א. בהינתן שתי רשימות דילוגים דטרמיניסטיות, הציעו אלגוריתם לאיחודן לרשימת דילוגים תקנית אחת, המכילה את איחוד המפתחות. ב. חיזרו על סעיף א', כאשר נתון שכל האיברים ברשימה הראשונה קטנים מהאיבר הקטן ביותר ברשימה השנייה. ג. בהינתן מספר k, תארו אלגוריתם לפיצול רשימת דילוגים קיימת לשתי רשימות דילוגים, כאשר באחת יהיו כל האיברים שקטנים או שווים ל- k , ובשנייה כל שאר האיברים. עכשיו לפתרונות שלי, הבעיה שהם דיי טריוואלים אבל נראה לי יעילים למדיי : א. לקחת את השורה הכי תחתונה, איפה שהמידע, לאחד אותה עם השורה הכי תחתונה של הרשימה השניה, בסיבוכיות N.. ולטפס למעלה וליצור מפתחות אחת לכל 3 צמתים (זה אמור להיות דטרמיניסטי). אבל הם כתבו "המכילה איחוד המפתחות" שלא כל כך ברור לי.. ב. הייתי לוקח את כל רשימה 1 מדביק מימינה את רשימה 2 והכל טוב ויפה.. אבל הבעיה היא אם הרשימת דילוגים מבחינת גובה לא אותו גובה .. אני לא בדיוק מצליח למצוא לזה פתרון אלגנטי.. ג. מחפשים את המספר K ברשימה, או מוצאים, אז כל מה שהיה מימין למסלול שלו רשימה אחת, ומה שמשמאל כולל אותו רשימה שניה. אם לא מוצאים את K .. אותו דבר בדיוק .. מה רע בפתרונות הדיי פשוטים האלה, כנראה שיש יותר הגיונים, אבל אני משום מה לא רואה אותם..