要約
このレッスンは、制御フローにあてられた、コースの第四単元の始まりである。まず単元の目的を説明する。すなわち、プログラムの文が実行される順序を分岐とループによって制御すること、そしてその正しさについて推論すること、つまりどの場合も処理され、どのループもなすべきことをし、しかも停止することを確かめる方法を教えることである。さらに、単元の四つのレッスンとそれらを貫く筋道を示し、単元が前提とすること、とりわけ第三単元の複合条件を思い出させる。そして単元が解決する問題、つまり決まった段数で最大公約数を計算し、データによっては誤った答えを返すか、0 による除算で止まってしまうプログラムの問題を提示する。不変条件を、単元がそのループを正当化するための道具として前もって紹介し、最後に、この先の単元と「C++ プログラミング II」コースへどうつながるかを示す。
学習目標
- 単元の内容の流れを説明し、各レッスンがそのすぐ後に続くレッスンに何をもたらすかを説明する。
- 第三単元の複合条件(論理結合子、短絡評価、ド・モルガンの法則による否定)を思い出し、必要なら復習する。
- 推論の道具としての不変条件を、例を通して前もって知る。不変条件とは、反復が保ち、終わったときに結果を与える、変数どうしの関係である。
- 単元を終えたときにできるようになっているべきことを見きわめ、それをこの先の単元で学ぶことと区別する。
導入テスト
単元に取りかかる前に、出発点を測っておくとよい。このテストは自己チェックのためのもので、採点はしない。目的はただ学習の方向づけにある。最初の四問は、単元が前提とすることを確かめる。複合条件の否定、短絡評価、レッスン 1.1 の反復のトレース、そして int の限界である。続く七問は、レッスンの順に、単元の中心となる考え方を扱い、そのいくつかは学校の数学から出発する。最大公約数、総和記号、手続きの停止性である。まだ正解できなくてもかまわないし、そのうちのいくつかでは「まだわからない」が誠実な答えである。正解であれ不正解であれ、どの答えもその要点を説明し、それを扱うレッスンを示すからである。同じ技能は、単元の最後のまとめのレッスンで再び測る。
単元を始める前に、自分の出発点を測りましょう。短い自己評価です。採点はされず、結果はあなたのブラウザーにだけ保存されます。
問 1前の単元から条件
1 <= n && n <= 10の否定はどれか。各部分を否定しているが、連言を残している。ド・モルガンの法則を忘れている。そのうえ、1 より小さくかつ 10 より大きい数は存在しないので、この条件は常に偽である。結合子は正しく変えているが、関係の否定を誤っている。もとの条件を満たす境界 1 と 10 まで余計に除いている。最初の部分しか否定していない。ド・モルガンの法則により、連言の否定は否定どうしの選言であり、1 <= nの否定はn < 1であって、n <= 1ではない。単元はこれを連鎖した分岐のたびに必要とする。elseの枝は、それより前の条件の否定をちょうど処理するからである。またループのたびにも必要とする。抜けたときに成り立つのは、その条件の否定だからである。復習: 関係と論理
問 2前の単元から
int d{0};とint n{5};のもとで、d != 0 && n / d > 2を計算すると何が起こるか。短絡評価を無視している。除算はそもそも計算されない。偽のオペランドを含む連言が真になることはありえない。式は正しい。コンパイラは実行時のdの値を知らない。第一オペランドが偽なので、短絡評価により第二オペランドは計算されない。左側の見張りが除算を守っている。単元はこの見張りを、明示的な分岐と、本体を守るループ条件とに変える。復習: 関係と論理
問 3前の単元からレッスン 1.1 の引き算の繰り返しによる割り算は 、 から始め、「 である間、 を から引き、 に 1 を足す」を繰り返す。、 のとき、反復の本体は何回実行されるか。
条件の計算回数を数えている。これは周回数より一つ多い。で反復を止めている。 を と読んでいる。周回数を の初期値と取り違えている。トレースすると となる。本体は四回実行され、条件は五回計算される。最後の計算が偽になる計算だからである。レッスン 4.2 はこの反復を C++ で書き、トレースを表にする。復習: 問題からアルゴリズムへ
問 4前の単元から32 ビットの
intで、46341 * 46341の値について規格は何を保証するか。型の範囲を無視している。この数はintに収まらない。オーバーフローは境界で止まると思っている。規格は何も約束しない。結果の型を決めるのは結果の値ではなく、intであるオペランドである。最大値は である。単元はこの積に、探そうとも思わない場所で出会う。約数を試すループの条件d * d <= nであり、これは が最大値に近いときにちょうどオーバーフローする。復習: 整数とその表現
問 5あるプログラムは次の分岐の連鎖を含む。「合格」と出力する
if (score >= 50)、「優」と出力するelse if (score >= 90)、そして「不合格」と出力するelseである。scoreが 95 のとき、何を出力するか。最も厳しい条件が勝つと思っている。勝つのは最初に成り立つ条件である。真の枝はすべて実行されると思っている。連鎖では一つしか実行されない。誠実な答えである。レッスン 4.1 で説明し、まとめテストで連鎖の境界をもう一度扱う。連鎖では条件が真である最初の枝が実行され、そして である。「優」の枝は決して実行されない。その実際の場合は かつ であり、空である。レッスン 4.1 は各枝の実際の場合を読み取り、条件を並べる方法を教える。復習: 分岐
問 6次の式のうち、和 を表すのはどれか。
回、数 を足しており、つまり になる。項と上限を取り違えている。を足している。範囲をずらして最後の項を失っており、ループの 1 ずれのエラーである。上限が添字そのものであることはできない。この式には意味がない。添字 は 1 から までの整数を動き、各項は そのものである。和を累積するforループは、この記法の直訳である。ループ変数が添字であり、その範囲が総和の範囲であり、本体が項を足す。復習: ループ
問 7
int total{0};のもとで、for (int i{0}; i < 5; ++i) { total += i; }の後、std::println("{}", total);は何を出力するか。iが 5 に達すると思っている。<を<=と読んでいる。累積変数とカウンタを取り違えている。5 は周回数であって、和ではない。誠実な答えである。レッスン 4.2 でforの形とその周回数の数え方を学ぶ。変数iは 0、1、2、3、4 の値をとり、 である。iが 5 になると条件が偽になり、本体は実行されない。これは前の問いの総和で、範囲を 0 から 4 としたものである。復習: ループ
問 8引き算の繰り返しによる割り算(、 とし、 である間、 を に、 を にする)で、条件が計算されるたびに成り立つ変数どうしの関係はどれか。
抜けたときにしか成り立たない。反復している間、条件はその逆を保証している。終わったときにしか成り立たない。それまでは は商より小さい。誠実な答えである。レッスン 4.3 でこの関係の見つけ方と確かめ方を学び、まとめテストでもう一度問われる。最初に成り立つ。 だからである。そして、ある周回の前に成り立てば、その後にも成り立つ。 だからである。抜けるときには条件の否定 が加わり、両者をあわせると結果が得られる。このような関係を不変条件といい、レッスン 4.3 はそれをループを設計し正当化するための方法にする。復習: 正しいループの設計
問 9ある手続きは任意の整数 (正、0、負のいずれでもよい)から出発し、「 である間、 から 2 を引く」を繰り返す。すべての について停止するか。
それは条件 の場合に起こることである。 なら、 が 0 か になった時点で反復は止まる。が負なら条件は最初から偽であり、本体は実行されない。結論は正しいが、理由は正しくない。整数であるだけでは足りない。量が反復している間は自然数であり、しかも減少することが必要である。量 は反復している間は自然数であり(条件がそれを保証する)、狭義に減少する。これは変量であり、レッスン 1.1 の道具で、レッスン 4.3 はこれをすべてのループで用いる。「 である間」とすると答えは変わる。奇数の は 0 を飛び越える。復習: 正しいループの設計
問 1084 と 36 の最大公約数はいくつか。
公約数ではあるが、最大ではない。公約数ではあるが、最大ではない。両者が同じく共有する因数 3 が欠けている。最小公倍数であって、最大公約数ではない。公約数は 1、2、3、4、6、12 である。ユークリッドの互除法は約数を探さずにそれを求める。、 であるから、 となる。レッスン 4.4 はこれをループとして書き、なぜうまくいくかを証明する。復習: 数値アルゴリズム
問 11約数を試して 101 が素数かどうかを判定するには、どの約数まで試せば十分か。
半分を使っている。正しいが、必要な長さの五倍になる。候補をすべて試している。正しいが、約数が対になって現れることを活かしていない。誠実な答えである。レッスン 4.4 で証明する。101 に約数 があって ならば、 も約数であり、二つのうち一方は高々 である。2 から 10 までを試せば十分であり、どれも 101 を割り切らないので、101 は素数である。レッスン 4.4 はこの規則を証明し、根号も、オーバーフローする積も使わずに書く。復習: 数値アルゴリズム
コンテンツを読み込んでいます…