高度プログラミング演習（０7）演習問題 • 月と日を入力して、それが1月1日から何一目であるか表示するプログラムを作成せよ。（ただし閏年は考慮しないこととする。） • 入力された２つの月日を求めるプログラムを作成せよ。（ただし、閏年は考慮しないこととする。） #include<stdio.h> int md(int m,int d) { switch (m) { case 12: d = d + 30; case 11: d = d + 31; case 10: d = d + 30; case 9: d = d + 31; case 8: d = d + 31; case 7: d = d + 30; case 6: d = d + 31; main() { int m0,d0,m1,d1; case 5: d = d + 30; case 4: d = d + 31; case 3: d = d + 28; case 2: d = d + 31; case 1: d = d; } return d; } scanf("%d %d %d %d",&m0,&d0,&m1,&d1); printf("%d\n",md(m1,d1)-md(m0,d0)); } 再帰関数 • 再帰 – 動作の対象が動作主そのもの。 • 主語＝目的語 – 彼は自分のことが好きだ。 – He loves himself. • 再帰関数 – 自分の中で自分自身を呼び出している関数。 void foo() { ………… ………… foo(); } 再帰関数を使う例(1) • n の階乗 – n! = n × n-1 × n-2 …. × 1 f(n) f(n-1) f(n-2) f(0) n*(n-1)*(n-2)*..*2*1 1*1 1 include <stdio.h> int fact(int n) { if(n==0) return 1; else return n * fact(n-1); } main() { int n; scanf("%d",&n); printf("%d ! = %d\n",n,fact(n)); } 再帰関数を使う例(2) • 10進表記の数 num を x進法表記するプログラム。 • num を x で割ったあまり桁の数字になる。 – 一番最初のあまりが一番小さい桁 • num が x よりも小さくなればそれが一番大きな桁になる。 10進表記 → 2進表記 #include <stdio.h> 1. num 2. num は 2 よりも大きい 5. num を表示する 3. num を 2 で割る 4. num % 2 を表示する 1. 2. 3. 2. 3. … 5. 2. 3. 4. 3. 4 void d2x(int num,int x) { if(num<x){ printf("%d",num); return; } d2x(num/x,x); printf("%d",num%x); } void main() { int num,x; scanf("%d %d",&num,&x); d2x(num,x); printf("\n"); } 例題問題 • 与えられた２数のべき乗を計算する関数を再帰関数を用いて作成せよ。練習問題 • ユークリッドの互除法を用いて最大公約数を求める関数を作成せよ。 • ヒント：２４と６４の最大公約数 – ６４％２４ → １６ – ２４％１６ → ８ – １６%８ → ０演習問題 • 格子の中で、点から点へは – 上または右にしか進めないとする。 • 任意の(x0,y0)から任意の(x1,y1)までの経路が何通りあるか計算するプログラムを作成せよ。 (x1,y1) (x0,y0)