Programming C ex11

２次元座標を表す Point型の構造体変数 c と a に２次元平面上の座標が格納されているとき、点 c を中心に、点 a を反時計まわりに指定された角度だけ回転させた点 b の座標を求めたい。

角度はキーボードから「度」単位で入力するものとする。下記の２通りの関数を使ってそれぞれ点 b の座標を求めるプログラムを作成せよ。(提出ファイル名: prog01.c)

２通りの関数の説明は以下の通り。なお、どちらも第１引数には回転する角度をラジアン単位（double型）で与える。

回転角度、点 c（中心）、点 a（回転させる点）を引数として受け取り、回転後の点 b を返す関数
Point rotate1(double, Point, Point);
回転角度、点 c（中心）へのポインタ、回転させる点へのポインタを受け取り、回転後の点をそのポインタの指すアドレスに上書きする関数
void rotate2(double, Point *, Point *);

main側では、各関数の計算結果がそれぞれ Point型構造体 b1, b2 に入るようにして、これらをプログラムの最後で出力する。（当然 b1、b2 は同じ値になるはず）。なお点 c, a の内容は変更せず、rotate2関数を呼ぶ前に点 a を b2 にコピーしておき、この b2 を rotate2関数内で書き換えること。

平面座標上で、ある点を原点の回りに回転させた時に点がどこに移るかの計算は、ハンドアウトLec11-10,11 (p134)が参考になる。ただし、今回の問題では回転の中心が原点ではない指定された点 c であるため、少し工夫が必要である。

ハンドアウトLec11-10 (p134)のサンプルプログラムlec11-4.cなどでは回転の計算に三角関数sin、cosを用いている。また、これらの関数ではラジアンで表現した角度を引数として与える必要があるため、円周率πが定義されたマクロM_PIを用いてラジアンへの変換を行なっている。

これらの三角関数のプロトタイプ宣言やマクロM_PIの宣言はmath.hの中で行われているので、

#include <math.h>

としてmath.hをインクルードしておく必要がある。

さらに、三角関数やその他のmath.hに含まれる数学関数を使用したプログラムをコンパイルする場合は、コンパイル時に -lmオプションをつける必要がある。

% gcc prog01.c -lm

これらの数学関数についてはハンドアウトのプログラミング入門パートのp61、巻末の付録4にも情報がある。

#include <stdio.h>
#include <math.h>

typedef struct {
  double  x; /* x座標 */
  double  y; /* y座標 */
} Point;

Point rotate1(double, Point, Point);
void  rotate2(double, Point *, Point *);

int main()
{
  double rad, deg;
  Point c = {1.0, 1.0}, a = {2.0, 3.0}; /* 中心と回転対象の点 */
  Point b1, b2;         /* 結果を入れる構造体 */

  printf("回転角 [度] を入力してください\n");
  scanf("%lf", &deg);
  rad = deg*M_PI/180;
  printf("回転角 %f [deg] (%f [rad])\n", deg, rad);
  
  /*
   * ここに関数呼び出しおよび関連するコードを書く
   */

  printf("Center  : %f %f\n", c.x, c.y);
  printf("Point A : %f %f\n", a.x, a.y);
  printf("Point B (rotate1) : %f %f\n", b1.x, b1.y);   /* rotate1関数の結果を出力 */
  printf("Point B (rotate2) : %f %f\n", b2.x, b2.y);   /* rotate2関数の結果を出力 */
  return 0;
}

/*
 * ここにプロトタイプに合わせた rotate1関数の中身を書く
 */

/*
 * ここにプロトタイプに合わせた rotate2関数の中身を書く
 */

実行例

% gcc prog01.c -lm      （注：数学関数を使うので、-lm オプションを付けること）
% ./a.out
回転角 [度] を入力してください
90
回転角 90.000000 [deg] (1.570796 [rad])
Center  : 1.000000 1.000000
Point A : 2.000000 3.000000
Point B (rotate1) : -1.000000 2.000000
Point B (rotate2) : -1.000000 2.000000
% ./a.out
回転角 [度] を入力してください
45
回転角 45.000000 [deg] (0.785398 [rad])
Center  : 1.000000 1.000000
Point A : 2.000000 3.000000
Point B (rotate1) : 0.292893 3.121320
Point B (rotate2) : 0.292893 3.121320
%

演習問題２

問１と同様な関数を、さらに２つ作成する。プログラムは prog01.c を prog02.c にコピーしたものをベースにして作成するとよい。 (提出ファイル名: prog02.c)

２つの関数の説明とプロトタイプは以下の通り。ここでも、第１引数は回転角（ラジアン単位）である。

二つの点を Point型構造体の配列（２個の要素をもち、要素０が中心、要素１が回転させる点）として受け取り、回転後の点を返す関数
Point rotate3(double, Point *);
二つの点を Point型構造体の配列（３個の要素をもち、要素０が中心、要素１が回転させる点）として受け取り、回転後の点をその配列の要素２に代入する関数
void rotate4(double, Point *);

これらの関数を使用するために、main側では Point型構造体の配列二つ（一つは要素数２、もう一つは要素数３）を宣言し、それぞれ rotate3関数と rotate4関数への座標値の受け渡しに用いること。また、rotate3関数の戻り値を受け取るための Point型構造体の変数も宣言する必要がある。

実行例

% ./a.out
回転角 [度] を入力してください
90
回転角 90.000000 [deg] (1.570796 [rad])
Center  : 1.000000 1.000000
Point A : 2.000000 3.000000
Point B (rotate3) : -1.000000 2.000000
Point B (rotate4) : -1.000000 2.000000
% ./a.out
回転角 [度] を入力してください
45
回転角 45.000000 [deg] (0.785398 [rad])
Center  : 1.000000 1.000000
Point A : 2.000000 3.000000
Point B (rotate3) : 0.292893 3.121320
Point B (rotate4) : 0.292893 3.121320
%

演習問題３

前２項の和が次の項の値になる、「フィボナッチ数列」の値を関数の再帰を利用して求めてみよう。最初の２項の定義にいろいろな流儀があるが、ここでは以下のように定められるものとする。

a₀ = 0, a₁ = 1
a_n = a_n-1 + a_n-2 （n >= 2 のとき）

1. まず、漸化式そのままに従って a_n を求めてみる。以下の仕様に従ってプログラムを作成し、提出しなさい。 (提出ファイル名: prog03a.c)

main関数では、まず項数 n の入力を求め、その後 n を引数として関数 fibo を呼び出し、結果を表示する（実行例参照）。
関数 int fibo(int n) は、呼び出された回数を記憶しており、呼び出されるとまず呼ばれた回数と引数 n の値を出力する（実行例参照）。
呼び出された回数の記憶には、第２回講義で扱った、静的変数を使うと良い。
その後 fibo関数は、n が 0 のときに 0 を返し、1 のときは 1 を返し、2以上のときは漸化式に従って再帰的に自分自身を呼び出すことで a_n の値を求めて戻り値とする。

実行例（a₂=2 と a₆=13を求めた例）

% ./a.out
n = 2
called 1 times: n=2　　　（注：実装によっては n=2, 0, 1 の順になることもある）
called 2 times: n=1
called 3 times: n=0
fibo(2) = 1
% ./a.out
n = 6
called 1 times: n=6　　　（注：実装によっては n=6, 4, 2,... の順になることもある）
called 2 times: n=5
called 3 times: n=4
called 4 times: n=3
called 5 times: n=2
called 6 times: n=1
called 7 times: n=0
　（中略）
called 23 times: n=2
called 24 times: n=1
called 25 times: n=0
fibo(6) = 8

2. 上の方法では、プログラムは再帰を使ってシンプルに書けるが、a₆ を求めるのに関数を20回以上も呼び出している。しかも、同じ引数での呼び出しを何度も行っていて、無駄が多い。そこで、計算した結果を配列に格納しておき、すでに計算した値はもう一度計算せずに、配列に保存してあった値を用いる方法を追加したプログラムを作成し、提出しなさい。 (提出ファイル名: prog03b.c)

main関数の仕様

main関数では、まず項数 n の入力を求め、その後 n を引数として関数 fibo を呼び出し、結果を表示する（prog03a.cの内容を残しておいてそのまま使う）。
次に、動的メモリ割り当てによって n+1 個の要素をもつ配列を作成する。作成した配列の全要素に初期値 0 を代入しておく。
n と作成した配列を引数として、関数 fibo_array を呼び出し、結果を表示する（実行例参照）。

fibo_array関数の仕様

関数 int fibo_array(int n, int *a) は、第１引数に計算したい項の番号、第２引数には結果保存用の配列の先頭アドレスをとる。
前と同様、この関数は呼び出された回数を記憶しており、呼び出されるとまず呼ばれた回数と引数 n の値を出力する（実行例参照）。
次に、a[n] がすでに計算済みかどうかを調べ、計算済みなら前に計算して保存してあった値を返す。（配列 a の要素には初期値 0 が代入されていたことに注意すること）
計算済みでない場合、n が 0 のときは a[n] に 0 を代入してそれを返す。n が 1 のときは a[n] に 1 を代入してそれを返す。 n が 2 以上のときは漸化式に従って再帰的に自分自身を呼び出すことで a[n] の値を求め、a[n] を返す。

実行例

% ./a.out
n = 2
called 1 times: n=2　　　（注：実装によっては n=2, 0, 1 の順になることもある）
called 2 times: n=1
called 3 times: n=0
fibo(2) = 1
called 1 times: n=2
called 2 times: n=1
called 3 times: n=0
fibo_array(2) = 1
% ./a.out
n = 6
called 1 times: n=6　　　（注：実装によっては n=6, 4, 2,... の順になることもある）
　（中略）
called 25 times: n=0
fibo(6) = 8
called 1 times: n=6　　　（注：実装によっては n=6, 4, 2,... の順になることもある）
called 2 times: n=5
called 3 times: n=4
called 4 times: n=3
called 5 times: n=2
called 6 times: n=1
called 7 times: n=0
called 8 times: n=1
called 9 times: n=2
called 10 times: n=3
called 11 times: n=4
fibo_array(6) = 8

今度は、大体 2n-1 回くらいの関数呼び出しで済むはずである。

もちろん、関数の再帰呼び出しを使わずに、a[2]=a[1]+a[0], a[3]=a[2]+a[1], ..... と順に求めていけば n-1 回の計算で求まるので効率的であるが、ここでは再帰の実験のため、あえて上記のようなプログラムとした。

演習問題４

ハンドアウトLec11-23 (p137)にある経路探査のプログラムでは、最短経路数を計算した。
本問題では、「最短経路」という条件を外し、考えられるすべての経路を見つけ、実行例のように各経路を通った順番に番号をつけて表示し、その時の経路長（マス数）も表示せよ。
なお、同じマスは１度しか通らないとする。また、マス数は縦、横ともに最大１０とする。 (提出ファイル名: prog04.c)

アルゴリズムとしては、経路探索のためのマップ用構造体を用意し、それを再帰関数の引数にすることで、関数を呼び出すたびにマップの複製を生成し、ゴールにたどり着けたマップのみを表示するというものである。
すなわち、マスのサイズを横 msize、縦 nsize としたとき、 map[nsize-1][msize-1] をスタートし、map上で上下、左右に経路が空いているかを探索しながら関数を再帰呼び出しし、map[0][0] に到達した時点でゴールとなる。

そのための関数として、 routing(int m, int n, SMAP map) を作成し使用する。そのほか、map表示のために関数 mapprint を作成する。下記のテンプレートのコメントを参考に各関数を作成して下さい。

★ 　 ┌ ┐

└ ┐ │ │

　 └ ┘ ☆

ちなみに、例えば下記実行例のパターン37は左のような経路を示している。
なお、実行例の経路パターンは、プログラムによって出現の順番は変わるがパターン数は変わらず、4x3のマスの場合38個、5x3マスなら125個となる。

[実行例]

% ./a.out
マスのサイズを入力して下さい(msize, nsize):
4 3
パターン:1,　経路長:6
 6  .  .  . 
 5  .  .  . 
 4  3  2  1 

パターン:2,　経路長:8
 8  7  .  . 
 5  6  .  . 
 4  3  2  1 

（中略）

パターン:37,　経路長:10
10  .  4  3 
 9  8  5  2 
 .  7  6  1 

パターン:38,　経路長:10
10  9  4  3 
 .  8  5  2 
 .  7  6  1 

% ./a.out
マスのサイズを入力して下さい(msize, nsize):
5 3
パターン:1,　経路長:7
 7  .  .  .  . 
 6  .  .  .  . 
 5  4  3  2  1 

（中略）

パターン:125,　経路長:15
15 10  9  4  3 
14 11  8  5  2 
13 12  7  6  1 

%

[テンプレート]

#include <stdio.h>
#define N 10

typedef struct {
  int map[N][N];
  int step; /* 各経路上で通った順番を表す変数 */ 
  int msize, nsize;
} SMAP;

void routing(int, int, SMAP);
void mapprint(SMAP);

int pat = 0; /* ゴールに到達したパターン数を記録するための外部変数 */

int main()
{
  SMAP smap;
  int i, j;

  printf("マスのサイズを入力して下さい(msize, nsize):\n");
  scanf("%d%d", &smap.msize, &smap.nsize);

  /* smapの初期化 */
  for ( i=0 ; i<N ; i++ )
    for ( j=0 ; j<N ; j++ )
      smap.map[i][j] = 0;
  smap.step = 1;

  routing(smap.msize-1, smap.nsize-1, smap); /* msize-1, nsize-1から探索開始 */

  return 0;
}

void routing(int m, int n, SMAP smap)
{
 /* まず m, n がマップ（マス）外なら即 return */
  /* m, n が 0, 0 ならゴールなので、pat++し、マップを表示して、return */
  /* マップの m, n の位置が0でない（既に通った）なら、何もせずにreturn */
  /* マップの m, n の位置が0なら step（通ったマスの順番）を代入し、step++ */
  /* m, n の周辺４方向について、再度 routing を呼び出す */
  /* 注）一般に配列は[縦][横]で使いますが、 m, n はマスの
  　　　 横、縦を表すので、整合性に注意して下さい */

  /*************************
      ここを作成
  **************************/
}

void mapprint(SMAP smap)
{
  /*************************
      ここを作成
  **************************/
}

プログラミングＣ 第１１回 演習問題

プログラミングＣ
第１１回演習問題