演習 08

問題 1

1111 以下の自然数のうち，11 の倍数を大きい順に半角スペース区切りで標準出力せよ。

問題 2

1000 以上，1111 未満の整数のうち，7 または 11 の倍数を小さい順に半角スペース区切りで標準出力せよ。

問題 3

配列 data の先頭 n 要素を選択ソートする関数 selectionSort(data, n) は以下のように再帰的に定義できる。

selectionSort(data, n)
  もし n が 0 より大きければ以下を実行する
    k を、dataの先頭からn個のうちの最大値の添字とする
    data[n - 1] と data[k] を入れ替え、selectionSort(data, n - 1) を実行する

この関数を再帰を用いて作成し、選択ソートを行う以下のプログラムを完成させよ。

void setup() {
  noLoop();
}

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

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

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

問題 4

選択ソートのプログラムを再帰を用いずに作成せよ。

問題 5

$\text{binarySearch}(a, l, h, t)$ は、$a[i] == t$ となる $i (l \leq i \leq h)$ が存在するとき $i$ を、そうでないとき $-1$ を返す関数である。 $\text{binarySearch}(a, l, h, t)$ は、次のように再帰的に定義できる。 ただし $m = (l + h) / 2$ とする。

$$\begin{align} \text{binarySearch}(a, l, h, t) = \begin{cases} -1 & (h < l) \\ m & (t = a[m]) \\ \text{binarySearch}(a, l, m - 1, t) & (t < a[m]) \\ \text{binarySearch}(a, m + 1, h, t) & (t > a[m]) \end{cases} \end{align}$$

この関数を再帰を用いて作成し、二分探索を行う以下のプログラムを完成させよ。 二分探索については 資料 も参照すること。

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 = binarySearch(data, 0, data.length - 1, target);
  if (index > -1) {
    println("Found: data[" + index + "] == " + target);
  } else {
    println("Not Found: " + target);
  }
}

問題 6

二分探索のプログラムを再帰を用いずに作成せよ。