剰余演算とは
じょうよえんざん
割り算の余りを求める演算で、擬似言語では mod、多くの言語では % と書く。x mod 10 で一の位、x mod 2 で偶数か奇数か、i mod n + 1 で1〜n を循環する番号が得られる。負の数の余りの符号は言語によって異なる。
「剰余演算」は、3分野の8問の練習問題に出てきます(プログラミングの基礎(擬似言語のトレース), データ構造とアルゴリズム, メモリ階層と性能など)。
この用語の分野: プログラミングの基礎(擬似言語のトレース)
剰余演算の練習問題に挑戦
大きさ7のハッシュテーブル(位置0〜6)に、ハッシュ関数 h(k) = k mod 7 でキー10、17、24、3をこの順に格納する。衝突したときは、位置を1つずつ後ろへずらして(6の次は0)空いている位置を探す線形探査法を使う。キー3が格納される位置はどれか。
- A位置3
- B位置4
- C位置6
答えと解説を見る
正解：C. 位置6
4つのキーはどれも7で割った余りが3なので、すべて位置3を最初に調べます。10は位置3に入り、17は位置3が埋まっているので位置4、24は位置3、4が埋まっているので位置5に入ります。3は位置3、4、5が埋まっているので、位置6に格納されます。このように線形探査法では、埋まった位置が固まって並び(クラスタ)、後から来るキーほど調べる回数が増えます。
関数 f(x, y) を「y が0なら x を返し、そうでなければ f(y, x mod y) を返す」と定義する。f(84, 36) を呼んだときの戻り値と、f が呼ばれる回数(最初の呼び出しを含む)の組はどれか。
- A戻り値12、呼ばれる回数3回
- B戻り値12、呼ばれる回数4回
- C戻り値6、呼ばれる回数3回
解説の中の「剰余演算」
f(84, 36) は 84 mod 36 = 12 なので f(36, 12) を呼び、36 mod 12 = 0 なので f(12, 0) を呼び、y が0なので12を返します。
関数 f(x, y) を「y が0なら x を返し、そうでなければ f(y, x mod y) を返す」と定義する。f…mod は + より先に計算するので、tail ← tail mod 4 + 1 は tail を 1 → 2 → 3 → 4 → 1 と循環させます。
要素数4の文字列型の配列 q を環状に使うキューがある。head と tail の初期値は1で、enq(v) は q[…セット番号はライン番号をセット数で割った余りで、72 mod 64 = 8 になります。
ラインサイズ64バイト、セット数64のキャッシュで、アドレス0x1234のデータが入るセットの番号はどれか。x mod 10 は x の一の位を取り出し、x ← x ÷ 10 は小数点以下を切り捨てる整数除算になるので、一の位を取り除きます。
÷ は除算で、整数型の変数(引数を含む)に代入するときは小数点以下を切り捨てる。次の関数 f を f(9087) とし…x mod 2 は2進数の一の位、x ← x ÷ 2 は2進数で1桁右へずらす操作です。
÷ は除算で、整数型の変数(引数を含む)に代入するときは小数点以下を切り捨てる。次の関数 toBin を toBin(…
「剰余演算」が出てくる問題(8問)
- 大きさ7のハッシュテーブル(位置0〜6)に、ハッシュ関数 h(k) = k mod 7 でキー10、17、24、3をこの順に格納する。衝突したときは、位置を1つずつ後ろへずらして(6の次は0)空いている位置を探す線形探査法を使う。キー3が格納される位置はどれか。
- 関数 f(x, y) を「y が0なら x を返し、そうでなければ f(y, x mod y) を返す」と定義する。f(84, 36) を呼んだときの戻り値と、f が呼ばれる回数(最初の呼び出しを含む)の組はどれか。
- 要素数4の文字列型の配列 q を環状に使うキューがある。head と tail の初期値は1で、enq(v) は q[tail] ← v の後に tail ← tail mod 4 + 1 を行い、deq() は q[head] の値を返した後に head ← head mod 4 + 1 を行う。次のプログラムを実行したとき、「E」が格納される q の要素はどれか。
- ラインサイズ64バイト、セット数64のキャッシュで、アドレス0x1234のデータが入るセットの番号はどれか。
- ÷ は除算で、整数型の変数(引数を含む)に代入するときは小数点以下を切り捨てる。次の関数 f を f(9087) として呼び出したときの戻り値はどれか。
- ÷ は除算で、整数型の変数(引数を含む)に代入するときは小数点以下を切り捨てる。次の関数 toBin を toBin(12) として呼び出したときの戻り値はどれか。
- 2つの整数 a、b を引き算で等しくしていく次のプログラムを実行した後の k の値はどれか。
- 次の関数 isLeap は、西暦 y 年がうるう年なら true を返す。and は or より先に計算する。isLeap(y) が true を返す y はどれか。
プログラミングの基礎(擬似言語のトレース)の参考書を探す PR
Amazonの検索結果へのリンクです。Amazonのアソシエイトとして、半導体教室は適格販売により収入を得ています。