A問題(50点)
2次元座標を表す Point型の構造体変数 center と a に2次元平面上の座標が格納されているとき、 点 center を中心に、点 a を反時計まわりに指定された角度だけ回転させた点 b の座標を求めたい。
角度はキーボードから「度」単位で入力するものとする。 下記の2通りの関数を使ってそれぞれ点 b の座標を求めるプログラム を作成せよ。(提出ファイル名: prog01.c)
2通りの関数の説明は以下の通り。なお、どちらも第1引数には 回転する角度をラジアン単位(double型)で与える。Point rotate1(double, Point, Point);
void rotate2(double, Point *, Point *);
main側では、各関数の計算結果がそれぞれ Point型構造体 b1, b2 に入るようにして、 これらをプログラムの最後で出力する。(当然 b1、b2 は同じ値になるはず)。 なお点 center, a の内容は変更せず、rotate2関数を呼ぶ前に点 a を b2 にコピーしておき、 この b2 を rotate2関数内で書き換えること。
ハンドアウトLec11-10 (p135)のサンプルプログラム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 center = {2.0, 1.0}, a = {4.0, 2.0}; /* 中心と回転対象の点 */
Point b1, b2; /* 結果を入れる構造体 */
printf("回転角 [度] を入力してください\n");
scanf("%lf", °);
rad = deg*M_PI/180;
printf("回転角 %f [deg] (%f [rad])\n", deg, rad);
/*
* ここに関数呼び出しおよび関連するコードを書く
*/
printf("Center : %f %f\n", center.x, center.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 : 2.000000 1.000000 Point A : 4.000000 2.000000 Point B (rotate1) : 1.000000 3.000000 Point B (rotate2) : 1.000000 3.000000 % ./a.out 回転角 [度] を入力してください 45 回転角 45.000000 [deg] (0.785398 [rad]) Center : 2.000000 1.000000 Point A : 4.000000 2.000000 Point B (rotate1) : 2.707107 3.121320 Point B (rotate2) : 2.707107 3.121320 %
B問題(50点)
問1と同様な関数を、さらに2つ作成する。 プログラムは prog01.c を prog02.c にコピーしたものをベースにして作成するとよい。 (提出ファイル名: prog02.c)
2つの関数の説明とプロトタイプは以下の通り。 ここでも、第1引数は回転角(ラジアン単位)である。Point rotate3(double, Point *);
void rotate4(double, Point *);
これらの関数を使用するために、main側では Point型構造体の配列二つ(一つは要素数2、もう一つは要素数3) を宣言し、それぞれ rotate3関数と rotate4関数への座標値の受け渡しに用いること。 また、rotate3関数の戻り値を受け取るための Point型構造体の変数も宣言する必要がある。
実行例
% ./a.out 回転角 [度] を入力してください 90 回転角 90.000000 [deg] (1.570796 [rad]) Center : 2.000000 1.000000 Point A : 4.000000 2.000000 Point B (rotate3) : 1.000000 3.000000 Point B (rotate4) : 1.000000 3.000000 % ./a.out 回転角 [度] を入力してください 45 回転角 45.000000 [deg] (0.785398 [rad]) Center : 2.000000 1.000000 Point A : 4.000000 2.000000 Point B (rotate3) : 2.707107 3.121320 Point B (rotate4) : 2.707107 3.121320 %
前2項の和が次の項の値になる、「フィボナッチ数列」の値を関数の再帰を利用して求めてみよう。 最初の2項の定義にいろいろな流儀があるが、ここでは以下のように定められるものとする。
a0 = 0, a1 = 1
1. まず、漸化式そのままに従って an を求めてみる。以下の仕様に従ってプログラムを作成し、
提出しなさい。
(提出ファイル名: prog03a.c)
fib_recursive
を呼び出し、結果を表示する(実行例参照)。
int fib_recursive(int n) は、呼び出された回数を記憶しており、呼び出されると
まず呼ばれた回数と引数 n の値を出力する(実行例参照)。
% ./a.out n = 2 called 1 times: n=2 (注:実装によっては n=2, 0, 1 の順になることもある) called 2 times: n=1 called 3 times: n=0 fib_recursive(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 fib_recursive(6) = 8
2. 上の方法では、プログラムは再帰を使ってシンプルに書けるが、a6 を求めるのに関数を20回以上も呼び出している。 しかも、同じ引数での呼び出しを何度も行っていて、無駄が多い。 そこで、計算した結果を配列に格納しておき、すでに計算した値はもう一度計算せずに、 配列に保存してあった値を用いる方法を追加したプログラムを作成し、提出しなさい。 (提出ファイル名: prog03b.c)
main関数の仕様fib_recursive
を呼び出し、結果を表示する(prog03a.cの内容を残しておいてそのまま使う)。
fib_memo
を呼び出し、結果を表示する(実行例参照)。
free() 関数を用いて解放すること。
int fib_memo(int n, int *a) は、第1引数に計算したい項の番号、
第2引数には結果保存用の配列の先頭アドレスをとる。
% ./a.out n = 2 called 1 times: n=2 (注:実装によっては n=2, 0, 1 の順になることもある) called 2 times: n=1 called 3 times: n=0 fib_recursive(2) = 1 called 1 times: n=2 called 2 times: n=1 called 3 times: n=0 fib_memo(2) = 1 % ./a.out n = 6 called 1 times: n=6 (注:実装によっては n=6, 4, 2,... の順になることもある) (中略) called 25 times: n=0 fib_recursive(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 fib_memo(6) = 8
今度は、大体 2n-1 回くらいの関数呼び出しで済むはずである。
Extra問題
ハンドアウト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 を作成する。
下記のテンプレートのコメントを参考に各関数を作成して下さい。
| ★ | ┌ | ┐ | |
| └ | ┐ | │ | │ |
| └ | ┘ | ☆ |
% ./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)
{
/*************************
ここを作成
**************************/
}
文字列の後方一致検索を行う。例えば
nothing submit stringという3つの文字列を「ing」と言う検索ワードで後方検索すると、
nothing stringという2つの文字列が該当する。 このような検索を行うために、同じ長さの二つの文字列が一致しているか調べる関数
rsrch() を考える。関数 rsrch() の要件は以下の通りである。
実行結果
% ./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]
%