לשאלה המלאה (שאלה מספר שלוש) לחצו כאן

סעיף א: יש לכתוב פעולה שמקבלת רשימה של מס' שלמים ומס' שלם num.

3

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

צמתים עוקבים, שהסכום שלהם שווה ל-num.

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

שימו לב:

● ניתן להניח שהרשימה אינה ריקה.

לדוגמא:

אם התקבלה הרשימה null>3->4->1->2->6-> - lst ו7-=num הפעולה

תחזיר מצביע לצומת של ,2 מכיוון ש- 2+1+4=7

סעיף ב: כתבו פעולה רקורסיבית חיצונית בשם sumNumLists , שמקבלת

תור של רשימות של מס' שלמים ועוד מס' שלם. הפעולה תחזיר את כמות

הרשימות בתור, שבהן יש סדרת צמתים עוקבים שסכומם שווה למס' שהתקבל

כפרמטר.

חובה להשתמש בפעולה מסעיף א.

כותרת הפעולה:

public static int sumNumLists (Queue<<Node<Integer>> q, int

)num

סעיף ג: מהי הסיבוכיות של הפעולה שכתבת בסעיף ב'? יש לנמק.

סעיף א פתרון בשפת Java

Ordinal

public static Node<Integer> ordinal (Node<Integer> lst , int num)

{

        Node<Integer> p1 = lst;

        Node<Integer> p2 = lst;

        while(p1!=null)

        {

                int sum=0;

                p2 = p1;

                while(p2 !=null)

                {

                        sum+=p2.getValue();

                        p2=p2.getNext();

                        if(sum == num)

                                return p1;

                }

                p1=p1.getNext();

        }

        return null;

}

שפת C#

public static Node<int> Ordinal (Node<int> lst , int num)

{

        Node<int> p1 = lst;

        Node<int> p2 = lst;

        while(p1!=null)

        {

                int sum=0;

                p2 = p1;

                while(p2 !=null)

                {

                        sum+=p2.GetValue();

                        p2=p2.GetNext();

                        if(sum == num)

                                return p1;

                }

                p1=p1.GetNext();

        }

        return null;

}

סיבוכיות: במקרה הכי גרוע לא קיימת סדרת מספרים עוקבים שסכומה שווה ל-num, לכן גם הלולאה הפנימית תרוץ n פעמים. כאשר n הוא גודל הרשימה. לכן הסיבוכיות היא O(n^2.

סעיף ב' פתרון בשפת java

נקודת הנחה: אין צורך לשמור על התור.

public static int sumNumLists(  Queue<Node<Integer>> q , int num )

{

        if(q.isEmpty())

                return 0;

        int addition = 0;

         if (ordinal ( q.remove() , num  ) !=null)

                addition++;

        return addition +sumNumLists(q , num);

        

}

פתרון בשפת C#

public static int sumNumLists(  Queue<Node<int>> q , int num )

{

        if(q.IsEmpty())

                return 0;

        int addition = 0;

         if (Ordinal ( q.Remove() , num  ) !=null)

                addition++;

        return addition +SumNumLists(q , num);

        

}