2016年度 発展プログラミング演習 練習問題 初級
目次
1. コマンドラインで受け取った文字列が特定の文字列かを確認する．
問題
次のプログラムを作成してください．
コマンドラインで渡された文字列が特定の文字列（"KSU_AP"）であれば，
「渡された文字列は"KSU_AP"です」と出力してください．
特定の文字列でなければ，「渡された文字列は"KSU_AP"ではなく，"(実際に渡された文字列)"です．」
と出力するプログラムを作成してください．
コマンドライン引数で複数の文字列が渡された場合，全ての文字列に対して判定を行ってください．
クラス名は，ComparingStringとしてください．
実行例
$ java ComparingString hoge KSU KSU_AP KSU_AP2 渡された文字列は "KSU_AP"ではなく"hoge"です． 渡された文字列は "KSU_AP"ではなく"KSU"です． 渡された文字列は "KSU_AP" です． 渡された文字列は "KSU_AP"ではなく"KSU_AP2"です．
参考資料
2. 乱数値100個の統計．
問題
0以上，1000未満の乱数を100個取得してください． それらの合計値，最大値，最小値，平均を求めてください．
出力は，まず，合計，最大値，最小値，平均を１行で出力してください． その次に，得られた乱数値を出力してください．ただし，10個出力するごとに改行を入れてください．
クラス名は，StatsValues としてください．
実行例
$ java StatsValues 合計: 45262, 最大値: 995, 最小値: 11, 平均値: 452.620000 252 37 553 448 504 144 969 928 177 262 836 15 198 496 650 977 102 630 348 351 820 59 288 435 622 677 103 588 576 683 916 138 154 528 179 411 578 740 715 372 351 105 41 203 596 746 195 153 469 328 166 189 754 862 541 84 165 428 567 76 848 730 947 439 376 258 330 365 896 144 688 27 380 573 377 752 19 70 965 605 551 355 103 860 629 660 528 465 995 134 154 574 11 763 268 443 723 872 233 674
ヒント
平均をDouble型として求めるには，Integer
で表される合計値をDoubleに変換する必要があります．
new Double(sum)でDouble
に変換でき，それ以降Double型として扱われるようになります．
DoubleとIntegerでは，Double
の方が扱える範囲が広く，範囲が広い方に合わせられるためです．
数値を揃えるには、printfのフォーマッタで、
"%d" ではなく、"%4d"
を利用してください。整数値を４桁で出力する、という命令です。
同じく、３桁で出力したければ、"%3d"、
足りない桁を0で埋めたい（パディング; padding）したければ、
"%04d"という命令が利用できます。
挑戦課題
- 初期化，計算，出力の3つのメソッドを使って実現しましょう．
StatsValuesにフィールドを宣言せずに実現してみましょう．
参考資料
- Javaプログラムの基本形
- 乱数の求め方
-
独自の型の定義方法
- 挑戦課題2の実現に必要．
3. 台形公式による積分計算を利用した$\pi$の計算．
問題
台形公式を用いて，$\pi$を計算してください．
まず，半径1の円を表す式$x^2＋y^2＝1$を考えましょう．
式を変形すると，$y= \sqrt{1 - x^2}$となります．
これの$0 \leq x \leq 1$の範囲を考えます．
右図のように，この式で描かれるグラフに内接するいくつかの台形を考えます．
右図では，2つの台形（1つは三角形のように見えますが，上底（右側の高さ）が0に近い台形と考えてください）
があり，横幅は$x_i - x_{i - 1}$，高さは$h_{i-1}$，$h_i$です（$h_{i-1} > h_i$）．
このとき，一つの台形の面積は，$\frac{(x_i - x_{i - 1}) \times (h_{i-1}+h_i)}{2}$です．
高さを求めるには，その時の$y=\sqrt{1 - x^2}$にその時の$x_i$の値を代入することで求められます．
これをすべての台形について求めます．そして，求めたすべての台形の面積を足し合わせると，
$\frac{\pi}{4}$の近似値が得られます．得られた値に4を掛けると$\pi$が得られます．
なお，すべての$i$において，横幅の間隔 $(x_i - x_{i-1})$ は同じ値（等間隔）です．
さらに，横幅により狭い値を指定することで，値を$\pi$に近づけられるようになります．
さて，この方法で，$\pi$を求めるプログラムを作成しましょう．クラス名は，
TrapezoidalRulePiとします．
作成する際に，コマンドライン引数で台形の横幅を指定できるようにしてください．
もし，コマンドライン引数で値が指定されなければ，0.001が指定されたものとしてください．
実行例
$ java TrapezoidalRulePi 0.01 pi = 3.1375956845831103 $ java TrapezoidalRulePi pi = 3.141591477698228 $ java TrapezoidalRulePi 0.001 pi = 3.1414660465553967 $ java TrapezoidalRulePi 0.0000001 pi = 3.141592654152668
ヒント
-
String型をDouble型に変換するにはDouble doubleValue = new Double(string)で実現できます． -
平方根は，
Math.sqrtで計算できます．Double givenValue = 2.0; // value には，1.41421356... が入る． Double value = Math.sqrt(givenValue);
参考資料
4. モンテカルロ法による$\pi$の計算．
問題
モンテカルロ法により，$\pi$を計算しましょう． モンテカルロ法とは，乱数を用いて統計計算を行う方法です． ここでは，$\pi$を求めます．次のアルゴリズムに従って実装してください．
- 0.0〜1.0の乱数を2つ取得し，$x, y$とします．
- 原点と$(x, y)$の距離を計算します．距離は，$\sqrt{x^2+y^2}$で求められます．
- 計算した距離が1よりも小さい場合，ヒットしたとみなします
- 距離が1以下の場合，点は円の内側に存在します（ヒットした）．
- 距離が1よりも大きな場合，点は円の外側に存在します．
- 1〜3を規定回数繰り返します．
- ヒットした回数の割合を計算します．
- この割合が$\pi/4$になるので，4を掛け$\pi$を計算します．
右図のように半径1の円の第１象限に注目します．
0.0から1.0の乱数を2つ取得して，$x, y$とします．右図の点が得られた乱数値から求められた座標とします．
求められた座標と原点との距離を計算します．距離は，$\sqrt{x^2+y^2}$で求められます．
この距離が1よりも小さい場合，円の内側に存在するため，ヒットしたものとします．
一方，円の外側にある場合は，ヒットしないものとします．
これを規定回数（デフォルトは1000回とします．）繰り返してください．
このとき，ヒットした確率は $\pi/4$に近付いていくため，
ヒットした確率に 4をかけると$\pi$の近似値が得られます．
クラス名は，MonteCarloPiとします．
引数に値が指定された場合，その値だけ繰り返してください．
値が何も指定されない場合は，1,000回の繰り返しとします．
実行例
$ java MonteCarloPi pi = 3.10800 $ java MonteCarloPi pi = 3.17200 $ java MonteCarloPi 10000 pi = 3.13916 $ java MonteCarloPi 100000 pi = 3.14776 $ java MonteCarloPi 1000000 pi = 3.14127 $ java MonteCarloPi 10000000 pi = 3.14229
計算結果は必ずしもこの通りではありません．
ヒント
- 0から1の乱数を取得するには，
Random型のnextDoubleを利用します． -
平方根は，
Math.sqrtで計算できます．Double givenValue = 2.0; // value には，1.41421356... が入る． Double value = Math.sqrt(givenValue);
-
Integer型の変数valueをDoubleに変換するには，Double doubleValue = new Double(value);で実現できます． -
String型の変数stringをDouble型に変換するにはDouble doubleValue = new Double(string);としてください．
参考資料
5. ユークリッド互除法による最大公約数．
問題
ユークリッド互除法（Euclidean Algorithm）により2つの自然数の最大公約数 （GCD; Greatest Common Divisor）を求めましょう． 最大公約数とは，共通の約数のうち最大のものを指します．
ユークリッド互除法は次の漸化式で与えられます（mod は割った余りを表す演算子です）． \[ \gcd(a, b) = \begin{cases} a & b = 0\\ \gcd(b, a \mod b) & b \geq 1 \end{cases} \]
ユークリッド互除法は，$a=qb+r$ において， $\gcd(a, b)=\gcd(b, r) (a \geq b)$が成り立つというものです．
以下，$\gcd(a, b)=\gcd(b, r)$の証明です．
-
$a, b$ がともに $m$の倍数であれば，$r = a - bp$も$m$の倍数です（右辺は$m$で割り切れる）．
つまり，$\gcd(a, b) \leq gcd(b, r)$が成り立ちます． -
$b, r$ がともに $m$の倍数であれば，$a = qb + r$も$m$の倍数です（右辺は$m$で割り切れる）．
つまり，$\gcd(a, b) \geq gcd(b, r)$が成り立ちます． -
以上，二つから，$\gcd(a, b) \leq gcd(b, r)$，$\gcd(a, b) \geq gcd(b, r)$の両方が成り立ちます．
すなわち，$\gcd(a, b)=\gcd(b, r)$となります．
さて，この式を用いて，最大公約数を求めるプログラムを作成しましょう．
クラス名は，EuclideanAlgorithmとします．引数に２つの整数値が与えられるものとします．
実行例
$ java EuclideanAlgorithm 15 5 gcd(15, 5)=5 $ java EuclideanAlgorithm 20 12 gcd(20, 12)=4 $ java EuclideanAlgorithm 600 12 gcd(600, 12)=12
挑戦課題
- 与えられた数値の大きさが，$a \leq b$であっても正しい答えを出力できるようにしましょう．
- 求めた最大公約数を利用して，最小公倍数（LCM; Least Common Multiple）を求めましょう． 最小公倍数は，$\frac{ab}{\gcd(a, b)}$で求められます．
ヒント
-
String型の変数stringをInteger型に変換するにはInteger integerValue = new Integer(string);としてください．
参考資料
6. lsコマンドの作成．
問題
lsコマンドのように，指定されたディレクトリ一覧を表示するプログラムを作成しましょう．
もし，ディレクトリが指定されなかった場合，カレントディレクトリの一覧を表示してください．
もし，ファイルが指定された場合，そのファイルの名前のみ（そのファイルのパスは含まない）
を出力してください．
クラス名は，FileListとしてください．
実行例
$ ls find library training $ java FileList find library training $ java FileList library Book.java books.csv History.java HistoryCreator.java Library.java LibraryUtil.java User.java UserManager.java $ java FileList library/Book.java Book.java
参考資料
7. wcコマンドの作成．
問題
wcコマンドのように，コマンドライン引数により与えられたテキストファイルの文字数，
単語数，行数を出力するプログラムを作成せよ．
また，コマンドライン引数で複数個のテキストファイルが渡されたとき 文字数，単語数，行数の合計を出力せよ．
クラス名は，WordCountとする．
実行例
$ cat sample1.txt
abcdefg
$ cat sample2.txt
ABCDEFG
1234567890
$ wc sample1.txt sample2.txt
1 1 8 sample1.txt
3 2 20 sample2.txt
4 3 28 total
$ java WordCount sample1.txt
Char Word Line
7 1 1 sample1.txt
$ java WordCount sample1.txt sample2.txt
Char Word Line
7 1 1 sample1.txt
17 2 2 sample2.txt
24 3 3 Total
上記のように，必ずしもwcコマンドの出力と一致している必要はありません．
wcコマンドとは改行の数え方が違うのが出力が異なる理由です．
(BufferedReaderのreadLineを使うと異なります)
左のプログラムで使っているファイルが必要な場合は， sample1.txt， sample2.txt から取得してください．
ヒント
String line = // ... 文字列を取得する．
String[] terms = line.split("[ \t]");
文字列をスペースとタブで区切るには，以下の方法（String型の
splitメソッド）が利用できます．
termsという配列に区切られた各値が入れられています．
"[ \t]"は、正規表現
でスペース、もしくはタブ文字を表しています。
line.split(" ")であれば、スペースで区切ります。
この方法でも良いです。
なお，\が¥になっていると，期待通りに動かない場合があります．
基本的には，\と¥は同じですが，Mac OSの場合，両者が区別されることもあります．
ですので，¥ではなく，\を使うようにしましょう．Optionキーを押しながら¥を押すことで，
\が出力されるようになります．
挑戦課題
以下のオプションを与えたとき，行数，単語数，文字数のうち， 指定されたもののみを出力するようにしてください． 何もオプションが指定されない場合，3つを出力するものとします． どのオプションが指定された場合でも，合計を出力する条件の場合は， 変わらず合計を出力してください．
-lもしくは--linesが指定された場合，行数を出力する．-wもしくは--wordsが指定された場合，単語数を出力する．-cもしくは--charsが指定された場合，文字数を出力する．-hもしくは--helpが指定された場合，ヘルプメッセージを表示して終了する．-
wcコマンドと同じ出力になるようにプログラムを更新してください．BufferedReaderのreadLineを使わず，1文字ずつ読むと良いでしょう．- 空白文字（スペース，タブ，改行）で単語の区切りとしてください．
- 連続した空白文字をどのように扱うかを考えましょう．
-
改行を意味する文字は３種類存在します（
\r，\n，\r\n）． どの改行文字が使われていても適切に扱うようにしましょう．
参考資料
8. Catコマンドの拡張．
問題
Findプログラム3日目の
練習問題1で作成した
Catコマンドを次の指示に従って拡張してください．
-nもしくは，--numberオプションをつけると行番号を表示する．-Nもしくは，--nameオプションをつけるとファイル名を表示する．-bもしくは，--ignore-blankオプションをつけると空行を無視する．-hもしくは，--helpオプションをつけるとヘルプメッセージを表示し，終了する．
実行例
$ cat sample1.txt
abcdefg
$ cat sample2.txt
ABCDEFG
1234567890
$ java Cat --number sample2.txt
1: ABCDEFG
2:
3: 1234567890
$ java Cat --name --number sample1.txt sample2.txt
====== sample1.txt ======
1: abcdefg
====== sample2.txt ======
1: ABCDEFG
2:
3: 1234567890
$ java Cat --name --number -b sample1.txt sample2.txt
====== sample1.txt ======
1: abcdefg
====== sample2.txt ======
1: ABCDEFG
3: 1234567890
左のプログラムで使っているファイルが必要な場合は， sample1.txt， sample2.txt から取得してください．
参考資料
9. 与えられたテキストファイルに現れる単語の頻度を求める．
問題
与えられたテキストファイル（英文）の中に現れる単語の頻度を求めるプログラムを作成してください． 単語の頻度とは，その単語が文書中に何回現れたかを示す値です．
実行例
$ cat string.txt String class represents character strings. All string literals in Java programs, such as "abc", are implemented as instances of this class. Strings are constant; their values cannot be changed after they are created. String buffers support mutable strings. Because String objects are immutable they can be shared. $ java FrequencyViewer string.txt "abc",: 1 constant;: 1 be: 2 string: 4 instances: 1 .... 以下略
左のプログラムで使っているファイルが必要な場合は，
string.txtから取得してください．
クラス名は，FrequencyViewerとしてください．
ヒント
String line = // ... 文字列を取得する．
String[] terms = line.split("[ \t]");
文字列をスペースとタブで区切るには，以下の方法（String型の
splitメソッド）が利用できます．
termsという配列に区切られた各値が入れられています．
"[ \t]"は、正規表現
でスペース、もしくはタブ文字を表しています。
line.split(" ")であれば、スペースで区切ります。
この方法でも良いです。
なお，\が¥になっていると，期待通りに動かない場合があります．
基本的には，\と¥は同じですが，Mac OSの場合，両者が区別されることもあります．
ですので，¥ではなく，\を使うようにしましょう．Optionキーを押しながら¥を押すことで，
\が出力されるようになります．
単語をキーとして，その出現回数をバリューとするMapを使って頻度を数えてみましょう．
キーを指定してバリューを取得するとき，値が入っていなければ（null）
であれば1をバリューとして追加（put）します．
バリューとして値が入っていれば，その値に1を加算し，バリューを更新（put）
しましょう．すべての単語に対してこの処理を行えば，頻度を求められます．
最後に結果を出力しましょう．
挑戦課題
- 大文字・小文字を区別せずに頻度を求めましょう．
- コンマやピリオド，コロン，セミコロンは除外して頻度を求めてみましょう．
参考資料
10. ファイルを逆順に表示するコマンド
問題
ファイルを逆順に表示するコマンドtacを作成してください．
複数のファイルが指定された場合，各ファイルの内容を逆順に表示してください．
クラス名は Tac（catの逆）とします．
実行例
$ cat sample2.txt ABCDEFG 1234567890 $ java Tac sample2.txt 1234567890 ABCDEFG
左のプログラムで使っているファイルが必要な場合は， sample2.txtから取得してください．
挑戦課題
次のオプションを解析するようプログラムを改良してください．
-nもしくは，--numberオプションをつけると行番号を表示する．-Nもしくは，--nameオプションをつけるとファイル名を表示する．-bもしくは，--ignore-blankオプションをつけると空行を無視する．