コンテンツへスキップ
Topos Uranos
日本語

複合データ：導入

要約

このレッスンは、コースの第 6 単元、複合データを扱う単元の始まりである。単元が何のためにあるかを説明する。データのコレクション（固定サイズと可変サイズの並び、表、レコード）を表し、それを基本的なアルゴリズムで処理すること、そのアルゴリズムを手で書くこともライブラリから借りることもでき、そのコストを見積もることを教えるのである。単元の六つのレッスンと、それらを結ぶ糸を紹介する。単元が前提とすること、とりわけ不変条件をもつループと const 参照渡しを振り返る。単元が解決する問題を述べる。個数のわからないデータを保存しなければならないのに、ばらばらの変数で書くと、余ったデータを黙って見過ごしてしまうプログラムの問題である。アルゴリズムを測る第二の尺度として、正しさと並ぶコストを前もって紹介する。そして、この先の単元と「C++ プログラミング II」のコースで、単元がどこへつながるかを示す。

学習目標

  1. 単元の内容の順序を説明し、各レッスンが次のレッスンに何をもたらすかを説明する。
  2. ループ、その不変条件、引数の渡し方（値渡し、参照渡し、const 参照渡し）を思い出し、必要なら復習する。
  3. 例を通して、アルゴリズムのコストを、正しさと並ぶその質の第二の尺度として前もってつかむ。
  4. 単元を終えたときに何ができるようになっているべきかを知り、それをこの先の単元で学ぶことと区別する。

導入テスト

単元に取りかかる前に、出発点を測っておくとよい。このテストは自己チェックのためのもので、採点はしない。目的はただ学習の方向づけにある。最初の四問は、単元が前提とすることを確かめる。最大値を探すループの不変条件、大きな引数の渡し方、二重の入れ子のループの周回数、そして符号なしの算術である。続く六問は、レッスンの順に、単元の中心となる考え方を扱う。並びの有効な添字、ベクターの作り方、あるサイズを何回半分にできるか、ソート済みのデータでの探索、表の二重の添字、そして同じ実体のデータを別々のコレクションに保存する危険である。まだ正解できなくてもかまわないし、そのうちのいくつかでは「まだわからない」が誠実な答えである。正解であれ不正解であれ、どの答えもその要点を説明し、それを扱うレッスンを示すからである。同じ技能は、単元の最後のまとめのレッスンで再び測る。

導入テスト

単元を始める前に、自分の出発点を測りましょう。短い自己評価です。採点はされず、結果はあなたのブラウザーにだけ保存されます。

  1. 問 1前の単元からコード片 int largest{0}; int t{}; while (std::cin >> t) { if (t > largest) { largest = t; } } は、largest に、読み込んだ気温のうち最大のものを残すはずである。どんな入力で失敗するか。

  2. 問 2前の単元からある関数が、std::string に保存された百万文字のテキストに母音がいくつあるかを数え、テキストは変更しない。その仮引数はどう宣言するのがよいか。

  3. 問 3前の単元から++count は for (int i{0}; i < 6; ++i) { for (int j{0}; j < i; ++j) { ++count; } } の中で何回実行されるか。

  4. 問 4前の単元からstd::println("{}", 0u - 1); は、unsigned int が 32 ビットのシステムで何を出力するか。

  5. 問 5C++ と同じように番号をつけた nn 個の要素の並びで、要素を指す添字 ii はどれか。

  6. 問 6v は、std::vector<int> v(3, 7); のあと何を含むか。

  7. 問 7for (int m{1024}; m > 1; m /= 2) { ... } は何周回するか。

  8. 問 8ある電話帳には百万の名前が五十音順に並んでいる。一つを見つけるには、電話帳を真ん中で開き、名前がありえない半分を捨て、残りの半分で同じことを繰り返す。最大で何回開く必要があるか。

  9. 問 9std::vector<std::vector<int>> t{{1, 2, 3}, {4, 5, 6}}; のとき、t[1][0] と t.size() の値はいくつか。

  10. 問 10あるプログラムが、グループの名前を一つのベクターに、成績を別のベクターに保存し、成績 grades[i] が names[i] の成績になるようにしている。成績のベクターだけをソートすると、何が起こるか。