Exercises on Scheme (1)

以下の記述は今回のみではなく課題全体に適用されます．課題を提出する際には，必ず動作確認を行ってください．またPandA記載の注意事項を守ってください．課題ごとに別ファイルとして正しい拡張子を付けて提出してください．なお，課題名にoptが付いた課題は，飛ばしてもその後の学習にあまり影響がありませんし，提出しなくても他が全てできていれば高得点となります．わからない時にはとりあえず飛ばして学習を進めて下さい．

[kadai02]

ある数xの2乗を計算する1引数関数(square x)を記述せよ．
以下のような2引数の関数(g2 x y)を記述せよ．
y=0のとき 1
y=1のとき x
y=2のとき x・x
という値を返す． yが0,1,2以外のときの値はどうなっていても(エラーでも)よい．

[kadai03]
nの階乗(n!)を求める関数(fact n)を記述し，300の階乗を求め，プログラムと結果を提出せよ．なお，

  n! = 1×(1×2×…×n)   (n≥0)

である．

[kadai04opt]
kadai03のプログラムが停止する整数の範囲を求め，数学的帰納法を用いて確かにその範囲で停止することを証明せよ．プログラムが停止するとは，有限時間で計算が終了することをいう．なお停止する範囲は理論上の値を求めればよい．つまり実際にコンピュータで実行するときのメモリ等の制約は考えなくてもよい．

ヒント: 引数の値が0の時にfactが再帰呼び出ししないようなプログラムだとする。
1. (fact 0)が停止することを、組み込みの各函数が停止することを使っていう。
2. (n≥0)のとき(fact n+1)が停止することを、(fact n)が停止することなどを使っていう。
数学的帰納法により・・・・

[kadai05]

0は偶数である．
n≥1のときn-1が偶数ならば，nは奇数である．
n≥1のときn-1が奇数ならば，nは偶数である．

という事実のみを直接用いて，引数が奇数ならば1を，偶数ならば0を返す1引数関数 (oe x)を記述せよ．

奇数でなければ偶数である．
偶数でなければ奇数である．
1は奇数である．

などの事実は与えられていないことに注意せよ．

[kadai06]
ユークリッドの互除法のアルゴリズムに基づいて最大公約数を求める2引数関数(gcd2 x y)を記述せよ． x,y≥1の範囲で正しく動作すること。

なお，ここでいうユークリッドの互除法のアルゴリズムとは，x ≥ yとしたとき，

x = y ならば，xとyの最大公約数は，x
そうでなければ(x > y)，xとyの最大公約数は，yと(x-y)の最大公約数である．

という事実を用いるものである．

このアルゴリズムは減算をmodに置き換えても動作する．大小関係の比較を最高次数の比較に置き換えることで，実数係数などの一変数多項式環の互除法を行うことができる．一般化してこのアルゴリズムはユークリッド環に適用できるものとなる (ユークリッド環などの定義は検索してほしい)．多変数多項式環のイデアルのGroebner基底を求める Buchbergerアルゴリズムは，さらに一般化したアルゴリズムと言える．

[kadai07opt]
正の整数nに対してその分割数を求める1引数関数 (partition n)を記述せよ．

正の整数nの分割数とは，nを正の整数の和に分割する方法が何通りあるかを表す数である(分割しない場合も含む)．たとえば，4の場合，

1+1+1+1
1+1+2
1+3
2+2
4

の5通りある．つまり(partition 4)=5である．

nの分割は，まず1を1個以上含む場合と1を含まない場合に分けることができる．いいかえると，nの分割数は，

まず1をとって，残りの(n-1)を1以上の整数で分割する場合の分割数
1を使わないで，nを2以上の整数だけで分割する場合の分割数

の二つの部分問題の解の和で求めることができる．一般に，正の整数mをk以上の正の整数で分割したときの分割数を，

  p(m,k)

と表すものとすると，上の関係を用いて，nの分割数，つまりnを1以上で分割する分割数partition(n)=p(n,1)は，

  p(n,1) = p(n-1,1) + p(n,2)

とかける．右辺は，それぞれ

  p(n-1,1) = p(n-2,1) + p(n-1,2)
  p(n,2)   = p(n-2,2) + p(n,3)

のようにさらに部分問題に分割できる．これらの右辺も再帰的により小さな問題に分割していくことができる．なおp(m,k)は，

m＝kであれば，1
m<kであれば，0

に決まる．このように分割数は再帰的に求めることができる．この方法は，自然で分かりやすいが，あまり効率はよくない．

参考

n	10	20	30	40	50
分割数	42	627	5604	37338	204226

2回目のまとめ

PLT Scheme(Dr. Scheme)を利用する場合、最初にlanguageを選択する。
LISP(Scheme)では新たな関数を定義していくことがプログラミングである。
schemeでは関数を定義するのにはdefineを用いる。
MIT schemeでファイルをschemeインタプリタに読み込むにはloadを用いる。
PLT Scheme(Dr. Scheme)の上の窓のプログラムをインタプリタに読み込むには「run」ボタンをクリックする。
2種類の条件文:ifとcond。
再帰呼出し・関数の再帰的定義。
任意多倍長整数演算。
関数が停止する範囲。
2回目の課題。

課題01のページへ

Schemeの課題 --- kadai02-07

2回目のまとめ