Evolton

九州大学 2003年度 前期日程 第2次学力試験 整数・図形と方程式文系数学 第3問(c)

(1) 次の流れ図に対応するプログラムを実行する.
C=105を入力したとき,X,YおよびNの値を出力順にすべて示せ.

問題の図

(2) 座標平面上で,x座標とy座標がともに整数である点を格子点と呼ぶ.自然数A,B,Rを入力したとき,第1象限(x軸,y軸は含まない)にあり,かつ中心が(A,B)で半径がRの円の内部および周上にある格子点の個数と,それらの格子点のうち原点からの距離が最大である格子点(複数個あるときはx座標が最大のもの)の座標を出力するプログラムの流れ図を,方針を記述してから作成せよ.

難易度6/ 10計算量5/ 10目安20分

整数、図形と方程式、論証・証明 数え上げ、範囲評価、計算整理

方針

既存確認済みの流れ図を、XY=C を満たす自然数の組を小さい X から調べ、出力個数 N を数える処理として読む。(2) は円を含む第1象限内の整数長方形だけを探索範囲にし、各格子点が円内にあるかを判定する。個数を増やす処理と、原点からの距離最大かつ同距離なら x 座標最大という更新条件を分けて設計する。

解答

(1)
この流れ図は、XY=C を満たす自然数の組を、X の小さい順に調べて出力し、その個数を N として最後に出力する処理である。 C=105 の正の約数は 1,3,5,7,15,21,35,105 である。したがって、出力される (X,Y) は順に (1,105),(3,35),(5,21),(7,15),(15,7),(21,5),(35,3),(105,1) である。組の個数は8個なので、最後に N=8 を出力する。

(2)
方針は、円を含む最小限の整数長方形を調べ、その中で第1象限にある格子点だけを判定することである。

まず探索する x の範囲は max⁡(1,A−R)≦x≦A+R でよく、y の範囲は max⁡(1,B−R)≦y≦B+R でよい。ここで下限を1以上にするのは、第1象限で x 軸、y 軸を含まないからである。

各格子点 (x,y) について (x−A)2+(y−B)2≦R2 を満たすなら、その点は円の内部または周上にあるので、個数 N を1増やす。

さらに、最大距離の点を記録するため、現在の記録を (MX,MY)、最大距離の2乗を M とする。新しい点が円内にあるとき x2+y2>M なら記録を更新する。また x2+y2=M で、かつ x>MX なら、問題の指定に従って x 座標が大きい点へ更新する。

すべての候補を調べ終えたら N,MX,MY を出力すればよい。流れ図では、外側の繰り返しで x を動かし、内側の繰り返しで y を動かすようにすれば実現できる。

別解

解法2(反復条件と不変量)

方針

(1) は外側ループごとに X が1増え、内側ループ終了時に Y=⌈C/X⌉ となることを使う。(2) は疑似コードで探索範囲・個数・最良点の不変量を明示する。

解答

(1)
各 X=1,2,…,C について、内側の反復が終了した時点でY=min⁡{y∈N∣Xy≧C}である。そこで XY=C のときだけ出力されるから、出力は C の正の約数
X と商 Y=C/X の組である。C=105 では(X,Y)=(1,105),(3,35),(5,21),(7,15),(15,7),(21,5),(35,3),(105,1),最後に N=8 が出力される。

(2) X1=max⁡(1,A−R),Y1=max⁡(1,B−R)とし、次の疑似コードを流れ図へ移せばよい。N←0,M←−1for x=X1,…,A+Rfor y=Y1,…,B+Rif (x−A)2+(y−B)2≦R2N←N+1if x2+y2>M or (x2+y2=M and x>MX)(M,MX,MY)←(x2+y2,x,y)output N,MX,MY各反復の終了時に、N は調査済みの円内格子点数、(MX,MY) は調査済み点の
うち指定順序で最大の点を表す。よって全候補の調査後に正しい値が出力される。

総評

難度6、計算量5。目安時間は16〜22分。採点ポイントは、(1) で流れ図の処理を約数対の出力として読み、105 の約数対を漏れなく出すこと、(2) で円を含む有限範囲に探索を絞ること、最大距離が同じ場合に x 座標が大きい点を選ぶ処理を明記することです。

誤りやすいのは、第1象限に軸を含めて x=0 や y=0 を探索してしまうことです。また距離比較では平方根を取る必要はなく、x2+y2 の大小で十分です。流れ図を書く場合も、個数を数える更新と、最大点を更新する条件を別々に置くと誤作動を避けられます。

Evolton Pro

月額
2,480円(税込)
保存・印刷
公開過去問PDF・オーダーメイド問題集PDF
プランを確認・登録

冊子PDFで見る九大の整数の問題で問題集を作る

出典: 九州大学 2003年度 前期 文系 第3問(大学公式の問題PDF)。問題文はHTML表示のために再入力・数式組版しています。