יום ראשון, 27 באפריל 2014

שאלה ממגן במעדי המחשב ב עם תשובה מלאה פתרון מלא כולל הסבר (תיכנות)

רשימה L מכילה מספר כלשהו של חוליות כשתוכן כל חוליה מהווה תור של מספרים שלמים.
מגדירים תור המספרים העוקבים המקסימלי כתור המספרים העוקבים הגדול ביותר בתור הנתון
(שני מספרים עוקבים אם השני גדול מהרשון באחד)
למשל,

עבור התור הבא:
q1: 3, 5, 6, 7, 8, -1, 0, 1, 2, 3, 5, 6, 14, 1, 2

יתקבל תור המספרים העוקבים המקסימאלי הבא:
q2: -1, 0, 1, 2, 3
א. כתוב פעולה חיצונית שתקבל פרמטר תור q1 ותחזיר תור המהווה תור המספרים העוקבים המקסימאלי.
ב. כתוב פעולה חיצונית שתקבל את רשימת התורים כפרמטר ותחזיר את הסכום הגבוהה ביותר של:
תור המספרים העוקבים המקסימאלי.
ג. מהי סיבוכיות הריצה של הפעולה שכתבת בסעיף א' ושל הפעולה בסעיף ב', נמק!


תשובות:

הסבר לוגי של סעיף א':

אנחנו ניגשים אל תור ואמורים להחזיר אליו תור חדש 

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

אנחנו נעבוד עם שני תורות עזר: תור אחד (QH) שנכניס אליו את כל המספרים העוקבים בסידרה (נגדיל את המונה help באחד כל פעם שיש מספר עוקב) - עד שנגיע למספר שהוא לא עוקב -אם המונה help גדול מהמונה של התור QK אז אנחנו נעביר את כל התור שהיה לנו לתור השני (QK) ונכניס את הערך של המונה help ל maxlong.
ונרוקן את QH כדי לקבל את הרצף הבא של המספרים העוקבים



using System;
//using System.Collections.Generic; 
using Unit4.CollectionsLib;
using System.Linq;
using System.Text; 
namespace ConsoleApplication1
{
    class Program
    {
        public static Queue<int> Okev(Queue<int> Q1)
        {
            int help = 1, maxlong = 0;
            Queue<int> QK = new Queue<int>();
            Queue<int> QH = new Queue<int>();
            int x = Q1.Remove();
            QH.Insert(x);

            while (!Q1.IsEmpty())
            {
                if (Q1.Head() - 1 == x)
                {
                    help++;
                    x = Q1.Remove();
                    QH.Insert(x);
                }
                else
                {
                    x=Q1.Remove();
                    if (maxlong < help)
                    {
                        maxlong = help;
                        while (! QK.IsEmpty()) QK.Remove();

                        while(! QH.IsEmpty())
                        {
                           QK.Insert(QH.Remove());
                        }
                        help=1;
                    }
                    else
                        while(! QH.IsEmpty()) QH.Remove();
                    QH.Insert(x);
                   

                }
            }
             return QK;
            }

            
        

        static void Main(string[] args)
        {
            Queue<int> Q1 = new Queue<int>();
            Q1.Insert(1);
            Q1.Insert(1);
            Q1.Insert(1);
            Q1.Insert(2);
            Q1.Insert(3);
            Q1.Insert(4);
            Q1.Insert(1);
            Q1.Insert(1);
             Console.WriteLine( Okev(Q1).ToString());
             Console.ReadKey();
        }
    }
}



זה מה שהפעולה הזאת תחזיר
[1,2,3,4]



סעיף ב'

 public static int Scomhigh(List<Queue<int>> L)
        {
            int max;
            Node <Queue<int>> q = L.GetFirst();
            max = sicom (Okev(q.GetInfo()));
            while (q !=null)
            {
                if (sicom(Okev(q.GetInfo()))> max)
                    max= sicom (Okev(q.GetInfo()));
                q=q.GetNext();
            }
            return max;
        }

        public static int sicom (Queue<int> Q)
        {
            int sum = 0;
            while (!Q.IsEmpty())
                sum = sum + Q.Remove();

            return sum;
        }

ג'. סיבוכיות הריצה היא 
O(n)
כאשר n הוא מספר האיברים שנמצאים בתור

אין תגובות:

הוסף רשומת תגובה