関数の再帰呼び出しとは ハノイの塔 リダイレクト レポート課題

Presentation on theme: "関数の再帰呼び出しとは ハノイの塔 リダイレクト レポート課題"— Presentation transcript:

1 関数の再帰呼び出しとは ハノイの塔 リダイレクト レポート課題
第10章　関　数 関数の再帰呼び出しとは ハノイの塔 リダイレクト レポート課題

2 関数の再帰呼び出し 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); } 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; 自分自身を呼び出す 数学的帰納法に良く似ている

3 fact(3)の呼び出しの展開 fact(3) fact(n)[n==3] 6 3*fact(2) fact(n)[n==2] 2
1 fact(n)[n==0] 1 1

4 ハノイの塔 3本の棒と大きさの異なる n枚の円盤がある。 すべての円盤は1番の棒に、上から下に大きくなるように入れてある。
1回につき1つの円盤を動かし、2番の棒に移し換える。 3つの棒はどのように利用しても良い。 どの時点、どの棒についても、大きな円盤が小さな円盤の上にきてはいけない。

5 １～3枚の場合(1から2に移す) 1枚 2枚 3枚 一番下を動かす前後に注目

6 ハノイの塔のアルゴリズム 上の n-1枚を３番目の棒(空き地)に移す 一番下の1枚を2番目の棒(目的地)に移す
1枚のときは単に

7 PAD src+dst+tmp = 1+2+3 = 6 の関係式より tmp = 6 - src - dst
hanoi(n-1,src,tmp,dst) hanoi(1,src,dst,tmp) hanoi(n-1,tmp,dst,src) hanoi(n,src, dst,tmp) n > 1 printf("%d → %d\n", src, dst) 目的地 空き地 src+dst+tmp = = 6　の関係式より tmp = 6 - src - dst を用いて第4引数tmpをなくすことも可能

8 ハノイの塔 #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;

9 リダイレクト（出力編） コマンドプロンプトにおいて、標準出力（ディスプレイ出力）をファイル出力に切り替える方法
例えば、階乗計算 fact.exe で10! を求める場合、 Z:\nyumon2>fact 10 > fact10.txt とすることで、画面に表示されていたものが、テキストファイルとして保存される。 レポートの課題などで長い出力結果の一部をレポートに添付する場合、画面上で結果の先頭部分が消えてしまう時でも、リダイレクトにより結果をファイルに保存すれば大丈夫。

10 演習問題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); 配列要素の数値の総和と 平均値を計算する関数 総和の計算 平均値の計算

11 演習問題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 演習問題12.3 （つづき） i = 1...m j = 1...n 行列の和 i = 1...m j = 1...n 行列の差 行列の積
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[]) int i, j, k; for (i = 0; i < ?; i++) { for (j = 0; j < ?; 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[]) i = 1...m j = 1...n 行列の和 i = 1...m j = 1...n 行列の差 行列の積 i, j = 1...m

13 演習問題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(???); return 0; } 掃出法

14 演習問題12.4 （つづき） void sweep_out(int n, double a[]) {
演習問題12.4　（つづき） void sweep_out(int n, double a[]) { int i, j, k; double w; 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[]) ???...??? k行目の成分をその対角成分で割る 掃き出し操作

15 第2回 レポート(任意) 課題 課題：教科書p.114の演習問題12.3 または 12.4
提出期限：2010年11月26日(金) 12:50 提出場所：ネットワーク実験室(１)の入口近くの箱 今回のレポートでは以下の項目をいれること。 学籍番号、氏名 問題番号 ソースリスト 実行結果 感　想（５行以上） レポートのファイルは 保存しておくこと レポートサンプルを参照のこと

16 本日のパズル 次のプログラムは何を出力するか
#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); while ( y<10 ) x += ++y; for ( y=1; y<10; y++ ) x=y; } 1 2 3