黄昏より暗きもの、血の流れより赤きもの

黄昏より暗きもの、血の流れより赤きもの

自分の好きな事を好きなように書いて行きます。

2010年度の灘中学校で出題された、ガウス記号の問題をC言語で解いてみる(後編)

問題


下の問題は2010年度の灘中学校の入試問題*1 を編集したものである。





プログラムは得意。でも数学が苦手なP君はこの問題を以下の[問題1]〜[問題3]のようなソースコードを組んで問題(2)(3)を解決しようとした。以下の問題1〜問題3を答えよ。



実数xについて、xを超えない最大の整数を[x]とする。

問題1:double xを引数として、[x]を返り値とする関数int gauss(double x)のソースコードを記述せよ。

[ヒント]:floor(double x)関数を使うとxの整数部分を求める事が出来る。

以下の問題では、問題1で作成した関数を断り無しに使って良いものとする。

問題2:数列b_nをb_n=[10(n+1)/7]と定義する。Σ(1<=n<=200)b_nの値を求めるソースコードを記述し実行結果を表示することで、(2)を解決せよ。

問題3:自然数m,nがある。今数列a_nを、a_n=[n^2/m]と定義する。このときa_1〜a_nまでに登場する自然数の種類kを出力する関数int series(int m,int n)のソースコードを記述せよ。又series(20,20)を実行し表示する事で(3)を解決せよ。

*今回は問題3を解説して行く。

原題(3)を手動で解く


手計算で問題を解いてみよう。[x]はx>=0の場合において、xの整数部分となる。さて1*1/20,2*2/20,.........,20*20/20を20回計算し、それらの整数部分を求めよう。求まった整数部分の個数を数え、答えとすればよい。以下は20回の手計算をExcelを使って行った物だ。尚整数部分を求める計算には、ExcelのINT関数を用いた。



上記の表より、0,1,2,3,4,5,6,7,8,9,11,12,14,16,18,20の16種類発見できる(答)

問題3の方針


上記の解き方のように、求まった整数部分の種類を数えて行く訳だが、プログラムで整数部分の種類を数えるのがなかなか大変だ。まず[1*1/20],[2*2/20],.........,[n*n/20]の計算結果を格納する長さnの配列を用意しよう。配列の長さをnに指定した理由としては、n種類以上の整数が答えの候補として考えられないからだ。依って(求める個数k) = n - (同じ数字が登場するa_n個数)となり、nから同じ数字が登場する個数を引けば良い。ここで下図のように尚数列a_nの添字の番号は1から始まり、配列の添字の番号は0から始まる。数列を配列で扱うとき、1づつ数値が減る事に注意されたい。



a_3の値がa_nの他の値と同じでないか調べる。ここでa_nはnの値に応じて増加するので、配列の全ての要素とを見比べる必要はない。今回はa_1,a_2の値とa_3の値とを比較すれば良い。



つまりjを2<=j



問題3の手順


ここまでの手順をまとめると、



  1. k=nと代入を行う。

  2. a_1〜a_nの値を配列に格納。

  3. jを2<=j

問題3のソースコード


問題3の実行結果


冒頭で計算したとおり、series(20,20)を計算したとき16と表示されていればよい。16と表示されているので題意は満たされ、問題3は解決された。