Navigation

再帰 (recursion)

階乗 (n! = ?)

factorial.c

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
/*
  Program: factorial.c
  Comment: Recursion for Factorial
  Compiler Version: gcc-4.2
  Build It: gcc -Wall -O2 -o factorial factorial.c
  Runtime Environment: Snow Leopard 10.6.4
  Date: Sep 3rd, 2010
  Author: Fei Zhao
  All Rights Reserved
*/

#include <stdio.h>

int fac(int n);

int main(int argc, char *argv[]){
  static int LIMIT = 10;
  int i;

  for( i=0; i<=LIMIT; i++ ){
    printf("%2d! = %7d\n", i, fac(i));
  }
  
  return 0;
}

int fac(int n){
  if(n == 0)
    return 1;
  else
    return n * fac(n-1);
}

factorial.c の実行結果は:

[cactus:~/code_c/math-for-p]% ./factorial
 0! =       1
 1! =       1
 2! =       2
 3! =       6
 4! =      24
 5! =     120
 6! =     720
 7! =    5040
 8! =   40320
 9! =  362880
10! = 3628800

順列と組み合わせ

permutation-combination.c

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
/*
  Program: permutation-combination.c
  Comment: Recursion for Permutation and Combination
  Compiler Version: gcc-4.2
  Build It: gcc -Wall -O2 -o permutation-combination permutation-combination.c
  Runtime Environment: Snow Leopard 10.6.4
  Date: Sep 3rd, 2010
  Author: Fei Zhao
  All Rights Reserved
*/

#include <stdio.h>

int fac(int n);
int permutation(int n, int k);
int combination(int n, int k);

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

  printf("The value of permutation is: %d\n", permutation(10, 4));
  printf("The value of combination is: %d\n", combination(10, 4));

  return 0;
}

int fac(int n){
  if(n == 0)
    return 1;
  else
    return n * fac(n-1);
}

int permutation(int n, int k){
  return fac(n) / fac(n-k);
}

int combination(int n, int k){
  return fac(n) / ( fac(n-k) * fac(k) );
}

permutation-combination.c の実行結果は:

[cactus:~/code_c/math-for-p]% ./permutation-combination
The value of permutation is: 5040
The value of combination is: 210

フィボナッチ数 (fibonacci)

fibonacci.c (次の項は前の 2 項の和)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
/*
  Program: fibonacci.c
  Comment: Recursion for Fibonacci Numbers
  Compiler Version: gcc-4.2
  Build It: gcc -Wall -O2 -o fibonacci fibonacci.c
  Runtime Environment: Snow Leopard 10.6.4
  Date: Sep 3rd, 2010
  Author: Fei Zhao
  All Rights Reserved
*/

#include <stdio.h>

int fibo(int n);

int main(int argc, char *argv[]){
  static int LIMIT = 10;
  int i;

  for( i=0; i<=LIMIT; i++ ){
    printf("F(%d) \t = %d\n", i, fibo(i));
  }
  
  return 0;
}

int fibo(int n){
  if(n == 0)
    return 0;
  else if(n == 1)
    return 1;
  else
    return fibo(n-1) + fibo(n-2);
}

fibonacci.c の実行結果は:

[cactus:~/code_c/math-for-p]% ./fibonacci
F(0)   = 0
F(1)   = 1
F(2)   = 1
F(3)   = 2
F(4)   = 3
F(5)   = 5
F(6)   = 8
F(7)   = 13
F(8)   = 21
F(9)   = 34
F(10)  = 55

トリボナッチ数 (tribonacci)

tribonacci.c (次の項は前の 3 項の和)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
/*
  Program: tribonacci
  Comment: Recursion for Tribonacci Numbers
  Compiler Version: gcc-4.2
  Build It: gcc -Wall -O2 -o tribonacci tribonacci.c
  Runtime Environment: Snow Leopard 10.6.4
  Date: Sep 3rd, 2010
  Author: Fei Zhao
  All Rights Reserved
*/

#include <stdio.h>

int tribo(int n);

int main(int argc, char *argv[]){
  int LIMIT = 10;
  int i;

  for( i=0; i<=LIMIT; i++ ){
    printf("Tribo(%d) \t = %d\n", i, tribo(i));
  }
  
  return 0;
}

int tribo(int n){
  if(n == 0)
    return 0;
  else if(n == 1)
    return 0;
  else if(n == 2)
    return 1;
  else
    return tribo(n-3) + tribo(n-2) + tribo(n-1);
}

tribonacci.c の実行結果は:

[cactus:~/code_c/math-for-p]% ./tribonacci
Tribo(0)  = 0
Tribo(1)  = 0
Tribo(2)  = 1
Tribo(3)  = 1
Tribo(4)  = 2
Tribo(5)  = 4
Tribo(6)  = 7
Tribo(7)  = 13
Tribo(8)  = 24
Tribo(9)  = 44
Tribo(10) = 81

テトラナッチ数 (tetranacci)

tetranacci.c (次の項は前の 4 項の和)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
/*
  Program: tetranacci
  Comment: Recursion for Tetranacci Numbers
  Compiler Version: gcc-4.2
  Build It: gcc -Wall -O2 -o tetranacci tetranacci.c
  Runtime Environment: Snow Leopard 10.6.4
  Date: Sep 3rd, 2010
  Author: Fei Zhao
  All Rights Reserved
*/

#include <stdio.h>

int tetra(int n);

int main(int argc, char *argv[]){
  int LIMIT = 10;
  int i;

  for( i=0; i<=LIMIT; i++ ){
    printf("Tetra(%d) \t = %d\n", i, tetra(i));
  }
  
  return 0;
}

int tetra(int n){
  if(n == 0)
    return 0;
  else if(n == 1)
    return 0;
  else if(n == 2)
    return 0;
  else if(n == 3)
    return 1;
  else
    return tetra(n-4) + tetra(n-3) + tetra(n-2) + tetra(n-1);
}

tetranacci.c の実行結果は:

[cactus:~/code_c/math-for-p]% ./tetranacci
Tetra(0)  = 0
Tetra(1)  = 0
Tetra(2)  = 0
Tetra(3)  = 1
Tetra(4)  = 1
Tetra(5)  = 2
Tetra(6)  = 4
Tetra(7)  = 8
Tetra(8)  = 15
Tetra(9)  = 29
Tetra(10) = 56

ハノイの塔 (再帰処理)

hanoi.c

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
/*
  """""""""""""""""""""""""""
       |            |       |
       |            |       |
    ___|___         |       |
   ____|____        |       |
  _____|_____       |       |
       |            |       |
  """""""""""""""""""""""""""
       A            B       C
  A -> B
  Program: hanoi.c
  Comment: Recursion for Hanoi Problem
  Compiler Version: gcc-4.2
  Build It: gcc -Wall -O2 -o hanoi hanoi.c
  Runtime Environment: Snow Leopard 10.6.4
  Date: Sep 3rd, 2010
  Author: Fei Zhao
  All Rights Reserved
*/

#include<stdio.h>

int i = 1; /* 手数 */

void hanoi(int n, char x, char y, char z);

int main(int argc, char *argv[]){
  hanoi(3, 'A', 'B', 'C');
  return 0;
}

void hanoi(int n, char x, char y, char z){
  if (n == 0){/* 何もしなくていい */}
  else{
    /* 柱 x から 柱 z へ柱 y を利用して移す (n-1) ハノイを解く  */
    hanoi(n-1, x, z, y);
    printf("%02d: %c -> %c\n", i++, x, y);
    /* 柱 z から 柱 y へ柱 x を利用して移す (n-1) ハノイを解く  */
    hanoi(n-1, z, y, x);
  }
}

hanoi.c の実行結果は:

[cactus:~/code_c/math-for-p]% ./hanoi
01: A -> B
02: A -> C
03: B -> C
04: A -> B
05: C -> A
06: C -> B
07: A -> B

パスカルの 3 角形

pascal-triangle.c

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
/*
  Program: pascal-triangle.c
  Comment: Recursion for Pascal's triangle
  Compiler Version: gcc-4.2
  Build It: gcc -Wall -O2 -o pascal-triangle pascal-triangle.c
  Runtime Environment: Snow Leopard 10.6.4
  Date: Sep 3rd, 2010
  Author: Fei Zhao
  All Rights Reserved
*/

#include <stdio.h>

int fac(int n);
int combination(int n, int k);

int main(int argc, char *argv[]){
  int i, j;
  for(i = 0; i < 10; i++){
    for(j = 0; j < i+1; j++){
      printf("%d\t", combination(i, j));
    }
    printf("\n");
  }

  return 0;
}

int fac(int n){
  if(n == 0)
    return 1;
  else
    return n * fac(n-1);
}

int combination(int n, int k){
  return fac(n) / ( fac(n-k) * fac(k) );
}

pascal-triangle.c の実行結果は:

1	
1	1	
1	2	1	
1	3	3	1	
1	4	6	4	1	
1	5	10	10	5	1	
1	6	15	20	15	6	1	
1	7	21	35	35	21	7	1	
1	8	28	56	70	56	28	8	1	
1	9	36	84	126	126	84	36	9	1

リッチなパスカルの 3 角形

rich-pascal.c

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
/*
  Program: rich-pascal.c
  Comment: Recursion for Pascal's triangle
  Compiler Version: gcc-4.2
  Build It: gcc -Wall -O2 -o rich-pascal rich-pascal.c -lcurses
  Runtime Environment: Snow Leopard 10.6.4
  Date: Sep 3rd, 2010
  Author: Fei Zhao
  All Rights Reserved
*/

#include <stdio.h>
#include <curses.h>
#include <unistd.h>

#define SIZE 10
#define ZOOM 3

int fac(int n);
int combination(int n, int k);

int main(int argc, char *argv[]){
  int i, j;
  initscr();
  noecho();

  for(i = 0; i < SIZE; i++){
    for(j = 0; j < i+1; j++){
      initscr();
      noecho();
      move( i*ZOOM, ZOOM * ( (SIZE-i) + (j*2) ) ); /* move (int y, int x) */
      printw("%3d", combination(i, j));
      refresh();
      usleep(100000);
    }
  }
  printf("\n");
  return 0;
}

int fac(int n){
  if(n == 0)
    return 1;
  else
    return n * fac(n-1);
}

int combination(int n, int k){
  return fac(n) / ( fac(n-k) * fac(k) );
}

rich-pascal.c の実行結果は:

                                1


                             1     1


                          1     2     1


                       1     3     3     1


                    1     4     6     4     1


                 1     5    10    10     5     1


              1     6    15    20    15     6     1


           1     7    21    35    35    21     7     1


        1     8    28    56    70    56    28     8     1


     1     9    36    84   126   126    84    36     9     1

シェルピンスキーのギャスケット (Sierpinski gasket)

パスカルの 3 角形お, 奇数と偶数で色わけする

最大公約数 (GCD)

gcd.c

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
/*
  Program: gcd.c
  Comment: Recursion for Greatest Common Divisor (GCD)
           Euclid 互除法 を用いる
  Compiler Version: gcc-4.2
  Build It: gcc -Wall -O2 -o gcd gcd.c
  Runtime Environment: Snow Leopard 10.6.4
  Date: Sep 3rd, 2010
  Author: Fei Zhao
  All Rights Reserved
*/

#include <stdio.h>

int gcd(int x, int y);

int main(int argc, char *argv[]){
  printf( "(100, 20) の最大公約数は: %d\n", gcd(100, 20) );
  printf( "(99, 23) の最大公約数は: %d\n", gcd(99, 23) );
  printf( "(1234, 682) の最大公約数は: %d\n", gcd(1234, 682) );
  
  return 0;
}

int gcd(int x, int y){
  if(y == 0)
    return x;
  else
    return gcd(y, x % y);
}

gcd.c の実行結果は:

[cactus:~/code_c/math-for-p]% ./gcd
(100, 20) の最大公約数は: 20
(99, 23) の最大公約数は: 1
(1234, 682) の最大公約数は: 2

最小公倍数 (LCM)

lcm.c

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
/*
  Program: lcm.c
  Comment: Recursion for Least Common multiple (LCM)
           Euclid 互除法 を用いる
  Compiler Version: gcc-4.2
  Build It: gcc -Wall -O2 -o lcm lcm.c
  Runtime Environment: Snow Leopard 10.6.4
  Date: Sep 3rd, 2010
  Author: Fei Zhao
  All Rights Reserved
*/

#include <stdio.h>

int gcd(int x, int y);
int lcm(int x, int y);

int main(int argc, char *argv[]){
  printf( "(33, 44) の最小公倍数は: %d\n", lcm(33, 44) );
  printf( "(29, 34) の最小公倍数は: %d\n", lcm(29, 34) );
  printf( "(46, 64) の最小公倍数は: %d\n", lcm(46, 64) );
  
  return 0;
}

int gcd(int x, int y){
  if(y == 0)
    return x;
  else
    return gcd(y, x % y);
}

int lcm(int x, int y){
  return (x * y) / gcd(x, y);
}

lcm.c の実行結果は:

[cactus:~/code_c/math-for-p]% ./lcm
(33, 44) の最小公倍数は: 132
(29, 34) の最小公倍数は: 986
(46, 64) の最小公倍数は: 1472

竹内関数 (Tak function) (遅延評価がない)

遅延評価がないので, かなり遅い.

tarai.c

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
/*
  Program: tarai.c
  Comment: Recursion for Tak function(竹内関数)
  Compiler Version: gcc-4.2
  Build It: gcc -Wall -O2 -o tarai tarai.c
  Runtime Environment: Snow Leopard 10.6.4
  Date: Oct 1st, 2010
  Author: Fei Zhao
  All Rights Reserved
*/

#include <stdio.h>

int tarai(int x, int y, int z);

int main(int argc, char *argv[]){
  int x = 15;
  int y = 10;
  int z = 0;
  
  printf( "Tak(%d, %d, %d) = %d\n", x, y, z, tarai(x, y, z) );
    
  return 0;
}

int tarai(int x, int y, int z){
  if(x <= y)
    return y;
  return tarai( tarai(x-1, y, z), tarai(y-1, z, x), tarai(z-1, x, y) );
}

tarai.c の実行結果は:

[cactus:~/code_c/math-for-p]% ./tarai
Tak(15, 10, 0) = 15
[cactus:~/code_c/math-for-p]% /usr/bin/time ./tarai
Tak(15, 10, 0) = 15
       35.54 real        35.20 user         0.03 sys

Table Of Contents

Previous topic

剰余 (あまり, residue)

Next topic

スタック (Stack)

Navigation

© Copyright 2010, WTOPIA.