レポート課題

以下の課題を C, C++, Java 6(Java 1.4 は使わないこと)のどれかの言語を使っ て作りなさい。

注意: Windows の API は使用しないで作って下さい。

課題1

レポート締切日: 2007年12月5日20:00

提出先: レポートボックス

受験番号と点数が空白で区切られたようなファイルに対して、成績処理を行な うためのプログラムを作成したい。 以下の小問について答えなさい。

なお、この問題は早々に 2ch に投稿され、既に解答も寄せられています。 同じ掲示板に何度も同じ問題を投稿するのはマナー違反ですので、もう新たに 2ch にこの問題を投稿しないようにして下さい。

質問が多い箇所に関して加筆しました。(2007/11/28)

お詫び

rand() の値は 0 から RAND_MAX までなので、 0 以上 1 未満の範囲の乱数を 得るには rand() を RAND_MAX で割るのではなく、 RAND_MAX+1 で割る必要が あります。 付録を訂正しておきます。 なお、レポートに関して、再提出の際は RAND_MAX+1.0 で割るようにしてくだ さい。 合格者に関しては評価を変えませんが、このような変更があったことは御留意 下さい。

課題1-1

99999 以下の整数の引数をとり、受験番号を C00001 から順に C00002 の ように引数の数だけ発生させ、 さらに各受験番号に対して乱数で発生させ た点数を組み合わせたテストファイルを作るプログラムを作りなさい。 但し、点数は、 0 点から 5 点までを乱数で 20 回発生させ和を取ること で求めなさい。 引数のとりかた、乱数の発生の仕方は付録を 参照のこと。

次に、作成したプログラムを利用して、 100 人分のテストファイルを作成 しなさい。

C, C++
C:\work> .\kadai1-1.exe 100 > testfile
C:\work> type testfile
C00001 60
C00002 35
C00003 78
...
Java
C:\work> java Kadai11 100 > testfile
C:\work> type testfile
C00001 60
C00002 35
C00003 78
...

課題1-2

作成した点数表に対して、手作業で合格最低人数を 20人、40人、60人とし たときの合格最低点と合格人数をそれぞれ求めなさい。 但し、合格最低点とは合格最低人数 20 人であれば、 20 位の点数のことであ る。また、合格人数とは合格最低点以上を得点している人数のこととする。

なお、手作業の代わりに、表計算ソフトを使用しても良い。但し、表計算ソフ トを使用した際は、必ず表の使用方法や、使用した関数の説明を行なうこと。

課題1-3

点数表を読み込み、点数の高い順に出力するプログラムを作成しなさい。 プログラムにおいて点数表の容量を制限してはいけない。コンピュータのメモ リが許す限り大きな点数表も表示できること。

次に、作成した点数表に対し、実行した結果を示しなさい。

C, C++
C:\work> .\kadai1-3.exe  < testfile
C00003 78
C00001 60
C00002 35
...
Java
C:\work> java Kadai13  < testfile
C00003 78
C00001 60
C00002 35
...

課題1-4

合格最低人数を引数にして合格最低点を求めるプログラムを作成しなさい。 但し、引数のとりかたは付録を参照すること。

そして、プログラムに対して、作成した点数表と、合格最低人数として、 20 人、40人、60人 をそれぞれ与え、合格最低点を求めなさい。

C, C++
C:\work> .\kadai1-4.exe 20 < testfile
65
C:\work> .\kadai1-4.exe 40 < testfile
60
C:\work> .\kadai1-4.exe 60 < testfile
53
Java
C:\work> java Kadai14 20 < testfile
65
C:\work> java Kadai14 40 < testfile
60
C:\work> java Kadai14 60 < testfile
53

課題1-5

合格最低点を引数に取り、受験番号順に合格者リストを表示するプログラ ムを作りなさい。

そして、 1-4 で得られた 3 種類の合格最低点をそれぞれ与 え、合格者リストを作成しなさい。

C, C++
C:\work> .\kadai1-5.exe 65 < testfile
C00003
...
C:\work> .\kadai1-5.exe 60 < testfile
C00001
C00003
...
C:\work> .\kadai1-5.exe 53 < testfile
C00001
C00003
...
Java
C:\work> java Kadai15 65 < testfile
C00003
...
C:\work> java Kadai15 60 < testfile
C00001
C00003
...
C:\work> java Kadai15 53 < testfile
C00001
C00003
...

注意

なお、ファイルの入出力は標準入出力でも、ファイルの入出力でもどちらを使 用しても良い。 但し、ファイルの入出力を使う際は、ファイルの非存在などのエラー処理は必 ず行うこと。

一文字の処理に、文字列の文字数に比例した時間かかったり、一行の処理に 全体の行数分の時間がかかるようなプログラムは大幅に減点します。

課題2

2007/12/21 課題 2-3 に加筆しました。

2,3 年生の提出条件

レポート締切日:
2008年1月9日20:00
提出先:
レポートボックス

4 年生以上の提出条件

12月19日は会議など所用で在室時間を確保できなくなりましたので、期限を一 日延長します。 できれば 12 月 20 日に提出してください。

レポート締切日:
2007年12月20日20:00
提出先:
坂本に直接
提出形式:

紙の場合、11号館12F1206室で手渡し。冬休み中にやりとり可能なメールアドレスを記入すること。PDF ファイルを受信できること

PDF ファイルをメールしてきても良い。但し、冬休み中にやりとり可能なメールアドレスを指定すること。

これ以外の形式(マイクロソフトのワープロのファイル、画像ファイル)などは受け取りませんので注意。

問題

ファイルを読み込み、英字のみか、先頭が英字で二文字目以降が英字または数 字である文字列を抽出し、文字列を辞書順に並べ、その文字列の頻度と 共に表示するプログラムを作成したい。 但し、大文字小文字は区別しない。 このプログラムを作成するのに、以下の設問にしたがって回答しなさい。

なお、辞書順とはつぎのような順序を言う

  1. 1 文字同士についてはアルファベット順に行う。 なお、今回は大文字小文字を区別しないので、 A=a<B=b<... などとな る。
  2. 複数の文字からなる文字列を比較する場合、先頭の文字が異なる場合、そ の文字のアルファベット順に従う。 同一なら次の文字を注目し、アルファベット順の比較をすることを繰り返す。 途中まで同一で、一方の文字列が先に終了した場合、先に終了した文字列の方 を小さいとする。

したがって、次のような順になります。

a < aa < aaa < ... < ab < aba < ...

注釈

実用上問題があるかもしれませんが、下記の例のように Matcher==matcher と しても構いません。 また、Matcher!=matcher として数え上げ、出力時の整列順序だけ大文字小文 字を区別しないようにプログラムを作成した場合は、より難易度の高い問題を 解いたとして評価します。

なお、この問題も既に 2ch に投稿され、解答も寄せられました。 何度も言いますが、同じ掲示板に何度も同じ問題を投稿するのはマナー違反で すので、くれぐれも新たに2ch にこの問題を投稿しないようにして下さい。 掲示板の皆様、本学の学生がお騒がせして済みませんでした。

実行例

入力


import java.io.*;
import java.util.regex.*;
class Test {
    public static void main(String[] arg) throws IOException {
	InputStreamReader isr = new InputStreamReader(System.in);
	BufferedReader br = new BufferedReader(isr);
	String buf;
	Pattern p = Pattern.compile("[0-9A-Za-z]+");
	Matcher m;
	while((buf=br.readLine())!=null){
	    m= p.matcher(buf);
	    while(m.find()){
		System.out.println(m.group());
	    }
	}
    }
}

出力

A: 1
arg: 1
br: 2
buf: 3
BufferedReader: 2
class: 1
compile: 1
find: 1
group: 1
import: 2
in: 1
InputStreamReader: 2
io: 1
IOException: 1
isr: 2
java: 2
m: 4
main: 1
Matcher: 2
new: 2
null: 1
out: 1
p: 2
Pattern: 2
println: 1
public: 1
readLine: 1
regex: 1
static: 1
String: 2
System: 2
Test: 1
throws: 1
util: 1
void: 1
while: 2
z: 1
Za: 1

課題2-1

ファイルを読み込み、英字のみか、先頭が英字で二文字目以降が英字または数字である文字列を出力するプログラムを作りなさい。

出力例

import
java
io
import
java
util
regex
class
Test
public
static
void
main
String
arg
throws
IOException
InputStreamReader
isr
new
InputStreamReader
System
in
BufferedReader
br
new
BufferedReader
isr
String
buf
Pattern
p
Pattern
compile
A
Za
z
Matcher
m
while
buf
br
readLine
null
m
p
matcher
buf
while
m
find
System
out
println
m
group

課題2-2

文字列 s1,s2 の二つを比較する関数またはクラスを作りなさい。

C 言語
関数名を cmp とするとき、プロトタイプ宣言は次のようにします。

int cmp(char *s1, char *s2);
これを strcmp と同じ仕様となるようにします。 但し、文字列は大文字、小文字を区別しないので、あらかじめ toupper()関数 (ctype.h をインクルードする必要あり)などを使用して比較対象を大文字に変 換します。 この後、辞書式順序の比較を行います。 s1 と s2 の文字を順番に比べていき (1) s1 が先に終わったか、 s1 の文字の方が小さい時に負の値、 (2) s2 が先に終わったか、 s2 の文字の方が小さい時に正の値を返します。 (3)両方同時に終わったときは 0 を返します。 どちらも終わらず、注目している文字が同じ場合は、注目する文字を次に移し ます。
C++ 言語
C++ では文字列 s1, s2 に対して、 s1 が s2 より小さい時 true を返す関数 を考えます。 文字列にはイテレータがあるので、それを利用します。 文字を比較する際、cctype ヘッダファイルに含まれる std::toupper() 関数 を使い、文字を大文字に変換してから比較する方法と、 C 言語同様、一文字 ずつ比較する方法があるでしょう。 この関数を以下のようにクラスの operator() のオーバロードとして作成しま す。

class Cmp : public std::binary_function<std::string,std::string,bool> {
public:
  bool operator()(const std::string& s1, const std::string& s2){
  // ここは自分で書く
  }
};
イテレータ、toupper の使用例:

#include <cctype>
#include <string>
#include <iostream>
int main(){
  std::string h="Hello World!\n";
  for(std::string::iterator p=h.begin(); p!=h.end(); ++p){
    std::cout << static_cast<char>(std::toupper(*p));
  }
}
Java6 言語
Java では java.util.Comparator を実装したクラスを作り、 compare を実装 してください。クラス名を Cmp とすると、次のような定義になります。

class Cmp implements java.util.Comparator<String> {
    public int compare(String s1, String s2){
    // ここは自分で書く
    }
}
但し、 Java の String クラスにはズバリ compareToIgnoreCase メソッドが ありますので、そのまま使って下さい。

なお、テスト方法はこちら

課題2-3

題意を満たすプログラムを作りなさい。 プログラムを説明する時、2-1, 2-2 で作成したプログラムをどのように活用したか も説明しなさい。

完成したプログラムに、上記の実行例の入力を与え、出力が同じになることを 確かめなさい。 但し、 出題後の問題の変更ですので、特に確かめなくても不合格にはしませんが、 ここが同一にならないプログラムを提出すると、もともとの問題が解けてない ことになり、不合格になります。必ず確かめること。 さらに、何度も言っていることですが、「確かめなさい」という問題で「確か めました」という答は減点の対象になりますので、注意してください。

なお、問題文注釈にある通りの仕様変更をした場合は、実行例の出力がどのよ うに変化するか説明し、実際に予想通りの出力になることを確かめてください。

課題2-4

作成したプログラムのソースコードを作成したプログラムに与え、出力を 求めなさい。

注意

ファイルの終端が改行の直後にあることを仮定しても構いません (販売するようなレベルのソフトウェアでは問題ですが)。

ファイルを二回以上 open しないこと。 0 回または 1 回で済ませて下さい。 また最適さを追求しすぎる必要はないですが、余りにも効率が悪すぎる手法を 使用した場合(バブルソートを使うなど)、講義の内容を理解していないと見な しますので、ご注意下さい。

ヒント

C++

#include <iostream>
#include <locale>
using std::isalpha;
using std::isalnum;
int main(){
    std::locale loc;
    std::cout << isalpha('2',loc)
	      << isalpha('a',loc)
	      << isalpha('#',loc)
	      <<std::endl;
    std::cout << isalnum('2',loc)
	      << isalnum('a',loc)
	      << isalnum('#',loc)
	      <<std::endl;
}

古い gcc を使っていると locale が入ってないため、上は動きません。 新しい mingw32 にバージョンアップを勧めますが、古い gcc のまま動かした い場合は下記のようにして下さい。 但し、結果は上とは異なります。


#include <iostream>
#include <cctype>
using std::isalpha;
using std::isalnum;
int main(){
    std::cout << isalpha('2')
	      << isalpha('a')
	      << isalpha('#')
	      <<std::endl;
    std::cout << isalnum('2')
	      << isalnum('a')
	      << isalnum('#')
	      <<std::endl;
}
C

#include <stdio.h>
#include <ctype.h>
int main(void){
  printf("%d %d %d\n", isalpha('2'),isalpha('a'),isalpha('#'));
  printf("%d %d %d\n", isalnum('2'),isalnum('a'),isalnum('#'));
  return 0;
}
課題 2-1 のプログラムの説明法

課題 2-1 でできあがったプログラムは、各行ごとにはそれほど複雑な関数を 使用したりしません。 したがって、各行毎に説明をしてもプログラムがどのように動作するのかは説 明できません。

課題2-1 のプログラムを説明するには、次のようにすると良いでしょう。

  1. 課題の内容を元に正規表現を作る
  2. 講義資料を参考にして、非決定性オートマトン、決定性オートマトンを作 る(要:オートマトンの図)。
  3. 決定性オートマトンにおいて、文字列のバッファの操作を付け加える。

文字列バッファの操作方法が記入されたオートマトンができたら、「これをそ のままプログラムにした」という主張だけで、プログラムの解説になっている はずです。

課題 2-3 のプログラミング

C++ で作る際、 map を使う方法と、 list を使う方法の二種類があります。 list を使う場合、 Cmp 型のオブジェクト変数を定義すると便利です。

レポート作成上の注意点

  1. どのプログラミング言語で書くのかあらかじめはっきりしておくこと
  2. プログラミングのレポートでは必ずプログラムの説明をすること。 その時に、一行一行を日本語に直訳するのではなく、データの読み込みとか、 出力とかの部分に分割し、機能毎に使用した手法を説明すること。 プログラム中にコメントを入れてもプログラムの説明とはみなさないので注意 する事。
  3. 「問題を解きなさい」という問に対して「解きました。合ってました」で は正解ではないことはわかるはず。 「テストしなさい」という問に対しては、テストの方法の説明、実際のテスト の実施方法、テスト結果、検証などを説明して下さい。
  4. レポートは手書きでもワープロでも構いません。但し、実行結果はコン ピュータの出力を添付すること。
  5. 考察は必ず書いて下さい。 ネタがない人は以下を参考にして下さい。
    • 大きなファイルが入力されるとき、メモリ領域はどのくらい使われるのか? また、プログラム中、プログラム終了時のメモリの使用状況を考えなさい。
    • C, C++, Java のうち、なぜそれを選んだか?
  6. 不必要なことはなるべく書かない事。C++, Java をプログラミング言語に 選んだ場合、本文は 10 ページ程度(プログラム、実行結果は付録)が標準とな るはずです。 長過ぎるレポートは減点します。またなるべく両面印刷にしてください。 但し、文字は必要以上に小さくしない事。レポート本文の文字は 10 ポイント 以上のものを使う事。

注意

なお、写したと思われるほど酷似したレポートが複数提出された場合、原著が どれかの調査を行わず、抽選で一通のレポートのみを評価 の対象とし、他は提出済みの不合格レポートとして再提出は課しません。 自分で意図せずに他人にコピーされてしまった場合も同様ですので、レポート の取り扱いについては十分に注意して下さい。


坂本直志 <sakamoto@c.dendai.ac.jp>
東京電機大学工学部情報通信工学科