2017年度「プログラミング言語1」「プログラミング言語演習」のページ

練習問題

2017年6月2日変更

課題1は難しいので、余力のある人のみ提出に変更します。

かわりに、易しい課題を二つ追加しました。課題2と課題3です。

2017年5月26日出題
  1. (余力のある人のみ)

    任意の正整数は多くとも四つの平方数の和として表すことができる。この事実はラグランジュの四平方定理と呼ばれている。

    定理の証明は簡単ではないが、個々の正整数について定理が成り立っていることは計算だけで確認できる。たとえば、\(35=1^2+3^2+5^2=1^2+3^2+3^2+4^2\)なので、\(35\)について成り立っていることは確認できる。

    1. 正整数\(n\)を入力して、\(n\)を多くとも四つの平方数の和として何通りに表せるかを出力するプログラムを書け。

      表現を数えるにあたって、足す順番が違うだけのものは同一視する。 たとえば、35が入力されると、2を出力する。 \(35=1^2+3^2+5^2=1^2+3^2+3^2+4^2\) がすべての表現を尽くしているからである。\(1^2+3^2+5^2\) と \(3^2+5^2+1^2\) は同一の表現とみなすことに注意すること。

      入力する正整数\(n\)は、\(2^{20}\)より小さいと仮定して良い。

  2. \(a\) を正の実数とする。数列 \(\langle x_n\rangle\) を以下のように定義する。 \[ \begin{aligned} x_0 &= 1 \\ x_{n+1} &= a+\frac{1}{x_n} \end{aligned} \] この \(\langle x_n\rangle\) は収束する。

    1. 浮動小数点数 \(a\) と整数 \(N\) を入力し、数列 \(\langle x_n\rangle\) の最初の\(N\)項、すなわち、\(x_0\), \(x_1\), \(x_2\), …,\(x_{N-1}\) を出力するプログラムを書け。

      入力は \(a\) も \(N\) も正であると仮定して良い。出力は一行に一つの数値を小数点以下12桁の小数表示で行うこと。

    2. 浮動小数点数 \(a\) と整数 \(N\) を入力し、数列 \(\langle x_n\rangle\) の最初の\(N\)項それぞれと極限値の差、すなわち、\(x_0-\lim_{n\to\infty}x_n\),  \(x_1-\lim_{n\to\infty}x_n\),  \(x_2-\lim_{n\to\infty}x_n\),  …, \(x_{N-1}-\lim_{n\to\infty}x_n\) を出力するプログラムを書け。

      入力は \(a\) も \(N\) も正であると仮定して良い。出力は一行に一つの数値を小数点以下8桁の指数部つき表示で行うこと。

  3. \(a\) と \(b\) を正の実数とする。 \(a\) と \(b\) の算術平均(相加平均)を \(a_1\) とし、\(a\) と \(b\) の幾何平均(相乗平均)を \(b_1\) とする。 \(a_1\) と \(b_1\) の算術平均を \(a_2\) とし、\(a_1\) と \(b_1\) の幾何平均を \(b_2\) とする。 \(a_2\) と \(b_2\) の算術平均を \(a_3\) とし、\(a_2\) と \(b_2\) の幾何平均を \(b_3\) とする。 以下、これを無限に繰り返す。 すなわち、数列 \(\langle a_n\rangle\) と \(\langle b_n\rangle\) を以下の漸化式で定義する。 \[ a_{1} = \frac{a+b}{2} \] \[ b_{1} = \sqrt{ab} \] \[ a_{n+1} = \frac{a_n+b_n}{2} \] \[ b_{n+1} = \sqrt{a_nb_n} \]

    このとき、数列 \(\langle a_n\rangle\) と \(\langle b_n\rangle\) は同じ値に収束することが知られている。共通の極限値を \(a\) と \(b\) の算術幾何平均と呼ぶ。

    1. 浮動小数点数 \(a\) と \(b\) を入力し、\(a\) と \(b\) の算術幾何平均を出力するプログラムを書け。 \(a\) も \(b\) も正であると仮定して良い。

    2. 浮動小数点数 \(a\) と \(b\) を入力し、算術幾何平均への収束の過程を出力するプログラムを書け。すなわち \[ \begin{array}{cc} a_1 & b_1 \\ a_2 & b_2 \\ a_3 & b_3 \\ \vdots & \vdots \end{array} \] の形で、\(a_n\) と \(b_n\) の差が見えなくなるまで出力せよ。

      \(a\) も \(b\) も正であると仮定して良い。

    3. \(a\) と \(b\) を入力して、以下のように定める \(m'\) と \(m''\) を出力するプログラムを書け。\(a\) と \(b\) の算術幾何平均を \(m\) とする。\(a\) と \(m\) の算術幾何平均を \(m'\) とする。\(m\) と \(b\) の算術幾何平均を \(m''\) とする。

    ヒント1

    \(a\gt b\) のとき、\[a_n-b_n\lt\frac{a-b}{2^n}\]が成り立つことが、証明できる。すなわち、算術平均の計算と幾何平均の計算を\(n\)回繰り返せば、算術幾何平均との誤差は \((a-b)/2^n\) 未満にできる。


戻る
奈良女子大学生活環境学部情報衣環境学科生活情報通信科学コース