לחצו כאן עבור השאלה המלאהתור מופלא הוא תור שבו האי...

לחצו כאן עבור השאלה המלאה


תור מופלא הוא תור שבו האיבר בראש התור שווה לסכום כל האיברים שבאים אחריו.

האיבר בראש התור הוא 50 והוא שווה לסכום כל האיברים שבאים אחריו...

"תור מדהים" הוא תור שבו כל איבר הוא תור מופלא, וסדר הופעת האיברים בו בסדר יורד מהסכום הגדול ביותר של התור המופלא....

כתוב פעולה המקבלת תור שכל אחד מאיבריו הוא תור של שלמים ומחזירה אמת אם הוא תור מדהים, אחרת מחזרה שקר..

תור מופלא
פתרון
ראשית נבין כי כדאי לנו לעשות פעולת עזר, לכן נסביר עבור הבוחן מה הפעולה מבצעת.

נכתוב פעולה אשרת מקבלת Queue תור של מספרים שלמים ומחזירה אמת אם וכאשר מדובר בתור מופלא. אחרת מחזירה שקר. נשים לב כי הפעולה איננה הורסת את התור!

נבנה פונקציית עזר בשם copy אשר מקבלת תור של מספרים שלמים ומחזירה העתק שלו. (וזאת מבלי להרוס את התור המקורי).

נשתמש בפעולת עזר של copy:
הסיבוכיות של פעולת השכפול היא: O(n) כאשר n הוא אורך התור (=כמותה האיברים בתור). בעצם אנחנו מרוקנים ומחזירים את כל התור כמה וכמה פעמים.
C#
public static Queue<int> Copy (Queue<int> q)
{
Queue<int> temp = new Queue<int>(); //empty Queue
Queue<int> result= new Queue<int>(); //empty Queue
while(!q.IsEmpty())
{
result.Insert(q.Head());
temp .Insert(q.Remove());
}

while(!temp.IsEmpty())
q.Insert(temp.Remove());

return result;
}

Java
public static Queue<Integer> copy (Queue<Integer> q)
{
Queue<Integer> temp = new Queue<Integer>(); //empty Queue
Queue<Integer> result= new Queue<Integer>(); //empty Queue
while(!q.isEmpty())
{
result.insert(q.head());
temp .insert(q.remove());
}

while(!temp.isEmpty())
q.insert(temp.remove());

return result;
}


מה הסיבוכיות של AmazingQueue:
קודם כל הסיבוכיות היא מינימום O(n) משום שהשתמשנו בפעולה הזאת פעם אחת בהתחלה.
בהמשך אנחנו מרוקנים את תור השכפול, פעולה שעלותה O(n), לכן סך הכל הסיבוכיות היא O(n)
C#:
public static bool AmazingQueue (Queue<int> queue)
{
Queue<int> q= copy(queue);

int f = 0; //first

if(!q.IsEmpty())
f = q.Remove();
else
return false;

int sum=0;

while(!q.IsEmpty())
sum+=q.Remove(); //sum=sum+q.Remove();
return sum==f;

}


Java:
public static boolean amazingQueue (Queue<Integer> queue)
{
Queue<Integer> q= copy(queue);

int f = 0; //first

if(!q.isEmpty())
f = q.remove();
else
return false;

int sum=0;

while(!q.isEmpty())
sum+=q.remove(); //sum=sum+q.remove();

return sum==f;

}


כעת נכתוב את הפעולה של סעיף א':
C#:
public static bool Awesome(Queue<Queue<int>> q)
{
Queue<Queue<int>> temp = new Queue<Queue<int>> ();
bool correct =true;
bool first = true;
int pre = 0;
while(!q.IsEmpty())
{
Queue<int> q1 = q.Remove();
if( !AmazingQueue(q1))
correct = false;
else if(first)
{
pre = q1.Head();
first = false;
}
else {
if( q1.Head() >= pre)
correct = false;
pre = q1.Head();
}

temp.Insert(q1);
}

// מחזיר את התור למצבו הראשון
while(!temp.IsEempty())
q.Insert(temp.Remove());
return correct;

}


Java:
public static bool awesome(Queue<Queue<Integer>> q)
{
Queue<Queue<Integer>> temp = new Queue<Queue<Integer>> ();
bool correct =true;
bool first = true;

int pre = 0;
while(!q.isEmpty())
{
Queue<Integer> q1 = q.remove();

if( !amazingQueue(q1))
correct = false;
else if(first)
{
pre = q1.head();
first = false;
}
else {
if( q1.head() >= pre)
correct = false;
pre = q1.head();
}

temp.insert(q1);
}

// מחזיר את התור למצבו הראשון
while(!temp.isEempty())
q.insert(temp.remove());

return correct;

}

סעיף ב
הסיבוכיות של הפעולה Awesome היא O(n*m) כאשר m הוא אורך התור של התורים (המתקבל בפונקציה Awesome ), ו-n הוא אורך התור המקסימלי שקיים מבין כל התורים של תור התורים.
עבור כל תור בתוך תור התורים, אנו מבצעים סריקה, מכאן הסיבוכיות. (ליד כל פעולת עזר הצגנו את הסיבוכיות הרלוונטית).