מה"ט מבני נתונים ותכנות מונחה עצמים — הנדסאי תוכנה — קיץ 2022 מועד א' (97105)

שרשרת חוליות מטיפוס שלם; "שרשרת ההפרשים" שלה היא שרשרת חדשה שבה כל איבר הוא ההפרש בערך מוחלט בין כל זוג איברים סמוכים במקור. דוגמה: 5,20,9,6,5,8,2 -> 15,11,3,1,3,6. הפעלה חוזרת עד לאיבר יחיד ("השורד"): ...-> 4,8,2,2,3 -> 4,6,0,1 -> 2,6,1 -> 4,5 -> 1.

דוגמה: השרשרת 5→20→9→6→5→8→2 (7 חוליות); שרשרת ההפרשים שלה: |20-5|=15, |9-20|=11, |6-9|=3, |5-6|=1, |8-5|=3, |2-8|=6 — כלומר 15→11→3→1→3→6 (6 חוליות). לסעיף ב׳: הפעלה חוזרת עד שנותר איבר אחד ("השורד"): 5,20,9,6,5,8,2 → 15,11,3,1,3,6 → 4,8,2,2,3 → 4,6,0,1 → 2,6,1 → 4,5 → 1. הפעולה מחזירה 1.

5 → 20 → 9 → 6 → 5 → 8 → 2 → null
(הפרשים) 15 → 11 → 3 → 1 → 3 → 6 → null
(הפרשים) 4 → 8 → 2 → 2 → 3 → null
(הפרשים) 4 → 6 → 0 → 1 → null
(הפרשים) 2 → 6 → 1 → null
(הפרשים) 4 → 5 → null
(הפרשים) 1 → null   <- השורד

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

public class A {
    protected int x;
    public A() {
        x = 0;
    }
    public void method(int num) {
        x += num;
    }
    public String toString() {
        return "" + x;
    }
}// end of class A

public class B extends A {
  private int y;
  public B()
  {
      super();
      y = 1;
  }
   public void method(int num)  {
      x -= num;
      y += num;
  }
  public String toString()  {
      return "" + x + "." + y;
  }
}// end of class B

public class C extends A {
  private int y;
  public C()
  {
      super();
      y = 10;
  }
  public void method(int num)  {
      x += num;
      y += num;
  }
  public String toString()  {
        return "" + x + "/"+ y;
  }
} // end of class C

public class Test
{
    public static void main (String [] args)
    {
        A [] array = new A[4];
        array[0] = new C();
        array[1] = new B();
        array[2] = new A();
        array[3] = new B();

        for (int i = 0; i < array.length; i ++)
        {
            System.out.println ("array[" + i + "] = " + array[i]);
            array[i].method(i+2);
            System.out.println ("array[" + i + "] = " + array[i]);
        }
    }
}