2016年度 発展プログラミング演習 練習問題 上級

目次

1. Diffコマンドの作成．
   • 問題
   • 実行例
   • 参考資料
2. 4つの数字から四則演算を用いて0〜9を作る．
   • 問題
   • 実行例
   • ヒント
   • 参考資料
3. 画像のフィルタリング
   • 問題
   • 実行例
   • 参考資料
4. Webサーバの作成
   • 問題
   • 実行例
   • ヒント
   • 参考資料

1. Diffコマンドの作成

問題

編集グラフ

2つのプログラムの差分を表示するコマンドDiffを作成してください． Diffプログラムの差分の考え方は，編集距離 の考え方と似ています．異なる点は，編集距離では置換が行えましたが，Diffの場合， 追加，もしくは削除のみが行われます（削除と追加を各１回行うことで置換が行われると考えてください）． まずは，ファイルの差分を考える前に，文字列の差分を考えましょう．

       k  i  t  t  e  n 
    0  1  2  3  4  5  6 
 k  1  0  1  2  3  4  5 
 i  2  1  0  1  2  3  4 
 t  3  2  1  0  1  2  3 
 t  4  3  2  1  0  1  2 
 y  5  4  3  2  1  2  3

ここでは，"kitten"と"kitty"の差分を考えます． 編集距離を参考に編集グラフを作成します． この時，置換は行えませんので，左上のセルの値を取得するのは，文字が同じ場合のみに限ります． 編集グラフを左に示します． このグラフから３回の追加，削除を行うことで，"kitten" から "kitty"への書き換えが行えることがわかります．

では，実際にどのように書き換えていけば良いかを考えてみましょう． 右下から，値の低いセルへ逆順に移動していき，最終的に左上のセルに到達させましょう． ルートの選び方は一通りとは限りません．しかし，どのようなルートの選び方をしたとしても， 同じような結果になります． また，右下から順に左上に辿っていくのは，正順（左上から右下）だと， 途中で行き止まりが出てくる可能性があるためです（右の例では，正順でも逆順でも同じ）．

上下の移動は追加，左右の移動は削除，斜めの移動は，そのままを意味します．

こうして右図のように移動すると，最初のルート（R1）では「削除，削除，追加，そのまま，そのまま， そのまま，そのまま」，そして，別解のルート（R2）では 「追加，削除，削除，そのまま，そのまま，そのまま，そのまま」となります． これは，辿って行った逆順のままですので，正順にして，"kitten" に当てはめて考えてみましょう．

R1
  k
  i
  t
  t
+ y
- e
- n

R2
  k
  i
  t
  t
- e
- n
+ y

まず，４文字目までは，どちらの回答もそのままですから，"kitt" まではそのままです．その後，R1では，追加が行われ"y"が追加されます． その後２回削除が行われますので， "en"が１文字ずつ削除されます．

一方，R2では，４文字目まではR1と同じですが，その後，削除が２回実行され，"en" が１文字ずつ削除されます．そして最後に追加で"y"が追加されます． 左の例のように，R1, R2では，追加・削除の順序が異なるだけで，結果は同じものになります．

さて，この例では，R1, R2の２ルートのみを示しましたが，実はもう一つルートがあります． 調べてみてください．R3のルートでも手順にかかる手間は同じです．

Diff

では，次に，Diffの実装を行いましょう． 編集グラフでは，ある文字から，別の文字に変更する方法を説明しました． Diffでは，あるファイルから，別のファイルにどうやれば変更できるのかを調べます．

まず，2つのファイルから，各行を取り出し，各行を 編集グラフでの１文字に置き換えて考えます． すると，行単位での編集グラフが作成できます（行単位での比較では， １文字でも違っていれば異なっていると判断してください）．

クラス名は、Diff.javaとしてください。

実行例

$ cat sample1.txt
abcdefg
$ cat sample2.txt
ABCDEFG

1234567890
$ java Diff sample1.txt sample2.txt
+ ABCDEFG
+ 
+ 1234567890
- abcdefg

左のプログラムで使っているファイルが必要な場合は， sample1.txt， sample2.txt， から取得してください．

参考資料

• Javaプログラムの基本形
• 独自の型の定義方法
• コマンドライン引数
• ファイルを開く
• 例外機構
• 編集距離
• Table.java

2. 4つの数字から四則演算を用いて0〜9を作る．

問題

概要

0〜9までの4つの数が与えられたとき，四則演算を用いて，0〜9の値をそれぞれ作成しましょう．

例えば，1, 2, 3, 4 の4つの数が与えられたとき，次の計算式でそれぞれ求められます． このように各数値ごとの計算式をプログラムで求めてみましょう． なお，求める式は，1つだけで良いです． 求められるのであれば，すべての式を求めても構いません．

0. (3-1-2)*4
1. (1-2)*3+4
2. 2-1-3+4
3. (4/1+2)/3
4. 1+2-3+4
5. (1+2)/3+4
6. 1-2+3+4
7. (2-1)*3+4
8. 2-1+3+4
9. 1*2+3+4

考え方

次のように考えましょう． ある値$x_1$を求めたいとき，与えられた数値$a, b, c, d$のうち，3つの数 $a, b, c$を使い， $x_1-d$, $x_1+d$, $x_1/d$, $x_1*d$ となる値を求められれば良いです． 数値の組み合わせを変えて，４通り行い，$x_1$を求めましょう．

また，3つの数の組み合わせ$a, b, c$と，求める値$x_2$が与えられたときも同様に， 2つの数$a, b$を用いて，$x_2-c$, $x_2+c$, $x_2/c$, $x_2*c$を求めましょう．

具体例

具体例で考えます． 1, 2, 3, 4 を与えられた数とし，まずは，0となる計算式を求めます． 1, 2, 3, 4 のうち1, 2, 3を使い，-4, 4を作ることを考えます． 1, 2, 3で，-4, 4が作成できたなら，-4+4, もしくは，4-4で0が作成できます．

次に，1, 2, 3で-4となる計算式を求めましょう． このときも先と同じように，1, 2 を使い，-1を作成することを考えましょう． 1, 2から-1が作成できれば，-1-3 で-4が作成できるためです． これは，1-2で求められます．

また，数値の組み合わせを変えれば，求める数値も変わりますが， これらを繰り返すことで，0〜9までの値を求める式を求められます．

クラス名は、NMaker.javaとしてください。

実行例

$ java NMaker 1 2 3 4
0,1-2-3+4,1-3-2+4,(1-3)*2+4,2-1+3-4,3-1+2-4,(3-1)*2-4,2+3-1-4,(1+2-3)*4,...
1,(1-2)*3+4,1*2+3-4,2/1+3-4,1*3+2-4,3/1+2-4,2*3-1-4,(2+3)*1-4,(2+3)/1-4,...
2,2-1-3+4,2-3-1+4,1+2+3-4,(1*2)*3-4,(2/1)*3-4,1+3+2-4,(1*3)*2-4,(3/1)*2-4,...
3,1*2-3+4,2/1-3+4,(1-3)/2+4,(2-3)*1+4,(2-3)/1+4,2*3+1-4,1*2+4-3,2/1+4-3,...
4,1+2-3+4,1-3+2+4,3-1-2+4,2-3+1+4,3-2-1+4,(1+3)*2-4,((1+2)/3)*4,(1*3-2)*4,...
5,(1+2)/3+4,1*3-2+4,3/1-2+4,(3-1)/2+4,(3-2)*1+4,(3-2)/1+4,(1+2)*3-4,(1/2)*4+3,...
6,1-2+3+4,1+3-2+4,(1+3)/2+4,3-2+1+4,((1/2)*3)*4,((1*3)/2)*4,((3/1)/2)*4,...
7,(2-1)*3+4,(2-1)*4+3,(1+4)*2-3,(4-1)*3-2,(3/2)*4+1,(4-2)*3+1,(4/2)*3+1,(3*4)/2+1
8,2-1+3+4,3-1+2+4,(3-1)*2+4,2+3-1+4,(1-2+3)*4,(1+3-2)*4,((1+3)/2)*4,(3-2+1)*4,...
9,1*2+3+4,2/1+3+4,1*3+2+4,3/1+2+4,2*3-1+4,(2+3)*1+4,(2+3)/1+4,1*2+4+3,2/1+4+3,...

左のプログラムでは，すべての組み合わせを求めて出力しています（一部出力を省略しています）． 各行の式は1つでも構いません．

ヒント

割り算を実際に計算すると，割り切れない場合など誤差により正確に計算できない場合があります． 分数形式で持っておくと良いかもしれません． ただし，あくまで考え方の一つで，この方法でないと実現できないものではありません．

参考資料

• Javaプログラムの基本形
• 独自の型の定義方法
• コマンドライン引数

3. 画像のフィルタリング

問題

概要

画像を読み込み，注目画素の周辺画素を用いて，新たな画像を作成しましょう． 注目画素の周辺画像から新たな画素を計算することで，画像のフィルタリングが行えます．

クラス名は、ImageFilter.javaとしてください。

画像とは

画像は，２次元配列のように画素が並んでいます． 一つの画素には，Red, Green, Blue の色成分が含められています． 多くの場合，1つの画素はInteger型で表現されます． 32ビットの画像の場合，上位から8ビットずつ透明度（α成分），赤成分（R），緑成分（G）， 青成分（B）です．

例えば，右図のように，とある場所の画素を取り出すと，16進数で f08b2cという値が得られました（透明度は今回関係ないので，下位24ビットのみで考えます）． このうち，最上位の２桁（f0）が赤成分，真ん中の２桁が緑成分（8b）， 最後の２桁が青成分（2c）です．

画素は画像の中に，width * heightだけ存在します． そして，注目画素とその周辺画素を元に，新たな画素を計算することで，画像のフィルタリングが実現できます． ただし，異なる色成分は別々に計算しなければ想定通りのフィルタリングにはなりませんので，注意してください． 例えば，赤成分なら赤成分だけを取り出して，フィルタリングを行い，その他の成分も同じように計算します． その後，3つの成分を合わせて新たな画素として計算しなければいけません．

Javaでの画像の入出力

Javaで画像フィルタリングを行うためには，以下のことが必要です． 順に説明します．

• 画像ファイルの読み込み．
• 画像の大きさ・画素の取得．
• 新たな空の画像の作成．
• 画素の設定．
• 作成した画像の確認．
• 画像のフィルタリングの方法．

画像を読み込む

BufferedImage readImage(File file) throws IOException{
    return ImageIO.read(file);
}

左のようなプログラムで画像の情報がBufferedImageに格納されて読み込まれます． 画像フォーマットは，gif, png, jpgなど一般的なフォーマットであれば読み込めます．

なお，BufferedImageを使うときは，java.awt.image.BufferedImage のインポートが，ImageIOを使うときは， javax.imageio.ImageIOのインポートが必要です．

画像の大きさ，画素を取得する

BufferedImage image = readImage(new File("image.png"));
Integer width = image.getWidth();
Integer height = image.getHeight();
for(Integer j = 0; j < height; j++){
    for(Integer i = 0; i < width; i++){
        Integer pixel = image.getRGB(i, j);
        Integer red   = (pixel >>> 16) & 0xff;
        Integer green = (pixel >>>  8) & 0xff;
        Integer blue  = (pixel >>>  0) & 0xff;
    }
}

左のように，BufferedImage型の変数に対して，getWidth， getHeightを呼び出すことで実現できます．

また，同じく，BufferedImage型の変数に対して，getRGB メソッドを呼び出すと画素が得られます．画素から各色成分を取り出すには， 左のプログラムのような計算式が必要です．なお，>>>は 符号を無視した右シフト演算子です．

新たな空の画像を作成する．

BufferedImage newImage = new BufferedImage(
    width, height, BufferedImage.TYPE_INT_ARGB
);

フィルタリング前後を別の画像の実体にしようとするとき，空の画像を新たに作成する必要があります． 左のプログラムで空の画像が作成できます．width，height で指定した大きさになります．最後の，BufferedImage.TYPE_INT_ARGB は作成する画像の画素フォーマットの指定です．ここでは，32ビットのInteger型で， 先に述べたような透明度，赤成分，緑成分，青成分が8ビットずつ含まれる画像として作成しています．

画素を設定する．

for(Integer j = 0; j < height; j++){
    for(Integer i = 0; i < width; i++){
        Integer pixel = image.getRGB(i, j);
        // 途中の処理を省略．
        Integer newPixel = // ... 新たな画素を計算する．
        newImage.setRGB(i, j, newPixel);
    }
}

画像を書き出す

BufferedImage writeImage(BufferedImage image) throws IOException{
    File outputFile = new File("output.png");
    // 真ん中の&qupt;png"は出力フォーマット．"jpg"などもOK．
    return ImageIO.write(image, "png", outputFile);
}

作成した画像の確認のために，今回は画像をファイルに出力します． 左のようなプログラムで，出力できます．真ん中の文字列は出力フォーマットを表しています． 例では，"png"ですが，"jpg"や "gif"などでも出力できるかもしれません．

画像のフィルタリング

Double[][] kernel = new Double[][]{
    { 1.0/9.0, 1.0/9.0, 1.0/9.0, },
    { 1.0/9.0, 1.0/9.0, 1.0/9.0, },
    { 1.0/9.0, 1.0/9.0, 1.0/9.0, },
};

あらかじめ，フィールドにkernelという変数で， どのようなフィルタリングを行うのかを定義しておきます． 左のようなkernelでは，周辺の画像の平均を取った画素になるため， 少しぼやけた画像に変換されます．

kernelの全要素の合計値が1になれば他にもどのようなフィルタでも可能です． 例えば，中心以外は，-1.0/9.0として，中心を17.0/9.0 にするとどのような画像になるか確認してみましょう．

Integer newPixel = 0xff_00_00_00;
for(Integer k = 0; k <= 16; k += 8){
    Double color =
          kernel[0][0] * ((image.getRGB(i - 1, j - 1) >>> k) & 0xff)
        + kernel[0][1] * ((image.getRGB(i - 1, j    ) >>> k) & 0xff)
        + kernel[0][2] * ((image.getRGB(i - 1, j + 1) >>> k) & 0xff)
        + kernel[1][0] * ((image.getRGB(i    , j - 1) >>> k) & 0xff)
        + kernel[1][1] * ((image.getRGB(i    , j    ) >>> k) & 0xff)
        + kernel[1][2] * ((image.getRGB(i    , j + 1) >>> k) & 0xff)
        + kernel[2][0] * ((image.getRGB(i + 1, j - 1) >>> k) & 0xff)
        + kernel[2][1] * ((image.getRGB(i + 1, j    ) >>> k) & 0xff)
        + kernel[2][2] * ((image.getRGB(i + 1, j + 1) >>> k) & 0xff);
    newPixel = newPixel | ((color.intValue() & 0xff) << k);
}
newImage.setRGB(i, j, newPixel);

次に，画素に対して，kernelを用いたフィルタリング処理を行います． 左のようなプログラムを利用しましょう． 繰り返しの中で各色成分に対する処理を行い，結果は，newPixel に代入されていきます．

元の画像が変数imageに入っており，newImage にフィルタリング結果の画像が入れられます． これを各画素に対して行うことで，フィルタリングが実行できます．

なお，このプログラム中のnewPixelの初期値が0xff_00_00_00 になっています．最初の0xは16進数で値を表すときの接頭辞を表しています． また，数値の間に_（アンダーバー）が入っていますが， これはコンパイル時には無視されます．人の理解のために数字の間に入れられます． 数値の最初のffは24ビット目から32ビットまでの値を表しており， 画素で言えば，透明度に当たります．透明度が16進数でffということは， 10進数だと255です．透明度が255は，完全に不透明を表しています．0に近くほど透明に近づいていきます． その他の成分は，前にも記したように，赤成分，緑成分，青成分を表しています． この部分は，13行目で指定されますので，どんな値でも構いませんが， 各成分の初期値を0にしています．

画像の表示

import java.awt.*;
import java.io.*;
import javax.swing.*;
import javax.imageio.*;
public class ImageViewer{
    void view(Image image){
        // ウィンドウを用意する．
        JFrame frame = new JFrame();
        frame.setDefaultCloseOperation(JFrame.DISPOSE_ON_CLOSE);
        // 画像をウィンドウに貼り付ける．
        frame.add(new JLabel(new ImageIcon(image)));
        // 大きさを画像に合わせる．
        frame.pack();
        // ウィンドウを表示する．
        frame.setVisible(true);
    }
    // ファイルから画像を読み込み，表示する．
    void view(File file) throws IOException {
        Image image = ImageIO.read(file);
        this.view(image);
    }
}

Javaで，画像を表示したい場合は，左のプログラムを利用してください． ImageViewerの実体を作成し，viewメソッドを呼び出せば， 画像を表示するウィンドウを表示してくれます．

ImageViewer.java からダウンロードもできるようにしています．利用する場合は， 利用したいプログラムと同じディレクトリに ImageViewer.javaを置いてください．

実行例

以下の画像がフィルタリング前後の画像です．左がフィルタ前，右がフィルタ後の画像です． 利用したカーネルは，画像のフィルタリングで紹介したもの （全要素が1.0/9.0）です． 画像をクリックすると大きな画像が開きますので，大きくして確認してみてください．

挑戦課題

• 2つの画像をマージするプログラムImageMergerを作成してください．
  • 大きさが同じで絵柄が全く異なる2つの画像を用意してください．
  • それぞれの画像の同じ位置の画素を取得し，その画素の平均を取り，新しい画素を求めてください．
  • 新しい画素を持つ画像はどのような画像になるか確認してみましょう．

参考資料

• Javaプログラムの基本形
• コマンドライン引数
• 例外機構

4. Webサーバの作成

問題

概要

ブラウザでアクセスした時に処理を行うWebサーバを作成してみましょう． ブラウザでアクセスした時，右図のように，ブラウザからリクエストが送られ， Webサーバはリクエストに応じたレスポンス（応答）を返信します． そのリクエストとレスポンスは，HTTP (Hyper text transfer protocol)という プロトコル （決まりごと）に従ったフォーマットで送受信されます．

基本的には，HTTPは１度のリクエストに対して１度のレスポンスを返します． このやりとり１回がHTTPのすべてです．HTTPは状態を持たないプロトコロルですので， 同じブラウザからの送信が何回目などの情報は全く保持しません．

HTTPプロトコルのフォーマット

HTTPのプロトコルでは，リクエストとレスポンスの両方が定義されています． 両方とも，ヘッダとボディに分けられます． ヘッダとボディの区切りは，空行です． また，ヘッダには幾つかのエントリが送られてきますが，エントリの区切りは改行で行われています． ネットワーク上の改行は，\r\nで直接指定され， printlnなどのメソッドでは指定されません． printlnは環境によって，改行コードが異なるためです． HTTPプロトコルでは，ヘッダ内のエントリの区切りは\r\n， ヘッダとボディの区切りは2つの連続した\r\nであると定められているため， 直接コードを指定する方が良いでしょう．

HTTPプロトコルのフォーマット リクエスト

GET /index.html HTTP/1.1
Accept:image/webp,image/*,*/*;q=0.8
Accept-Encoding:gzip, deflate, sdch
Accept-Language:ja,en-US;q=0.8,en;q=0.6
Cache-Control:max-age=0
Connection:keep-alive
Cookie:_gat=1; _ga=GA1.2.433842312.1465889038
Host:dev.ontheroad.jp
If-Modified-Since:Wed, 25 May 2016 02:41:04 GMT
If-None-Match:"928-533a19ad9f2d3"
        

では，実際のHTTPのリクエストを見てみましょう． とあるサイトを見た時にブラウザからサーバ側に送られるリクエストです（一部省略しています）． ヘッダは，ここに挙がっている以外のものもありますが，今回はヘッダの内容までは踏み込んで解析しません． 今回の簡易Webサーバの実装のために，解析が必要な箇所は１行目だけです．

1行目のGET /index.html HTTP/1.1という内容が， 今回のWebサーバ作成のために必要な情報です． これは空白で区切られた3つの要素が含まれています． GET，/index.html，HTTP/1.1 です．それぞれ，HTTPメソッド，リクエストパス，HTTPのバージョンを表しています． HTTPメソッドは，どのような方法でリクエストパスを要求しているかを表しています． 今回は，GETのみを知っていれば良いでしょう． リクエストパスは，どのようなリソースが要求されたかを表しています． 例えば，http://ksuap.github.io/materials/training/advanced.htmlというURLが 要求された時，/materials/training/advanced.htmlというリクエストパスが 送信されます． 最後のHTTPのバージョンも今回は触れません．

さて，リクエストを受け取ったWebサーバがどのような処理を行うのかを見てみましょう． Webサーバは，リクエストパスに基づいて，ファイルを探します． そして，ファイルが見つかれば，そのファイルの内容をレスポンスとして送り返します． ファイルが見つからなければ，見つからなかったというレスポンスを返します． ただこれを行うだけでWebサーバの完成です．

HTTPプロトコルのフォーマット レスポンス

HTTP/1.1 200 OK
Date:Tue, 14 Jun 2016 07:24:42 GMT
Last-Modified:Wed, 25 May 2016 02:41:04 GMT
Server:nginx
        

さて，左に示すものが，サーバが送り返すレスポンスの例（ヘッダのみ）です． リクエストの時と同じように，ヘッダにサーバやそのページの様々な情報が記されています． しかし，ここで重要なのは，やはり１行目のみです． その他のヘッダは無視しましょう． 1行目は，HTTPのバージョン，ステータスコード，メッセージがスペースで区切られています． HTTPのバージョンはリクエストの時と同じく，HTTP/1.1という文字列を送れば良いでしょう． ステータスコードとメッセージは，200 OKと404 Page not found だけ知っておけば良いでしょう．

ファイルが見つかり，正常にレスポンスが返信できれば，200 OKというステータスコードと メッセージが返されます． 一方，リクエストされたファイルが見つからなかった場合は，404 Page not found というステータスコードとメッセージが返信されます．

ファイルが見つかった，見つからないに限らず，レスポンスのボディで，ファイルの内容が返信されます． ファイルが見つからない場合は，専用のページ（例えば，404.html）というファイルが読まれ， その内容をボディとして返信します． なお，ヘッダとボディはリクエストと同じく，空行（\r\n）で区切られます．

実行例

$ java -jar web-server.jar .

実際に動作させてみましょう． web-server.jarをクリックし， プログラム例をダウンロードしてください． ダウンロードしてできた web-server.jarが置かれているディレクトリに移動し （今いるディレクトリにweb-server.jarを移動させ）， javaコマンドの-jarオプションで実行しましょう． 最後に，.を忘れずに．

次に，ブラウザを開き，http://localhost:18080/ファイルにアクセスしてみましょう． ファイルの部分は，web-server.jar を動かしたディレクトリに置かれているファイルを指定してください．

ヒント

すべてを説明するのは時間的に無理がありますので， WebServer.javaと ClientHandler.java をダウンロードし，ClientHandler.javaを編集しましょう． ClientHandler.javaのrespondメソッドを編集しましょう． ここが，ブラウザから送られてきたリクエストに従って， レスポンスを返す処理を行う部分です．

コメントの内容に従って，ファイルを読み，outを使い， ファイルの内容を書き出しましょう． 書き出す先は，ブラウザへのネットワークです．

$ java WebServer .

さて，完成すれば，左のように実行して，ブラウザから，例えば， http://localhost:18080/WebServer.javaにアクセスしてみましょう．

参考資料

• コマンドライン引数
• ファイルを開く
• 例外機構
• Hyper Text Transfer Protocol (Wikipedia)