コラム４正しいプログラムを書く【珠玉のプログラミング】

自分の回答を乗せる。

1

0除算：
起きない？

オーバーフロー：

n-1がuの型で表現可能かチェック
(l + u) / 2がmで表現可能かチェック
mがpで表現可能かチェック
m+1がlの型で表現可能かチェック

配列の範囲外参照：
l, uが0未満、または配列の大きさ以上になっていないかチェック

証明の形式化：
分からなかった

2

分からなかった

3

探索範囲は外から与えるようになる。
中央の値mの計算や条件分岐は変わらない。
question3.cpp参照。

4

nの大きさをn=1からある程度の大きさまでインクリメントしながら2分探索を行い、与えたnから計算されるlogn2の値と実際の比較回数をプロットする。

5

xが発散するためループは終了しないのでは？

6

黒豆が減るのは取り出した豆が２つとも黒豆のときで、黒豆は１度に１つずつしか減らない。そのため最後の1つになった黒豆が取り出されることはなく、黒豆が缶の中からなくなることはない。

白豆が増えることはなく、2つとも黒豆という条件の場合以外、白豆は減り続ける。
2つとも黒豆という条件が常に成り立つのは、缶の中に黒豆だけが2個以上残っている場合のみ。
この条件が常に成り立つことはないので、最終的に白豆はなくなる。

缶の中に黒豆しかない場合、黒豆が最後の1つになるまで、2つとも黒という条件が常に成り立つ。
したがって最終的に缶の中には黒豆が1つだけ残る。

7

分からなかった

8

配列を分割して並列処理する
CPUの性能を上げる
メモリアクセスを高速化する
専用回路を作る

9

9-1

/* a, b, cは長さnの配列 */
i = 0
while i < n
  /* a[i-1] == b[i-1] + c[i-1] */
  a[i] = b[i] + c[i]
  i = i + 1
  /* a[i-1] == b[i-1] + c[i-1] */
/* i == n && a[i-1] == b[i-1] + c[i-1] */

9-2

/* xは長さnの配列 */
max = x[0]
i = 1
while i < n do
  /* x[i-1] <= max */
  if x[i] > max
    /* x[i-1] <= max < x[i] */
    max = x[i]
  i = i + 1
  /* x[i-1] <= max */
/* i == n && x[i-1] <= max */

9-3

/* xは要素数nの配列 */
i = 0
while i < n && x[i] != t
  /* i <= n && x[i-1] != t */
  i = i+1
  if i >= n
    /* i <= n && x[i-1] != t */
    p = -1
  else
    /* i < n && x[i-1] != t */
    p = i
  /* i <= n && x[i-1] != t */
/* (i == n || (i < n && x[i] == t)) && x[i-1] !=t */

9-4

function exp(x, n)
  /*
   * 前提条件：n >= 0
   * 結果：result = x^n
   */
  
  if n = 0
    return 1
  else if nが偶数なら
    /* n%2 == 0 */
    return exp(x, n/2)の2乗
  else
    /* n%2 != 0 */
    return x*exp(x, n-1)

10

とばした

11

とばした

感想

なかなか契約プログラミングの考え方に馴染めず時間がかかった。まだうまく飲み込めていない気がする。数学の苦手な単元に取り組んでいるようなもどかしさがある。

ソースコード

// question3.cpp

#include <iostream>
#include <vector>
#include <numeric>

constexpr int ARRAY_SIZE = 100;

int binarySearch(const int t, const std::vector<int> v, int l, int u) {
  if(l < 0 || u >= v.size()) return -1;
  if(l > u) return -1;

  int m = (l + u) / 2;

  if(v[m] < t) l = m + 1;
  else if(v[m] == t) return m;
  else if(v[m] > t) u = m - 1;

  return binarySearch(t, v, l, u);
}

int main(int argc, char** argv) {
  if(argc != 2) return -1;

  int t = std::atoi(argv[1]);
  if(t >= ARRAY_SIZE) return -1;

  std::vector<int> v(ARRAY_SIZE);
  std::iota(v.begin(), v.end(), 0);

  std::cout << binarySearch(t, v, 0, v.size() - 1) << std::endl;

  return 0;
}