Ex13

From Prog0

Jump to: navigation, search

演習第13回

Contents

演習問題

主な内容

  • スタック
  • キュー
  • 数値計算と誤差

以下の問題を解いて期限内に解答を提出してください。

なお、一人ひとりの授業理解度を確認することを目的として、口頭試問形式による採点を行います。
採点対象の問題が解けたら手を挙げ、教員またはTA/SAを呼んでください。口頭で解答の内容を説明してもらいます。
正しく説明できた場合は点数を付け、説明が不十分な場合はやり直してもらいます（間違えても減点はしません）。
今回の口頭採点の対象は A-2 の1問のみです。
(口頭採点の対象も、その他の問題と同様、menuコマンドで提出してください。)

出席確認

演習時間中に出席確認をLMS上の「演習出欠」で行ってください。出席確認用のパスワードは演習時間のどこかのタイミングで提示されます。


A問題

A-1 外部変数の利用

ファイル名: ex13a1.c

下記に示すのは、外部変数を用いて2つの関数function1とfunction2が何回呼び出されたのかを記録し、表示するプログラムである。無限ループの中でどちらの関数を呼び出すのかを入力させ、それに応じて関数の呼び出しを行う。関数function1とfunction2は、自身が何回呼び出されたのかの回数と、二つの関数の合計呼び出し回数を内部で加算する。

コメントや_____で示された未完成の部分を補って、実行例通りに動作するよう、プログラムを完成させよ。なお、指定箇所以外は変更してはならない。

プログラム 

 
#include <stdio.h>

/* ここに必要な宣言を行うこと */

int main() {
    int n;
    while(1) {
        printf("Which function will you call? [1 or 2 (0: Stop)]: ");
        scanf("%d", &n);
        if ( n == 0 ) break;
        switch(n) {
            /* ここでnの値に応じた関数の呼び出しを行うこと */
            /* switch-case構文に関わる処理と、関数呼び出し処理以外は書いてはならない */
            /* つまり、呼び出し回数の加算をここで行ってはならない */
        }
  }
  printf("Function 1 was called %d times.\n", count1);
  printf("Function 2 was called %d times.\n", count2);
  printf("Functions 1 and 2 were called %d times in total.\n", countTotal);
  
  return 0;
}

_____ function1(_____) {
    printf("Function 1 was called.\n");
    /* ここで関数呼び出し回数の加算を行うこと */
}

_____ function2(_____) {
    printf("Function 2 was called.\n");
    /* ここで関数呼び出し回数の加算を行うこと */
}

実行例 

% ./a.out
Which function will you call? [1 or 2 (0: Stop)]: 1
Function 1 was called.
Which function will you call? [1 or 2 (0: Stop)]: 2
Function 2 was called.
Which function will you call? [1 or 2 (0: Stop)]: 2
Function 2 was called.
Which function will you call? [1 or 2 (0: Stop)]: 0
Function 1 was called 1 times.
Function 2 was called 2 times.
Functions 1 and 2 were called 3 times in total.
%

A-2 (口頭試問) リングバッファを使ったキューのプログラム

ファイル名: ex13a2.c

1. ハンドアウトの例題 lec13-2b.c を自分のディレクトリにコピーし、実行して動作を理解してください。 

% cp /home/course/prog0/public_html/2026/lec/source/lec13-2b.c .

2. これをもとに、以下のような変更を加えて、実行例のように動作するプログラムを書いてください。

  • キューのサイズを定義するマクロQSIZEの値を5にする（キューのサイズを小さくし、キューがいっぱいかどうかの確認を容易にするため）
  • キューがいっぱいかどうかをチェックする関数 isFull() を作成する。
    • 引数は無し。戻り値は int型。
    • キューがいっぱいなら 1 を、空きがあれば 0 を返す。
  • キューが空かどうかをチェックする関数 isEmpty() を作成する。
    • 引数は無し。戻り値は int型。
    • キューが空なら 1 を、データが一つでもあれば 0 を返す。
  • enqueue()関数内のキューがいっぱいでないことのチェックと、dequeue関数内のキューが空でないことのチェックを、作成した isFull()関数、isEmpty()関数を使う形に変更する。
    • これに伴い、不要な変数を減らす等の変更をしてもよい。

[実行例] 

% ./a.out
input>> 2
  [Queue] 2
input>> 4
  [Queue] 2 4
input>> 6
  [Queue] 2 4 6
input>> 8
  [Queue] 2 4 6 8
input>> 10
Queue overflow!
% ./a.out
input>> 2
  [Queue] 2
input>> 4
  [Queue] 2 4
input>> 6
  [Queue] 2 4 6
input>> 0
Data: 2
  [Queue] 4 6 
input>> 0
Data: 4
  [Queue] 6 
input>> 0
Data: 6
  [Queue] 
input>> 0
Queue is empty!
%

B問題

B-1 検索機能つきスタックのプログラム

ファイル名: ex13b1.c

ハンドアウトの例題 lec13-1b.c を参考に、以下のような仕様で、スタックの動作を試すプログラムを書きなさい。

  • スタックに格納するデータは int型で、最大100個まで格納できることとする（lec13-1b.cに実装済み）
  • スタックに対する操作はキーボードから整数を入力することで指示する。スタックの操作は無限ループで繰り返す。
    • 正の整数 が入力されたら、push関数（実装済み）を呼び出して入力値をスタックに挿入する。
    • 負の整数 が入力されたら、pop関数（実装済み）を呼び出してスタックからデータを一つ取り出して表示する。
    • 0 が入力されたら、detect関数（新規に実装すること）を呼び出してスタックの中を検索できるようにする。detect関数の仕様は以下の通りとする。
      • スタックが空かどうかを調べ、空の場合はpop関数と同様の動作を行う。空ではない場合、以下の処理を行う。
      • 検索したい値（検索値）の入力を促す。
      • 入力された検索値がスタック中に存在するか調べ、存在している場合はスタック中の位置を含めてメッセージを表示する。この時、検索値がスタック中に二つ以上存在する可能性は考慮する必要はない。
      • 検索値がスタック中に存在しない場合、その旨のメッセージを表示し、プログラムを終了する。
  • 次のいずれかの場合はエラーとなり、プログラムを終了する。
    • pop()時にスタックが空（lec13-1b.cに実装済み）
    • push()時にスタックがいっぱい（lec13-1b.cに実装済み）
    • 検索時に検索値がスタック中に存在しない（実行例参照）


実行例 

% ./a.out
--- Input [+] to push, [-] to pop, [0] to detect --- >> 10
  [Stack] 10

--- Input [+] to push, [-] to pop, [0] to detect --- >> 20
  [Stack] 10 20

--- Input [+] to push, [-] to pop, [0] to detect --- >> 30
  [Stack] 10 20 30

--- Input [+] to push, [-] to pop, [0] to detect --- >> 40
  [Stack] 10 20 30 40

--- Input [+] to push, [-] to pop, [0] to detect --- >> -8
Data: 40
  [Stack] 10 20 30

--- Input [+] to push, [-] to pop, [0] to detect --- >> -9
Data: 30
  [Stack] 10 20

--- Input [+] to push, [-] to pop, [0] to detect --- >> 0
Detect what ? :20
20 exists at stack[1]
  [Stack] 10 20

--- Input [+] to push, [-] to pop, [0] to detect --- >> 0
Detect what ? :44
44 not in stack!
%

B-2 キュー：別の実装法

ファイル名: ex13b2.c

ハンドアウトでは head, tail という変数を用いてキューのデータの位置を管理していた。 ここでは、変数 tail を使わず、代わりに格納されているデータの数を変数としてキューを管理するプログラムを作ってみよう。 このやり方では、キューが空の状態とキューがいっぱいの状態は区別できるので、配列をすべて使い切るようにプログラムを書けるはずである。

仕様は以下の通り。

  • キューに格納するデータは int型で、配列サイズは 5 とする。
  • キューに格納されたデータの先頭位置を表す変数 head と、格納されているデータ数を表す変数 dnum を外部変数として宣言する。変数 tail は使わない。
  • 実行時は、キーボードから 0 が入力された時はデータを取り出して表示し、 0 以外の整数が入力されたらその値をキューに追加する。これを無限ループで繰り返す。（ハンドアウトと同様）
  • データ追加／取り出しの処理後に毎回、キューの内容をすべて 1行で表示する。（実行例参照）


プログラム例 

#include <stdio.h>
#include <stdlib.h>

#define QSIZE 5

void enqueue(int);
int dequeue(void);

int queue[QSIZE];
int head = 0;
int dnum = 0;   /* データ数 */

int main(){
  int data, status, i; /* もし必要なら変数宣言を追加してもよい */

  while (1) {
    printf("input>> ");
    status = scanf("%d", &data);
    if (status != 1) break;
    if (data == 0) printf("  Data: %d\n", dequeue() );
    else enqueue(data);

    /* ここキューの内容表示処理を追加すること（変数tailは使わない） */
  }
 return 0;
}

/* 続けて、問題に合わせて修正した enqueue関数、dequeue関数を書く */

実行例（配列サイズが 5 で、5つデータを格納していることに注意） 

% ./a.out
input>> 1
  [Queue] 1
input>> 3
  [Queue] 1 3
input>> 5
  [Queue] 1 3 5
input>> 7
  [Queue] 1 3 5 7
input>> 9
  [Queue] 1 3 5 7 9
input>> 0
  Data: 1
  [Queue] 3 5 7 9
input>> 0
  Data: 3
  [Queue] 5 7 9
input>> 2
  [Queue] 5 7 9 2
input>> 4
  [Queue] 5 7 9 2 4
input>> 6
Queue overflow!
%

ポイント：

  • データ数が変数になっているので、キューが空 or いっぱいの判定は簡単にできるはず。
  • enqueue関数で、追加したデータを配列のどの位置に入れるべきかは、きちんと計算する必要がある。配列サイズを越えたら添え字を 0 に戻す操作は if 文で実現しても良いが、% 演算子をうまく使うとシンプルに書ける。
  • キューの内容をすべて表示する部分では、ループを使うとともに、配列の添え字を適切に決める必要がある。これも if 文を使って書いてもよいし、% 演算子を使って書いてもよい。


Extra問題

E-1 空気抵抗を考慮した落下運動

ファイル名: ex13e1.c

ハンドアウトでは、質点の自由落下の問題の数値計算法を扱った。

現実には空気抵抗によって減速されるので、落下速度はもっと遅くなりうる。速度が遅く小さい物体の場合には「粘性抵抗」と呼ばれる速度の大きさに比例した抵抗力がかかり、速度が速く大きい物体には「慣性抵抗」と呼ばれる速度の2乗に比例した抵抗力がかかる。ここでは、粘性抵抗を考慮した場合の落下運動を計算してみよう。

速度 v でゆっくり動いている半径 a の球に働く粘性抵抗力は、速度と逆の向きに

File:Ex13d2_StokesLaw.png‎

となる。ここで、空気の粘性係数 File:Ex13d2_ViscosityAir.png‎ （単位はSI単位系で、長さ m, 質量 kg, 時間 s 等である）

したがって、重力と空気抵抗を考えた時の運動方程式は、質量を m 、重力加速度を g として

File:Ex13d2_EqMotion.png‎

となる。

では、上記の空気抵抗を考慮した運動方程式を用いて、球状の物体が重力で落下する時に時間、位置、速度がどのように変化していくか計算するプログラムを以下の仕様で作成しなさい。

  1. 下にプログラムの一部（キーボード入力までの部分）を示すので、これに必要なコードを追加していくと良い。重力加速度と粘性係数はマクロで与えてある。また、計算タイムステップ dt （ハンドアウトの変数 h に対応）は小さくしないと正常に計算が行えないことがあるので、0.00001 にしてある。
  2. 初期状態の速度（m/s）、位置（m）、計算を行う時間（秒）、物体の半径（m）、質量（kg）はキーボードからの入力で与える（実行例参照）。
  3. 時間変化の計算は、ハンドアウトと同様に、オイラー法を使った繰り返し計算を行えばよい。速度を計算する部分を上記の運動方程式に合わせて修正すること。
  4. ハンドアウトと異なり、時刻 t がキーボードから入力した秒数に達したら終了とする。
  5. タイムステップが小さいので、毎回結果表示するのでは出力が多すぎる。そこで、出力すべき時間間隔もキーボード入力で与える（実行例参照）。出力は毎回ではなく、指定した時間が経過するごとに時刻、位置、速度を1行に出力する。（浮動小数点数の丸め誤差を考慮しないと思い通りの出力にならない可能性があるので注意）

なお、物体としては、半径 0.001 mm～0.05 mm (1 x 10-6 ～ 5 x 10-5 m) 程度の水滴（雲や霧の粒くらい）を想定する （これ以上重くなると、慣性抵抗も考慮する必要が出てくる）。 実行時に質量を入力する必要があるが、水滴の質量は、半径 0.001 mm で 4.2 x 10-15 kg、半径 0.01 mm では 4.2 x 10-12 kg、 半径 0.05 mm では 0.52 x 10-9 kg である。

[プログラム例] 

#include <stdio.h>

#define G  9.80     /* 重力加速度 */
#define VISC 1.8e-5 /* 空気の粘性係数 */

int main (){
  double v, x, t=0.0, tmax, a, m, c_m;
  double dt=0.00001;     /* タイムステップの値（十分小さくとること） */
  double dtp;
  double pi = 3.14159265358979; /* 円周率 */
  /* 必要な変数宣言を追加すること */


  printf("初期状態の速度、位置と、計算する時間を入力してください\n");
  scanf( "%lg%lg%lg", &v, &x, &tmax );
  printf("物体の半径と質量を入力してください\n");
  scanf( "%lg%lg", &a, &m );

  printf("出力の間隔を入力してください: ");
  scanf("%lg", &dtp);
  if (dtp < dt) dtp = dt; /* おかしな入力は修正 */

  ..... 続きを作成 .....

[実行例] 

% ./a.out
初期状態の速度、位置と、計算する時間を入力してください
0 0 1
物体の半径と質量を入力してください
5e-5 0.52e-9             ←半径 0.05 mm の例
出力の間隔を入力してください: 0.02
    時間     位置     速度
  0.0000   0.0000   0.0000
  0.0200  -0.0016  -0.1440
  0.0400  -0.0053  -0.2189
  0.0600  -0.0101  -0.2580
  0.0800  -0.0155  -0.2783
  0.1000  -0.0212  -0.2889
  ...
  0.9600  -0.2792  -0.3004
  0.9800  -0.2852  -0.3004
  1.0000  -0.2912  -0.3004     ←下向き約 30 cm/s で落下
% ./a.out
初期状態の速度、位置と、計算する時間を入力してください
0 0 0.5
物体の半径と質量を入力してください
1e-5 4.2e-12             ←半径 0.01 mm の例
出力の間隔を入力してください: 0.05
    時間     位置     速度
  0.0000   0.0000   0.0000
  0.0500  -0.0006  -0.0121
  0.1000  -0.0012  -0.0121
  0.1500  -0.0018  -0.0121
  0.2000  -0.0024  -0.0121
  0.2500  -0.0030  -0.0121
  0.3000  -0.0036  -0.0121
  0.3500  -0.0042  -0.0121
  0.4000  -0.0048  -0.0121
  0.4500  -0.0054  -0.0121
  0.5000  -0.0061  -0.0121     ←下向き約 1.2 cm/s で落下
%

この結果から、粒子が小さくなるにつれて落下速度は極めてゆっくりになり、しかもごく短時間で重力と空気抵抗が釣り合って速度が一定になることが分かる。 空気抵抗のため、雲をつくっている水滴や、細かい塵、黄砂、PM2.5のような非常に小さく軽い物体は、空気中ではなかなか落ちてこない。

課題提出上の注意事項

解答ファイルはmenuコマンドを使って提出してください。以下のようにmenuコマンドを実行し、表示されるメッセージに沿って操作すること。 

% ~prog0/bin/menu

menuコマンドは、解答ファイルが ~/Prog0/Ex## のディレクトリに指定されたファイル名で置かれているものとして処理します。正常に提出された場合は ○ が、何らかのエラーが生じた場合は × が表示されます。

解答の提出期間は以下のとおりです。

問題提出受付開始提出〆切
A問題 演習日の6日前の午後9時演習終了時刻
B, Extra問題 演習日の6日前の午後9時演習日の6日後の午後9時

提出は〆切前であれば何度でもやり直すことができます。再提出すると、前に提出したファイルは新しい内容で上書きされます。

Retrieved from "http://localhost../../../../articles/e/x/1/Ex13.html"
Personal tools