פתרון מלא"תור שווה סכומים", הוא תור של מספרים שלמי...
פתרון מלא
"תור שווה סכומים", הוא תור של מספרים שלמים, המכיל מספר אי זוגי של איברים, כך שכל שני
איברים קיצוניים (ראשון+אחרון, שני+לפני האחרון וכו') שווים בסכומם לאיבר האמצעי של התור.
לדוגמא: התור הבא הוא "תור שווה סכומים" -
האיבר האמצעי הוא 25 וכל זוג איברים קיצוניים שווה ל 25
| 18← | 3 | 10 | 13 | 4 | 25 | 21 | 12 | 15 | 22 | ←7 |
18+7 = 25
3+22 = 25
10+15 = 25
13+12 = 25
4+21 = 25
הניחו שקיימת פעולה getAndRemoveLast, המקבלת תור לא ריק של מספרים שלמים. הפעולה מוציאה את האיבר שבסוף התור, ומחזירה את ערכו כתוצאה לזימון שלה. הפעולה שומרת על התור המקורי, למעט האיבר שהוסר. סיבוכיות הפעולה היא (O(n. אין צורך לממש פעולה זו.
כתבו פעולה חיצונית equalSums, המקבלת q תור של מספרים שלמים ומחזירה true אם התור הוא "תור שווה סכומים", אחרת יוחזר false.
פתרון בשפת java:
public static boolean equalSums(Queue<Integer> q)
{
int counter=0;
int realMid=0;
int mid = 0;
int f=0; //first
if(!q.istEmpty())
{
counter++;
f=q.remove();
}
int l=0; //last
if(!q.isEmpty())
{
counter++;
l = getAndRemoveLast(q);
}
mid = f+l;
while( !q.isEmpty() )
{
realMid = q.remove(); //נכון רק פעם אחת
counter++;
if(!q.isEmpty())
{
counter++;
f = realMid;
l = getAndRemoveLast(q);
if(f+l != mid)
return false;
}
}
return (realMid == mid && counter%2==1 );
}