演習

問題 1

void setup() {
  noLoop();
}

void draw() {
  int[] data = new int[10];
  for (int i = 0; i < data.length; ++i) {
    data[i] = int(random(10));
  }
  printArray(data);
  println(f(data, data.length));
}

int f(int[] a, int k) {
  if (k == 0) {
    return 0;
  }
  return a[k - 1] + f(a, k - 1);
}

問題 2、問題 3

void setup() {
  noLoop();
}

void draw() {
  int[] data = new int[10000];
  for (int i = 0; i < data.length; ++i) {
    data[i] = int(random(100000));
  }

  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;
}

int parent(int i) {
  return (i - 1) / 2;
}

int left(int i) {
  return 2 * i + 1;
}

int right(int i) {
  return 2 * i + 2;
}

boolean isRoot(int i) {
  return i == 0;
}

boolean hasParent(int i) {
  return !isRoot(i);
}

boolean hasLeft(int i, int n) {
  return left(i) < n;
}

boolean hasRight(int i, int n) {
  return right(i) < n;
}

boolean hasChild(int i, int n) {
  return hasLeft(i, n);
}

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

boolean isHeap(int[] data, int n) {
  for (int i = 1; i < n; ++i) {
    if (data[parent(i)] < data[i]) {
      return false;
    }
  }
  return true;
}

void siftup(int[] data, int i) {
  if (!isRoot(i) && data[i] > data[parent(i)]) {
    swap(data, i, parent(i));
    siftup(data, parent(i));
  }
}

int greaterChild(int[] data, int i, int n) {
  if (!hasRight(i, n)) {
    return left(i);
  }
  if (data[left(i)] > data[right(i)]) {
    return left(i);
  } else {
    return right(i);
  }
}

void siftdown(int[] data, int n, int i) {
  int g = greaterChild(data, i, n);
  if (hasChild(i, n) && data[i] < data[g]) {
    swap(data, i, g);
    siftdown(data, n, g);
  }
}

void heapSort(int[] data) {
  for (int i = 0; i < data.length; ++i) {
    siftup(data, i);
  }
  for (int n = data.length - 1; n > 0; --n) {
    swap(data, 0, n);
    siftdown(data, n, 0);
  }
}

問題 4

void setup() {
  noLoop();
}

void draw() {
  int[] data = {5, 9, 23, 26, 55, 66, 79, 80, 82, 93};
  find(data, 0);
  find(data, 5);
  find(data, 50);
  find(data, 55);
  find(data, 93);
  find(data, 100);
}

void find(int[] data, int target) {
  int index = linearSearch(data, 0, target);
  if (index > -1) {
    println("Found: data[" + index + "] == " + target);
  } else {
    println("Not Found: " + target);
  }
}

int linearSearch(int[] data, int k, int target) {
  if (k == data.length) {
    return -1;
  }
  if (data[k] == target) {
    return k;
  }
  return linearSearch(data, k + 1, target);
}

問題 5

void setup() {
  noLoop();
}

void draw() {
  int[] data = generateData(20);

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

  bubbleSort(data, data.length);

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

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

int[] generateData(int n) {
  int[] result = new int[n];
  for (int i = 0; i < n; ++i) {
    result[i] = int(random(50000));
  }
  return result;
}

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

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

void bubbleSort(int[] data, int n) {
  if (n > 0) {
    for (int i = 1; i < n; ++i) {
      if (data[i - 1] > data[i]) {
        swap(data, i - 1, i);
      }
    }
    bubbleSort(data, n - 1);
  }
}

問題 6

void setup() {
  noLoop();
}

void draw() {
  int[] data = generateData(20);

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

  bubbleSort(data);

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

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

int[] generateData(int n) {
  int[] result = new int[n];
  for (int i = 0; i < n; ++i) {
    result[i] = int(random(50000));
  }
  return result;
}

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

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

void bubbleSort(int[] data) {
  for (int n = data.length; n > 0; --n) {
    for (int i = 1; i < n; ++i) {
      if (data[i - 1] > data[i]) {
        swap(data, i - 1, i);
      }
    }
  }
}

問題 7

次のエラーが発生し、ソートが完了しません。

StackOverflowError
A StackOverflowError means that you have a bug that's causing a function
to be called recursively (it's calling itself and going in circles),
or you're intentionally calling a recursive function too much,
and your code should be rewritten in a more efficient manner.

関数呼び出し時には、関数呼び出し前の状態をメモリに格納しておく必要があり、それはスタック領域に格納されます。スタック領域が足りなくなると StackOverflowError が発生します。そのため、関数の再帰呼び出しで再帰できる回数には上限があることに注意しましょう。

問題 8

void setup() {
  noLoop();
}

void draw() {
  for (int i = 0; i <= 10; ++i) {
    println("fibonacci(" + i + ") = " + fibonacci(i));
  }
}

int fibonacci(int n) {
  int f0 = 0;
  int f1 = 1;
  if (n == 0) {
    return f0;
  }
  if (n == 1) {
    return f1;
  }
  for (int i = 2; i <= n; ++i) {
    int tmp = f0 + f1;
    f0 = f1;
    f1 = tmp;
  }
  return f1;
}

問題 9

void setup() {
  noLoop();
}

void draw() {
  for (int i = 0; i <= 10; ++i) {
    println("fibonacci(" + i + ") = " + fibonacci(i));
  }
}

int fibonacci(int n) {
  if (n == 0) {
    return 0;
  }
  if (n == 1) {
    return 1;
  }
  return fibonacci(n - 1) + fibonacci(n - 2);
}

問題 10

int callCount = 0;

void setup() {
  noLoop();
}

void draw() {
  int start = millis();
  println("fibonacci(40) = " + fibonacci(40));
  int stop = millis();
  println("callCount = " + callCount);
  println("time = " + (stop - start) + " milli seconds");
}

int fibonacci(int n) {
  callCount += 1;
  if (n == 0) {
    return 0;
  }
  if (n == 1) {
    return 1;
  }
  return fibonacci(n - 1) + fibonacci(n - 2);
}

実行例

fibonacci(40) = 102334155
callCount = 331160281
time = 549 milli seconds

fibonacci(n - 1) と fibonacci(n - 2) が何度も繰り返し呼ばれるため、非再帰版と比べ多くの計算時間がかかります。

問題 11

int callCount = 0;
int[] cache = new int[100];

void setup() {
  noLoop();
}

void draw() {
  int start = millis();
  println("fibonacci(40) = " + fibonacci(40));
  int stop = millis();
  println("callCount = " + callCount);
  println("time = " + (stop - start) + " milli seconds");
}

int fibonacci(int n) {
  callCount += 1;
  if (n == 0) {
    return 0;
  }
  if (n == 1) {
    return 1;
  }
  if (cache[n] > 0) {
    return cache[n];
  }
  cache[n] = fibonacci(n - 1) + fibonacci(n - 2);
  return cache[n];
}

実行例

fibonacci(40) = 102334155
callCount = 79
time = 1 milli seconds

既に計算した fibonacci(n) の値を cache に格納することで計算時間を大幅に抑えられます。このテクニックをメモ化再帰と呼びます。

問題 12

void setup() {
  noLoop();
  size(800, 800);
}

void draw() {
  drawCircles(width / 2.0, height / 2.0, width / 2.0);
}

void drawCircles(float x, float y, float diameter) {
  if(diameter >= 10.0) {
    ellipse(x, y, diameter, diameter);
    drawCircles(x - diameter / 4.0, y, diameter / 2.0);
  }
}

問題 13

void setup() {
  noLoop();
  size(800, 800);
}

void draw() {
  drawCircles(width / 2.0, height / 2.0, width);
}

void drawCircles(float x, float y, float diameter) {
  if(diameter >= width / 8.0) {
    ellipse(x, y, diameter, diameter);
    drawCircles(x - diameter / 4.0, y, diameter / 2.0);
    drawCircles(x + diameter / 4.0, y, diameter / 2.0);
  }
}

問題 14

void setup() {
  size(800, 800);
  fill(0);
  stroke(255);
  background(255);
  noLoop();
}

void draw() {
  drawRects(0, 0, width, 50);
}

void drawRects(float x, float y, float size, float minSize) {
  if (size <= minSize) {
    return;
  }
  rect(x + size / 2, y, size / 2, size / 2);
  rect(x, y + size / 2, size / 2, size / 2);
  drawRects(x, y, size / 2, minSize);
  drawRects(x + size / 2, y + size / 2, size / 2, minSize);
}

問題 15

省略

演習の解答例

演習