レポート課題

以下の課題を C, C++, Java のどれかの言語を使って作りなさい。

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

課題1

レポート締切日: 2005年11月30日

ファイルを読み込み、空白が早く現れる順に各行を並べ替えるプログラムを作成したいと思います。空白とはスペース記号 0x20 とタブ 0x9 を意味します。空白の無い行は 0 番目に空白が現れたことにして下さい。

以下の手順にしたがって作成し報告して下さい。

始めに文字列を入れたら最初に空白が来る位置を求める関数を作りたいと思います。その関数をテストするための文字列をいくつか作り、関数が出力しなければいけない値をそれぞれ求めなさい。また、そのような文字列を作った理由を解説しなさい。
文字列を入れたら最初に空白が来る位置を求める関数を作りなさい。但し、空白で始まる文字列には 1, 空白がなければ 0 を返しなさい。
作成したテストを行い、予想した結果と一致するか確かめなさい。
次に題意を満たすプログラムを作成しようと思います。そのプログラムをテストするようなファイルをいくつか作りなさい。そして完成したプログラムが出力すると予想した値を書きなさい。また、そのようなファイルを作成した理由を解説しなさい。
上で作成した関数を利用して、題意を満たすプログラムを実際に作成しなさい。
作成したテストを行い、予想と一致することを確かめなさい。
作成したプログラムのソースファイル自体をそのプログラムに読み込ませ、出力を求めなさい

注意

予想したテスト結果と実際の結果が異なる場合は、それでも題意を満たしていることと、なぜ異なったかを必ず説明して下さい。

ファイルのサイズに上限を設けてはいけません。何 MB のファイルでも読めるようになってなければいけません。要は「配列は使うな」です。行の入力バッファには配列を使っても良いですが、各行の格納場所に配列を使ってはいけません。

(追加 2005/11/9 午後) 但し、一行の文字制限が無いと入力バッファの処理が複雑になる場合、一行を高々 80 文字と仮定し、一行を表す文字列としてだけ配列を使っても良い。

(追加 2005/11/26) 講義中に言いましたが、バブルソート、挿入ソートなど、平均の効率が O(n²) のものも使わないでください。ソートを自分で組む場合、クイックソート、ヒープソートの他、マージソート、シェルソートなどを採用してください。講義で解説していない手法は当然詳しく説明してください。

実行例

入力

#include <stdio.h>
int main(){
  printf("Hello World\n");
  return 0;
}

出力

}
  printf("Hello World\n");
  return 0;
int main(){
#include <stdio.h>

ヒント

C++ で行の取得をするには std::istream のメンバ関数である getline メソッドを使います。これは getline(文字配列のポインタ, 文字数, 区切り文字)で呼びます。ここで、区切り文字が来る前に文字数-1 文字だけ読み込んでしまった時、 std::ios:failbit が ON になってしまいます。この場合 clear() メソッドでこのビットを OFF にする必要があります。但し、この clear() メソッドは std::ios:eofbit も OFF にしてしまうので、注意して使う必要があります。

以下は標準入力から各行を高々 80 文字だけ読み込み出力するプログラムです。


#include <iostream>
using std::cin;
using std::cout;
using std::endl;
int main(){
  char buffer[81];
  while(!cin.eof()){
    cin.getline(buffer,sizeof(buffer));
    cout << buffer << endl;
    while((!cin.eof())&&cin.fail()){
      cin.clear();
      cin.ignore(80,'\n');
    }
  }
  return 0;
}

レポート講評

どのプログラミング言語で書くのかあらかじめはっきりしておくこと
プログラミングのレポートでは必ずプログラムの説明をすること。その時に、一行一行を日本語に直訳するのではなく、データの読み込みとか、出力とかの部分に分割し、機能毎に使用した手法を説明すること。
「問題を解きなさい」という問に対して「解きました。合ってました」では正解ではないことはわかるはず。「テストしなさい」という問に対しては、テストの方法の説明、実際のテストの実施方法、テスト結果、検証などを説明して下さい。
考察は必ず書いて下さい。ネタがない人は以下を参考にして下さい。
- 課題の他に必ずファイルの読み込み方法を独自に考えなければならないはずですので、どのような考えでファイルの読み方を選んだのか
- 講義では様々な並べ替えの方法を紹介しましたが、その中で今回採用した方法と採用しなかった方法の比較
- C, C++, Java のうちどれを選んだか理由を書く

課題2

レポート締切日: 2006年1月11日。但し 4 年生以上は冬休み中にやりとりできる e-mail アドレスを表紙に記入して 2005年12月20日

ファイルを読み込み、英字のみか、先頭が英字で二文字目以降が英字または数字である文字列を抽出し、辞書順に並べ、その文字列が何行目に現れるか列挙するプログラムを作成したい。以下の設問にしたがって回答しなさい。

なお辞書順とは、文字列の比較法の一つで、文字列の先頭から順に比較していき、最初に異なった文字の大小関係とします。但し、途中で文字が無くなった場合は無い方が小さいとします。

例

0<9<A<Z<a<z
aaa<aaaa
aaa0<aaa1

実行例

入力


#include <stdio.h>
#include <ctype.h>
main(){
  int c;
  char b;
  b='\0';
  while((c=getchar())!=EOF){
    if((!isalnum(b))&&isalnum(c)){
      printf("\n");
    }
    if(isalnum(c)){
      printf("%c",c);
    }
    b=c;
  }
}

出力

EOF:7 
b:5 6 8 14 
c:4 7 8 11 12 14 
char:5 
ctype:2 
getchar:7 
h:1 2 
if:8 11 
include:1 2 
int:4 
isalnum:8 11 
main:3 
n:9 
printf:9 12 
stdio:1 
while:7

設問

ファイルを読み込み、英字のみか、先頭が英字で二文字目以降が英字または数字である文字列を抽出するプログラムを作ることを考える。文字列と、それが出現した行番号を一緒に出力することとする。まず、実行例にある入力を読み込んだ時、どのような出力になるかをプログラムを使わず求めなさい。

(2005/12/20 追記) この設問では出力する順番は指定されてません。したがって、どんな順番でも(行番号順でも辞書順でも)構わないと言うことです。
ファイルを読み込み、英字のみか、先頭が英字で二文字目以降が英字または数字である文字列を抽出し、行番号とともに出力するプログラムを作りなさい。

(2005/12/20 追記) この設問では出力する順番は指定されてません。したがって、どんな順番でも(行番号順でも辞書順でも)構わないと言うことです。
1 で求めた結果と作成したプログラムに与えた結果が一致することを確かめなさい。
~~取消: 題意を満たすプログラムは、実行例にある入力を読み込んだ時、どのような出力になるかをプログラムを使わず求めなさい。~~
題意を満たすプログラムを作りなさい。プログラムを説明する時、2 で作成したプログラムをどのように変更したか手順も説明しなさい。
作成したプログラムに実行例の入力を与え、求めた出力と等しくなることを確かめなさい。
作成したプログラムのソースコードを作成したプログラムに与え、出力を求めなさい。

注意

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

ヒント

C++ を使う人は次がヒントになるかも知れません。

ヒント1


#include <iostream>
#include <set>
typedef std::set<int> NumSet;
int main(){
  NumSet s;
  s.insert(3);
  s.insert(3);
  s.insert(5);
  s.insert(2);
  for(NumSet::iterator i=s.begin(), lend=s.end();
      i!=lend; i++){
    std::cout << *i << std::endl;
  }
}

ヒント2


#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;
    return 0;
}

古い 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;
    return 0;
}

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