標準入力からN個の整数を受け取って、それらを昇順(小さいほうから大きい方)にソートして改行区切りで出力するプログラムをCで作成せよ。Nは1000以下としてよい。ソートアルゴリズムとしては、バブルソート・クイックソート・マージソートの3種類を全て実装すること。main関数は以下をそのまま利用すること。
int main(void){
int N, M;
scanf("%d", &N);
scanf("%d", &M);
if (M == 0) {
BubbleSort(N);
} else if (M == 1) {
QuickSort(N);
} else if (M == 2) {
MergeSort(N);
}
return 0;
}
補足: 整数値のリストが全て異なる値であるとは限らない事に注意せよ。
締切: 01/10 23:59
文字列のリストを受け取って昇順に整列されたリストを返す関数「my-sort」をSchemeで定義せよ。ここでいうリストとは、Schemeのデータ構造としてのリストのことである。文字列の比較には、「string=?」「string<?」「string>?」を用いること。ソートのアルゴリズムは何を利用しても構わないが、O(n!)やO(2^n)などのオーダーで実装されており、計算時間がかかりすぎるコードは受理しない。(60~70個くらいの要素が2秒以内にソートできていれば問題ない。)
補足: 空のリスト、一つしか要素を含まないリストも適切に処理できるよう注意せよ。
締切: 01/10 23:59
次のような形式で始点と終点のある重み付き有向グラフを定義することにする。
最初の行には、グラフの始点の名前が書かれている。
次の行には、グラフの終点の名前が書かれている。
以後は、各行が辺を意味している。辺は、辺の始点、終点、重みがスペースを区切りとして並んだものである。
辺の重みは正の整数であるとする。
例えば、次のようなものがグラフの表現である。
A
F
A B 3
A C 1
A E 12
B A 5
B C 1
B D 8
C D 10
C E 8
D F 2
E F 4
辺の重みを2点間の移動にかかるコストと考えることにする。この表現によるグラフをファイル入力から読み込み(ファイル名は"graph.txt"とする事標準入力から受け取るとする事。標準入力から与えられる入力には、".txt" も含まれる。ファイル名は50文字以下として良い。)、グラフの始点からグラフの終点までの移動コストを最小にする経路を求め、その経路上の点を始点から順に終点まで、改行を区切りとして表示するプログラムをCで作成せよ。始点から終点に到達可能でない場合は、「(no route)」と表示せよ。該当する経路が複数存在する場合には、それらのうち1つだけを表示するものとする。点名の文字数は99以下、点の総数と辺の総数はそれぞれ1000以下、辺の重みの総和がintの範囲を超えないと仮定してよい。
実行例: 少し大きなグラフのサンプルを配布しておく。このサンプルを入力として与えた場合の出力は以下の通りである。
渋谷
表参道
青山一丁目
永田町
四ツ谷
市ケ谷
飯田橋
春日
本郷三丁目
締切: 01/10 23:59
2つの文字列をキーボード入力から受け取った時に、動的計画法によってそれらの最長共通部分列を求めるアルゴリズムを実装し、その最長共通部分列を表示するプログラムを作成せよ。最長共通部分列が複数考えられる場合には、どれか一つのみ表示すれば良い。
注意: 表示するものは、最長共通部分列の長さではなく、最長共通部分列である。最長共通部分列の定義は、「アルゴリズムとデータ構造」の講義で利用している教科書によるものとする。
入力例
AFFEACEDCA
DDFCFCBDA
出力例
FFCDA
締切: 01/10 23:59