Document

■ 工学部 2015 年度「情報環境実験１」(富永)
課題レポート第４回(100 点)
問題
2015.07.27(月)
P.1
以下の問題から、3 問程度を選択して解答する。
【問題 4-05】と【問題 4-06】は、少し配点が高い。
オンラインの提出先は、\\chausson0\Report\InfoExpr1\Report4 のアカウント名の下で、主ファイル名は Report4 とする。
答案のテンプレートとして、\\chausson0\Material\InfoExpr1\Problem\Style4.docx を利用する。
各問で利用したプログラムや入出力データ、分析ファイルなども提出する。問題ごとに Q01 などのフォルダを作成して、その下に置く。
【問題4-01】
30点
プレーオフの勝敗パターン数
[第3-2章第05～08節]
(1) m 試合で、連勝条件 n のプレーオフにおいて、優勝チームからみたときの勝敗パターンの個数を求める関数を再帰的に定義せよ。
C言語の関数 po_cnt(n, m) を実装し、実行結果を確認する。m＝10, n＝3 などの場合で試してみる。
計算可能な範囲や、入力値による処理時間の増加の状況を考察する。無駄な再帰呼出を回避するなどの効率化も検討する。
例えば、残り試合数によって優勝が不可能な場合などに着目する。
(2) 先勝条件 n のプレーオフにおいて、優勝チームが f 連敗しない場合の勝敗パターンの個数を求める関数を再帰的に定義せよ。
C言語の関数 po_fst(n, f) を実装し、実行結果を確認する。n＝9, f＝3 などの場合で試してみる。
計算可能な範囲や、入力値による処理時間の増加の状況を考察する。無駄な再帰呼出を回避するなどの効率化も検討する。
【問題4-02】 30点
整数の分割数
[第5-1章第01～06節]
(1) 正整数 num と個数範囲 len を入力とし、len 個以内の正奇数の総和の形に表す方法の個数を求める関数を再帰的に定義せよ。
C言語の関数 ct_parti1(num, len) を実装し、実行結果を確認する。num＝12 までの分割数を、lenの値も変えて求めよ。
例えば、num＝4 のとき、3+1＝1+1+1+1 の2通りの分割がある。num＝5 のとき、5＝3+1+1＝1+1+1+1+1 の3通りの分割がある。
無駄な再帰呼出を回避するなどの効率化を検討する。再帰呼出の回数も求める。
numとlenの組と、分割数の値や再帰呼出の回数との関係をグラフに描き、傾向を分析する。
(2) 正整数 num を入力とし、奇数個の異なる正整数の総和の形に表す方法の個数を求める関数を再帰的に定義せよ。
C言語の関数 ct_parti2(num) を実装し、実行結果を確認する。num＝20 までの分割数を求めよ。
例えば、num≦5 のとき、それ自身の1通りの分割しかない。num＝6 のとき、6＝3+2+1 の2通りの分割がある。
無駄な再帰呼出を回避するなどの効率化を検討する。再帰呼出の回数も求める。
numと、分割数の値や再帰呼出の回数との関係をグラフに描き、傾向を分析する。
【問題4-03】 40点
整数の分割法の列挙
[第5-1章第01～06節]
(1) 正整数 num、個数範囲 len を入力とし、len 個以内の正奇数の総和の形に表す方法を全て列挙する関数を再帰的に定義せよ。
C言語の関数 enum_parti1(num, upp, len) を実装し、実行結果を確認する。num＝9 までの分割数を、lenの値も変えて求めよ。
(2) 使用可能な硬貨の種類のリスト、金額 mny、枚数範囲 cnt を与え、可能な支払い方法を全て列挙する関数を再帰的に定義せよ。
硬貨のリストは、配列 coin[] に小さい順に格納する。ただし、必ず coin[0]＝1 とする。
C言語の関数 enum_money(coin, mny, cnt) を実装し、実行結果を確認する。
例えば、coin[]＝{1,10,50} のとき、総数は 100＝50×2＝50×1＋10×5＝50×1＋10×4＋1×10＝‥ より、18通りの列挙となる。
枚数範囲 cnt＝20 とすれば、以下の5通りに絞られる。プログラムの出力の列挙も、以下のようにする。
50 10
1 枚
----------------2
0
0
2
1
5
0
6
1
4 10 15
0 10
0 10
0
9 10 19
mny＝50～200 (50刻み)、cnt＝10～50 (10刻み) などとし、
日本式 coin[]＝{1,5,10,50} や米国式 coin[]＝{1,5,10,25,50} で実行してみる。
なお、日本の法律では、20枚を越える硬貨での支払いは、受取りを拒否できるとなっている。
■ 工学部 2015 年度「情報環境実験１」(富永)
【問題4-04】 60点
多重再帰の樹状展開の効率化
課題レポート第４回(100 点)
問題
2015.07.27(月)
P.2
[第5-1章第01～06節]
(1) 正整数 num、要素上限 upp、個数範囲 len を入力とし、num を upp 以下の要素の二乗数の len 個以内の総和の形に表わす方法の
個数を求める関数を再帰的に定義せよ。C言語での関数 sq_parti(num, upp, len) を実装し、実行結果を確認する。
計算時間も計測し、分析する。 f(300, 20, 20) および f(500, 15, 10) を求めよ。
例えば、8＝4+4＝4+1+1+1+1＝1+1+‥+1 より、3^2＝9＞8 に注意すれば、 f(8,8,8)＝f(8,2,8)＝3, f(8,2,5)＝2 となる。
また、 f(100, 10, 100)＝1116, f(400, 15, 20)＝26536 である。無駄な再帰呼出を回避するなどの効率化を検討する。
(2) 適当なサイズの三次元配列 val[n][u][p] を用意し、ある範囲内の値を val[n][u][p]＝f(n,u,p) と結果表に格納しておき、
必要に応じて参照する。漸化式の計算も、再帰法でなく反復法で求める。このような効率化を動的計画法またはDPと呼ぶ。
動的計画法を用いて、 f(400, 20, 15)＝17669, f(400, 15, 20)＝55567 の値を効率良く求めよ。
計算時間も計測し、分析する。事前計算した結果表のサイズを変えて、傾向をグラフにまとめるとよい。
結果表は、大域変数の配列とすればよい。ただし、事前処理としての結果表への格納も、計算時間に含める。
(+) AWK言語の連想配列や、Ruby言語のハッシュを用いると、ある範囲内の全ての <n,u,p> に対する値ではなく、実際に計算に必要になる
組の値のみを記憶しておけばよいようにできる。これは、さらなる効率化とメモリの大幅な節約に繋がる。これをメモ化という。
メモ化を用いて、 f(1000, 15, 30)＝20807364, f(1000, 31, 20)＝4271239 の値を効率良く求めよ。
計算時間および利用した記憶領域の個数も計測し、分析する。他の値も試して、傾向をグラフにまとめるとよい。
メモ化は、再帰法において、記憶済なら再帰呼出せずにその値を使う、新たに値を求めたら記憶するという処理を加えればよい。
ただし、別な値で試すときは、メモをクリアしておかないと、前回の計算状況に依存してしまうので、注意が必要である。
【問題4-05】 60点
有理分数のエジプト表記
[第5-1章第01～06節]
1/3 や 1/7 など、分子が1で分母が正整数の有理分数を単位分数という。
古代エジプトでは、2/5 などの一般の分数も、分母が異なる単位分数の和の形で表わしていた。これを分数のエジプト表記という。
例えば、 5/6＝1/2＋1/3, 11/20＝1/4＋1/5＋1/10 などである。単位分数は、それ自体も、エジプト表記とみなす。
なお、分母が同じでもよければ、2/3＝1/3＋1/3 なども和の形になっているが、これはエジプト表記に含めない。
また、エジプト表記は1通りとは限らない。 1/2＝1/3＋1/6＝1/3＋1/12＋1/18＋1/36＝1/4＋1/5＋1/20 など、無数に考えられる。
特に、あるエジプト表記に含まれる単位分数を、そのエジプト表記に置き換えれば、元の分数の新たなエジプト表記が得られる。
(1) 分子が正整数 fc で、分母が正整数 fm である、1未満の有理分数 fc/fm ; fc＜fm に対し、
分母上限 upp と個数範囲 len を設けて、エジプト表記を考える。
この表記の個数を求める関数を再帰的に定義せよ。C言語での関数 ct_egypt(fc, fm, num, upp, len) を実装し、
実行結果を確認する。無駄な再帰呼出を回避するなどの効率化を検討する。計算時間も計測し、分析する。
例えば、 f(1, 2, 20, 3)＝6, f(1, 2, 30, 10)＝66 などとなる。 f(1, 2, 50, 10) や f(2, 3, 60, 15) を求めよ。
なお、本問は、数年前のACM-ICPCのインターネット予選の問題である。
(2) 列挙の関数 enum_egypt() も作成する。fc,fm,upp,len を引数とし、各行に、表記ごとの分母を列挙する。
例えば、 1 2 20 4 を入力すると、以下のように出力される。動的計画法やメモ化による効率化も検討せよ。
3 6
3 12 18 36
4 5 20

Download Report