演習 06

今回は、全ての問題において、前の問題で作成した関数を利用することを前提とする。

問題 1

二分木について、parent(i) 、 left(i) 、 right(i) の 3 つを関数として作成し、以下のプログラムを完成させよ。

• parent(i)：i 番の頂点の親の番号を返す関数
• left(i)：i 番の頂点の左の子の番号を返す関数
• right(i)：i 番の頂点の右の子の番号を返す関数

void setup() {
  noLoop();
}

void draw() {
  for (int i = 1; i < 4; ++i) {
    println(i + "番の親は" + parent(i) + "番");
    println(i + "番の左の子は" + left(i) + "番");
    println(i + "番の右の子は" + right(i) + "番");
  }
}

実行結果

1番の親は0番
1番の左の子は3番
1番の右の子は4番
2番の親は0番
2番の左の子は5番
2番の右の子は6番
3番の親は1番
3番の左の子は7番
3番の右の子は8番

問題 2

二分木について、hasLeft(i, n) 、hasRight(i, n) 、hasChild(i, n) 、hasRoot(i) 、 hasParent(i) の 5 つを関数として作成し、以下のプログラムを完成させよ。 それぞれの関数の中で、問題 1 で作成した parent(i)、left(i) 、right(i) を適切に利用すること。

• hasLeft(i, n)：配列の先頭 n 個で表される二分木について、 i 番の頂点が左の子を持つとき true 、そうでないとき false を返す関数
• hasRight(i, n)：配列の先頭 n 個で表される二分木について、 i 番の頂点が右の子を持つとき true 、そうでないとき false を返す関数
• hasChild(i, n)：配列の先頭 n 個で表される二分木について、 i 番の頂点が左右どちらかの子を持つとき true 、そうでないとき false を返す関数
• isRoot(i)：i 番の頂点が根のとき true 、そうでないとき false を返す関数
• isParent(i)：i 番の頂点が親を持つとき true 、そうでないとき false を返す関数

void setup() {
  noLoop();
}

void draw() {
  int[] data = {76, 74, 58, 50, 54, 25, 42, 23, 41, 39};
  printStatus(data, 0);
  println();
  printStatus(data, 3);
  println();
  printStatus(data, 4);
  println();
  printStatus(data, 7);
}

void printStatus(int[] data, int i) {
  println("hasChild(" + i + ") == " + hasChild(i, data.length));
  println("hasLeft(" + i + ") == " + hasLeft(i, data.length));
  if (hasLeft(i, data.length)) {
    println("  left(" + i + ") == " + left(i));
    println("  data[left(" + i + ")] == " + data[left(i)]);
  }
  println("hasRight(" + i + ") == " + hasRight(i, data.length));
  if (hasRight(i, data.length)) {
    println("  right(" + i + ") == " + right(i));
    println("  data[right(" + i + ")] == " + data[right(i)]);
  }
  println("hasParent(" + i + ") == " + hasParent(i));
  if (hasParent(i)) {
    println("  parent(" + i + ") == " + parent(i));
    println("  data[parent(" + i + ")] == " + data[parent(i)]);
  }
  println("isRoot(" + i + ") == " + isRoot(i));
}

int left(int i) {
}

int right(int i) {
}

int parent(int i) {
}

boolean isRoot(int i) {
}

boolean hasLeft(int i, int n) {
}

boolean hasRight(int i, int n) {
}

boolean hasParent(int i) {
}

boolean hasChild(int i, int n) {
}

実行結果

hasChild(0) == true
hasLeft(0) == true
  left(0) == 1
  data[left(0)] == 74
hasRight(0) == true
  right(0) == 2
  data[right(0)] == 58
hasParent(0) == false
isRoot(0) == true

hasChild(3) == true
hasLeft(3) == true
  left(3) == 7
  data[left(3)] == 23
hasRight(3) == true
  right(3) == 8
  data[right(3)] == 41
hasParent(3) == true
  parent(3) == 1
  data[parent(3)] == 74
isRoot(3) == false

hasChild(4) == true
hasLeft(4) == true
  left(4) == 9
  data[left(4)] == 39
hasRight(4) == false
hasParent(4) == true
  parent(4) == 1
  data[parent(4)] == 74
isRoot(4) == false

hasChild(7) == false
hasLeft(7) == false
hasRight(7) == false
hasParent(7) == true
  parent(7) == 3
  data[parent(7)] == 50
isRoot(7) == false

問題 3

まず前の問題の draw 関数を以下のように書き換えよ。

void swap(int[] data, int i, int j) {
  int tmp = data[i];
  data[i] = data[j];
  data[j] = tmp;
}

void draw() {
  int[] data = {76, 74, 58, 50, 54, 25, 42, 23, 41, 39, 68};

  println("before swap");
  println("isHeap(data, 10) == " + isHeap(data, 10));
  println("isHeap(data, 11) == " + isHeap(data, 11));

  swap(data, 4, 10);

  println("after swap");
  println("isHeap(data, 10) == " + isHeap(data, 10));
  println("isHeap(data, 11) == " + isHeap(data, 11));
}

ieHeap(data, n) を関数として作成し、プログラムを完成させよ。

• isHeap(data, n)：配列 data の先頭 n 個で表される二分木がヒープのとき true 、そうでないとき false を返す関数

実行結果

before swap
isHeap(data, 10) == true
isHeap(data, 11) == false
after swap
isHeap(data, 10) == true
isHeap(data, 11) == true

ヒント

boolean isHeap(int[] data, int n) {
  for (int i = 1; i < n; ++i) {
    // ヒープの条件を満たさなければfalseを返す
  }
  return true;
}

問題 4

まず前の問題の draw 関数を以下のように書き換えよ。

void draw() {
  int[] data = {51, 13, 40, 95, 60, 26, 97, 68, 81, 24, 52, 42, 15, 27, 47, 94, 34, 85, 32, 48};

  for (int i = 0; i < data.length; ++i) {
    println("before siftup: isHeap(data, " + (i + 1) + ") == " + isHeap(data, i + 1));
    siftup(data, i);
    println("after siftup : isHeap(data, " + (i + 1) + ") == " + isHeap(data, i + 1));
  }
}

siftup(data, i) を関数として作成し、プログラムを完成させよ。

• siftup(data, i)：i - 1 番目までヒープの条件が保たれている配列 data において、data の i番目の要素をヒープに追加する関数

実行結果

before siftup: isHeap(data, 1) == true
after siftup : isHeap(data, 1) == true
before siftup: isHeap(data, 2) == true
after siftup : isHeap(data, 2) == true
before siftup: isHeap(data, 3) == true
after siftup : isHeap(data, 3) == true
before siftup: isHeap(data, 4) == false
after siftup : isHeap(data, 4) == true
before siftup: isHeap(data, 5) == false
after siftup : isHeap(data, 5) == true
before siftup: isHeap(data, 6) == true
after siftup : isHeap(data, 6) == true
before siftup: isHeap(data, 7) == false
after siftup : isHeap(data, 7) == true
before siftup: isHeap(data, 8) == false
after siftup : isHeap(data, 8) == true
before siftup: isHeap(data, 9) == false
after siftup : isHeap(data, 9) == true
before siftup: isHeap(data, 10) == true
after siftup : isHeap(data, 10) == true
before siftup: isHeap(data, 11) == false
after siftup : isHeap(data, 11) == true
before siftup: isHeap(data, 12) == false
after siftup : isHeap(data, 12) == true
before siftup: isHeap(data, 13) == true
after siftup : isHeap(data, 13) == true
before siftup: isHeap(data, 14) == true
after siftup : isHeap(data, 14) == true
before siftup: isHeap(data, 15) == false
after siftup : isHeap(data, 15) == true
before siftup: isHeap(data, 16) == false
after siftup : isHeap(data, 16) == true
before siftup: isHeap(data, 17) == true
after siftup : isHeap(data, 17) == true
before siftup: isHeap(data, 18) == false
after siftup : isHeap(data, 18) == true
before siftup: isHeap(data, 19) == true
after siftup : isHeap(data, 19) == true
before siftup: isHeap(data, 20) == false
after siftup : isHeap(data, 20) == true

ヒント

void siftup(int[] data, int i) {
  while (/* （i番の頂点が親を持つ）かつ（i番の頂点の値 > i番の頂点の親の値） */) {
    swap(data, i, parent(i));
    i = parent(i);
  }
}

問題 5

まず前の問題の draw 関数を以下のように書き換えよ。

void draw() {
  int[] data = {21, 74, 58, 50, 54, 25, 42, 23, 41, 39};

  println("before siftdown");
  println("isHeap(data, 10) == " + isHeap(data, 10));

  siftdown(data, 10);

  println("after siftdown");
  println("isHeap(data, 10) == " + isHeap(data, 10));
}

siftdown(data, i, n) を関数として作成し、プログラムを完成させよ。

• siftdown(data, n)：配列 data の先頭 n 個で表される二分木（根の左部分木と右部分木はヒープの条件が満たされている）をヒープとして再構築する関数

実行結果

before siftdown
isHeap(data, 10) == false
after siftdown
isHeap(data, 10) == true

ヒント

int greaterChild(int[] data, int i, int n) {
  if (!hasRight(i, n)) {
    return /* iの左の子の番号 */;
  }
  if (data[left(i)] > data[right(i)]) {
    return /* iの左の子の番号 */;
  } else {
    return /* iの右の子の番号 */;
  }
}

void siftdown(int[] data, int n) {
  int i = 0;
  int g  = greaterChild(data, i, n);
  while (/* （i番の頂点が子を持つ）かつ（i番の頂点の値 < i番の頂点の大きい方の子の値） */) {
    swap(data, i, g);
    i = g;
    g = greaterChild(data, i, n);
  }
}

問題 6

まず前の問題の draw 関数を以下のように書き換えよ。

void draw() {
  int[] data = {51, 13, 40, 95, 60, 26, 97, 68, 81, 24, 52, 42, 15, 27, 47, 94, 34, 85, 32, 48};

  heapSort(data);

  println("after sort");
  printArray(data);

  if (isSorted(data)) {
    println("OK");
  } else {
    println("NG");
  }
}

boolean isSorted(int[] data) {
  for (int i = 1; i < data.length; ++i) {
    if (data[i - 1] > data[i]) {
      return false;
    }
  }
  return true;
}

ヒープソートを実装した関数 heapsort(data) を作成し、プログラムを完成させよ。

実行結果

after sort
[0] 13
[1] 15
[2] 24
[3] 26
[4] 27
[5] 32
[6] 34
[7] 40
[8] 42
[9] 47
[10] 48
[11] 51
[12] 52
[13] 60
[14] 68
[15] 81
[16] 85
[17] 94
[18] 95
[19] 97
OK

ヒント

void heapSort(int[] data) {
  for (int i = 0; i < data.length; ++i) {
    siftup(data, i);
  }
  for (int i = data.length - 1; i > 0; --i) {
    // ヒープの先頭と未ソート部分の末尾を入れ替える
    // 未ソート部分をヒープに再構築する
  }
}