数学をやっている方のためのプログラミング講座

例1 階乗

• n = 0 のときは、n の階乗は 1 となり、
• n > 0 のときは、n の階乗は n * ((n - 1)!) となります。

この定義は、階乗を計算するための手順と考えることもできます。 計算の手順を表すために、次の記法を使うことにします。

• function(文字; 式)
  は、式の中に現れる文字のところを置き換える(1変数の)関数を表します。 例 f = function(x; x + 2) とすると、f(5) は x + 2 の x を 5 で 置き換えたものとなり、f(5) = 7 となります。
• if(条件; 式1; 式2)
  は、条件が成立するときは式1、 条件が成立しないときは式2であるような式を表します。 (条件は結果が真理値であるような式)

この手順をプログラミング言語Cで書いてみます。

• それぞれの値には型が必要となります。 n、f(n) は自然数なので、ここではCで整数を表す型のうちの一つ「int」を使います。 型は文字(名前)の前につけます。
  例:

  int n
  int f(int n)

  名前は、アルファベットで始まり、後にアルファベットか数字が続く任意の長さの 文字列です。 名前は関数の名前(例ではf)、関数の引数の名前(例ではn)、 変数の名前(後述)などに使います。
• f(n) = α は、Cでは int f(int n) = { α } のようになります。 Cでは適当なところ(名前の途中や演算子の途中はだめ)に 改行、タブ、スペースを入れても意味は変わりません。
• n = 0 はCでは n == 0 になります。 Cでは以下のような演算子があります。

  x == y --- x と y は等しい。
  x != y --- x と y は等しくない。
  x < y --- x は y より小さい。
  x <= y --- x と y は等しいか x は y より小さい。
  x > y --- x は y より大きい。
  x >= y --- x と y は等しいか x は y より大きい。

• if(α; β; γ) はCでは if(α) {β} else {γ} となります。 Cでは式と文の区別があり、if文の β、γ のところは文でなでればいけません。 return文(return e;)は、指定した式 e の値を関数の値として関数を終了する文です。 { … } は複合文と言って、この中に複数の文を記述することができるのですが(後述)、 この例では文は一つしかないので、return文に変えるだけでよいです。

Cでの記述例:

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

例2 階乗

• i = 0 のときは、k[i] は 1 となり、
• i > 0 のときは、k[i] は i * k[i - 1] となります。

計算の手順を表すために、次の記法を使います。

• function(文字1, 文字2, …, 文字n; 式)
  は、n 変数の関数を表すとします。
• function(文字1, 文字2, …, 文字n; 式1, 式2, …, 式m)
  は、n 変数で、値が(式1, 式2, …, 式m)の組になるものを表すとします。 m 個の組 (x₀, x₁, …) から x_i を取り出すには、 (x₀, x₁, …)(i) と書くことにします。
• while(条件関数; 式; 関数)
  (条件関数は値が条件になる関数) は、関数の値に対して条件が成立する間、繰り返して 関数を適用することを表します。 このとき関数の値が次の関数の変数になります。 式の値は最初の関数の変数になります。 while(α; ξ; β) = if(α(ξ); γ(ξ); ξ), γ(ξ) = while(α; ξ; β)
• while(条件関数; 式1, 式2, …, 式n; 関数)
  は、関数が n 変数で値が n 個の組であるものを表します。 (条件関数は n 変数)

この記法を使うと、n の階乗 f(n) は、以下のように定義することができます。 上の手順を書き直すと、

• μ = 0 のときは、i[μ] = 1、k[μ] = 1 となり、
• μ > 0 のときは、i[μ] = i[μ-1] + 1、k[μ] = i[μ] * k[μ-1] となります。

• 変数とは、上の k[0], k[1], k[2], … のように、計算を進めるに従って 値が変わっていく列のことを言います。 ここでは k[0], k[1], k[2], … を変数 k で表します。 変数にも型が必要となります。k の型は int とします。 int f(int n) { … } の { … } の中の最初に変数の宣言 (Cでは定義)が必要となります。 変数の宣言の形式は「型名 変数名;」です。例: int k;
• 同様に i も変数とします。型は int とします。
• α、β が1変数の関数のとき、while(α; ξ; β) は 変数 x の宣言 x = ξ; while(α(x)) { x = β(x); } となります。 ただし、変数の宣言は、この記述の含まれるブロック({ … })の先頭 (他の変数の宣言の後でもよい)に記述することとし、 変数の名前はそのブロックで他に定義されていないものとします。 x = β(x); のような文(代入文、Cではx = β(x)が式で、 式に;をつけると文になる)に出てくる変数は、x[μ+1] = β(x[μ]) のような意味で、この前の文の変数はμで、後の文の変数はμ+1となります。
• α、β が2変数の関数のとき、while(α; ξ, η; β) は 変数 x, y の宣言 x = ξ; y = η; while(α(ξ, η)) { σ } となります。 変数の宣言、変数の名前については上と同じです。 β = function(x, y; c(x, y), d(x, y)) とすると σ のところは次と同じ意味になるようにします。

  x[μ+1] = c(x[μ], y[μ]);
  y[μ+1] = d(x[μ], y[μ]);

• β = function(i, k; i + 1, i * k) とすると σ のところは次と同じ意味になるようにします。

  i[μ+1] = i[μ] + 1;
  k[μ+1] = i[μ] * k[μ];

  前の代入文の左辺で添字がμ+1になった変数は、後の代入文の左辺でもμ+1に なっているようにします。この場合は

  k[μ+1] = i[μ] * k[μ];
  i[μ+1] = i[μ] + 1;

  とすればよいので、σ のところは

  k = i * k;
  i = i + 1;

  とすればよいです。Cの代入文の省略した書き方を使うと

  k *= i;
  i++;

  となります。
• Cのfor文を使って記述することもできます。 Cで
  for ( α; β; γ ) { σ₁, σ₂, … , σ_n }
  は
  α; while ( β ) { σ₁, σ₂, … , σ_n γ; }
  と同じ意味になります(記述例2)。

Cでの記述例1:

	int f(int n)
	{
		int i;
		int k;
		i = 1;
		k = 1;
		while ( i <= n ) {
			k *= i;
			i++;
		}
		return k;
	}

Cでの記述例2:

	int f(int n)
	{
		int i;
		int k;
		k = 1;
		for ( i = 1; i <= n; i++ ) {
			k *= i;
		}
		return k;
	}

例3 最大公約数

• n = 0 のときは、g(m, n) = m となり、
• n > 0 のときは、g(m, n) = g(n, m % n) となります。

今までの記法を使って

この手順をプログラミング言語Cで書いてみます。

• 記述例1については、上と同様です。
• α、β が2変数の関数のとき、while(α; ξ, η; β) は 変数 x, y の宣言 x = ξ; y = η; while(α(ξ, η)) { σ } となります。 変数の宣言、変数の名前については上と同じです。 β = function(i, j; j, i % j) とすると σ のところは次と同じ意味になるようにします。

  i[μ+1] = j[μ];
  j[μ+1] = i[μ] % j[μ];

  前の代入文の左辺で添字がμ+1になった変数は、後の代入文の左辺でもμ+1に なっているようにします。この場合は新しい変数 k を導入してk[μ+1] = i[μ];

  i[μ+1] = j[μ];
  j[μ+1] = k[μ+1] % j[μ];

  とすればよいので、σ のところは

  k = i;
  i = j;
  j = k % j;

  とすればよいです。 変数 k の宣言はブロックの先頭に記述します。(記述例2)
• for文を使って記述することもできます(記述例3)が、 普通はこのような場合にはfor文は使いません。 for文は、前の例のように for ( i = a; i <= b; i++ ) { … } のようになる ときに主に使います。

Cでの記述例1:

	int g(int m, int n)
	{
		if ( n == 0 ) {
			return m;
		} else {
			return g(n, m % n);
		}
	}

Cでの記述例2:

	int g(int m, int n)
	{
		int i;
		int j;
		int k;
		i = m;
		j = n;
		while ( j > 0 ) {
			k = i;
			i = j;
			j = k % j;
		}
		return i;
	}

Cでの記述例3:

	int g(int m, int n)
	{
		int i;
		int j;
		int k;
		for ( i = m, j = n; j > 0; k = i, i = j, j = k % j ) {
		}
		return i;
	}

例4 素数1

• i = 1 のときは、q[i] = T (このために q[1] も使う)、
• 2 ≦ i ≦ n - 1 のときは、 q[i] = (q[i-1] && (n % i != 0))、 となります。(&& は論理積) 実際には q[i-1] == F ならば q[i] 以後は全部 F となるので、 q[i-1] が T である間だけ調べればよいということになります。 また n が i で割り切れるときは n/i でも割り切れるので、 一方だけを調べればよいということになります。 これは i * i <= n という条件になるので、i ≦ n - 1 という条件は 不要になります。

今までの記法を使って

この手順をプログラミング言語Cで書いてみます。

• α、β が2変数の関数のとき、while(α; ξ, η; β) は 変数 x, y の宣言 x = ξ; y = η; while(α(ξ, η)) { σ } となります。 変数の宣言、変数の名前については上と同じです。 β = function(i, q; i + 1, q && (n % i != 0)) とすると σ のところは次と同じ意味になるようにします。

  i[μ+1] = i[μ] + 1;
  q[μ+1] = (q[μ] && (n[μ] % i[μ] != 0));

  前の代入文の左辺で添字がμ+1になった変数は、後の代入文の左辺でもμ+1に なっているようにします。この場合は

  q[μ+1] = (q[μ] && (n[μ] % i[μ] != 0));
  i[μ+1] = i[μ] + 1;

  とすればよいです。 真理値を表す型は bool (または bool が使えないときは int)とします。 真を表す値は true (または 1)、偽を表す値は false (または 0)とします。 (記述例1)
• for文を使って記述することもできます(記述例2)。

Cでの記述例1:

	bool p(int n)
	{
		int i;
		bool q;
		i = 2;
		q = true;
		while ( q && i * i <= n ) {
			q = (q && (n % i != 0));
			i++;
		}
		return q;
	}

Cでの記述例2:

	bool p(int n)
	{
		int i;
		bool q;
		q = true;
		for ( i = 2; q && i * i <= n; i++ ) {
			q = (q && (n % i != 0));
		}
		return q;
	}

例5 素数2

Cでの記述例:

	bool p(int n)
	{
		int i;
		bool q;
		q = true;
		for ( i = 2; q && i * i <= n; i++ ) {
			q = (q && (!p(i) || (n % i != 0)));
		}
		return q;
	}

Cでの記述例:

	bool s[1000];

	bool p(int n)
	{
		int i;
		bool q;
		q = true;
		for ( i = 2; q && i * i <= n; i++ ) {
			q = (q && (!s[i] || (n % i != 0)));
		}
		return q;
	}

	void find_prime(int n)
	{
		int i;
		for ( i = 2; i <= n; i++ ) {
			s[i] = p(i);
		}
	}