אלגוריתם

[karoitay]

אלגוריתם

שלום... אני צריך למצוא אלגוריתם אשר בהינתן מערך ממויין של ממשיים שונים ימצא האם קיימים 4 איברים שונים במערך שסכומם הוא z. סדר הגודל של זמן הריצה צריך להיות (O(n^2logn. אשמח לקבל כיוון תודה

 

[ron369]

אתה יודע איך פותרים את הבעיה ל-2?

זה תרגיל יחסית קשה. תחשוב איך אפשר לפתור את זה עבור 2 איברים שונים במערך שסכומם הוא-z. אז, תשתמש באותה דרך בדיוק, עם שינויים קלים ב-4. בהצלחה.

 

[karoitay]

עבור 2 זה די פשוט

בסיבוכיות (O(n אפשר בקלות למצוא עבור 2 חשבתי להתחיל בשביל ה-4 עם שניים בכל צד השאלה היא איך לקדם אותם בדיוק....

 

[ron369]

אוקיי. יש לך עבור 2.

עכשיו אתה צריך להגיע לאותו מצב כמו מקודם. אבל, יש לך n^2lgn! אז מה אפשר לעשות?

 

[karoitay]

חשבתי על משהו בסגנון של

לעטוף הכל בפור שרץ מהתחלה לסוף ועבור על איבר לשים אינדקס בכל קצה ואז עם האיבר הרביעי לחלק את המערך ל2 כל פעם השאלה היא אין לקדם את שתי הקצוות.... לפי איזה השוואה של האיבר הרביעי... אני מקווה שאני מובן

 

[ron369]

תחשוב פשוט, לא יעיל, ומגעיל

גם אני חשבתי על התרגיל הזה (בדיוק) די הרבה זמן. לצערי, הפתרון שעליו עליתי בסופו של דבר הוא גועלי ממש, שנראה כאילו יעבוד בסיבוכיות נוראית, אבל יעבוד. בסופו של דבר הדרך נשארה גועלית, אבל נראה שהסיבוכיות היא כנדרש. כך שהדרך ה"חדשה", של ה-4, היא פשוט הישנה, של ה-2, במסווה של רדוקציה קטנה (וגועלית). תחשוב פשוט פשוט פשוט.

 

[karoitay]

בחשיבה,פשוטה, לא יעילה ומגעילה

אני מגיע ל n^3

 

[ron369]

תחשוב אז טיפה יותר טוב ../images/Emo13.gif

איך אתה מגיע ל-O(N^3)?

 

[karoitay]

ע"י

ע"י 2 לולאות מקוננות שבתוכם אני עושה חיפוש לשני איברים

 

[ron369]

תפרט קצת יותר...

 

[karoitay]

ככה

find4(A,z) { for j=1 to n-2 for i=2 to n-1 if find2(A,i+1,n,z-A-A[j]) return true //after all for loops ended return false } find2(A,p,r,z) { if p<r { if A[p]+A[r]=z return true if A[p]+A[r]>z return find2(A,p,r-1,z) if A[p]+A[r]<z return find2(A,p+1,r,z) } return false }​

 

[ron369]

נסה שימוש קצת יותר מהיר...

תחשוב על מכפלה קרטזית.

 

[karoitay]

ככה?

לעשות מערך שמכיל את כל הסכומים האפשריים ואז לעבור עליו?? אין משהו יותר פשוט? הרי אז אני צריך לשמור גם את האינדקסים של המקור (כדי לדעת מאיפה נוצר האיבר החדש).

 

[ron369]

לא ממש. מה הבעיה?

תיצור struct ותמיין לפי sum ולא לפי הגורמים. (אגב, יש פונקציה בשם qsort ב-C, אם זה עוזר)

 

[karoitay]

.....

אני לא ממיין לפי הגורמים פשוט אם יש לי שני זוגות של סכומים שנותנים לי את המספר המלא אני צריך לוודא שבשני הזוגות אין איזשהו איבר משותף (לכן אני צריך לשמור אינדקסים)

 

[ron369]

וזה עד כדי כך מסבר את העניינים?

נניח, תמצא זוג, ורק אז תבדוק אם כולם שווים.

 

[karoitay]

בכל אופן...

בשביל להגיע לn^2logn אני צריך אפושהוא לצמצם חצי מערך כל פעם חשבתי על משהו בסגנון של

for j=1 to n-3 { a=j+1 b=n while a<b { if binarysearch(A,a+1,b,z-A[a]-A[j]-A)=true​

בשלב הזה לפי תוצאות החיפוש הבינארי להוסיף 1 לa או להוריד 1 מ-b

}//end of while loop }//end of for loop​

השאלה היא לפי מה אני מחליט אם להוסיף 1 לa או להוריד 1 מ-b

 

[karoitay]

תודה בכל אופן

הסתדרתי כבר

 

[ron369]

מה עשית בסוף? ../images/Emo13.gif

 

[karoitay]

...

בניתי מערך של סכומי זוגות באורך n(n-1))/2) על 3 (עוד 2 עמודות בשביל האינדקסים) מיינתי אותו ואז עברתי עליו וכשמצאתי בו שני איברים (שהם 4 במקורי) בדקתי אם האינדקסים שונים.