מציאת ערכים במערך

[uvdude]

מציאת ערכים במערך

יש לי שאלה כזאת: נתון מערך של n מספרים ממשיים, ועוד מספר ממשי z, נתון שכל המספרים שונים זה מזה. כתוב אלגוריתם שקובע האם קיימים: א. 2 איברים שונים במערך שסכומם הוא בדיוק z - זמן ריצה נדרש O(nlogn) ב. 3 איברים שונים במערך שסכומם הוא בדיוק z - זמן ריצה נדרש O(n^2) ג. 4 איברים שונים במערך שסכומם הוא בדיוק z - זמן ריצה נדרש O(n^2logn) ד. 5 איברים שונים במערך שסכומם הוא בדיוק z - זמן ריצה נדרש O(n^3) את הסעיפים הראשונים הצלחתי לפתור. בסעיף הראשון ממיינים את המערך בO(nlogn) ואז עוברים על המערך מההתחלה ומהסוף בו זמנית, עד שמגיעים או לא מגיעים לסכום הדרוש. בסעיף השני שוב ממיינים, סורקים את המערך פעם אחת (n פעמים) ועבור על תא בודקים את שאר המערך כמו בסעיף א'. אני תקוע עם 2 הסעיפים האחרונים. למישהו יש רעיון? תודה!

 

[vicz]

היי

לגבי ג': אתה מחשב סכום של כל שני איברים במערך המקורי ושומר אותם במערך (מומלץ לשמור עם כל סכום את הערכים שמהם הוא התקבל, תכף תראה למה). מערך זה הוא בגודל n^2 ממיין אותו ב- n^2lgn רץ משני הצדדים כמו בסעיף א' כשמוצא סכום מתאים בודק שכל מרכיביו שונים זה מזה לגבי ד: אתה מקבל אותו מ-ג' כמו שקיבלת את ב' מא' בהצלחה ויקי

 

[uvdude]

כמה בעיות

לגבי ג', זה אכן הפתרון אליו הגעתי היום, אבל הבעיה היא מה קורה כשאני רץ על המערך ומוצא זוג לא מתאים, את איזה מהפוינטרים אני מקדם, נדמה שנדרשת פה רקורסיה. לגבי ד': אם נעשה כמו שא' משתמש בב', נקבל n^3logn...

 

[vicz]

../images/Emo203.gif

לגבי ד': אתה לא צודק אתה ממיין מערך באורך n^2 פעם אחת בלבד! לאחר מכן עבור כל אחד מ-n המספרים אתה רץ על מערך זה משני הצדדים סה"כ: n^2 * n = n^3 לגבי ג': זה הפתרון המקובל לבעיה הזו (שיש לציין חוזרת על עצמה כל הזמן) צריך דרך יצירתית במקרה שמצאנו את הסכום הדרוש אך הוא מורכב ממספרים שלא כולם שונים. אם אני אחשוב על משהו אני אעלה לפה.

 

[johnny d]

אף פעם לא נדרשת רקורסיה.