סעיף א'

כתבו פעולה שמקבלת רשימה של רשימות של מספרים שלמים, בכל רשימה של מספרים שלמים יש ספרות (0-9) היוצרות מספרים שלם.

ראש הרשימה הוא האחדות, אחר כך עשרות וכו'.

כל המספרים כמובן חיוביים.

סעיף ב',

מהי הסיבוכיות (שימו לב חובה להתייחס לפעולות עזר שכתבתם)

ראשית נבנה פעולת עזר אשר תקבל רשימה של מספרים שלמים ותחזיר מספר שלם, הסיבוכיות של הפעולה:

O(n)

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

פתרון בשפת Java:

Java:

public static int convertListToInt(Node<Integer> lst)

{

Node<Integer> p = lst;

int result=0;

int mul = 1;

while(p!=null)

{

result+=p.getValue()*mul; // result=result + p.getValue()*mul;

mul*=10; //mul=mul*10;

p=p.getNext();

}

return result;

}

C#:

public static int ConvertListToInt(Node<int> lst)

{

Node<int> p = lst;

int result=0;

int mul = 1;

while(p!=null)

{

result+=p.GetValue()*mul; // result=result + p.GetValue()*mul;

mul*=10; //mul=mul*10;

p=p.GetNext();

}

return result;

}

כעת נפתור את השאלה עצמה בשימוש פעולת העזר:

Java:

public static int findMax( Node<Node<Integer>> lst )

{

Node<Node<Integer>> p = lst;

int max=-1;

if(p!=null)

{

max = convertListToInt ( p.getValue());

p = p.getNext();

}

while(p!=null)

{

Node<Integer> h = p.getValue();

int n = convertListToInt (h);

if(n>max)

max = n;

p = p.getNext();

}

return max;

}

C#:

public static int FindMax( Node<Node<int>> lst )

{

Node<Node<int>> p = lst;

int max=-1;

if(p!=null)

{

max = ConvertListToInt ( p.GetValue());

p = p.GetNext();

}

while(p!=null)

{

Node<int> h = p.GetValue();

int n = ConvertListToInt (h);

if(n>max)

max = n;

p = p.GetNext();

}

return max;

}

סעיף ב

הסיבוכיות של פעולת העזר ConvertListToInt שלנו היא O(n) כאשר n הוא אורך הרשימה.

בפעולה FindMax אנו סורקים רשימה של רשימות, נניח שאורכה הוא m. עבור כל איבר ברשימה זו אנו מבצעים קריאה לפעולת העזר.

נניח שמתוך רשימת הרשימות, אורכה המקסימלי n, אזי נוכל להגיד: שהסיבוכיות היא O(n*m).

כלומר על כל רשימה מתוך רשימת הרשימות ביצענו את פעולת העזר.