JAVA

Java.アニメーション.シミュレーション

これは情報科学実験IB2（Javaによるアニメーションとシミュレーション）のテキストです。

この中には次の３種類の情報が含まれている。

（１）基礎知識：提出課題作成に必要な基礎知識をまとめた資料

（２）提出課題：期限限定で、必ず提出しなくてはいけない課題

　　（提出時にはインタビューを行う、その際の質問項目も記載してある）

（３）自由提出課題：提出の義務はないが、提出した方がよい課題

以下の記述では、まず課題を示し、その後に課題を完成するのに必要な基礎知識や参考プログラムを示す。

----------------------------------------------------------------------------------

提出課題１：

目的１：繰り返し命令の復習

目的２：動画がどのようにして実現されるのかを学ぶ

提出期限：１回目の授業

内容：円を２つ表示し、１つの円は左から右へ、もう１つの円は上から下へ、２つ同時に移動するプログラムを作成せよ。

インタビュー内容：

質問例１：円が大きく膨らんで破裂するようにするにはどこを変える？

質問例２：円がsinカーブを描いて左から右に移動するようにするには？

質問例３：円が円を描いて移動するようにするには？（ヒント：sinとcosを使う）

質問例４：右へ移動する円が右端で消え、左端から現れるようにするには？

質問例５：円が左右の壁で跳ね返り、往復運動するようにするには？

基礎知識１.1：アニメーション

アニメーションは、１つの画像を表示し、少々時間を置いて近くに同じ画像を表示する、という操作を繰り返すと、画像が動いているように見える。プログラムとしては、次の様に、一つの画像を表示し、少々休んでは（眼に焼きつけては）、消す、という操作を繰り返すことになる。

for( int i=0; i<100; i++) {

　背景を描いて画像を消す；

描画命令；

　少々休み；

　少し移動；

｝

基礎知識1.２：JAVAによるアニメーション

Javaで上の描画プログラムを作成する場合、少々休む命令はsleep()という命令で実現できる。しかし、描画を一つだけのプロセス（Javaではスレッドと呼ばれ、普通Javaプログラムは走るとき最初１つのスレッドが走る）で実行しようとすると、sleep()の際などJavaのイベントの管理などができなくなる。そこで主スレッドの他に別のスレッドを発生させ、そこで描画を行う。スレッドを使うプログラムの構造と、そこで描画を行うプログラムの構成は以下のようになる。以下の描画部に描画プログラムを書く。

public class Animation extends Applet implements Runnable

{ Thread th; //スレッド宣言

public void init() {

th= new Thread(this); //

th.start(); //スレッド起動

}

public void run() {

try {

for ( int i=0; i<1000; i++) { //描画繰り返し

//-------------------------------

//　ここに描画プログラム

//-------------------------------

Thread.sleep(1000); //１秒休み

}

catch(InterruptedException e) {

}

public void paint(Graphics g) {

//　上のThread.sleep(1000)の前にrepaint();を入れ、

//ここに描画プログラムを書く場合もある

}

描画命令は多数用意されている。本実験ではしばしば円を描くが、その命令は

drawOval(x,y,w,h); である。ここで

x,y　は楕円に外接する四角形の左上の座標、

w,h は楕円の幅と高さである。

ただし、描画のx,y座標は画面の左上隅が（0,0）で右方向がｘ軸の正方向、下方向がｙ軸の正方向である。

上記のプログラムの構造を基に描画を実現する方法は２つ考えられる。第一の方法は描画部をpaint()の中に書いておき、repaint()の繰り返しで画像を動かす方法である。第２の方法はrun()の中で描画を行う。この場合、描画の繰り返しのたびに、描画した画像を背景で消す作業が必要になる。以下の２つのプログラムの例を示す。

（１）paint()の中に描画命令を書くプログラム

import java.awt.*;

import java.applet.*;

public class H9 extends Applet implements Runnable {

Thread th=null;

int x=10;

public void init(){

Thread th;

th= new Thread(this);

th.start();

}

public void paint(Graphics g) {

g.drawOval(x+20,20,10,10);//ここで描画

}

public void run() {

try{

for(int j=0; j<5; j++)

{ x=x+10;

repaint();

th.sleep(1000);

}

} catch (InterruptedException e){}

}

（２）背景による消画を行うプログラム

import java.applet.*;

import java.awt.*;

public class E4 extends Applet implements Runnable

{

Graphics g;

Thread th=null;

Image back; //背景用

public void init()

{

g=getGraphics();

Graphics gb; //ここから背景用

back=createImage(200,200);//背景作成

gb=back.getGraphics(); //背景グラフックス

gb.setColor(Color.blue); //背景色

gb.fillRect(0,0,199,199); //背景サイズ

th=new Thread(this);

th.start();

}

public void run()

{

int i;

try

{

for(i=0; i<10; i++)

{

g.drawImage(back,0,0,this); //背景による消画

g.drawOval(i*20,30,10,10);　ここが描画部

th.sleep(1000);

}

catch(InterruptedException e)

{}

}

画面上に（複数の）物体（丸や画像）を動かすいくつかの方法を示す。上の実験では以下の1.5までの知識を使えばプログラムを作成できる。

参考プログラム

プログラム1.1　

"Hello"と表示するアプレット。

スレッドは使っていない。

import java.applet.Applet;

import java.awt.Graphics;

public class e1 extends Applet

{

public void paint(Graphics g)

{

g.drawString("Hello",50,40);

}

プログラム1.2　

１つの丸の移動（丸の移動軌跡は消さないで残す）

スレッドを１つ発生させている。

import java.applet.Applet;

import java.awt.Graphics;

public class e2 extends Applet implements Runnable

{

Graphics g;

Thread th=null;

public void init()

{

g=getGraphics();

th=new Thread(this);

th.start();

}

// public void start() // This is OK, too!!

// {

// if(th==null)

// th=new Thread(this);

// th.start();

// }

public void run()

{

int i;

try

{

for(i=0; i<10; i++)

{

g.drawOval(i*20,30,10,10);

th.sleep(1000);

}

catch(InterruptedException e)

{}

}

プログラム1.3　

１つの丸の移動（丸を白で消しながら移動）

import java.applet.Applet;

import java.awt.*;

public class e3 extends Applet implements Runnable

{

Graphics g;

Thread th=null;

public void init()

{

g=getGraphics();

th=new Thread(this);

th.start();

}

// public void start() //Thread can be started here, too.

// {

// if(th==null)

// th=new Thread(this);

// th.start();

// }

public void run()

{

int i;

try

{

for(i=0; i<10; i++)

{

g.drawOval(i*20,30,10,10);

th.sleep(1000);

g.setColor(Color.white);

g.drawOval(i*20,30,10,10); // over-write by white.

g.setColor(Color.black);

}

catch(InterruptedException e)

{}

}

プログラム1.4　

１つの丸の移動（背景で丸を消す）。

丸がはみだしたりして、表示が美しくないが、これは

プログラムの動きを理解し易くするため。

import java.applet.*;

import java.awt.*;

public class e4 extends Applet implements Runnable

{

Graphics g;

Thread th=null;

Image back;

public void init()

{

g=getGraphics();

makeBackImage();

}

private void makeBackImage()

{

Graphics gb;

back=createImage(200,200);

gb=back.getGraphics();

gb.setColor(Color.blue);

gb.fillRect(0,0,199,199);

}

public void start()

{

if(th==null)

th=new Thread(this);

th.start();

}

public void run()

{

int i;

try

{

for(i=0; i<10; i++)

{

g.drawImage(back,5,5,this);

g.drawOval(i*20,30,10,10);

th.sleep(1000);

}

catch(InterruptedException e)

{}

}

プログラム1.5　

２つの丸の移動（スレッドを１つ発生させ、そこで２つの丸を描いている）。

import java.applet.*;

import java.awt.*;

public class e5 extends Applet implements Runnable

{

Graphics g;

Thread th=null;

Image back; //back image

int[] x,y;

public void init()

{

g=getGraphics();

makeBackImage();

}

private void makeBackImage() //make a back image

{

Graphics gb;

back=createImage(200,200);

gb=back.getGraphics();

gb.setColor(Color.blue);

gb.fillRect(0,0,199,199);

}

public void start()

{

if(th==null)

th=new Thread(this);

th.start();

}

public void run()

{

int i,ball;

x=new int[2];

y=new int[2];

try

{

for(i=0; i<10; i++)

{

g.drawImage(back,5,5,this); //rewrite back image

y[0]=30; y[1]=80;

for(ball=0; ball<2; ball++)

{

x[ball] += 10;

g.drawOval(x[ball],y[ball],10,10);

}

th.sleep(1000);

}

catch(InterruptedException e)

{}

}

プログラム1.6　

クラスを定義し、インスタンスを発生させる練習。

スレッドを使わない2つのインスタンスを発生。

import java.awt.*;

import java.applet.*;

public class h2 extends Applet {

hM theH[];

public void init(){

}

public void start() {

theH =new hM[2];

theH[0] =new hM();

theH[1] =new hM();

theH[0].room=4;

theH[0].data();

theH[1].room=5;

theH[1].data();

}

class hM {

int room;

void data() {

System.out.println("この家は"+room+"。");

}

プログラム1.7

クラスを定義し、インスタンスを発生させる練習。

スレッドを使う2つのインスタンスを発生。

import java.awt.*;

import java.applet.*;

import java.lang.*;

public class h3 extends Applet {

hM theH[];

public void init(){

}

public void start() {

theH =new hM[2];

theH[0] =new hM(0); //コンストラクタ駆動

theH[1] =new hM(1);

theH[0].start();

theH[1].start();

}

class hM implements Runnable{

Thread th;

int room;

h3 parent;

public hM(int num) {

room= num+3;

}

public void start() {

if(th==null)

th= new Thread(this);

th.start();

}

public void run() {

// try{

System.out.println("この家は"+room+"。");

// } catch (InterruptedException e){}

}

プログラム1.8

子クラスのインスタンスに、親のスクリーンに描画させる

には（親のpaint関数からしかgを子に送れない）。

import java.awt.*;

import java.applet.*;

public class h5 extends Applet {

hM theH;

public void init(){}

public void start() {

// theH =new hM;

theH =new hM();

}

public void paint(Graphics g)

{ theH.st(g); }

}

class hM {

public hM() {}

public void st(Graphics g) {

g.drawOval(20,20,10,10);

}

プログラム1.9　

２つの丸が独立固体のように動く（各丸はスレッドを発生するクラスのインスタンスである）。丸の数だけスレッドが出来る。

import java.awt.*;

import java.applet.*;

import java.lang.*;

public class h6 extends Applet {

M theM[];

public void init(){}

public void start() {

theM =new M[2];

theM[0] =new M(this,0); //constructor start

theM[1] =new M(this,1);

this.hstart();

}

public void paint(Graphics g)

{

theM[0].draw(g);

theM[1].draw(g);

}

public synchronized void hstart()

{

theM[0].start(); //child thread start

theM[1].start();

}

class M implements Runnable{

Thread th;

int m;

h6 parent;

int x,y;

public M(h6 applet, int num) {

m= num;

parent=applet;

parent.repaint();

y=20*num+20;

x=20*num+20;

}

public void start() {

if(th==null)

th= new Thread(this);

th.start();

}

public void run() {

try{

for(int j=0; j<5; j++)

{ th.sleep(1000);

x +=10;

parent.repaint();

}

} catch (InterruptedException e){}

}

public void draw(Graphics g) {

g.drawOval(x,y,10+m*4,10+m*4);

}

プログラム1.10　

２つの丸が独立固体のように動く。各丸はスレッドを発生するクラスのインスタンスである。丸の数だけスレッドが出来る。ただし、ここではスレッドクラスというものを使っているため、上よりすっきりしている。

import java.awt.*;

import java.applet.*;

import java.lang.*;

public class h7 extends Applet {

M theM[];

public void init(){}

public void start() {

theM =new M[2];

theM[0] =new M(this,0); //constructor start

theM[1] =new M(this,1);

}

public void paint(Graphics g)

{

theM[0].draw(g);

theM[1].draw(g);

}

class M extends Thread {

int m;

h7 parent;

int x,y;

public M(h7 applet, int num) {

m= num;

parent=applet;

parent.repaint();

y=20*num+20;

x=20*num+20;

start();

}

public void run() {

try{

for(int j=0; j<5; j++)

{ Thread.sleep(1000);

x +=10;

parent.repaint();

}

} catch (InterruptedException e){}

}

public void draw(Graphics g) {

g.drawOval(x,y,10+m*4,10+m*4);

}

プログラム1.11　

２つの丸の代わりに、用意しておいた画像を動かす

import java.awt.*;

import java.applet.*;

import java.lang.*;

public class h4 extends Applet {

hM theH[];

Image hI;

public void init(){

hI=this.getImage(getDocumentBase(),"girl.gif");

}

public void start() {

theH =new hM[2];

theH[0] =new hM(this,hI,0); //コンストラクタ駆動

theH[1] =new hM(this,hI,1);

this.hstart();

}

public void paint(Graphics g)

{

theH[0].draw(g);

theH[1].draw(g);

}

public synchronized void hstart()

{

theH[0].start(); //子スレッド起動

theH[1].start();

}

class hM implements Runnable{

Thread th;

int room;

h4 parent;

Image h;

int x,y;

public hM(h4 applet, Image theImage, int num) {

room= num;

h=theImage;

parent=applet;

parent.repaint();

y=20*num+20;

x=20*num+20;

// g=getGraphics();

}

public void start() {

if(th==null)

th= new Thread(this);

th.start();

}

public void run() {

try{

for(int j=0; j<5; j++)

{ th.sleep(1000);

x +=10;

parent.repaint();

}

} catch (InterruptedException e){}

}

public void draw(Graphics g) {

g.drawImage(h,x,y,parent);

}

-----------------------------------------------------------------------------------------

提出課題２：ランダムウオーク（酔歩）

目的１：乱数の発生法と使用法。

目的２：次の時点の状態＝現在の状態＋今回の移動分、だということを意識させる。これは以後の課題（シミュレーション）で常に使用する基本的考え方である。

提出期限：２回目の授業

内容：円を酔歩（酔っ払いのようにあちこち動く）させるプログラムを作成せよ。

インタビュー内容：

質問例１：乱数の発生法

質問例２：２つの円を酔歩させ、ぶつかったら１つになるようにするには？

基礎知識2.1：シミュレーションと乱数

シミュレーションは、（酔歩が酔っ払いの真似であるように）真似をすることである。シミュレーションでは乱数（乱数とは文字通りでたらめな数）を多用する。そのためどのプログラミング言語でも乱数が簡単に作れるよう、乱数発生関数が用意されている。乱数発生関数は、これを呼ぶごとに乱数を返してくる。

JavaではMath.random()　があり、0~1の間の実数値を返してくる。

イメージがわかない人は次のプログラムで乱数が発生される様子を見てみよう。

import java.awt.*;

import java.applet.*;

import java.lang.*; //これを忘れないように

public class Random extends Applet {

int i;

double ran;

public void init(){}

public void start() {

for(i=0; i<10; i++) {

ran=Math.random();

System.out.println("乱数"+ran+"。");

}

ちなみにC言語の乱数発生関数にはrand()　があり、0から整数の最大値までの値の整数値を返してくる。

酔歩の場合Math.random()で乱数を発生させ、0~0.25なら右、0.25~0.5なら上、0.5~0.75なら左、0.75~1なら下へ、決まった距離だけ画像を移動させればよい。

基礎知識2.2 ：色々な乱数

例えば、“０から１の間の乱数を返す関数”と言った場合、０～１の間の数を偏りなく返してくる。これはもう少し厳格に言うと一様分布に従った乱数である。これに対し、ある確率分布に従った値を返してくる乱数を使いたくなる場合がある。例えば、正規分布に従った乱数というものがある。これは正規分布の富士山型曲線を思い浮かべれば想像が付くと思うが、０付近の数が多く発生される乱数である。普通正規乱数を発生する関数は用意されていないため自分で作ることになる。作り方は簡単で、０～１の一様乱数を１２回発生させ、６を引けばよい。この理論は確率の本で勉強しなさい。

基礎知識2.3：簡単な自作の乱数発生関数

あくまでも偏りのない乱数を作る研究は専門家に任せるとして、ランダムさは少し怪しいが簡単に乱数を発生させるプログラムとしては、次のようなものがある。

-------------------------------------------------------------------------------

提出課題３：バネで繋がれた質点の振動

目的：微分方程式で記述される物理現象のシミュレーション法（オイラー法）を学ぶ

提出期限：３回目の授業

内容：次の図のように、９個の質点をバネでつなぎ両端は壁に固定した。

　　　　壁｜---○---○---○---○---○---○---○---○---○---｜壁

i番目の質点の運動方程式は、平衡位置からの変位をとすると

　　　　　　　　　　　　　　　　　　　　　　　　（式１）

となる。ここでmは質量（今回１とする）、kはバネ定数（今回１とする）である。

ある質点を平衡点から少しずらして放した時の振動の様子をシミュレートせよ。

インタビュー内容：

質問例１：オイラー法とは？

質問例２：バネ係数を変えると動きは変わるか？

質問例３：１つだけ重い質点に代えるとどうなる？

基礎知識3.1：オイラー法

微分方程式（運動方程式）を差分方程式に置き換えて解いていく数値計算法にオイラー法がある。運動方程式は、質点の位置をｘとすると、一般に

　　　　　　　　（式２）　といった形をしている。

ここでは簡単のために　　（式３）　という運動方程式を使ってオイラー法を説明する。この式を速度変数ｖを使って書きなおすと、

　、　　（式４）　という２つの式になる。

ここで覚えておいて欲しいことは、運動方程式と初期条件（t=0におけるｘとｖ）を与えると、任意の時刻におけるｘとｖが一意に決まるということである。オイラー法では、先ず微分方程式を差分方程式に変える。上の２式を差分方程式にすると、

　と　　（式５）になる。この式を使うと、初期値（）が与えられるとΔt時間後の値（）が（）と計算できる。求まった（）を初期値と考え、次の時点のｘとｖを求める、という操作を繰り返せば任意の時点のxとvを求めることができる。

このアルゴリズムを整理すると、次のようになる。

step1: 時間刻みΔtを決める

step2: 初期条件（x,v）を決める

step3: 初期値（x,v）を式５に入れてΔv、Δxを計算する

step4: 時間Δt後の（）を（）として求める

step5: step4で求めた（）を初期値としてstep3に戻る

以上。

基礎知識3.2：オイラー法を用いた課題プログラムの作成

質点の平衡点からの変位をｘ、速度をｖとすると、（式１）は

　　　と　　　　　という２つの式に分解できる。

この微分方程式を差分表現すると、ととなる。

時間刻みΔｔを0.01にして各時刻ごとの質点の変位を表示すると振動の様子が見える。

ヒント：C言語によるプログラムと、アルゴリズムの紹介

step1 初期設定Δt=0.01,x[0~11]=0,x[1]=50,v[0~11]=0,newx[0~11]=0,newv[0~11]=0;

step2 Δt後の変位ｘと速度ｖを差分の式から求める（x[]からnewx[],v[]からnewv[]）。

　　（注意：Δは変化分なので、変位は x=x+Δxとなる）。step2を繰り返す。

質点のみを表示する。質点の変位を平衡点からの垂直方向に表示すると振動の様子がよく分かる。

以下に、本課題をC言語で書いたプログラム例を示す。

#include <stdio.h>

#include <stdlib.h>

#include <igraph.h>

void main() {

float x[11]={0},v[11]={0},newx[11]={0},newv[11]={0};

float k= 1.0; float dt= 0.02; float gensui=0.9985;

int i,j;

x[1]=50.0; //最初１つの質点を強制移動させる

for( i=0; i<5000; i++) {

SetFillColor(CL_BLUE);//色設定

for( j=0; j<11; j++) //質点の水平移動表示

Ellipse( j*70+x[j], 50, j*70+x[j]+5, 50+5);//円描画

for( j=0; j<11; j++) //質点の垂直移動表示

Ellipse( j*70, 150+x[j], j*70+5, 150+x[j]+5);//円描画

for( j=1; j<10; j++) {

newv[j]= v[j] + k * (x[j-1] -2*x[j] + x[j+1]) * dt;//次時刻の速度

newx[j]= gensui*(x[j] + v[j] * dt);//次時刻の平衡点からの偏移

}

for(j=1; j<10; j++) {

v[j]= newv[j];

x[j]= newx[j];

}

ClearScreen(); //画面消去

}

（このプログラムは描画に、UltraCと呼ばれる処理系の命令を使用している。即ち、このままgccで実行しようとしても描画できない）

-------------------------------------------------------------

提出課題４：離散系シミュレーション

目的１：離散系シミュレーションを学ぶ

目的２：オブジェクト志向プログラミングを学ぶ

提出期限１：４回目の授業（待ち行列クラスを作成）

提出期限２：５回目の授業（完成プログラム）

内容：サービス窓口に出来る客の“待ち行列”の状況をシミュレートする。窓口数は１つで、客の到着確率が分かっている時、客の平均待ち時間と、窓口の利用率を求めなさい。

話を簡単にするために、到着客数は100人とし、それらの到着時刻は予め乱数で求めイベントテーブルに登録しておいてよい。

課題提出法：オブジェクト指向プログラミングとシミュレーションは相性がよい。というのも、元々クラスという概念はSimuraと呼ばれるシミュレーション言語で提案されたものである。Javaプログラムの腕試しということで、この課題を全部自力で作るのに越したことはない。自作できない人のためにここでは３つのプログラム設計法を紹介し、その内２つについて虫食い状態のプログラムを示す。この虫食い部を埋めてプログラムを完成させる。

３つのプログラムの特徴は以下の通りである。

プログラム4.1：猿にでも分かるよう簡単化し、イベントは使わず、オブジェクト指向のみで作成している。オブジェクト指向プログラミングの有りがたさを実感できるはず。できればこれを理解した上で、次の4.2に挑戦されたい。

プログラム4.2：これは正統派であり、オブジェクト指向を用いイベント管理を備えている。これをベースにすることが望ましい。

プログラム4.3：イベント管理を使うが、オブジェクト指向を使わないCプログラム。これは参考までに示したもので、今回は扱わない。

課題4.1は（１）（２）共通でキューのクラスを作り、簡単なテストスタブを用意して動作確認を行う。

課題4.2は、プログラム4.1または4.2を完成する。

プログラム4.1　（簡単で理解しやすい）

アプレットクラスの他、待ち行列クラスと客クラスを作成する。アプレットクラスでは時刻をTNOWという変数に割り当て、これを１時刻ずつ進めてシミュレーションを実行する。各時刻ごとに乱数で客の到着があるかを調べる。窓口がサービス中の時に到着した客を待ち行列に入れる。各客のサービス終了は乱数で確率的に求める。図4.1がフローチャートであり、これに沿って説明を加える。

　　　　　　　　　　　図４．１　シミュレーションの流れ

現時刻に客の到着があるか否かを最初に乱数で決定している。到着客がいる場合客のインスタンスをnewで作る。虫食いプログラムでは現時刻の到着確率を20%としている（Math.random()<0.2）。その後、窓口がbusyか否かによる場合分けを行う。窓口が空いている場合は、先に求めた到着客がいる場合は窓口をbusy=1にする。窓口が空いていない時は、その時点で処理中のサービスが終わるかどうかを乱数で調べる。この調べ方は、客到着を調べるのと同じ方法を使う。今処理中のサービスがこの時刻に終わらない場合で到着客がいれば、その客をキューに入れる。現在処理中のサービスがこの時刻に終わる時は、いったん窓口を“空”にした後、到着客がいる場合キューに入れる。その後キューに客がいれば、キューの先頭の客の処理に移る。

次の図はキュークラスの構成である。客インスタンスを入れる配列を用意し、次の３つのメソッドを作る。

（１） enter：客をキューに入れる

（２） top：キューの先頭の客を返す

（３） qlength：キューの長さを返す

以下が虫食いプログラムである。課題4.1はキューを完成させる。課題4.2はフローチャートの点線で囲まれた部分を作成しプログラムを完成する。

import java.awt.*;

import java.applet.*;

import java.lang.*;

public class q10 extends Applet {

public customer theC, CfromQ; //客クラス

public queue theQ; //キュー（待ち行列）クラス

public int TNOW=0; //シミュレーション時刻

int i,busy=0,arrive,totalwait=0,number=0;

double averagewait; //平均待ち時間

public void init(){theQ= new queue(); CfromQ= new customer();}

public void start() {

for(TNOW=0; TNOW<100; TNOW++) {

arrive=0;

if(Math.random()< 0.2) { //この時刻に到着客ありなら

theC= new customer(); //客のインスタンスを作る

arrive=1; //この時刻に到着客有り

number++; //客総数

}

if(busy==0) //窓口に客なし

{if(arrive==1) busy=1;} //窓口を仕事中にする

else { //窓口接客中

???????????????課題4.2???????????????????????????????

}

else if(arrive==1) { theC.time=TNOW; theQ.enter(theC);}

}

averagewait=(double)totalwait/(double)number;

System.out.println("平均待ち時間"+averagewait+"。");

}

class customer { //客クラス

int time;

}

class queue { //キュークラス

int qptr, i; customer theCq[], c;

public queue() {theCq= new customer[100]; qptr=0;}

public void enter(customer thecc) {

??????????課題4.1???????????????

};

public customer top() {

??????????課題4.1??????????????????

return (c);

}

public int qlength() { return (qptr);

}

インタビュー内容

質問例１：キューオーバーフローをチェックするにはどうするか

質問例２：空のキューに、先頭取りだし指令がきた時警告をだすにはどうするか

質問例３：窓口の利用率を求めるにはどうすればよいか

プログラム4.2　（イベント駆動）

このプログラムではmainにイベントの管理を行わせ、窓口クラス、待ち行列クラス、イベント表クラス、客クラスを用意する。プログラム4.1を勉強した人は窓口での客に対するサービス時間の扱い方が違うので注意する必要がある。プログラム4.1では各時刻ごとに終了を確率で出していたが、ここではサービスに入った時窓口クラスが終了時刻を乱数で出すようになっている。

イベントとしては客の到着（’a’）と各客の窓口サービスの終了（’l’）を取る。イベント表は次のように、イベント発生時刻と、そのイベントの種類（到着または終了）からなる２次元配列とする。下の例は、時刻１０に客が到着し、時刻２０にサービス中の仕事が終わることを示している。

イベント発生時刻	10	20
イベントの種類’a’ or ‘l’	‘a’	‘l’

mainは、この表を管理し、最も近い将来発生するイベントを駆動する。例えば、上の例では時刻１０に到着イベントが発生することになるので、シミュレーション時刻（TNOW）を１０にセットし、客インスタンスを作って窓口インスタンスに送る。客インスタンスはプログラム4.1と同様、到着時刻だけを持ったものである。また、終了イベントの場合は窓口インスタンスに終了時刻がきたことを知らせる。

窓口クラスは、キューを使って窓口に並んでいる客を管理する。客到着メソッドでは窓口がbusyなら、到着した客をキューに入れ、not_busyならサービスに入る。“サービスに入る”とは、乱数で終了時刻を求め、それをmainに知らせる。プログラムではmainに終了時刻を返す場合はサービス時間を、返す必要がない場合は-1を返している。客退去メソッドは、客のサービスが終わった時呼ばれ、キューに待っている人がいれば、その人のサービス時間をmainに返す。いなければ-1を返す。

キュークラスと客クラスはプログラム4.1と同じなので、そちらを参照。ここではその他nexteventというクラスを使っている。これはイベント表の先頭（最も近い将来のイベント）をmainに返すためのデータ構造である。

質問例１：キューオーバーフローをチェックするにはどうするか

質問例２：空のキューに、先頭取りだし指令がきた時警告をだすにはどうするか

質問例３：TNOWがstaticになっているのはなぜか

質問例４：なぜ窓口クラスはイベントクラスの extends　になっているのか

質問例５：窓口の利用率を求めるにはどうすればよいか

質問例６：客の到着を予め求めておかなくてもよいようにするにはどこを変えればよいか

基礎知識４.1：離散システムシミュレーション

　課題３までのシミュレーションは、（意識していなかったと思いますが）1時刻ずつ物体の動きを追いかけて表示してきた。このようなシミュレーションを（時間）連続システムシミュレーションと言う。連続システムシミュレーションは対象システムが連続的に変化する、という考え方に立っている。このようなシステムでは、システムの変化を差分方程式群で表現する場合が多い。

　これに対し離散変化モデルに基づく、離散システムシミュレーションというものがある。この場合は、対象システムを不等時間間隔で生起するイベントにより不連続的に変化すると考える。例えば、待ち行列のシミュレーションはこの代表で、客の到着や退去でシステムの状態が不連続的に変化する。

　以上２つのシミュレーションプログラムを作成する場合の大きな違いは、連続システムはシミュレーション時刻が等間隔で増加するのに対し、離散システムは生起するイベントに依存して不等時間間隔で変化する。そのため、前者ではシミュレーション時刻が陽に宣言されない場合がある。これに対し後者ではシミュレーション進行の中核としてグローバルに宣言される（上の課題ではTNOWという変数がそれである）。離散システムではイベントの発生時刻を管理するためにイベントテーブルを用いる。この中に将来起こるイベントの発生時刻とイベントの種類を逐一登録していき、シミュレーション管理プログラムはイベントテーブルから次々と（時間順に）イベントを取りだし、処理を進める。

　離散システムシミュレーションプログラムの構成は次のように、イベントテーブルを管理してシミュレーション時刻を進めていくシミュレーションの中核部（イベント管理部）と、各イベントの処理内容を記述するイベント部よりなる。イベントテーブルにはイベント発生時刻が登録されているため、イベント管理部はイベントテーブルをサーチし最も小さいシミュレーション時刻

のイベントを取り出し、その処理部に制御を移す。イベント処理部ではイベントテーブルに将来発生するイベントを登録するため、シミュレーションが続くことになる。

プログラム4.3 C言語で記述するとどうなるか（かつてシミュレーションの授業の課題）

スーパーのレジへの客の到着のシミュレーションを考えてみましょう。店は客が不満を持たない範囲でレジ数をできるだけ少なくしたいと考えます。このような時、乱数で客の到着時刻を出し、レジの混み具合（客の待ち時間）をシミュレートして、最適レジ数を求めます。このようなシミュレーションは待ち行列のシミュレーションと呼ばれ、様々な分野で使われています。

このようなシミュレーションを連続系で行うと、客の到着が少ない時など、ただ時刻を１ずつ進める以外何もしない時間が多くなり無駄な計算時間を取られます。そこで、“客の到着”や“各客のレジ処理の終了”といったイベント（出来事）に着目し、イベント発生時刻ごと（時間を飛び飛びに）進め、無駄な処理をなくす方法が提案されています。これは時間が飛び飛びなので離散系シミュレーションと呼ばれます。

イベント駆動の離散系シミュレーションの実現法

最も簡単な１レジの場合：

＜仮定＞

客は 5+rand()%5　分間隔で到着。

レジでの処理時間は　5+rand()%5 分。

＜求めたいもの＞

レジで客がサービスに入るまでの待ち時間の平均。

レジの稼動率。

プログラムのデータ構造（これらはグローバル（main()の前）に定義）

#define Etmax 20

#define Qmax 30

#define KyakuTotal 50

int TNOW;

int EventTable[2][Etmax]={{0},{0}};

int Queue[Qmax]={0};

int Qlength=0;　　

int WaitTime[KyakuTotal]={0};

int WTptr=0;

TNOWは飛び飛びに進むシミュレーション時刻を格納する変数です。

離散系シミュレーションでは先ず、何をイベントにするかを考えます。この問題では、“客の到着（イベント１）”と“各客のレジでのサービス終了（イベント２）”をイベントにします。

EventTable（イベント表）は２次元配列で、イベント発生時刻とイベントの種類（１or２）が入ります。

７	０	９	０	０
１	０	２	０	０

この場合時刻７にイベント１が、時刻９にイベント２が発生することを示します。イベント表は必ずしも右や左から詰まっているわけではありません。

Queue（待ち行列）は、レジが現在サービス中のため待っている客が入っています。ここには待ちに入った時刻を入れます（待ちから出たとき、待っていた時間をWaitTimeに登録します）。

WaitTimeは各客の待ち時間を入れる配列（WTptrは配列がどこまで埋まっているかを示すポインタ（Ｃのポインタではない））。

プログラムの構造

次の関数を用意（関数ごとに動作確認をしてから統合すること）：

void insert( int time)　：Queueの末尾にtime　を入れる。

int delete() ：　Queueの先頭を取り出し（取り除き）、その値を返す。

void schedule(int time, int event)：EventTableにイベント（発生時刻とイベントの種類）を登録。

int event()　：EventTableの中から最も近い将来発生するイベントの時刻をTNOWに格納し、　　　　　　　そのイベント番号を関数の値として返す。

＊Queueのデータ構造とinsert,deleteのアルゴリズム

Queueは1次元配列（最初all０）とし、待ちの客は、配列への左方から詰めていく（配列要素へは到着時刻を記入）。即ち、配列の左端（Queue[0]）が待ちの先頭となる。insertではQlengthを頼りに到着時刻を書き込む。deleteでは配列左端のデータを取り除き、全体のデータを左にシフトする。

＊EventTableのデータ構造とschedule,eventアルゴリズム

EventTableは最初全て０にする。scheduleでは将来発生するイベントを登録するが、EventTableを左から見ていって、書き込みが行われていない（０でない）配列要素にイベント発生時刻とイベントの種類を書き込む。event では最も近い将来のイベントを取り出し、取り出した後に０を入れる。

＊稼働率は、ServeとServeStartの２つの変数を使う。Serveはレジが現在サービス中かどうかを示すフラグとする。ServeStartはサービスを始めた時間を入れる（サービス終了時にサービス時間の合計をためていき、最後に集計）。

#include<math.h>

#include<stdio.h>

#include<stdlib.h>

#define Etmax 20

#define Qmax 30

#define KyakuTotal 50

int TNOW;

int EventTable[2][Etmax]={{0},{0}};

int Queue[Qmax]={0};

int Qlength=0;

int WaitTime[KyakuTotal]={0};

int servef;

void insert(int time);

int delete();

void schedule(int time,int event);

int event();

void init();

main(){

int i,x,ninzuu=0,sum,nst=0,Total_nst=0;

init(); //最初のお客さんの到着

for(;;){

if(ninzuu>=KyakuTotal) break; //最後のお客さん？

x=event(); //到着？　終了？

printf("TNOW=%d event=%d Qlength=%d sf=%d\n",TNOW,x,Qlength,servef);

if(x==1){ //到着イベント

schedule(TNOW+rand()%5+5,1); //次のお客さんの到着

ninzuu++;

if(servef==0){ //もしサービス中じゃなかったら

schedule(TNOW+rand()%5+5,2); //終了イベントのスケジュール

servef=1; //サービス中にする

Total_nst+=(TNOW-nst); //サービスしてなかった時間の計算

nst=0;

}else{ //サービス中だったら

insert(TNOW); //待ち行列に入れる

}

else{ //終了イベント

servef=0; //とりあえずサービス終了

if(Qlength>0){ //もし待っているお客さんがいたら

WaitTime[ninzuu]=TNOW-delete(); //待ってた時間の計算

schedule(TNOW+rand()%5+5,2); //終了イベントのスケジュール

servef=1; //サービス中にする

}

if(servef==0) nst=TNOW; //サービスしてない時間の始まり

}

sum=0; //平均待ち時間と稼働率の計算

for(i=0;i<KyakuTotal;i++) sum+=WaitTime[i];

printf("\nFinish!!\AverageWaitTime=%f\n Utilization =%f\n",(double)sum/KyakuTotal,(double)(TNOW-Total_nst)/TNOW);

}

void init(){

TNOW=0;

schedule(1,1);

}

void insert(int time){

Queue[Qlength]=time;

Qlength++;

}

int delete(){

int i,temp;

temp=Queue[0];

for(i=0;i<Qlength;i++)

Queue[i]=Queue[i+1];

Qlength--;

return temp;

}

void schedule(int time,int event){

int i;

for(i=0;i<Etmax;i++){

if(EventTable[0][i]==0){

EventTable[0][i]=time;

EventTable[1][i]=event;

break;

}

int event(){

int i,num,x;

for(i=0;i<Etmax;i++){

if(EventTable[0][i]!=0&&EventTable[0][i]>=TNOW){

num=i;

}

for(i=0;i<Etmax;i++){

if(EventTable[0][i]>=TNOW&&EventTable[0][i]<=EventTable[0][num]&&EventTable[0][i]!=0){

num=i;

}

TNOW=EventTable[0][num];

x=EventTable[1][num];

EventTable[0][num]=0;

EventTable[1][num]=0;

return x;

}

参考プログラム：

オブジェクト指向プログラミング（孫クラスへのデータの伝達法）

プログラム１：

import java.awt.*;

import java.applet.*;

public class Q3 extends Applet {

W theW;

public void init(){} //publicが不可欠

public void start() {

theW = new W();

theW.W(); //これがないとエラーになる

theW.arrive(5);

}

class W {

Queue theQ;

void W(){ theQ = new Queue();}

void arrive( int y) {

System.out.println("Wに伝わった"+y+"。");

theQ.enter(y+10);}

}

class Queue {

void enter(int x){

System.out.println("Queue伝わるか"+x+"。");}

}

プログラム２：

import java.awt.*;

import java.applet.*;

public class Q31 extends Applet {

W theW;

public void init(){}

public void start() {

theW = new W();

theW.arrive(5);

}

class W {

Queue theQ;

void arrive( int y) { theQ = new Queue();

System.out.println("Wに伝わった"+y+"。");

theQ.enter(y+10);}

}

class Queue {

void enter(int x){

System.out.println("Queueに伝わった"+x+"。");}

}

オブジェクト指向プログラミング（孫クラスへのインスタンスの伝達法）

import java.awt.*;

import java.applet.*;

public class Q4 extends Applet {

public W theW; public Customer theC;

public void init(){}

public void start() {

theW = new W();

theC = new Customer();

theC.time=10;

theW.arrive(theC);

}

class W {

Queue theQ;

void arrive( Customer thec) { theQ = new Queue(); //このcustomerを取るとエラー

System.out.println("Wに伝わった"+thec.time+"。");

theQ.enter(thec);}

}

class Customer {

int time;

int start1() { return( time);}

}

class Queue {

public void enter(Customer thecc){

System.out.println("queueに伝わった"+thecc.time+"。");}

}

オブジェクト指向プログラミング（メソッドの返り値が配列の場合）

import java.awt.*;

import java.applet.*;

public class Q6 extends Applet {

W theW; int a[]= new int[2];

public void init(){} //publicが不可欠

public void start() {

//int a[]= new int[2];ここでもよい

theW = new W();

a=theW.arrive();

System.out.println("伝わった"+a[0]+"。");

System.out.println("伝わったよ"+a[1]+"。");

}

class W {

int a[]= new int[2];

public int[] arrive() { //int a[]= new int[2];上でも、ここでもOK

a[0]=1;a[1]=2;

return (a);}

}

-------------------------------------------------------

自由提出課題

ライフゲーム（生態系をモデル化したもの）

50x50の碁盤の目にいくつかの生命体を配置し、各生命体を以下の規則で生死させる。但し、碁盤の各目は、周辺の８近傍の目と隣接していると考える。

規則１：もし、ある目に生命体が存在せず、その近傍３つの目に生命体が存在する時は、その目に次の時点に生命体が発生する。

規則２：生命体が存在する目は、隣接する目に生命体は１以下だったり、４近傍以上に生命体が存在すると次の時点に消滅する。