Schemeの課題 --- kadai02-07

Copyright(C)1995-2009 by 桜川貴司
Copyright(C)1998-2005 by 日置尋久

課題を提出する際には,必ず注意事項を守ってください. なお,*が付いた課題は,飛ばしてもその後の学習にあまり影響がありません. わからない時にはとりあえず飛ばして学習を進めて下さい.


[kadai02]

  1. ある数xの2乗を計算する1引数関数(square  x)を記述せよ.
  2. 以下のような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)
である.

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

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

[kadai05]

  1. 0は偶数である.
  2. n≥1のときn-1が偶数ならば,nは奇数である.
  3. n≥1のときn-1が奇数ならば,nは偶数である.
という事実のみを用いて,引数が奇数ならば1を,偶数ならば0を返す1引数関数 (oe  x)を記述せよ.
などの事実は与えられていないことに注意せよ.

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

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

  1. x = y ならば,xとyの最大公約数は,x
  2. そうでなければ(x > y),xとyの最大公約数は,yと(x-y)の最大公約数である.
という事実を用いるものである.

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

[kadai07*]
正の整数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の分割数は,

の二つの部分問題の解の和で求めることができる. 一般に,正の整数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)は, に決まる.このように分割数は再帰的に求めることができる. この方法は,自然で分かりやすいが,あまり効率はよくない.

参考

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

2回目のまとめ


課題01のページへ