プログラミングC
第11回 演習問題


A問題(50点)

演習問題1

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

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

2通りの関数の説明は以下の通り。なお、どちらも第1引数には 回転する角度をラジアン単位(double型)で与える。
  1. 回転角度、点 c(中心)、点 a(回転させる点)を引数として受け取り、 回転後の点 b を返す関数
    Point rotate1(double, Point, Point);
  2. 回転角度、点 c(中心)へのポインタ、回転させる点へのポインタを受け取り、 回転後の点をそのポインタの指すアドレスに上書きする関数
    void rotate2(double, Point *, Point *);

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

平面座標上で、ある点を原点の回りに回転させた時に点がどこに移るかの計算は、 ハンドアウトLec11-10,11 (p134)が参考になる。 ただし、今回の問題では回転の中心が原点ではない指定された点 c であるため、 少し工夫が必要である。
角度は、「度*π/180」でラジアン単位に変換できる。 円周率 π は math.h 内でマクロ M_PI として定義されているので、本プログラムではこれを使っている。 また、この問題では数学関数を使うので、コンパイル時に -lm オプションをつけること。
#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, 0.0}, a = {3.0, 2.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("rotate1 : %f %f\n", b1.x, b1.y);   /* 関数1の結果を出力 */
  printf("rotate2 : %f %f\n", b2.x, b2.y);   /* 関数2の結果を出力 */
  return 0;
}

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

/*
 * ここにプロトタイプに合わせた rotate2関数の中身を書く
 */
実行例
% gcc prog01.c -lm      (注:数学関数を使うので、-lm オプションを付けること)
% ./a.out
回転角 [度] を入力してください
90
回転角 90.000000 [deg] (1.570796 [rad])
Center  : 1.000000 0.000000
Point A : 3.000000 2.000000
rotate1 : -1.000000 2.000000
rotate2 : -1.000000 2.000000
% ./a.out
回転角 [度] を入力してください
45
回転角 45.000000 [deg] (0.785398 [rad])
Center  : 1.000000 0.000000
Point A : 3.000000 2.000000
rotate1 : 1.000000 2.828427
rotate2 : 1.000000 2.828427
%

B問題(50点)

演習問題2

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

2つの関数の説明とプロトタイプは以下の通り。 ここでも、第1引数は回転角(ラジアン単位)である。
  1. 二つの点を Point型構造体の配列(2個の要素をもち、 要素0が中心、要素1が回転させる点)として受け取り、回転後の点を返す関数
    Point rotate3(double, Point *);
  2. 二つの点を Point型構造体の配列(3個の要素をもち、 要素0が中心、要素1が回転させる点)として受け取り、回転後の点を その配列の要素2に代入する関数
    void rotate4(double, Point *);

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

実行例

% ./a.out
回転角 [度] を入力してください
90
回転角 90.000000 [deg] (1.570796 [rad])
Center  : 1.000000 0.000000
Point A : 3.000000 2.000000
rotate3 : -1.000000 2.000000
rotate4 : -1.000000 2.000000
% ./a.out
回転角 [度] を入力してください
225
回転角 225.000000 [deg] (3.926991 [rad])
Center  : 1.000000 0.000000
Point A : 3.000000 2.000000
rotate3 : 1.000000 -2.828427
rotate4 : 1.000000 -2.828427
%

演習問題3

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

a0 = 1,   a1 = 1
an = an-1 + an-2 (n >= 2 のとき)

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

実行例(a2=2 と a6=13を求めた例)
% ./a.out
n = 2
called 1 times: n=2   (注:実装によっては n=2, 0, 1 の順になることもある)
called 2 times: n=1
called 3 times: n=0
fibonacci(2) = 2
% ./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
fibonacci(6) = 13

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

main関数の仕様 fibonacci_array関数の仕様

実行例
% ./a.out
n = 2
called 1 times: n=2   (注:実装によっては n=2, 0, 1 の順になることもある)
called 2 times: n=1
called 3 times: n=0
fibonacci(2) = 2
% ./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 8 times: n=1
called 9 times: n=2
called 10 times: n=3
called 11 times: n=4
fibonacci(6) = 13

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

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

Extra問題

演習問題4

ハンドアウトLec11-23 (p137)にある経路探査のプログラムでは、最短経路数を計算した。
本問題では、「最短経路」という条件を外し、考えられるすべての経路を見つけ、 実行例のように各経路を通った順番に番号をつけて表示し、その時の経路長(マス数) も表示せよ。
なお、同じマスは1度しか通らないとする。また、マス数は縦、横ともに最大10とする。 (提出ファイル名: 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 の周辺4方向について、再度 routing を呼び出す */
  /* 注)一般に配列は[縦][横]で使いますが、 m, n はマスの
      横、縦を表すので、整合性に注意して下さい */

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

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

演習問題5

(提出ファイル名: prog05.c)

文字列の後方一致検索を行う。例えば

nothing
submit
string
という3つの文字列を「ing」と言う検索ワードで後方検索すると、
nothing
string
という2つの文字列が該当する。

このような検索を行うために、同じ長さの二つの文字列が一致しているか調べる関数 rsrch() を考える。関数 rsrch() の要件は以下の通りである。
  1. 引数は二つの文字列(文字型ポインタ)とする。 第一引数が検索される側、第二引数が検索する文字列である。
  2. 引数に与える二つの文字列は同じ長さとする。つまり、元の文字列が "submit"、 検索文字列が "ing" の時、第一引数にはうしろ3文字の文字列 "mit"、 第二引数には "ing" を入れて呼ばれる。
  3. 戻り値の型は int型とする。値は、二つの文字列が一致したら 1、 一致しない時は 0 となるようにする(下記の仕様を参照)。
  4. 再帰的に使用する関数として作成する。
  5. 二つのポインタが指す文字が異なる場合は即、0 を返す。 同じ場合は、一文字先を引数にして再帰的に関数を呼ぶ。
  6. ヌル文字まで到達したら 1 を返す。
それではこの関数を用いて、/usr/share/dict/words という辞書ファイル中のすべての 単語から、入力された文字列と後方一致する単語を表示するプログラムを作成せよ。 プログラムの仕様は以下の通りである。
  1. テキストファイル /usr/share/dict/words を開く。 なお、fopen関数でファイルを開く際に、ファイル名として名前だけ(words)ではなく ファイルのフルパス( /usr/share/dict/words )を指定すれば、 カレントディレクトリにないファイルにもアクセスできるので、 自分のディレクトリにファイルをコピーせずに読み込めるはずである。
  2. 検索する文字列をキーボードから入力する。
  3. 辞書ファイルから一単語ずつ読み込み、以下の処理を行う。 なお、以下では検索される側の文字列を文字列A、検索する側を文字列Bと呼ぶ。
    1. 文字列 A, B の長さを LA, LB とすると、LA < LB の場合は、 明らかに一致しないので関数を呼ぶ必要すら無い。
    2. 上記以外の時は関数を呼ぶが、文字列を同じ長さにするため、 文字列 A の最後の LB 文字のみの文字列を文字列 C とすると、 rsrch( 文字列C, 文字列B ) のように関数を呼ぶ。 (実際に文字列 C を作らなくても、ポインタ演算のみで実現可能である)
    3. 後方一致した場合にはディスプレイに表示する。その際、一致した個数も数えておく。
  4. 辞書ファイルの終端に達したら、最後に一致した個数を表示する。
  5. なお、strcmp 等の文字列比較関数は使用しないこと。(strlen は使って構わない)
辞書ファイルは一行に一単語が書かれているテキストファイルで、最も長い単語は 40~50文字程度あるので、十分余裕を持って文字配列を宣言すること。
近年のシステム更新で辞書ファイルが大きくなったため、全単語を一気に大きな二次元配列に読み込む ことはできない。そのため、ファイルから一単語読み込むごとに文字列の比較を行う。
なお、辞書ファイルの内容は CentOS マシンと Mac で異なるので、実行結果も表示される数が異なる。 (実行例は CentOS の場合)

実行結果

% ./a.out
Enter string to search for : out
    1 : about
    2 : acting-out
    
  (中略)

  444 : wung-out
  445 : x-out
Total 445 words matched [out]
% ./a.out
Enter string to search for : pepper
    1 : bepepper
    2 : chilipepper
    3 : overpepper
    4 : pepper
    5 : salt-and-pepper
Total 5 words matched [pepper]
%