第12章関数と配列

第10章関数
関数の再帰呼び出しとは
ハノイの塔
リダイレクト
レポート課題
関数の再帰呼び出し

nの階乗(有効数字15桁)
fact.c
#include <stdio.h>
double fact(int n)
{
if (n==0) return 1;
printf("fact:%u, n=%d\n", frac, n);
return n*fact(n-1);
}
自分自身を呼び出す
(n  0)
1
n! 
n  (n 1)! (n  0)
int main(int argc, char *argv[])
{
int n=3;
if (argc >1) sscanf(argv[1], "%d", &n);
printf("fact:%u, %d!=%.0f\n", fact, n, fact(n));
return 0;
}
数学的帰納法に
良く似ている
fact(3)の呼び出しの展開
fact(3)
6
fact(n)[n==3]
3*fact(2)
2
fact(n)[n==2]
2*fact(1)
1
fact(n)[n==1]
1*fact(0)
1
fact(n)[n==0]
1
ハノイの塔





3本の棒と大きさの異なる n枚の円盤がある。
すべての円盤は1番の棒に、上から下に大きくな
るように入れてある。
1回につき1つの円盤を動かし、2番の棒に移し
換える。
3つの棒はどのように利用しても良い。
どの時点、どの棒についても、大きな円盤が小さ
な円盤の上にきてはいけない。
１～3枚の場合(1から2に移す)

1枚

1

2
3枚
3
2枚
1
2
3
一番下を動かす前後に注目
1
2
3
ハノイの塔のアルゴリズム



上の n-1枚を３番目の棒(空き地)に移す
一番下の1枚を2番目の棒(目的地)に移す
3番目の棒(空き地)の n-1枚を2番目(目的地)に
移す
1枚のときは単に
 一番下の1枚を2番目の棒(目的地)に移す
PAD
hanoi(n-1,src,tmp,dst)
hanoi(1,src,dst,tmp)
hanoi(n,src,
dst,tmp)
目的地
n > 1
hanoi(n-1,tmp,dst,src)
printf("%d → %d\n", src, dst)
空き地
src+dst+tmp = 1+2+3 = 6 の関係式より
tmp = 6 - src - dst
を用いて第4引数tmpをなくすことも可能
ハノイの塔
#include <stdio.h>
void hanoi(??????)
{
??????
}
int main(int argc, char *argv[])
{
int n=3;
if (argc > 1) sscanf(argv[1], "%d", &n);
hanoi(n, 1, 2, 3);
return 0;
}
リダイレクト（出力編）



コマンドプロンプトにおいて、標準出力（ディスプ
レイ出力）をファイル出力に切り替える方法
例えば、階乗計算 fact.exe で10! を求める場合、
Z:\nyumon2>fact 10 > fact10.txt
とすることで、画面に表示されていたものが、テ
キストファイルとして保存される。
レポートの課題などで長い出力結果の一部をレ
ポートに添付する場合、画面上で結果の先頭部
分が消えてしまう時でも、リダイレクトにより結果
をファイルに保存すれば大丈夫。
演習問題12.2 (1次元化版)
#include <stdio.h>
#define NROW 3
#define NCOL 3
#define IDX(i,j) ((i)*NCOL+(j))
void sum_ave(int m, int n, double a[], double *s, double *av);
int main(void)
{
double s, av;
double a[NROW*NCOL] = {3.24, 1.76, 5.32,
2.37, 4.33, 1.26,
1.86, 1.86, 3.64};
sum_ave(NROW, NCOL, a, &s, &av);
printf("総和 = %7.2f, 平均 = %7.2f¥n", s, av);
return 0;
}
配列要素の数値の総和と
平均値を計算する関数
void sum_ave(int m, int n, double a[], double *s, double *av)
{
int i, j;
*s = 0;
for (i = 0; i < m; i++) {
総和の計算
for (j = 0; j < n; j++) *s += a[IDX(i,j)];
}
*av = *s/(m*n);
平均値の計算
}
演習問題12.3 (1次元化版)
#include <stdio.h>
#define N 3
#define IDX(i,j) ((i)*N+(j))
void sum(int m, int n, int x[], int y[], int z[]);
void diff(int m, int n, int x[], int y[], int z[]);
void prod(int m, int n, int x[], int y[], int z[]);
void disp_2D_array(int m, int n, int x[]);
int main(void)
{
int a[] = {1, 2, 3, 4, 5, 6, 7, 8, 9};
int b[] = {11, 12, 13, 14, 15, 16, 17, 18, 19};
int c[N*N];
disp_2D_array(N, N, a); disp_2D_array(N, N, b);
sum(?????????); disp_2D_array(N, N, c);
diff(?????????); disp_2D_array(N, N, c);
prod(?????????); disp_2D_array(N, N, c);
return 0;
}
演習問題12.3 （つづき）
void sum(int m, int n, int x[], int y[], int z[])
{
zi, j
行列の和
???...???
}
void diff(int m, int n, int x[], int y[], int z[])
{
zi, j
???...???
行列の差
}
void prod(int m, int n, int x[], int y[], int z[])
{
int i, j, k;
行列の積
for (i = 0; i < ?; i++) {
for (j = 0; j < ?; j++) {
zi, j
z[IDX(i,j)] = 0;
for (k = 0; k < ?; k++)
z[IDX(i,j)] += ???????????????;
}
}
}
void disp_2D_array(int m, int n, int x[])
{
???...???
}
 xi, j  yi, j
i = 1...m
j = 1...n
 xi, j  yi, j
i = 1...m
j = 1...n
n

x
i,k
 yk , j
k 1
i, j = 1...m
演習問題12.4 (1次元化版)
#include <stdio.h>
#define N 3
#define IDX(i,j) ((i)*(N+1)+(j))
void sweep_out(int n, double a[]);
void disp_2D_array(int m, int n, double a[]);
int main(void)
{
double a[N*(N+1)] = {2,3,1,-1, 3,1,2,7, 1,2,3,6};
disp_2D_array(???????);
sweep_out(???);
disp_2D_array(???????);
return 0;
}
掃出法
 2 3 1 1 1 0 0 x 

 

3 1 2 7   0 1 0 y 
1 2 3 6   0 0 1 z 

 

演習問題12.4
（つづき）
void sweep_out(int n, double a[])
{
int i, j, k; double w;
k行目の成分をその対角成分で割る
for (k = 0; k < n; k++) {
w = a[IDX(k,k)];
for (j = 0; j < n+1; j++) a[IDX(k,j)] /= w;
for (i = 0; i < n; i++) {
if (i != k) {
w = a[IDX(i,k)];
for (j = 0; j < n+1; j++) a[IDX(i,j)] -= w * a[IDX(k,j)];
}
}
掃き出し操作
}
}
void disp_2D_array(int m, int n, double a[])
{
???...???
}
第2回レポート(任意) 課題



課題：教科書p.114の演習問題12.3 または 12.4
提出期限：2010年11月26日(金) 12:50
提出場所：ネットワーク実験室(１)の入口近くの箱
今回のレポートでは以下の項目をいれること。
1. 学籍番号、氏名
2. 問題番号
レポートのファイルは
3. ソースリスト
保存しておくこと
4. 実行結果
5. 感想（５行以上）
レポートサンプルを参照のこと
本日のパズル
次のプログラムは何を出力するか
#include <stdio.h>
#define PRINT(x,y) printf("%d\t%d\n",x,y)
main()
{
int x, y;
x=y=0;
while ( y<10 ) ++y; x += y;
PRINT(x,y);
x=y=0;
while ( y<10 ) x += ++y;
PRINT(x,y);
for ( y=1; y<10; y++ ) x=y;
PRINT(x,y);
}
1
2
3

Download Report