Oppgave 1 a)

  public static int[] enkelFletting(int[] a, int[] b)
  {
    int[] c = new int[a.length + b.length];  // en tabell av rett størrelse
    int k = Math.min(a.length, b.length);    // lengden på den korteste

    for (int i = 0; i < k; i++)
    {
      c[2*i] = a[i];        // først en verdi fra a
      c[2*i + 1] = b[i];    // så en verdi fra b
    }
    // vi må ta med resten
    System.arraycopy(a, k, c, 2*k, a.length - k);
    System.arraycopy(b, k, c, 2*k, b.length - k);

    return c;
  }

Oppgave 1 b)

  public static String enkelFletting(String a, String b)
  {
    int k = Math.min(a.length(), b.length());  // lengden på den korteste  
    StringBuilder s = new StringBuilder();

    for (int i = 0; i < k; i++)
    {
      s.append(a.charAt(i)).append(b.charAt(i));
    }

    s.append(a.substring(k)).append(b.substring(k));

    return s.toString();
  }

Oppgave 2 a)

a

1 3 4 6 9 9 11   i

b

2 3 5 6 7 8 9 10 12 14   j

c	1 2 3 3 4 5 6                       k
Syv verdier er flettet sammen.

a

1 3 4 6 9 9 11   i

b

2 3 5 6 7 8 9 10 12 14   j

c	1 2 3 3 4 5 6 6 7                   k
Ni verdier er flettet sammen.

a

1 3 4 6 9 9 11   i

b

2 3 5 6 7 8 9 10 12 14   j

c	1 2 3 3 4 5 6 6 7 8 9               k
Elleve verdier er flettet sammen.

Oppgave 2 b)

Hvis a inneholder tallene 1, 2, 3 og b tallene 4, 5, 6, 7, 8, vil sammenligningen a[i] <= b[j] bli utført 3 ganger, dvs. lik a.length. Da har alle verdiene i a blitt kopiert over i c.

Hvis a inneholder tallene 1, 3, 5, 7 og b tallene 2, 4, 6, 8, vil a[i] <= b[j] bli utført 7 ganger, dvs. a.length + b.length - 1. Da har alle verdiene i a blitt kopiert over i c.

Hvis a inneholder m verdier og b inneholder n verdier, vil sammenligningen a[i] <= b[j] bli utført maksimalt m + n - 1 ganger og minst k ganger der k er det minste av tallene m og n.

Oppgave 3

  int[] a = Tabell.randPerm(10_000_000);
  int[] b = a.clone();

  long tid1 = System.currentTimeMillis();
  Tabell.flettesortering(a);
  tid1 = System.currentTimeMillis() - tid1;

  long tid2 = System.currentTimeMillis();
  Tabell.kvikksortering(b);
  tid2 = System.currentTimeMillis() - tid2;

  System.out.println("Flettesortering: " + tid1);
  System.out.println("Kvikksortering: " + tid2);

Oppgave 4

I alle tre metodene vil tilfellene a[0:m> med m <= 0 virke som en tom mengde. Det samme med b[0:n>. Tar vi f.eks. snittet, blir resultatet tomt (returverdien er 0). Men hvis m > a.length eller n > b.length, blir det kastet et ArrayIndexOutOfBoundsException. I koden burde det imidlertid ha blitt kastet et unntak hvis a[0:m> eller b[0:n> er ulovlige. F.eks. slik:

  public static int flett(int[] a, int m, int[] b, int n, int[] c)
  {
    if (m < 0 || m > a.length)
      throw new IllegalArgumentException("a[0:m> er ulovlig!");

    if (n < 0 || n > b.length)
      throw new IllegalArgumentException("b[0:n> er ulovlig!");

    int i = 0, j = 0, k = 0;
    while (i < m && j < n) c[k++] = a[i] <= b[j] ? a[i++] : b[j++];

    while (i < m) c[k++] = a[i++];   // tar med resten av a
    while (j < n) c[k++] = b[j++];   // tar med resten av b

    return k;   // antallet verdier som er lagt inn i c
  }

Oppgave 5

  public static int forskjellige2(int[] a)
  {
    if (a.length <= 1) return a.length;

    int[] b = new int[a.length-1];  // hjelpetabell

    int i = 1, k = 1, j = 0;
    while (i < a.length)
      if (a[i] != a[i-1]) a[k++] = a[i++];
      else b[j++] = a[i++];

    System.arraycopy(b, 0, a, k, j);
    return k;
  }

Oppgave 6

Løsningsforslag ikke laget.

Oppgave 7

  public static boolean erLik(int[] a, int m, int[] b, int n)
  {
    if (m < 0 || m > a.length)
      throw new IllegalArgumentException("a[0:m> er ulovlig!");

    if (n < 0 || n > b.length)
      throw new IllegalArgumentException("b[0:n> er ulovlig!");

    if (m != n) return false;  // forskjellige lengder

    if (a == b) return true;   // det samme intervallet

    for (int i = 0; i < m; i++)
      if (a[i] != b[i]) return false;

    return true;
  }

  public static boolean erLik(int[] a, int[] b)
  {
    return erLik(a,a.length,b,b.length);
  }

Oppgave 8

  public static int differens(int[] a, int m, int[] b, int n, int[] c)
  {
    if (m < 0 || m > a.length)
      throw new IllegalArgumentException("a[0:m> er ulovlig!");

    if (n < 0 || n > b.length)
      throw new IllegalArgumentException("b[0:n> er ulovlig!");

    int i = 0, j = 0, k = 0;

    while (i < m && j < n)
    {
      if (a[i] < b[j]) c[k++] = a[i++];
      else if (a[i] == b[j]) { i++; j++;}
      else j++;
    }
    while (i < m) c[k++] = a[i++];

    return k;
  }

  public static int differens(int[] a, int[] b, int[] c)
  {
    return differens(a, a.length, b, b.length,c);
  }

Oppgave 9

  public static boolean inklusjon(int[] a, int m, int[] b, int n)
  {
    if (m < 0 || m > a.length)
      throw new IllegalArgumentException("a[0:m> er ulovlig!");

    if (n < 0 || n > b.length)
      throw new IllegalArgumentException("b[0:n> er ulovlig!");

    int i = 0, j = 0;

    while (i < m && j < n)
    {
      if (a[i] < b[j]) i++;
      else if (a[i] == b[j]) {i++; j++;}
      else return false;
    }

    return j == n;
  }

  public static boolean inklusjon(int[] a, int[] b)
  {
    return inklusjon(a, a.length, b, b.length);
  }

Oppgave 10

  public static int xunion(int[] a, int m, int[] b, int n, int[] c)
  {
    if (m < 0 || m > a.length)
      throw new IllegalArgumentException("a[0:m> er ulovlig!");

    if (n < 0 || n > b.length)
      throw new IllegalArgumentException("b[0:n> er ulovlig!");

    int i = 0, j = 0, k = 0;

    while (i < m && j < n)
    {
      if (a[i] < b[j]) c[k++] = a[i++];
      else if (a[i] == b[j]) { i++; j++;}
      else c[k++] = b[j++];
    }
    while (i < m) c[k++] = a[i++];
    while (j < n) c[k++] = b[j++];

    return k;
  }

  public static int xunion(int[] a, int[] b, int[] c)
  {
    return xunion(a, a.length, b, b.length,c);
  }