Accelerated C++ Chapter 03

Programming C++

どもどす。
ネスペの午後1は通ってるだろとかぶっこいたのが，先日。
ほいで，あぁ，あれって午後1で落ちているというフラグが立った
ということだったのか，と気づいたのが本日。
ま，どっちみち，午後2で落ちているのでいいんですけど。


さて，やってまいりました，Chapter3です。

メモ

  • streamsize は，iomanip で宣言されている。
  • median のサンプルは，vector のサイズが1の時に out of bounds する。
    • median[mid - 1] => median[-1] にアクセスするので。


そろそろ Exercise 1問の解答が長くなってくるので，分けていきます。
解答については基本的に投げっぱなしジャーマンですお。
リファクタリングの練習とか言っていたのは誰だっ!?
いや，だって，このへんの章では，まだ使える武器がそろってないし・・・という言い訳。

Exercise 3-2

en.wikipedia によると，quartile の定義は色々あるようだけど，
この解答では，大体 meidan というざっくりとした感じで。
というか，これ書いていて気づいたけど，すごい面倒なことをしている気がしてきた。
もっとさっぱりした方法がありそうだ。

#include <iostream>
#include <vector>
#include <algorithm>
#include <iomanip>
#include <cstdlib>
#include <ctime>
#include <cassert>

using namespace std;

void print_vec(const vector<int>& v)
{
  for (vector<int>::size_type i = 0; i < v.size(); ++i) {
    cout << v[i] << ", ";
  }
  cout << endl;
  return;
}

// return a median of elements in [start, end)
double median(vector<int> vec, size_t start, size_t end)
{
  assert(start < end);

  // we don't assume the vector is sorted beforehand.
  sort(vec.begin(), vec.end());

  // target: [start, end)
  size_t size = end - start;
  size_t mid = size / 2;

  if (size == 1) {
    return vec[start];
  }

  if (size % 2 == 0) {
    return (vec[start + mid - 1] + vec[start + mid]) / 2;
  }
  else {
    return vec[start + mid];
  }
}

void quartiles(vector<int> vec)
{
  double first_quartile = -1, second_quartile = -1, third_quartile = -1;

  sort(vec.begin(), vec.end());
  second_quartile = median(vec, 0, vec.size());
  size_t mid =  vec.size() / 2;
  if (vec.size() % 2 == 0) {
    // vec[0], ..., vec[mid-2], vec[mid-1], vec[mid], vec[mid+1], ..., vec[vec.size()-1]
    // ^^^^^^^^^^^^^^^^^^^^^^^                        ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    //    the first half                                   the second half
    first_quartile = median(vec, 0, mid - 1);
    third_quartile = median(vec, mid + 1, vec.size());
  }
  else {
    // vec[0], ..., vec[mid-2], vec[mid-1], vec[mid], vec[mid+1], ..., vec[vec.size()-1]
    // ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^            ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    //          the first half                                 the second half
    first_quartile = median(vec, 0, mid);
    third_quartile = median(vec, mid + 1, vec.size());
  }
  cout << first_quartile << ", " << second_quartile << ", " << third_quartile << endl;
}

int main()
{
  vector<int> ivec;
  const int num_elem = 10;

  srand(time(NULL));
  for (int i = 0; i < num_elem; ++i) {
    ivec.push_back(rand() % 100);
  }

  sort(ivec.begin(), ivec.end());
  cout << "Sorted vector:" << endl;
  print_vec(ivec);

  cout << "Quartiles are:" << endl;
  quartiles(ivec);
  cout << endl;

  return 0;
}

Exercise 3-3

ここで，まだご登場してらっしゃらないmapを使うのはチートか。

#include <iostream>
#include <map>

using namespace std;

int main()
{
  map<string, int> word_occurrences;

  string w;
  while (cin >> w) {
    ++word_occurrences[w];
  }
  map<string, int>::iterator iter;
  for (iter = word_occurrences.begin(); iter != word_occurrences.end(); ++iter) {
    cout << "Word: " << iter->first << ", Count: " << iter->second << endl;
  }

  return 0;
}

Exercise 3-4

#include <iostream>
#include <map>

using namespace std;

int main()
{
  string s, longest, shortest;
  string tmp;
  string::size_type max = 0, min = tmp.max_size(), l = 0;

  while (cin >> s) {
    l = s.length();
    if (l > max) {
      max = l;
      longest = s;
    }
    else if (l < min) {
      min = l;
      shortest = s;
    }
  }

  cout << "Longest: " << longest << endl;
  cout << "Shortest: " << shortest << endl;

  return 0;
}

Exercise 3-5

うーん，C 臭いコードだね。
おぉ，律儀に関数に static をつけていたのか。えらいね，オレ。

#include <iostream>
#include <vector>
#include <iomanip>
#include <algorithm>

using namespace std;

static void read_name(string& name)
{
  cout << "Please enter your first name: ";
  cin >> name;
  cout << "Hello, " << name << "!" << endl;
}

static void read_mid_and_final(double& midterm, double& final)
{
  cout << "Please enter your midterm and final exam grades "
          "separated by whitespace: ";
  cin >> midterm >> final;
}

static void read_homeworks(vector<double>& hw)
{
  cout << "Enter all your homework grades separated by whitespace, "
          "followed by end-of-file: ";
  double x;
  while (cin >> x) {
    hw.push_back(x);
  }
  cin.clear();
}

static int calc_median(vector<double>& homework, double& median)
{
  vector<double>::size_type size = homework.size();

  if (size == 0) {
    return -1;
  }
  else if (size == 1) {
    median = homework[0];
  }
  else {
    sort(homework.begin(), homework.end());
    vector<double>::size_type mid = size / 2;
    median = (size % 2 == 0) ? (homework[mid] + homework[mid-1]) / 2 : homework[mid];
  }

  return 0;
}

static double calc_final_grade(double midterm, double final, double median)
{
  return 0.2 * midterm + 0.4 * final + 0.4 * median;
}

static void print_final_grade(const vector<string>& names, const vector<double>& final_grades)
{
  streamsize prec = cout.precision();
  for (uint i = 0; i < names.size(); ++i) {
    cout << endl << names[i] << ", Your final grade is "
         << setprecision(3)
         << final_grades[i]
         << setprecision(prec) << endl;
  }
}

int main()
{
  vector<string> names;
  vector<double> final_grades;

  while (true) {
    string name;
    read_name(name);

    double midterm = 0, final= 0;
    read_mid_and_final(midterm, final);

    vector<double> homework;
    read_homeworks(homework);

    double median = 0;
    int ret = calc_median(homework, median);
    if (ret < 0) {
      return 1;
    }
    double final_grade = 0;
    final_grade = calc_final_grade(midterm, final, median);

    // Store a studnet's name
    names.push_back(name);
    // Store the corresponding grade
    final_grades.push_back(final_grade);

    string cont;
    cout << "Another student? (y/n): ";
    cin >> cont;
    if (cont.compare("n") == 0) {
      break;
    }
  }

  print_final_grade(names, final_grades);

  return 0;
}

まとめ

vectorとかsortとかでてきて楽しくなる予感がする章でした。
けど，クラスがはまだだいぶ先だ。
それにこの頃はまだ，テストを書いていなかったようだ。