レポート問題▼第１回レポート

(1)

レポート問題

▼ 第１回レポート

• report_A_01_01

２本の定規を用いて掛け算と割り算を行う方法を考えなさい.この場合,定規に与えられた「関数目盛」はどのような関数かも説明しなさい.

• report_A_01_02

面積計で面積が計測できる理由を数学を用いて説明しなさい.

▼ 第２回レポート

• report_A_02_01

n ビットの情報{a_i}ⁿ_i=1 のすべての XORを取った値をa₀とおく.この時,いずれか一つの a_k (k = 1,· · ·, n)の値が失われた時,a₀と失われていない{a_i}たちの値を用いて,a_kの値を復元する方法を述べよ.

• report_A_02_02

正の整数bの１の補数をbとする.この時,−b の２の補数による表現は−b=b+ 1であることを示せ.

▼ 第３回レポート

• report_A_03_01

正の整数a,bに対して,a−bを計算する回路を加算回路を用いて実現せよ.

• report_A_03_02

日本語で書かれた新聞１ページが１５段からなり,１段は８２行,１行は１２文字からなると仮定する.さらに,１日の新聞は２０ページからなると仮定する. この時,新聞１年分（３６５日分）のデータ量を求めよ.

• report_A_03_03

１０進数の0.1を２進数で表せ.

▼ 第５回レポート

• report_A_05_01

先頭が-で始まるファイルを消去する方法を考えよ.

• report_A_05_02

２つのファイルを連結して,新しいファイルを作成する方法を考えよ.

▼ 第６回レポート

• report_A_06_01

Exercise 6.9.2, Exercise 6.9.3, Exercise 6.9.4, Exercise 6.9.5に答えよ.

• report_B_06_01

printf関数は出力した文字数を返す. “Hello

World” を書換えて,プログラムの戻り値が出

力した文字数となるようにせよ.

• report_B_06_02

次のプログラムは期待した結果を表示しない.

その理由を考え,期待した結果を表示するように書換えよ.

#include <stdio.h>

#include <limits.h>

int main() {

printf("CHAR_BIT = %d\n", CHAR_BIT) ;

printf("SCHAR_MIN = %d = %X\n", SCHAR_MIN, SCHAR_MIN) ; printf("SCHAR_MAX = %d = %X\n", SCHAR_MAX, SCHAR_MAX) ; printf("UCHAR_MAX = %u = %X\n", UCHAR_MAX, UCHAR_MAX) ; printf("CHAR_MIN = %d = %X\n", CHAR_MIN, CHAR_MIN) ; printf("CHAR_MAX = %d = %X\n", CHAR_MAX, CHAR_MAX) ; printf("----\n") ;

printf("SHRT_MIN = %d = %X\n", SHRT_MIN, SHRT_MIN) ; printf("SHRT_MAX = %d = %X\n", SHRT_MAX, SHRT_MAX) ; printf("USHRT_MAX = %u = %X\n", USHRT_MAX, USHRT_MAX) ; printf("----\n") ;

printf("INT_MIN = %d = %X\n", INT_MIN, INT_MIN) ; printf("INT_MAX = %d = %X\n", INT_MAX, INT_MAX) ; printf("UINT_MAX = %u = %X\n", UINT_MAX, UINT_MAX) ; printf("----\n") ;

printf("LONG_MIN = %ld = %X\n", LONG_MIN, LONG_MIN) ; printf("LONG_MAX = %ld = %X\n", LONG_MAX, LONG_MAX) ; printf("ULONG_MAX = %lu = %X\n", ULONG_MAX, ULONG_MAX) ; return 0 ;

}

• report_B_06_03

１バイトが８ビット,int型,unsigned int 型が４バイトであると仮定する.さらに,負の数は２の補数で表現されていると仮定する.この時,unsigned int型で表すことが出来る最

大の数(UINT_MAXに等しい),int型で表すこ

とが出来る最大の数(INT_MAXに等しい),int 型で表すことが出来る最小の数(INT_MINに等しい)を値1からはじめて,ビット演算のみ

(2)

で作成せよ.

▼ 第７回レポート

• report_A_07_01

正の整数 xに対して,xのb進表示に関する b−1 の補数をx, b の補数をx˜ とするとき, x˜=x+ 1を示せ.

• report_A_07_02

有理数は有限小数または循環小数で表される.

この事実はbの取り方によらないことを示せ.

また,nとbが互いに素の時,既約分数m/nのb 進小数表示の循環節の長さはb^e≡1 (modn) をみたす最小のeに等しいことを示せ.

• report_A_07_03

ある物体の質量を天秤で測定する.その重さは整数値で,M 以下とする.この時,必要な分銅の最小の数（種類）と測定方法を述べよ.ただし,分銅は物体と異なる側にしかのせれない場合と,両方にのせれる場合を考えよ.

• report_B_07_01

for文を利用して,1から20までの偶数の和を計算するプログラムを書け.

• report_B_07_02

while文を利用して,1から20までの偶数の和を計算するプログラムを書け.

• report_B_07_03

摂氏で表現された温度を0度から100度まで, 10度刻みで,華氏で表現するプログラムを書け.その際,華氏の温度は小数点以下第２桁目を四捨五入すること.

• report_B_07_04

標準入力から１文字を入力して,それが数字であるとき,偶数か奇数かを判定し,数字でないときには,再び入力を求めるプログラムを書け.

• report_B_07_05

正の有理数を１０進で小数点以下１００桁まで求めるプログラムを書け.

• report_B_07_06

１０進数で表現された０以上１未満の有限小数を２進数で表示するプログラムを書け.ただし,有限小数にならないときには,小数点以下第１０桁まで表示すればよい.

•

与えられた正の整数の −1倍をビット演算とインクリメントのみで計算するプログラムを書け.

• report_B_07_08

加算・減算のみで乗算と除算を行うプログラムを書け.

• report_B_07_09

加算・減算・ビット演算のみで乗算と除算を行うプログラムを書け.

• report_B_07_10

W週間D日H時間M分S秒という表現で与えられた２つの数値の加算を行うプログラムを書け.

• report_B_07_11

W週間D日H時間M分S秒という表現で与えられた２つの数値の減算を行うプログラムを書け.ただし,結果は「非負」と仮定して良く,0≤W <100と仮定する.

▼ 第８回レポート

• report_A_08_01

２つの正の整数a,bの最大公約数を求めるために必要な除算の回数を,a,bを用いて出来る限り精密に評価せよ.（ヒント：フィボナッチ数列との比較をおこなえ.）

• report_A_08_02

３つの正の整数a,b,cに対して,ax+by+cz= gcd(a, b, c)をみたすx,y,zを１組求めるアルゴリズムを示し,その計算回数の評価を行え.

• report_A_08_03

既約分数n/m,0< n < mを相異なる単位分数の和に分解するアルゴリズムを示せ.

• report_A_08_04

a,bを互いに素な正の整数とする.この時, χ(a, b)

= inf









 n∈N:

全てのm≥nに対して ax+by=m

をみたす自然数の組 (x, y)∈(N∪ {0})² が存在する.











(3)

とおく.この時,

χ(a, b) = (a−1)(b−1) であることを示せ.

• report_A_08_05 フィボナッチ数列

F_n+2 =F_n+1+F_n, n≥1, F₂=F₁= 1 の第n項F_nを再帰的関数呼出しを用いて求めようとするとき,関数呼出しの回数をnを用いて評価せよ.

• report_A_08_06

任意の正の整数a,b,kに対して, gcd(a, b) =gcd(b, b−ka) が成り立つことを証明せよ.

• report_B_08_01

２つの正の整数の最大公約数を求めるプログラムを書け.

• report_B_08_02

２つの正の整数の最大公約数を求めるプログラムを再帰的関数呼出しを用いて書け.

• report_B_08_03

２つの正の整数の最大公約数を求めるプログラムを,２進ＧＣＤアルゴリズムを用いて書け.

• report_B_08_04

３つの正の整数の最大公約数を求めるプログラムを書け.

• report_B_08_05

２つの正の整数 a, b に対して, ax +by = gcd(a, b)をみたす x, y を１組求めるプログラムを書け.

• report_B_08_06

３つの正の整数a,b,cに対して,ax+by+cz= gcd(a, b, c)をみたすx,y,zを１組求めるプログラムを書け.

• report_B_08_07

正の整数nの最小の約数を求めるプログラムを書け.

• report_B_08_08

正の整数nが完全数であるとは,nのすべての約数（1とnを含む）の和が2nに等しいこと

をいう.10000までのすべての完全数を求める

プログラムを書け.

• report_B_08_09

帰納的に定義された数列, a_n = 2a_n−1 +n, (n≥1),a₀= 0の第10項までを順に表示するプログラムを,再帰的関数呼出しを用いて書け.

• report_B_08_10

a,bを互いに素な正の整数とする.a円,b円の切手を用いて,n円の組合わせを作成したいとする. 実現出来ないnの値をすべて求めるプログラムを書け.

• report_B_08_11

正の整数nに対して,関数µを

µ(n) =











1 n= 1,

0







 n >1,

nは素数の２乗で割りきれる,









(−1)^k







 n >1, nはk個の相異なる素数の積,









と定義する.与えられた正の整数nに対して, µ(n)を求めるプログラムを書け.

• report_B_08_12

0より大きく1未満の有理数を分母が相異なる単位分数の和に分解するプログラムを書け.

• report_B_08_13

0より大きく1未満の有理数を,可能なときには,２つまたは３つの分母が相異なる単位分数の和に分解し,それが不可能なときには,そのことを出力するプログラムを書け.

▼ 第９回レポート

• report_B_09_01

西暦Ｙ年Ｍ月Ｎ日がその年の１月１日から数えて何日目になるかを与える関数を書け.

• report_B_09_02

エラトステネスのふるいを用いて,１００００までの素数を全て求めるプログラムを書け.

▼ 第１０回レポート

• report_B_10_01

(4)

正の１０進整数をb進整数に変換するプログラムを書け.ただし,2≤b≤36とし,「数字」は 0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ

を用いる.

• report_B_10_02

１０進整数を平衡３進整数に変換するプログラムを書け. ただし,平衡３進整数の「数字」

はp,z,nとし,それぞれ1,0,−1に対応する数字とする.

• report_B_10_03

１０進整数を−b進整数に変換するプログラムを書け.ただし,2≤b≤36とし,「数字」は 0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ

を用いる.

• report_B_10_04

２つの平衡３進整数を与えたとき,それらの加算・減算・乗算・整除を行うプログラムを書け.

ただし,整除に関しては,除数は０でないとし, 剰余は正の最小剰余をとること.

• report_B_10_05

２つの同じ型のオブジェクトを入れ替える関数を書け.

• report_B_10_06

標準関数atoiを実現せよ.

• report_B_10_07

標準関数strncmpを実現せよ.

• report_B_10_08

標準関数strncatを実現せよ.

• report_B_10_09

次の仕様をみたす関数を書け.

int str2int(char *s, int *d)

文字列sには一つ以上の「空白文字」で区切られた,int型の整数値を表す数値が入っているとき,int型の配列にその数値を代入する.

全ての数値が正しくint型の数値に変換できたときには,配列dに入っている有効な要素数を返し,一つでも正しく変換できなかったときには,値0を返す.

ただし,「空白文字」とは,標準関数isspace で区別できる文字のことをいう.

▼ 第１１回レポート

• report_A_11_01

IEEE浮動小数点規格で演算を行う計算機上で, a₀= 0, a₁= 1−√

5 2 , a_n+1=a_n+a_n−1

に従う数列{a_n}を,この帰納的定義（漸化式）

によって計算したとき,その結果は期待したものと異なる挙動を示す.この事実を説明せよ.

• report_A_11_02

f(x) = 0の解αがm重根(m≥2)である時, ニュートン法による近似解の誤差_nは,

_n= m m−1_n−1

を満たすことを証明せよ. （ヒント：f(x) = (x−α)^m−1g(x)と書け,x=αはg(x) = 0の単根であることを利用する.）

• report_A_11_03

１変数のニュートン法の収束に関する定理（講義中に述べたもの）を証明せよ.

• report_A_11_04 ニュートン法を用いて

f₁(x) = (x−1)(x+ 1), f₂(x) = (x−1)²(x+ 1), f₃(x) = (x−1)³(x+ 1), f₄(x) = (x−1)⁴(x+ 1)

の解x= 1への近似解の収束の様子を出力し, その誤差の収束について論ぜよ.

すなわち,（例えば）x= 2.0を初期値としたニュートン法の近似解の真の解との相対誤差を出力し,それが0に収束する様子をプロットしなさい. さらに,report_A_11_02の結果を合わせて,収束の様子について論ぜよ.

• report_A_11_05

f(x)をn次多項式とする. f(x+c)をcについての多項式とみたとき,そのk次の係数は f^(k)(z)/k!に等しいことを証明せよ.

• report_B_11_01 区間縮小法を用いて√

2の値を相対誤差10⁻⁷ で求めよ.

(5)

• report_B_11_02 ニュートン法を用いて√

2の値を相対誤差10⁻⁷ で求めよ.

• report_B_11_03

１変数多項式fをz−aで割った商,f(a)を求めるプログラムを書け.

▼ 第１２回レポート

• report_A_12_01

Chebyshev 多項式 T_n(x) = cos(narccosx), n≤1に対して,

T_n+1(x) = 2xT_n(x)−T_n−1(x)

を満たすことを証明せよ.

• report_A_12_02

Hermite 補間の定理で用いた行列

V⁽²⁾(x₁,· · ·, x_n)は

detV⁽²⁾(x₁,· · ·, x_n) =

j>i

(x_j−x_i)²

を満たすことを証明せよ.

• report_A_12_03

(−2,0),(−1,1),(0,0),(1,−1),(2,0)をサンプル点とする, Lagrange補間多項式を求めよ.

• report_B_12_01

２つの１変数多項式f,gを与えたとき,その最大公約多項式を求めるプログラムを書け.

• report_B_12_02

{(x_i, y_i)}ⁿ_i=1 を与えて,そのLagrange 補間多項式P(x)を求めるプログラムを書け.