● 先週の授業のキーポイント 【ポインタ】

● 先週の授業のキーポイント

【ポインタ】

• Cにおける「ポインタ」とは,他のオブジェクト（変数や関数）のアドレスを値に持つ変数のこ とである.

• ポインタは,「どの型のオブジェクトのアドレスを値とするか」（「どの型のオブジェクトを指し 示すか」）を明示して定義する必要がある. 例えば,int型の変数を指し示すポインタ（int型 の変数へのポインタ）は,

int *pa ; と定義する.

• ポインタを扱う上で登場する演算子は, – 「間接演算子」“*”

ポインタに間接演算子を適用すると,指し示しているオブジェクトの値を参照することがで きる.

– 「アドレス演算子」“&”

単純なオブジェクトにアドレス演算子を適用すると,そのオブジェクトのアドレスを得る.

したがって,paがintへのポインタ,aがint型の変数の時, pa = &a ;

によってpaが aを指し示すようになる.

【配列とポインタ】

• 配列int a[10]と定義されているとき, “a” そのものは,配列の先頭アドレスを値とするオブ ジェクトとなる. すなわち, 要素の型へのポインタとなる. したがって, paが intへのポイン タ,aがint型の要素を持つ配列であるとき,

pa = a ;

は正しい代入となる.

• ポインタpa に対して, pa+1は paが指し示すアドレスの「次のアドレス」を値に持つポイン タとなる. 「次のアドレス」とは,「１バイト先」ではなく,ポインタが指し示す型がfooであ るとき, 「sizeof(foo)バイト先」のアドレスである.

• aが配列であるとき,a[i]は*(a+i)と等価である. 逆に,paがポインタであるとき,*(pa+i) を pa[i]と書くこともできる.

• ポインタpaに対して,pa++というインクリメントを行うことが可能である. これは,（参照と 値の変更の順序を無視すると）paの値をpa+1に置き換える操作である. しかし,配列aに対 してa++という操作はできない. これがポインタと配列が異なる点である.

【ポインタを関数の引数に利用する】

• ポインタを関数の引数に利用することができる. 例えば int型へのポインタを引数に持ち, 戻

と宣言される. このとき,関数プロトタイプ宣言は int foo(int *) ;

とすればよい. この関数をint型の変数aを使って foo(&a)

と呼び出すことができる.

• このようにポインタを引数として関数を呼び出すことにより, 「関数の副作用」を利用できる.

すなわち,foo側でaの値を書き換えることにより,呼び出し側へ書き換えの作用を及ぼすこと ができる. 以前の「配列を関数引数として,関数側で配列要素を書き換えると,呼び出し側へも それが反映される」という事実は,実際には配列全体を関数（実）引数としているのではなく, 配列の先頭アドレスのみを関数（実）引数としているからである.

• この事実から,一旦関数に渡ってしまった配列はポインタとして扱われることがわかる. （プロ グラムを配列として書いているか,ポインタとして書いているかは無関係.）

• ポインタを関数の戻り値とすることができる. 例えばchar型へのポインタを戻り値とする関数

（引数は,ここではintとした）は char *foo(int a) ;

とすればよい.

• Cの関数は戻り値として値をただ一つしか取れないが,ポインタを引数として使うことで,複数 の値を返したり,配列を返すのと同等の効果を生む関数を作ることができる.

● 実習内容

★ ex13-1.c 簡単な再帰の例 (1: 線形漸化式).

1. 次の漸化式で定義される数列を計算する.

a_n+1= 2a_n+ 1, a₀= 1.

2. a[n]を求める関数として,foo(n)を作り,上の定義式通りにプログラムしてみる. (ex13-1-1.c) 3. 関数fooの中で,「自分自身の呼び出し」が含まれている.

「帰納的定義（漸化式）＝再帰的関数呼び出し」

4. ex13-1-2.cは,同じ計算を再帰を使わずに書いたもの.

★ ex13-2.c 簡単な再帰の例 (2: 階乗).

1. a_n=n!は,次の漸化式で定義された数列と思うことができる.

a_n+1=n×a_n, a₀= 1.

2. a[n] を求める関数として, factorial(n) を作り, 上の定義式通りにプログラムしてみる.

(ex13-2-1.c)

3. ex13-2-2.cは,同じ計算を再帰を使わずに書いたもの.

★ ex13-3.c 再帰の方法

1. このプログラム内では２種類の再帰が書かれている. いずれの関数も,引数をプリントするだけ の単純な関数である.

2. recursion_headでは,最初に自分自身を呼び出した後,引数をプリントする.

3. recursion_tailでは,最初に引数をプリントし,その後に自分自身を呼び出す.

再帰呼び出しの後に何も行わない呼び出しとなっている. これを「末尾再帰」(tail recursion) と呼ぶ.

4. 一見,何の変哲もないプログラムのように見えるが,recursion_tailは自分自身を呼び出した 後に,何の作業も行っていないことに注意しよう.

★ ex13-4.c 高速乗算

1. 課題exercise-10-4.c「高速乗算」を再帰で書いてみよう.

2. 「高速乗算」のキーポイントは,a²ⁿ = (aⁿ)²を用いて巾乗を計算することであった. したがっ て,この部分を再帰で書くことが可能となる. これをそのまま再帰にしてみたのがex13-4-1.c である.

3. 一方,その再帰計算に少々の工夫を行ったものex13-4-2.cを書くことができる.

4. 高速乗算は,本質的にはA₀= 1,A_n= (A_n−1)²によって定義された数列を求める問題とも理解 できる.

● これらのプログラムの実行時間の計測

試しに,ex13-1,ex13-2,ex13-4 の各プログラムの実行時間の計測を行ってみよう. そのためには, 例えば ex13-1-1.cならば foo(10)の呼び出しを一定回数（１万回など）を行って,その実行時間 を計測すればよい. （プログラム例はex13-1-time.c. 関数“gettime”の中身は気にしないことに しよう.）

ただし,他のプロセスの影響を可能な限り避けるため, N回の関数呼び出しを M回交互に行って, 合 計時間を Mで割った値である. (N,Mは問題ごとに異る.）

実際の実行時間の計測例は以下のようになる. （単位「秒」）

再帰 非再帰 (ex13-4-1.c)

ex13-1 0.093902 0.028047 ex13-2 0.103447 0.030577

ex13-4 0.018104 0.015128 0.091896

ただし, ex13-4については「再帰版」としてex13-4-2.cを用いている.

このように「再帰」で書いたプログラムは「非再帰」のものよりも（一般に）低速であることがわか る. さらに ex13-4-1.cに関しては,ex13-4-2.cと比較して, 極めて遅くなっていることがわかる.

/* $Id: ex13-1-1.c,v 1.3 2004-07-02 08:31:45+09 naito Exp $ */

/* a_{n+1} = 2 a_n + 1, a_0 = 1 を計算 */

#include <stdio.h>

int foo(int) ;

int main(int argc, char **argv) {

printf("%d\n", foo(10)) ; return 0 ;

}

int foo(int n) {

if (n == 0) return 1 ; return 2*foo(n-1) + 1 ; }

★

ex13-1-2.c

/* $Id: ex13-1-2.c,v 1.3 2004-07-02 08:31:54+09 naito Exp $ */

/* a_{n+1} = 2 a_n + 1, a_0 = 1 を計算 */

#include <stdio.h>

int foo(int) ;

int main(int argc, char **argv) {

printf("%d\n", foo(10)) ; return 0 ;

}

int foo(int n) {

int i, k=1, m=1 ; for(i=0;i<n;i++) {

m = 2*k + 1 ; k = m ; }

return m ; }

★

ex13-2-1.c

/* $Id: ex13-2-1.c,v 1.3 2004-07-02 08:48:00+09 naito Exp $ */

#include <stdio.h>

int fractional(int) ; int main(int argc, char **argv) {

printf("%d\n", fractional(10)) ; return 0 ;

}

int fractional(int n) /* n! を計算 */

{

if (n == 0) return 1 ; return n*fractional(n-1) ; }

★

ex13-2-2.c

/* $Id: ex13-2-2.c,v 1.3 2004-07-02 08:47:59+09 naito Exp $ */

#include <stdio.h>

int fractional(int) ; int main(int argc, char **argv) {

int i ;

printf("%d\n", fractional(10)) ; return 0 ;

}

int fractional(int n) /* n! を計算 */

{

int i, m=1 ;

if (n == 0) return 1 ; for(i=1;i<=n;i++) m *= i ; return m ;

}

/* $Id: ex13-3.c,v 1.5 2004-07-06 09:23:50+09 naito Exp $ */

#include <stdio.h>

int recursion_head(int) ; int recursion_tail(int) ; int main(int argc, char **argv) {

printf("ret=%d\n", recursion_head(9)) ; printf("ret=%d\n", recursion_tail(9)) ; return 0 ;

}

int recursion_tail(int n) {

printf("%d\t", n) ; if (n == 0) return 0 ; return recursion_tail(n-1) ; }

int recursion_head(int n) {

if (n == 0) { printf("%d\t", n) ; return 0 ; } recursion_head(n-1) ;

printf("%d\t", n) ; return n ;

}

★

ex13-4-1.c

/* $Id: ex13-4-1.c,v 1.4 2004-07-02 09:55:37+09 naito Exp $ */

/* 巾乗（高速乗算） */

#include <stdio.h>

unsigned int uint_power(unsigned int, unsigned int) ; int main(int argc, char **argv)

{

printf("%u\n", uint_power(2,10)) ; return 0 ;

}

/* 高速乗算 */

unsigned int uint_power(unsigned int a, unsigned int n) {

if (n == 0) return 1 ;

if (n&1) return a*uint_power(a, n>>1)*uint_power(a, n>>1) ; return uint_power(a, n>>1)*uint_power(a, n>>1) ;

}

★

ex13-4-2.c

/* $Id: ex13-4-2.c,v 1.3 2004-07-02 09:55:50+09 naito Exp $ */

/* 巾乗（高速乗算） */

#include <stdio.h>

unsigned int uint_power(unsigned int, unsigned int) ; int main(int argc, char **argv)

{

printf("%u\n", uint_power(2,10)) ; return 0 ;

}

/* 高速乗算 */

unsigned int uint_power(unsigned int a, unsigned int n) {

unsigned int m ; if (n == 0) return 1 ; m = uint_power(a, n>>1) ; if (n&1) return m*m*a ; return m*m ;

}

/* $Id: ex13-1-time.c,v 1.1 2004-07-02 10:01:34+09 naito Exp $ */

#include <stdio.h>

#include <sys/time.h>

#define N 100000

#define M 10

#define MICRO 1000000 unsigned long gettime(void) ; int foo_recursive(int) ; int foo_non_recursive(int) ; int main(int argc, char **argv) {

int i, j ;

unsigned long start, end, recursive=0UL, non_recursive=0UL ; for(j=0;j<M;j++) {

start = gettime() ;

for(i=0;i<N;i++) foo_recursive(10) ; end = gettime() ;

recursive += end - start ; start = gettime() ;

for(i=0;i<N;i++) foo_non_recursive(10) ; end = gettime() ;

non_recursive += end - start ; }

printf("recursive:\n") ;

printf("\t%lu.%.06lu secs\n", (recursive/M)/MICRO, (recursive/M)%MICRO) ; printf("non_recursive:\n") ;

printf("\t%lu.%06lu secs\n", (non_recursive/M)/MICRO, (non_recursive/M)%MICRO) ; return 0 ;

}

/* ここに foo の recursive 版 "foo_recursive"

* non-recursive 版 "foo_non_recursive"

* を入れる */

unsigned long gettime(void) {

struct timeval tp ; gettimeofday(&tp, NULL) ;

return (unsigned long)tp.tv_sec*MICRO + tp.tv_usec ; }

【課題】 以下の課題では,必要に応じて関数を作ってプログラムを書くこと. また,「標準関数」は自由に 利用してかまわないが,当然,その問題自身の目的になっている標準関数は利用してはならない. （必 要なものはstdio.h,ctype.h,strings.hに含まれるものだけである.）ただし,以下の問題のうち

exercise-13-10以降ではunsigned int,int型は32ビットであることを,文字列の長さを決める ために利用してもよい.

☆ exercise-13-1 ２つの正の整数を求めるユークリッドの互除法のプログラムを再帰を用いて書き

なさい.

☆ exercise-13-2 Fibonacci数列

a_n+2 =a_n+1+a_n, a₀= 0, a₁= 1

の第n項を求めるプログラムを,再帰を用いたもの,再帰を用いないものの両方を書きなさい.

また,可能ならばそれらのプログラムの実行時間を計測しなさい.

★ exercise-13-3 ex13-4-1.cとex13-4-2.cのプログラムにおいて,それぞれのプログラムで関 数 uint_powerの呼び出し回数を求めなさい.

★ exercise-13-4 与えられた文字列を「逆順に」出力するプログラムを再帰を用いて書きなさい.

この問題は,以前に例示したstrrevを再帰を用いて実現するのではなく,関数内部で出力を行 うプログラムを書きなさいということです.

【ヒント】 関数に渡された文字列の長さが「１文字」になったら,その文字を出力する関数を 再帰的に呼び出せばよい.

★ exercise-13-5 次の仕様をみたす関数をつくりなさい.

【形式】

char *strrev(char *s)

【機能説明】

文字列sを逆転した文字列に書き換えます. 戻り値はsへのポインタです.

【ヒント】

s の末尾文字へのポインタを作成し, その文字を一旦退避してから, そこにNULL 文字を 書き込めば,再帰で呼び出した関数内部での文字列の長さが２減ります.

【注意】

この問題はK&Rに「問題」として掲載されています.

★ exercise-13-6 「ハノイの塔」 (Hanoi Tower)とは以下のような問題です.

【ハノイの塔】

３本の柱があり,そのうちの１本の柱に大きさの異るn枚の円盤が,下から大きな順に並ん でいます. （他の２本の柱には円盤はありません.）この n枚の円盤を以下の条件の元に, 他の２本のいずれかの柱に,下から大きな順に並ぶように移動させなさい.

1. １回に移動できる円盤の枚数は１枚のみである.

2. 小さな円盤の上に大きな円盤を載せることはできない.

★ exercise-13-6-1 ハノイの塔を解くアルゴリズムを示し,それを証明しなさい.

☆ exercise-13-6-2 n枚の円盤に関するハノイの塔を解くために必要な移動回数を求めなさい.

☆ exercise-13-6-3 再帰を用いてハノイの塔を解く手順を出力するプログラムを書きなさい.

【注意】 「ハノイの塔」は次の意味で極めて有名な問題です.

（ソートされるデータ列は{a_k}_k=1 とします.）

1. {a_k}ⁿ_k=1 の中央にある値A=a_n/2 を取り,集合S ={a_k}ⁿ_k=1 をA 以下の値の集合S₁, A と等しい値の集合S₂,A 以上の値の集合S₃ に分割する. ここで, S のS₁, S₃,S₂ への 分割とは,データ列{a_k} を並び替え,先頭にS₁ の要素を, その後にS₂ の要素を, 最後に S₃ の要素を並べることを意味します. （各S_i の中の並び方は指定していません.）

2. S₁,S₂ に対して,それぞれの要素数が1以下になるまで上と同じ操作を繰り返す.

ここで, S の{S_k}³_k=1 への分割は,次のアルゴリズムを用いることで実現できます.

1. i= 1,j=nとおく.

2. a_i< Aである間,i←i+ 1とする.

3. a_j> A である間,j←j−1とする.

4. i≤j ならば, a_i と a_j を交換し,i←i+ 1,j←j−1を行う.

5. i > j ならば2 に戻る.

これが終了したとき,S₁={a_k}ⁱ⁻¹_k=1,S₃={a_k}ⁿ_k=j+1 となる.

【例１】 3 2 4 1 5 を a₃= 4 をキーに分割する.

1. i= 1,j= 5 とおく.

2. i= 3,j= 4 となる.

3. i < j なので,a₃= 4とa₄= 1を交換し,i= 4,j= 3となる.

したがって,S₁= 3 2 1 ,S₃= 4 5 となる.

【例２】 4 4 4 4 4 を a₃= 4 をキーに分割する.

1. i= 1,j= 5 とおく.

2. i < j なので,a₁= 4とa₅= 4を交換し,i= 2,j= 4となる.

3. i < j なので,a₂= 4とa₄= 4を交換し,i= 3,j= 3となる.

したがって,S₁= 4 4 ,S₃= 4 4 となる.

int型のデータ列をクイックソートでソートするプログラムを書きなさい.

▽ exercise-13-8 「マージソート」 (Merge Sort)とは次の例で示されるソートのアルゴリズム です. 簡単のため,要素数は2 の巾乗とします. （以下の例では,要素数は 8 = 2³ とします.）

1. ソートされる列を 5 1 2 4 7 0 6 3 とします.

2. 列を再帰的に要素数2まで分割し,順序が逆転していればそれを交換します.

1 5 2 4 0 7 3 6

3. 再帰から戻る際に, 2^k個の要素を持つ2つの配列をマージします. その際に,両配列の先頭 から小さいものからマージしていきます.

1 5 2 4 0 7 3 6

↓

1 2 4 5 0 3 6 7

↓

0 1 2 3 4 5 6 7

int型のデータ列をマージソートでソートするプログラムを書きなさい.

★ exercise-13-10 b を2 以上 36以下の整数としたとき, unsigned int型の値を b 進表示した 結果を表示するプログラムを以下のような関数を構成して書きなさい.

【形式】

void radix(char *s, unsigned int a, unsigned int b)

【機能説明】

unsigned int型の値aの b進表示した文字列をsに返す.

☆ exercise-13-11 int型の値を平衡３進表示した結果を表示するプログラムを以下のような関数

を構成して書きなさい.

【形式】

void blanced_three(char *s, int a)

【機能説明】

int型の値aの平衡３進表示した文字列をsに返す.

★ exercise-13-12 bを2以上36以下の整数としたとき,int型の値を−b進表示した結果を表示 するプログラムを以下のような関数を構成して書きなさい.

【形式】

void neg_radix(char *s, int a, int b)

【機能説明】

int型の値aの-b進表示した文字列をsに返す.

★ exercise-13-13 {b_i}ⁿ⁻¹_i=0 を 2 以上 36 以下の整数の列としたとき, unsigned int 型の値を {b_i}ⁿ⁻¹_i=0 が定める混合基数による表示の結果を表示するプログラムを以下のような関数を構成 して書きなさい. ただし,nは32以下とします.

【形式】

void mixed_radix(char *s, unsigned int a, int *b, unsigned int n)

【機能説明】

unsigned int型の値aの bの定める混合基数表示した文字列をsに返す.

ただし, int型は32ビットであることを,文字列の長さを決めるために利用してもよい.

★ exercise-13-14 unsigned int型の値をフィボナッチ表現した結果を求めるプログラムを以下 のような関数を構成して書きなさい.

【形式】

int fibonacci_exp(int *f, unsigned int a)

【機能説明】

unsigned int型の値 aのフィボナッチ表現の添字の列をfに返す. 戻り値は意味のある fの要素数です.

☆ exercise-13-15 {b_i}³_i=0 ={60,60,24,7}とします. いま,x={x_i}³_i=0,y={y_i}³_i=0 が, 混合基 数{b_i} による表示をうけた非負整数であるとき,xとy の差の混合基数による表示{z_i}ⁿ_i=0 を 求めるプログラムを書きなさい. ただし,x > yは仮定してかまわないものとし,x₃,y₃<50と 仮定します. それぞれの混合基数表示を非負整数にもどしてはいけません.

「☆」のついた問題および「▽」のうち１問を8月4日(木)深夜までに提出してください.

☆ exercise-10-4 次の仕様をみたす関数をつくり,正の整数a,nに対してaⁿ を求めるプログラムを書 きなさい. ただし,ex10-1.cで作成したuint_powerよりも計算量の少ないものを作成すること.

【形式】

unsigned int uint_power(unsigned int a, unsigned int n)

【機能説明】

aのn乗を返します.

【エラー】

結果が unsigned int で表現できる値の範囲を超える場合には正しい値を返す保証はありま

せん.

★ 方針 nの2進を考えればよい. すなわち,

n=n₀+ 2n₁+ 2²n₂. . .+ 2^kn_k, aⁿ=aⁿ⁰a²ⁿ¹a²²ⁿ²· · ·a^2knk

と考えて,a, a², a⁴, . . . a^2k を順に計算すればよい. すなわち, 以下のアルゴリズムを利用する.

このアルゴリズムを「高速乗算法」と呼ぶ.

1. p= 1.

2. nが 0になるまで以下を繰り返す.

(a) nの最下位ビットが1ならば,pにaを掛ける.

(b) aを2乗する.

(c) nを右に1ビットシフトする.

これが終了したとき,p=aⁿ となっている.

このアルゴリズムは,nのビット数分だけの繰り返しで終了するので,有限ステップで終了する ことがわかる. また,j 回目の繰り返しが終了したとき,aには（当初のaの）a^j+1の値が入っ ている. このことから容易に求めるべき結果を得るための正しいアルゴリズムであることが証 明できる.

また,nのビット数分の繰り返しの後に終了するため,繰り返し回数はO(logn)となり,ex-10-1.c よりも少ない計算量で計算できる.

★ 解答例 上の方針を使えば,解答例としては次のプログラムになる.

/* $Id: exer-10-1.c,v 1.4 2005-07-12 12:45:44+09 naito Exp $ */

#include <stdio.h>

unsigned int uint_power(unsigned int, unsigned int) ; int main(int argc, char **argv)

{

unsigned int a=3U, n=10U ;

printf("%u^{%u} = %u\n", a, n, uint_power(a,n)) ; return 0 ;

}

/* a^n を計算する：高速乗算法 */

unsigned int uint_power(unsigned int a, unsigned int n) {

unsigned int p=1U ; while(n) {

if (n&1) p *= a ; a *= a ;

n >>=1 ; }

return p ; }

★ 提出されたプログラムに対するコメント

提出されたプログラムに関してはほぼ問題ないと思われる結果であった.

☆ exercise-11-3 与えられた文字列に含まれる単語の頭文字を大文字に変換するプログラムを書きなさ

い. ただし,「単語」の区切り文字は「英数字」以外の文字とします.

★ 方針 一番単純な方法は, 「単語の先頭文字」の判定として, 「現在見ている文字」が「英字」で あって, 「直前に見ていた文字」が「英数字」以外であるときときとすればよい.

★ 解答例 上の方針を使えば,解答例としては次のプログラムになる.

#include <stdio.h>

#include <ctype.h>

#define CAPITALIZE(c) ((c) - ’a’ + ’A’) char *_str_capital(char *, const char *) ; int main(int argc, char **argv)

{

char s[] = "this is a test. a-b-c" ; char t[100] ;

printf("%s\n", s) ;

printf("%s\n", _str_capital(t,s)) ; return 0 ;

}

char *_str_capital(char *t, const char *s) {

char *save = t ;

int before = 1 ; /* 直前の文字が「英数字」以外の時に 1 とする */

while(*s) {

if ((before)&&(islower(*s))) *t++ = CAPITALIZE(*s) ; else *t++ = *s ;

before = !(isalpha(*s) || isdigit(*s)) ; s++ ;

}

return save ; }

☆ exercise-11-4 次の仕様をみたす関数をつくりなさい.

【形式】

int arraycmp(int a1[], int a2[], int size)

【機能説明】

同じ要素数size個を持つint型の配列a1,a2に対して, {i∈[0,size−1] :a1[i]=a2[i]} を返す.

★ 方針 式“a1[i] != a2[i]”は a1[i]と a2[i]が等しくないときに1となる. この事実を使え

ばよい.

★ 解答例 上の方針を使えば,解答例としては次のプログラムになる.

/* $Id: exer-11-4.c,v 1.2 2005-07-12 17:48:34+09 naito Exp $ */

#include <stdio.h>

#define N (10)

int arraycom(int [], int [], int size) ; int main(int argc, char **argv)

{

int a[N] = {0,1,2,3,4,5,6,7,8,9} ; int b[N] = {0,0,2,0,4,0,6,0,0,0} ; printf("%d\n", arraycmp(a,b,N)) ; return 0 ;

}

int arraycmp(int a[], int b[], int size) {

int d = 0, i ;

for(i=0;i<size;i++) d += (a[i]!=b[i]) ; return d ;

}

でも,普通ならこちらのはずです.

/* $Id: exer-11-4-1.c,v 1.1 2005-07-12 18:43:06+09 naito Exp $ */

#include <stdio.h>

#define N (10)

int arraycom(int [], int [], int size) ; int main(int argc, char **argv)

{

int a[N] = {0,1,2,3,4,5,6,7,8,9} ; int b[N] = {0,0,2,0,4,0,6,0,0,0} ; printf("%d\n", arraycmp(a,b,N)) ; return 0 ;

}

int arraycmp(int a[], int b[], int size) {

int d = 0, i ;

for(i=0;i<size;i++) if (a[i]!=b[i]) d += 1 ; return d ;

}

▽ exercise-11-5 データ列{a_i}^k_i=1をソートするアルゴリズムのうち,「単純挿入法」とは,以下のアル ゴリズムで示されるものである.

fori:= 2to ndo

begin

a_j+1:=a_j ;j:=j−1 end

a_j+1=x end

単純挿入法を利用したソーティングのプログラムを書きなさい.

★ 方針 そのまま書くだけです.

★ 解答例 上の方針を使えば,解答例としては次のプログラムになる.

/* $Id: exer-11-6.c,v 1.1 2005-07-12 13:38:02+09 naito Exp $ */

#include <stdio.h>

#include <stdlib.h>

#include <time.h>

#define N (10)

#define M (100)

void insersion_sort(int [], int) ; int main(int argc, char **argv) {

int a[N], b[N], i ; srand(time(NULL)) ;

for(i=0;i<N;i++) a[i] = rand()%M ; insersion_sort(a, N) ;

for(i=0;i<N;i++) printf("%d\t", a[i]) ; printf("\n") ; return 0 ;

}

/* 単純挿入法 */

void insersion_sort(int a[], int width) {

int i,j ; int x ;

for(i=1;i<width;i++) { x = a[i] ; j = i-1 ;

while((x < a[j])&&(j >= 0)) { a[j+1] = a[j] ; j = j-1 ; }

a[j+1] = x ; }

return ; }

▽ exercise-11-6 データ列{a_i}^k_i=1をソートするアルゴリズムのうち,「単純選択法」とは,以下のアル ゴリズムで示されるものである.

fori:= 1to n−1 do begin

k:=i;x:=a_i forj:=i+ 1tondo

iff(a_j)< f(x)then begin

k:=j ;x:=a_j end

a_k :=a_i; a_i:=x end

単純選択法を利用したソーティングのプログラムを書きなさい.

★ 解答例 上の方針を使えば,解答例としては次のプログラムになる.

#include <stdio.h>

#include <stdlib.h>

#include <time.h>

#define N (10)

#define M (100)

void selection_sort(int [], int) ; int main(int argc, char **argv) {

int a[N], b[N], i ; srand(time(NULL)) ;

for(i=0;i<N;i++) a[i] = rand()%M ; selection_sort(a, N) ;

for(i=0;i<N;i++) printf("%d\t", a[i]) ; printf("\n") ; return 0 ;

}

/* 単純選択法 */

void selection_sort(int a[], int width) {

int i,j,k ; int x ;

for(i=0;i<width-1;i++) { k = i ; x = a[i] ; for(j=i+1;j<width;j++) {

if (x > a[j]) { k = j ; x = a[j] ; }

}

a[k] = a[i] ; a[i] = x ; }

return ; }

☆ exercise-11-7 「単純挿入法」, 「単純選択法」, 「単純交換法」（バブルソート）に対して, n 個の データをソートするために必要な計算量を求めなさい.

★ 解答例 問題がかなりいい加減でした. 正しい設問は,「それぞれの比較回数のオーダを求めなさ い」というものです. 答は,全てO(n²)です.

● 訂正

以下の２問の「例」に間違いがありました. お詫びして訂正します.

△ exercise-11-10 F₂ 係数の２つの一変数多項式f, gに対して, その最大公約多項式gcd(f, g)を求め るプログラムを書きなさい.

【例２】 f(x) =x³+x²+ 1,g(x) =x⁴+x³+x²+ 1に対しては, gcd(f, g) = 1. （ここのGCD が間違っています.）

△ exercise-11-16 ex11-10.cで使った方法を用いて, 64ビット整数に関するユークリッドの互除法を 書きなさい. すなわち,２つの64ビット整数a,bに対して,その最大公約数gcd(a, b)を求めるプロ グラムを書きなさい.

【例１】

a= (0F000A22 FFFF0000)₁₆

= (1080875056008986624)₁₀, b= (E00000B0 7FFF0A00)₁₆

= (16140901822557522432)₁₀,

gcd(a, b) = (200)₁₆= (512)₁₀（ここの. GCDが間違っています）