２００２年度・計算機数学・第１０回実習 1
実習内容１（実習時間中に行うもの）
1. 次の仕様をみたす関数を書け.
int is_leap_year(unsigned int year)
year が西暦をあらわす数値と考えて,西暦year年が閏年ならば1を,平年ならば0を返す.
2. 次の仕様をみたす関数を書け.
int gcd(unsigned int a, unsigned int b)
a, bで表される非負整数の最大公約数を返す. もし, aまたは bの少なくとも一方が 0 ならば, −1 を返す.
内部表現が２進で,負の整数の表現が２の補数表現の時,この仕様の関数は,intでは表現できないが
unsigned intで表現可能な２つの数の最大公約数を,ある例外を除いて正しく求めることが出来る
ことを示せ. 特に,その例外とは何かを考えよ.
3. unsigned int型の２つの数 a,bに対して,ax+by= gcd(a, b)をみたす整数 x,y を一組求める関 数を書け.
4. これらの関数を用いて,今までに書いたプログラムを書き直しなさい.
5. 漸化式 a1= 0,an = 2an−1+ 1によって定められた数列の第n項を求める関数を,再帰的関数呼出 しを使って書け. また, 再帰的関数呼出しを使わずに書け.
6. 上のgcd関数を再帰的関数呼出しを使って書け.
7. ２つの int型の変数の値を入れ替える関数を書け.
実習内容２（各自で自習）
1. ３個の正の整数の組 {ai}3i=1 に対して,その最大公約数gcd({ai})を求める関数を書け. あらかじめ 定められた最大n個の正の整数の組に対しても,容易に拡張できるように書くこと.
2. ３個の正の整数の組 {ai}3i=1 に対して, gcd({ai}ni=1) = 1 の時, 3
i=1xiai = 1 をみたす整数の組 {xi}3i=1 を一組求める関数を書け. あらかじめ定められた最大n個の正の整数の組に対しても,容易 に拡張できるように書くこと. さらに, gcd({ai}ni=1)= 1 の時にはどうするかを考えよ.
3. n 個の正の整数の組 {ai}ni=1 に対して, gcd({ai}ni=1) = 1 の時, n
i=1xiai = 1 をみたす整数の組 {xi}ni=1 が少なくとも一組存在することを証明せよ. （ヒント：中国式剰余定理）
4. ２つの同じ型の変数の値を入れ替える関数を書け. （ヒント：標準関数qsort の引数の渡し方を参 考にせよ.）
5. フィボナッチ数列 Fn =Fn−1+Fn−2, F1 =F2 = 1を再帰的関数呼出しを使って計算する場合, 第 n項を求めるための関数呼出しの回数を求めよ.
ex10.tex,v 1.4 2002-06-25 09:50:01+09 naito Exp
