設定問題： この競技大会を行なう会場として、図のような400メートルのコースが 使えることになった。
図のコース１〜４はそれぞれ長さは100mの直線である。100ｍ走、100ｍハードル走は コース１〜４のどこででも行なえる。200ｍ走、200ｍハードル走はコース1とコース2、 コース2とコース3などのように、コース2つをつなげて行なう。ただしコース1と コース4は間に競技本部が設置されるので、つなげて使うことはできない。 300ｍ走も同様に、例えばコース2、3、4のように3つのコースを使って行なうとする。
ここで以下の競技を行なうことを考える。
100ｍ走Ａ 100ｍ走Ｂ 200ｍ走 300ｍ走 100ｍハードル走 200ｍハードル走それぞれにかかる時間は次のように予定されている。
100ｍ走Ａ 30分 100ｍ走Ｂ 30分 200ｍ走 30分 300ｍ走 30分 100ｍハードル走 45分 200ｍハードル走 60分それぞれの競技をどのコースでどのようなスケジュールで行なったらいいだろうか。
演習：それぞれの競技をどのコースでどのようなスケジュールで行なったらいいか 考えてプランを作ってみよ。またそのスケジュールでは始めてから終るまで 時間がどれだけ必要か考えてみよ。
いろいろなものが考えられるが、例えば方法１のようにすると、全体が終るのに２時間かかる。
//陸上競技のコース割り当て 方法１ // コース１〜４の４つのコースに各競技を割り当てる // コース１で100ｍの競技全部を順次行なう。 コース２〜４をつなげて200ｍ、300ｍの競技全部を順次行なう。この競技場は使う時間が長いとそのぶん利用料を多く支払わなければならないので、 始めてから終えるまでの時間はできるだけ短くしたい。競技の割当を工夫して、 終る時間をもっと早くすることを考えてみよう。
ここで以下の方法に基づいて割り当てることを考えよう。（方法２−第１段階）
//陸上競技のコース割り当て 方法２−第１段階
// コース１〜４の４つのコースに各競技を割り当てる
//
コースが空いたら
空いたコースで行なうことのできる中で一番距離の長い競技を行なう
（同じ距離の競技がいくつもある場合は
その中で時間が最もかかる競技を行なう）
この説明を、「実際にコースを割り当ててスケジュールを作る方法」の形に 書きなおしてみよう。割り当ては、大会開始の時刻から始めて
時間を順に追って行なうことが必要になる。すなわち
1.まず大会開始時点の割り当てをする。（コースは最初は全て空いているので そこに上の方法に基づいて競技を割り当てる。）
2.その後は、開始から15分後の状況、30分後の状況、と、15分ごとの 時刻を順次想定して状況を考えてゆく。それぞれの時刻において、その時終わった競技 がありコースが空いたら、上の方法に従って別の競技を割り当る。
3.全ての競技が終わったら大会を終了する。
と進めていくことになる。これを考慮して手順を書いてみよう。（第２段階）
//陸上競技のコース割り当て 方法２−第２段階
// コース１〜４の４つのコースに各競技を割り当てる
//
すべての競技が終了するまで時刻を１５分づつ進めながら繰り返す：
この時刻に競技が終了したコースがあれば
そのコースのしるしを「空」に変える
（終了したコースがいくつもあれば上記を繰り返す）
空いた／空いているコースがあれば
実行できる中で最も距離の長い競技を選んで開始する
（距離が同じ競技がいくつもある場合は最もかかる時間の長い
競技を選ぶ）
（競技を開始できた場合は上記を繰り返す
−もう一つ同時に開始できる場合もあるので）
繰り返しはここまで
このように時間を順に追って割り当てを進めるためには「いま開始何分後の 作業をやっているのか」を控えておくことが必要になる。すなわち紙の上などに
「現在時刻」という場所を設けて ・最初にそこに０分と書く ・大会開始時点の競技割当を行う ・０分を15分に直す ・開始後15分の状況での割当作業を行う ....のように進めていくことになる。
また、上記の割当方法では、一つ競技が終わってコースが空いても開始できる競技が無く、 コースをしばらく空いたままにせざるをえなかったり、またその後で
再度そのコースで競技を開始することになる等の場合もある。 そのため「このコースはいま空いている」というしるしをつけておく
必要があるので、そのための場所も用意しておく。
演習：「一つ競技が終わってコースが空いても開始できる競技が無く、 コースをしばらく空いたままにせざるをえない」のはどんな場合があるか。
これらの考え方を使って、この方法をより正確に書き直してみよう。（第３段階）
//陸上競技のコース割り当て 方法２−第３段階
// コース１〜４の４つのコースに各競技を割り当てる
//
繰り返す：
//この時刻に終了した競技があればそのコースのしるしを「空」に変える
コース１〜４それぞれについて：
そのコースでその時競技が終了するなら
そのコースのしるしを「空」に変える
//コースの印を「空」に変える処理はここまで
//空いているコースがあれば割り当てる−可能な限り繰り返す
繰り返す：
//空いている最長コースを調べる
//単独の空いているコースがあるかを調べる
コース1〜4それぞれについて：
そのコースが空ならば
コースが1つ空いていることと、コース番号を控えておく
//２つつなげて使えるコースがあるかを調べる
コース「1と2」「2と3」「3と4」それぞれの組について：
その両方のコースが空ならば
コースが2つ空いていることと、コース番号2つを控えておく
//３つつなげて使えるコースがあるかを調べる
コース「1と2と3」「2と3と4」それぞれの組について：
その3つのコースが空ならば
コースが3つ空いていることと、コース番号3つを控えておく
//空いている最長コースを調べる処理はここまで
//空いているコースがあり、割り当てられる競技があれば割り当てる
空いた／空いているコースがあるならば
今空いているコースの長さで実行できる最も長距離の競技を選ぶ
そのような競技があるならば
そのような競技（最も長距離の競技）が２つ以上あるならば
その中で必要時間が最大のものを選ぶ
//割り当てを行なう
空いているコース中の、競技に使うコースにだけ：
使用中の印を付ける
競技が終わりコースが空く時刻を控えておく
//割当の処理はここまで
//空いているコースへの割り当て処理はここまで
繰り返しはここまで−競技を割り当てたならもう一度繰り返す
// さらにまた別の競技も始められるかも知れないので繰り返し試みる
「現在時刻」を15分進める
繰り返しはここまで−コースが一つでも使用中なら繰り返しを続ける
演習：上記の方法を忠実になぞるとどのように競技が割り当てられていくかやってみよ。 始めてから終るまで時間は何分かかったか。
このようにあること（この場合は競技へのコースの割り当て）を行なう方法をきちんと 書いたものをアルゴリズムという。
演習：上記の方法２も必ずしも最良の割当をするものではなく、行なう競技の 個数・距離・時間を変えると無駄なコースの割り当てを行なうこともある。 より無駄の少ない割当をするような別のアルゴリズムを考えてみよ。 それによるコース割り当てをいろいろな場合について方法２でのものと比較してみよ。
上記のアルゴリズムはまだ細かい部分を省略して書いてある。 同じアルゴリズムをより細かく書いたものを下に示す。（第４段階）
//陸上競技のコース割り当て アルゴリズム（方法）２−第４段階
// コース１〜４の４つのコースに各競技を割り当てる
//
//記憶場所を用意する
競技種目の名前・必要距離・時間を覚えておく場所「競技」を用意し、
各競技種目の名前・必要距離・時間を設定する
各コースが「使用中」か「空」か、および終了時刻を覚えておく場所
「コース１」から「コース４」を用意し、最初は「空」にする
現在時刻を覚えておく場所「現在時刻」を用意し、最初は「０分」にする
//割り当てを行なう
繰り返す：
//この時刻に終了した競技があればそのコースのしるしを「空」に変える
ｉを１〜４まで変えながら：
もし コースｉが使用中で
かつ 現在時刻＝コースｉの終了時刻 ならば
コースｉを空にする
//コースの印を「空」に変える処理はここまで
//空いているコースがあれば割り当てる−可能な限り繰り返す
繰り返す：
//空いている最長コースを調べる
場所「最大コース長」（最初は０とする）と「候補コース」を用意する
//単独の空いているコースがあるかを調べる
ｊを１〜４まで変えながら：
もし コースｊが空 ならば
最大コース長を１に、候補コースをｊにする
//２つつなげて使えるコースがあるかを調べる
もし （コース３が空 かつ コース４が空） ならば
最大コース長を２に、候補コースを[3,4]にする
もし （コース２が空 かつ コース３が空）ならば
最大コース長を２に、候補コースを[2,3]にする
もし （コース１が空 かつ コース２が空）ならば
最大コース長を２に、候補コースを[1,2]にする
//３つつなげて使えるコースがあるかを調べる
もし （コース２が空 かつ コース３が空 かつ コース４が空）ならば
最大コース長を３に、候補コースを[2,3,4]にする
もし （コース１が空 かつ コース２が空 かつ コース３が空）ならば
最大コース長を３に、候補コースを[1,2,3]にする
//空いている最長コースを調べる処理はここまで
「開始競技」を「なし」に設定する
//空いているコースがあり、割り当てられる競技があれば割り当てる
もし 最大コース長 ＞ ０ ならば
「競技」の中の、必要距離が最大コース長以下のものの中で
最も長いものを選び「開始競技」とする
もし 「開始競技」がある ならば
もし 「開始競技」が２つ以上ある ならば
その中で必要時間が最大のものだけ「開始競技」とする
//割り当てを行なう
「開始競技の必要距離」の回数繰り返す：
//距離100mの競技なら１回、200mの競技なら２回繰り返す
「候補コース」の先頭のコースを使用中にする
「候補コース」の先頭のコースの終了時刻を
現在時刻＋「開始競技の終了時刻」に設定する
「候補コース」から先頭のコースを削除する
「競技」から開始競技を削除する
//割当の処理はここまで
//空いているコースがあっても、そこでできる
// 開始競技がない場合は割り当てはできない
//空いているコースへの割り当て処理はここまで
繰り返しはここまで−「開始競技」が「なし」でないなら繰り返しを続ける
// さらにまた別の競技も始められるかも知れないので繰り返し試みる
「現在時刻」を15分進める
繰り返しはここまで−コースが一つでも使用中なら繰り返しを続ける
アルゴリズムをここまで詳しく正確に書けば、コンピュータもこれを理解できる ようになる。ただしコンピュータに理解できる、「プログラミング言語」という
決まった形式に従って書かなければならない。これをプログラムという。 これをコンピュータに与えると、上の演習で手作業でやったのと全く同じことを
コンピュータは忠実に超高速で行なってくれる。
上のアルゴリズムをプログラミング言語で書いたものを以下に示す。 プログラミング言語には多くの種類がある。ここではＣ＋＋（シープラスプラス）言語 でのものを示す。(*1)
//陸上競技のコース割り当て アルゴリズム（方法）２ C++言語によるプログラム
// コース１〜４の４つのコースに各競技を割り当てる
void main()
{
//記憶場所を用意する
t_kyougi kyougi; //各競技種目の名前・必要距離・時間を覚えておく場所
//各競技種目の名前・必要距離・時間の設定
kyougi.settei("100ｍ走Ａ", 1, 30);
kyougi.settei("100ｍ走Ｂ", 1, 30);
kyougi.settei("200ｍ走", 2, 30);
kyougi.settei("300ｍ走", 3, 30);
kyougi.settei("100ｍハードル走", 1, 45);
kyougi.settei("200ｍハードル走", 2, 60);
//各コースが「使用中」か「空」か、および終了時刻を覚えておく場所
t_course course;
//最初は「空」にする
course.shiyou[1] = aki;
course.shiyou[2] = aki;
course.shiyou[3] = aki;
course.shiyou[4] = aki;
//現在時刻を覚えておく場所
int genzaijikoku = 0; //最初は「０分」にする
//割り当てを行う
do {
//この時刻に終了した競技があればそのコースのしるしを「空」に変える
for (int i = 1; i <= 4; ++i) {
if (course.shiyou[i] == shiyoochuu
&& genzaijikoku == course.shuryoujikoku[i]) {
course.shiyou[i] = aki;
}
}
//コースの印を「空」に変える処理はここまで
//空いているコースがあれば割り当てる−可能な限り繰り返す
t_intset kaishikyougi;
do {
//空いている最長コースを調べる
int saidai_course_chou = 0;
t_courseset kouho_course;
//単独の空いているコースがあるかを調べる
for (int j = 1; j <= 4; ++j) {
if (course.shiyou[j] == aki) {
saidai_course_chou = 1;
kouho_course.settei(j);
}
}
//２つつなげて使えるコースがあるかを調べる
if (course.shiyou[3] == aki && course.shiyou[4] == aki) {
saidai_course_chou = 2;
kouho_course.settei(3, 4);
}
if (course.shiyou[2] == aki && course.shiyou[3] == aki) {
saidai_course_chou = 2;
kouho_course.settei(2, 3);
}
if (course.shiyou[1] == aki && course.shiyou[2] == aki) {
saidai_course_chou = 2;
kouho_course.settei(1, 2);
}
//３つつなげて使えるコースがあるかを調べる
if (course.shiyou[2] == aki && course.shiyou[3] == aki && course.shiyou[4] == aki) {
saidai_course_chou = 3;
kouho_course.settei(2, 3, 4);
}
if (course.shiyou[1] == aki && course.shiyou[2] == aki && course.shiyou[3] == aki) {
saidai_course_chou = 3;
kouho_course.settei(1, 2, 3);
}
//空いている最長コースを調べる処理はここまで
kaishikyougi.clear();
//空いているコースがあり、割り当てられる競技があれば割り当てる
if (saidai_course_chou > 0) {
kaishikyougi = kyougi.saidaichou_erabu(saidai_course_chou);
if (kaishikyougi.num_elem >= 1) {
if (kaishikyougi.num_elem >= 2) {
kaishikyougi = kyougi.saidaijikan_erabu(kaishikyougi);
}
//割り当てを行う
for (int c = 1; c <= kyougi.kyori[kaishikyougi.value()]; c++) {
//距離100mの競技なら１回、200mの競技なら２回繰り返す
course.shiyou[kouho_course.course_elem[0] ] = shiyoochuu;
course.shuryoujikoku[kouho_course.course_elem[0] ]
= genzaijikoku + kyougi.jikan[kaishikyougi.value()];
//割り当ての表示
printf("jikan=%i, kyogi=%s, course=%i, shuryojikoku=%i\n",
genzaijikoku, kyougi.namae[kaishikyougi.value()],
kouho_course.course_elem[0],
course.shuryoujikoku[kouho_course.course_elem[0] ] );
kouho_course.sakujo();
}
kyougi.sakujo(kaishikyougi.value() );
//割当の処理はここまで
}
//空いているコースがあっても、そこでできる
// 開始競技がない場合は割り当てはできない
}
//空いているコースへの割り当て処理はここまで
} while(kaishikyougi.num_elem >= 1);
// さらにまた別の競技も始められるかも知れないので繰り返し試みる
genzaijikoku += 15;
} while (course.shiyou[1] == shiyoochuu || course.shiyou[2] == shiyoochuu
|| course.shiyou[3] == shiyoochuu || course.shiyou[4] == shiyoochuu);
}
コンピュータが動くには必ずプログラムが必要である。どんな時もコンピュータが
動いている時には、その中にはかならず、誰かが作った上の例のようなプログラムが 入っており、コンピュータはそれに忠実に従ったことを超高速に行なっているに
すぎないのである。
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
const SAIDAIMOJI = 64;
const SAIDAIKYOUGI = 32;
// t_使用：空きか使用中か
enum t_shiyou {aki, shiyoochuu};
// t_intset：整数の集合
class t_intset {
public:
int num_elem; //要素の数
int elem [SAIDAIKYOUGI];
t_intset() {num_elem = 0;}
void clear() {num_elem = 0;}
// add：集合に要素を加える
void add(int a){if (num_elem >= SAIDAIKYOUGI) exit(1); elem[num_elem] = a; ++num_elem; }
// value：集合の要素が一つの時にその値を得る−複数要素が入っている時は使用不可
int value() {if (num_elem != 1) exit(1); return (elem [0]);}
};
// t_競技：競技一覧の集合
class t_kyougi {
private:
int num_elem; //要素の数
public:
char namae [SAIDAIKYOUGI] [SAIDAIMOJI] ; // 競技の名前
int kyori [SAIDAIKYOUGI]; // 必要距離
int jikan [SAIDAIKYOUGI]; // 時間
public:
t_kyougi() {num_elem = 0;}
void settei(char *a_namae, int a_kyori, int a_jikan); // 設定：集合に要素を加える
// 最大長選ぶ：最大コース長以内で距離が最長の競技を選ぶ
t_intset saidaichou_erabu(int saidai_course_chou);
// 最大時間選ぶ：インデックス集合ａから時間が最長のものを選びそのインデックスを返す
t_intset saidaijikan_erabu(t_intset a);
void sakujo(int a); // 削除：競技集合からインデックスで与えられた要素を削除する
};
// 設定：競技の集合に要素を加える
void t_kyougi::settei(char *a_namae, int a_kyori, int a_jikan)
{
if (num_elem >= SAIDAIKYOUGI) {
printf("競技数が多すぎる\n");
exit(1);
}
strcpy(namae[num_elem], a_namae);
kyori[num_elem] = a_kyori;
jikan[num_elem] = a_jikan;
++num_elem;
}
// 最大長選ぶ：最大コース長以内で距離が最長の競技を選ぶ
t_intset t_kyougi::saidaichou_erabu(int c)
{
//登録されている競技の中で最長の距離を求める
int saidaichou = 0;
for(int i = 0; i<num_elem; ++i) {
if (kyori[i] <= c && kyori[i] > saidaichou) {
saidaichou = kyori[i];
}
}
//最長の距離を持つ競技を全て取り出しそのインデックスの集合を返す
t_intset r;
for(int j = 0; j<num_elem; ++j) {
if (kyori [j] == saidaichou) {
r.add(j);
}
}
return r;
}
// 最大時間選ぶ：インデックス集合ａから時間が最長のものを選びそのインデックスを返す
t_intset t_kyougi::saidaijikan_erabu(t_intset a)
{
int x_saidaijikan = a.elem[0];
for (int i = 0; i<a.num_elem; ++i) {
if (jikan[a.elem[i] ] > jikan[x_saidaijikan]) {
x_saidaijikan = a.elem[i];
}
}
t_intset r;
r.add(x_saidaijikan);
return r;
}
// 削除：競技集合からインデックスで与えられた要素を削除する
void t_kyougi::sakujo(int a)
{
for (int i = a; i< (num_elem - 1); ++i) {
strcpy(namae[i], namae[i+1]);
kyori[i] = kyori [i+1];
jikan[i] = jikan [i+1];
}
--num_elem;
}
// t_コース：４つのコースのそれぞれの状態を保持する（要素１〜４のみ使用）
struct t_course {
t_shiyou shiyou [5]; //コースがあいているかどうか
int shuryoujikoku [5]; //今そのコースで行っている競技の終了時刻
};
// t_コースセット：コースの集合を保持
class t_courseset {
public:
int course_elem [4];
t_courseset() {for (int i = 0; i<4; ++i) {course_elem[i] = 0;} }
// 設定：集合をクリアし値を一度にセット
void settei(int a0) {course_elem[0] = a0;}
void settei(int a0, int a1) {course_elem[0] = a0; course_elem[1] = a1;}
void settei(int a0, int a1, int a2)
{course_elem[0] = a0; course_elem[1] = a1; course_elem[2] = a2;}
void sakujo();
};
// 削除：コースの集合から第０要素を削除
void t_courseset::sakujo()
{
for (int i = 0; i<3; ++i) {
course_elem[i] = course_elem[i+1];
}
course_elem[3] = 0;
}
--------------------------