「基礎プログラミングおよび演習」のための問題集

概要

本記事は電気通信大学1年次後学期で開講されている「基礎プログラミングおよび演習」のために用意した問題集である．ここに用意されている問題がおおかた解ければ，単位を取ることもそう難しくないことだろう．以下に2019年度の講義資料が公開されている．joho.g-edu.uec.ac.jp

注意事項

本記事の問題は外部サイトなどを参照しながら解くことも考慮に入れて，例年の試験より難しめに作成した問題も含まれている．
2019年度の「基礎プログラミングおよび演習」期末試験では，試験中のコードの実行，外部サイトの参照は禁じられている．本記事では「実行せよ」「メソッドを作成せよ」などの指示があるが，実際の試験にはこれらの形式の問題は出題されないことに注意せよ．
本記事によって読者の被った落単などの損害については，一切の責任を負いかねる．

問題

Ruby

問題1

関数 $f(a, b)$ を次のように定義する．
$\displaystyle f(a, b) = \frac{1335}{4}b^6 + a^2(11a^2b^2-b^6-121b^4-2)+\frac{11}{2}b^8+\frac{a}{2b}.$

また， $f(a, b)$ の値を計算するメソッド f(a, b) を以下のように定義する． (実行時にはこのコードをコピペして実行せよ．)

def f(a,b)
  Rational(1335,4)*b*b*b*b*b*b+a*a*(11*a*a*b*b-b*b*b*b*b*b-121*b*b*b*b-2) + Rational(11,2)*b*b*b*b*b*b*b*b + a/(2*b)
end

このメソッドに以下の3種類の引数の組を与えて実行し，返値f(a, b)を比較せよ．また，これらの返値のうち， $f(77617, 33096)$ の真の値に最も近いのはどれか．

a = 77617, b = 33096 (ともに整数)
a = 77617.0, b = 33096.0 (ともに浮動小数点数)
a = Rational(77617), b = Rational(33096) (ともに有理数，RubyのRationalクラスを利用)

問題2

$y, m, d$ をそれぞれグレゴリオ暦におけるある日の年，月，日を表す整数とする．例えば， $y = 2020, m = 1, d = 21$ は2020年1月21日に相当する． $y, m, d$ の値を与えるとその日の曜日を文字列 ("Sun", "Mon", "Tue", "Wed", "Thu", "Fri", "Sat"のいずれか) として返すメソッドday_of_the_week(y, m, d)を作成せよ．

$y, m, d$ から曜日を求める公式としてツェラーの公式を用いてもよい．
ja.wikipedia.org

問題3

以下の問いに答えよ．問題2で作成したday_of_the_week(y, m, d)を用いてプログラムを作成してもよい．

1970年1月1日から1970年1月31日までのうち，それぞれの曜日に属する日は何日ずつあるか．
20世紀には合わせて100日間の「1月1日」があるが，このうち日曜日は何日あるか．
20世紀のすべての「2月」に属する日のうち，日曜日は何日あるか．

問題4

実数 $x$ に対し，周期関数 $f(x)$ を次のように定義する．
$\displaystyle f(x)= \begin{cases}f(x + 2)&(x < -1) \\|x|&(-1 \leq x < 1) \\ f(x - 2)&(1 \leq x) \end{cases}$

浮動小数点数xに対し $f(x)$ の値を計算するメソッドf(x)を以下の3種類の方針によってそれぞれ作成せよ．

ループを用いて．
再帰を用いて．
ループ，再帰のいずれも用いずに．

問題5

ユークリッドの互除法によって，2つの整数 $x, y$ の最小公倍数を返すメソッドlcm(x, y)を以下の2種類の方針によってそれぞれ作成せよ．

ループを用いて．
再帰を用いて．

問題6

$A$ を $n$ 個の整数要素からなる配列とする．ユークリッドの互除法によって， $n$ 個の整数 $A[0], A[1], \dots, A[n - 1]$ の最小公倍数を返すメソッドを以下の2種類の方針によってそれぞれ作成せよ．

メソッドの引数として配列 $A$ , 要素数 $n$ を与える．array_lcm([4, 5, 6], 3) のように呼び出す．
メソッドの引数として配列 $A$ のみを与え，要素数はメソッド内で自動的に取得する．array_lcm([4, 5, 6]) のように呼び出す．

問題7

$A$ を $n$ 個の浮動小数点数要素からなる配列とし，その (0-indexedにおける) $i$ 番目の要素を $A[i]$ と表す．実数 $x$ を引数とする次のような関数 $f(x)$ を考える．
$f(x) = \displaystyle \sum_{k = 0}^{n - 1} A[k]x^k.$
$f(x)$ の導関数 $\displaystyle \frac{d}{dx}f(x)$ に対し，配列 $B$ を $n$ 個の浮動小数点数要素からなる，次の等式を満たす配列とする．
$\displaystyle \frac{d}{dx}f(x) = \sum_{k = 0}^{n - 1} B[k]x^k.$

配列 $A$ に対応する配列 $B$ の値を計算するメソッドdf(A)を以下の2種類の方針によってそれぞれ作成せよ．

df(A)はメソッド内で配列 $A$ とは別に新たに配列 $B$ を作成し，それを返す．配列 $A$ に対して破壊的変更を行わない．
df(A)はメソッド内で配列 $A$ に破壊的変更を加え，配列 $B$ の内容に置き換える．配列 $B$ を格納するための新たな領域を確保しない．

問題8

$n$ を奇数とする． $A$ を $n$ 個の整数要素からなる配列とする．以下の2種類の設定の下， $A$ の中央値を返すメソッドmedian(A)をそれぞれ作成せよ．

配列 $A$ は昇順に整列済みである．
配列 $A$ は整列済みとは限らない．

ただし，メソッド内での以下の操作は禁じる．

メソッド内で配列 $A$ に対し破壊的変更を加えること．
$A$ の要素数 $n$ に対し $\Omega(\log n)$ の領域を新たに確保すること．

問題9

$A$ を $n$ 個の整数要素からなる配列とする．また， $A$ は昇順に整列済みであるとする． $A$ の要素を並べ替えてできる長さ $n$ の順列をすべて出力するメソッドperm(A)をそれぞれ作成せよ．ただし，perm(A)は同じ順列を複数回出力してはならない．

また， $A$ の要素を並べ替えてできる互いに相異なる順列の数を返すメソッドn_perm(A)を作成せよ．計算には多項定理を用いてもよい．
ja.wikipedia.org

問題10

$n \times n$ 行列 $M$ が2次元配列 $A$ として与えられる．すなわち，行列 $M$ の $(i, j)$ 成分が $A[i - 1][j - 1]$ に等しい $(1 \leq i \leq n, 1 \leq j \leq n)$ ． $A$ と要素数 $n$ を与えると， $M$ の性質によって次のような値を返すメソッドtri(A, n)を作成せよ．

$M$ が対角行列であるときtri(A, n) = 3.
$M$ が対角行列でなく，上三角行列であるときtri(A, n) = 2.
$M$ が対角行列でなく，下三角行列であるときtri(A, n) = 1.
$M$ が上三角行列でも下三角行列でもないときtri(A, n) = 0.

問題11

$(x, y)$ 直交座標平面上の点を表すレコード型を作成せよ．また，作成した型の4個のレコードを引数にとり，4点 $\mathrm{A}, \mathrm{B}, \mathrm{C}, \mathrm{P}$ について，点 $\mathrm{P}$ が三角形 $\mathrm{ABC}$ の内部にあればtrue，さもなければfalseを返すメソッドinside(A, B, C, P)を作成せよ．ただし，4点 $\mathrm{A}, \mathrm{B}, \mathrm{C}, \mathrm{P}$ のうちどの3点も一直線上にないとする．

問題12

問題11の $(x, y)$ 直交座標平面上の点を表すレコード型をクラスとして再度定義せよ (レコードにおけるフィールドではなく，クラスにおけるインスタンス変数とinitializeメソッドを利用して各点の座標を保持できるようにせよ) ．

また，このクラスのスーパークラスObjectから継承されたメソッドto_s()をオーバーライドして，このクラスのインスタンスを引数としてprintメソッドなどを呼び出したときの表示形式を自由に変更せよ．

問題13

単連結リストのセルを表すレコード型 (すなわち，セルの値と次のセルへの参照をフィールドとして保持するレコード型) を定義せよ．

問題14

問題13で定義したセルへの参照を引数として，そのセルを単連結リストの先頭とみなし，その単連結リストのすべての要素の平均値を返すメソッドを作成せよ．

問題15

問題13で定義したセルへの参照を引数として，そのセルを単連結リストの先頭とみなし，その単連結リストの「 (0-indexedにおける) 偶数番目の要素の和」と「 (0-indexedにおける) 奇数番目の要素の和」の差を返すメソッドを，次の2種類の方針によって作成せよ．

再帰を用いずに．
再帰を用いて．

問題16

問題13で定義した型のレコードへの参照をメンバ変数としたクラスを定義し，このクラスにリストの末尾に要素を追加するインスタンスメソッドを定義せよ．問題14，問題15のメソッドもこのクラスのインスタンスメソッドとすることで，単連結リストの構造を外部から隠蔽せよ．

さらに，このクラスのスーパークラスObjectから継承されたメソッドto_s()をオーバーライドして，このクラスのインスタンスを引数としてprintメソッドなどを呼び出したときの表示形式を自由に変更せよ．

問題17

松屋フーズ (https://www.matsuyafoods.co.jp/) の丸いロゴマークをおおまかに再現した画像を生成せよ．講義資料に掲載されているソースコードを流用してもよい．

C言語

問題1

整数 $n$ に対し， $0 \leq n \leq 30$ とする． $n$ の値を引数として与えると $2^n$ の値を返す関数int pow2(int n)を次の3種類の方針によってそれぞれ作成せよ．

$2$ を $n$ 回掛ける方法によって．
$n$ を二進展開して $n = (a_4 a_3 a_2 a_1 a_0)_{(2)}$ とし， $2^n = 2^{2^4\times a_4} \times 2^{2^3\times a_3} \times 2^{2^2\times a_2} \times 2^{2^1\times a_1} \times 2^{2^0\times a_0}$ を計算する方法によって．
ビット演算 (左シフト) を用いる方法によって．

問題2

問題1で作成した関数int pow2(int n)に対し，引数の型および返値の型の変更を含む実装の改変をして， $0 \leq n \leq 63$ に対し正しい $2^n$ の値が返るようにせよ．

問題3

実数 $x$ に対し， $-1 \leq x \leq 1$ とする． $x$ の値を浮動小数点数として与えると $\arccos x\ (-\pi < \arccos x < \pi)$ の値を返す関数double pow2(double x)を次の3種類の方針によってそれぞれ作成せよ．

数え上げによって．
区間二分法によって．
ニュートン法によって．

問題4

モンテカルロ法によって，次に示す $I$ の値を数値的に求めよ．
$\displaystyle I = \frac{1}{\sqrt{2\pi}} \int_{-1.96}^{1.96} e^{-\frac{x^2}{2}} dx.$

問題5

2つの配列 $A, B$ はそれぞれ長さ $n$ の文字列 (char型の配列) とする． $A, B, n$ を与えると $A, B$ の内容を入れ替える関数swap_array(char A, char B, int n)を作成せよ．

問題6

2つの配列 $A, B$ はそれぞれ文字列とする． $A, B$ を与えると $A$ を逆転した文字列と $B$ を逆転した文字列のどちらが辞書順で小さいかを判定する関数rev_strcmp(char A, char B)を作成せよ．返値の仕様を次のように定める．

$A$ を逆転した文字列のほうが辞書順で小さいとき rev_strcmp(A, B) = -1.
$B$ を逆転した文字列のほうが辞書順で小さいとき rev_strcmp(A, B) = 1.
$A$ を逆転した文字列と $B$ を逆転した文字列が等しいときrev_strcmp(A, B) = 0.

ただし，関数内での以下の操作は禁じる．

メソッド内で配列 $A, B$ に対し破壊的変更を加えること．
文字列 $A, B$ の長さ $n_A, n_B$ に対し $\Omega(\log (\min(n_A, n_B)))$ の領域を新たに確保すること．

問題7

RGB値 (それぞれの値 $R, G, B$ は整数で， $0 \leq R, G, B \leq 255$ ) をフィールドとして持つことで色を扱う構造体struct colorを定義せよ．

問題8

問題7で作成した構造体を要素とする2次元配列は画像とみなすことができる．struct color型の2次元配列 $A$ と，それを画像としてみなしたときの幅 $w$ ，高さ $h$ を引数として，PPM形式の画像を出力する関数output_image(int w, int h, struct color a[h][w])を作成せよ．出力先は標準出力などでもよい．

問題9

問題7で作成した構造体を要素とする2次元配列は画像とみなすことができる． $A$ をstruct color型の2次元配列とし，それを画像としてみなしたときの幅を $w$ ，高さを $h$ とする．この画像に対し，左上の座標 $(x_1, y_1)$ と右下の座標 $(x_2, y_2)$ で決まる矩形領域の塗りつぶしを考える．塗る色をstruct color cとする．この塗りつぶしを行う関数paint_rect(int w, int h, struct color a[h][w], int x1, int y1, int x2, int y2, struct color c)を作成せよ．この関数を呼び出した後に問題8のoutput_image(int w, int h, struct color a[h][w])を呼ぶことで，塗りつぶしが正しく行われていることを確認せよ．

nkhrlab~

140字超の記事