FC2ブログ

Excelじゆうちょう

Excelのお絵描きツール『りっぷ2(りっぷつぅ)』のサポートページ、まずは「はじめに」をご覧ください。 [NewEntry] [Admin]

記事更新カレンダー

12 « 2019-01 « 02
- - 1 2 3 4 5
6 7 8 9 10 11 12
13 14 15 16 17 18 19
20 21 22 23 24 25 26
27 28 29 30 31 - -

やたらに多いカテゴリ

比較的新しい記事

新しいコメント

ありがたいブログ拍手

拍手コメント一覧(拍手はしない)

さみしいトラックバック

申し訳ないプロフィール

申し訳ない

管理人  [ 申し訳ない ]

pxivもやってます
リンクの一番上からのぞきに来てください
※閲覧にはユーザー登録が必要です

RSSってなんぞ?

広告は消せないらしい

FC2Ad

        --------       スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

        2011-07-31       基本情報(平23春)午後問11

平成23年度特別試験の基本情報技術者試験の午後問の解説です。

ただし、表計算とJavaに限る!

あれ、 この前 も似たようなこと言ってたような…

えっと、申し訳ないです。
前言撤回してJavaも解説してみようと思います。
今日は特別、許してください。



↓平成23年特別試験基本情報技術者試験午後問題問11↓
基本情報(平23春)午後問51
基本情報(平23春)午後問52
基本情報(平23春)午後問53
基本情報(平23春)午後問54
基本情報(平23春)午後問55
基本情報(平23春)午後問56

今回のJavaの問題は少々難しいかもしれません。
というのも、プログラムの内容が抽象的なのです。
文字列を扱うふたつのクラスがあり、両者の違いを確認しながら、最終的に実行時間の違いを考えるというものです。
問のほとんどは文字列クラスのプログラムです。
ですから、これらのクラスがどういった動きをするのかというのを理解できるかで、解けるかどうかが決まってきます。
今回は珍しくコンストラクタやsuperに関する設問はありません、直球勝負です。

各設問を考える前に、それぞれのプログラムを見てみることにしましょう。

・[プログラム1]インタフェースAppedableCharSequence
文字列を扱うクラスが実装するインタフェースです。
これを実装するクラスは、ここで定義されているメソッドの中身ををすべて記述しなければなりません。
メソッドの動きは[プログラムの説明]の(1)~(4)で説明されています。
ここがこの問の要ですからね、よく読んでおきましょう。

・[プログラム2]クラスArrayAppedableCharSequence
文字列を一連の配列として格納するクラスです。
これはすぐにイメージがわくと思います。

最初は10文字(EXT_SIZEが10だから)の配列を用意し、文字列を追加していっぱいになったら、そのたびに10文字分ずつ拡張していきます。

●初期状態
[ , , , , , , , , , ]

●'a'を追加
[a, , , , , , , , , ]

●どんどん要素を追加
[a,b,c,d,e,f,g,h,i,j]

●次の要素'k'を追加したい場合は、配列を拡張してから追加
[a,b,c,d,e,f,g,h,i,j,k, , , , , , , , , ]

このような感じで、10文字ずつどんどん配列が長くなっていきます。
ですので、この配列に要素を追加したり取り出したりする場合は、何文字目かを指定するだけでOKです。

・[プログラム3]クラスListAppedableCharSequence
文字列を一定数ごとにまとめて、それらを順番に連結させてひとつづりの文字列として扱うクラスです。
こちらは少しイメージしづらいと思います。

最初は10文字(EXT_SIZEが10だから)の配列を用意し、文字列を追加していっぱいになったら、そのたびに10文字の配列をnextで連結させます。

●初期状態
[ , , , , , , , , , ]

●'a'を追加
[a, , , , , , , , , ]

●どんどん要素を追加
[a,b,c,d,e,f,g,h,i,j]

●次の要素'k'を追加したい場合は、新しい配列を用意して連結
[a,b,c,d,e,f,g,h,i,j]…(next)…[k, , , , , , , , , ]

このような感じで、10文字ずつの配列がどんどん連結されていきます。
ですので、この配列に要素を追加したり取り出したりする場合は、何連結目の何文字目かを考えなければなりません。

・[プログラム4]クラスTest
これは実行時間を測定するだけのクラスです。
'a'から'z'までの26文字の小文字アルファベットを順番に追加しながら決められた回数を繰り返して('z'の次は'a'へ戻る)、ArrayAppedableCharSequenceとListAppedableCharSequenceでの実行時間を画面に出力します。

【設問1】
・[プログラム2]クラスArrayAppedableCharSequence
まずはArrayAppedableCharSequenceを見ていきます。
ここはそんなに難しくありません。
ですから、空欄もひとつだけです。

public ArrayAppedableCharSequence()は、初期化です。
最初に10文字(EXT_SIZEが10だから)の配列を用意します。

public char charAt(int index)は、indexの位置にある要素を返します。
indexが範囲外にあるとエラーが発生します。
戻り値のdata[index]はそのまま配列の位置を参照しています。
配列の要素は0から始まりますので、1文字目を取得したい場合はcharAt(0)とします。

public int length()は、文字列の長さを求めます。
単にlengthを返すだけ、ただそれだけです。

public AppedableCharSequence append(char c)は、文字列の最後尾に要素を追加します。
もし配列がいっぱいだったら、10文字分配列を拡張してから、要素を追加します。
配列を拡張する方法は、新しく10文字分大きい配列を別に用意し、中身をコピーしてから元の配列と入れ替えます。
[a]は、中身をコピーする際の繰り返しのendが入ります。
ループのカウンタiは0から、文字列の長さをあらわすlengthは1から、よってlengthは含めずに0からlength未満まで繰り返します。

■a、ウ

public String toString()は、格納した文字列を返します。
格納した文字列を返すだけ、ただそれだけです。

・[プログラム3]クラスListAppedableCharSequence
次にListAppedableCharSequenceを見ていきます。

public ListAppedableCharSequence()は、初期化です。
新しく作成しているBucket()が、連結する10文字ずつの配列です。

public char charAt(int index)は、indexの位置にある要素を返します。
indexは文字列の位置を通し番号で指定します。
よってまずはindexが何連結目を示すのかを求める必要があります。
それをしているのが、getBucket(index)です。
メソッドでいうと、private Bucket getBucket(int index)です。
getBucketに通し番号を与えると、通し番号の要素を含むBucket(10文字の文字列)が返ります。
ですから、indexが範囲外でなければgetBucket(0)もgetBucket(9)も同じBucketが返ってきます。
最終的に10文字の中から何文字目かを指定して、このメソッドの返り値となります。
それが[b]で、各Bucketが10文字分ありますから、int indexを10で割った余りを計算すればいいわけです。

■b、イ

public int length()は、文字列の長さを求めます。
単にlengthを返すだけ、ただそれだけです。

public AppedableCharSequence append(char c)は、文字列の最後尾に要素を追加します。
もし配列がいっぱいだったら、10文字分配列を新しく連結してから、要素を追加します。
配列がいっぱいかどうかは、一番後ろに連結されているBucketを調べる必要があります。
そこで、[c]の部分に文字列の長さを示すlengthを指定して最後のBucketを調べます。
ただし、getBucket(int index)の引数は0から始まる値でしたので、1から始まるlengthから1を減算しておきます。

■c、ウ

public String toString()は、格納した文字列を返します。
格納した文字列を返すだけ、といいたいところですが、10文字ずつに区切られているBucketをひとつにまとめないといけません。
それをしているのが入れ子になっているforループなのですが、これがなかなかくせものです。
この問一番の難問ではないでしょうか。

外側のループではBucketの数だけ、内側のループでは各Bucketの要素数だけ繰り返します。

外側の繰り返しはintを0からlength % EXT_SIZEでよさそうな感じもしますが、そうはしていません。
lengthからループごとに処理した文字数分だけ減算することで、カウンタのlenで残りの文字数を管理しています。
処理した文字数分とはsizeのことです、最後のBucketならそこに格納されている要素数、それ以外なら10(EXT_SIZE)になります。
外側のループ直後でsizeに代入しているのが、内側のループで繰り返す回数にもなります。

内側のループでは、各Bucketの要素を順番に取り出しています。
data[j]は出力するための文字列、bucket.data[i]はBucketの文字列です。
dataのjはひとつづりの文字列になりますから、文字数の通し番号になります。
具体的には、0からlength - 1の値まで増えていきます。
bucket.dataのiは、各Bucketの要素番号になります。
具体的には、最後のBucketは0から要素数 - 1まで、それ以外なら0から9まで繰り返します。
[d]はjの開始の値を指定します。
jは通し番号ですから、前の外側のループで格納した続きから再開しなければなりません。
元々の文字数はlengthですね、そこから残りの文字数lenを減算すれば求められます。

■d、カ

public Bucket getBucket(int index)は、もう説明しましたので省きます。

クラスprivate static class Bucketも、省きます。
10文字格納するBucketクラスを定義しています。

・[プログラム4]クラスTest

最後に、Testを見てみます。

static final int[] TIMESは、繰り返す回数です。
5000回、10000回、50000回、100000回を繰り返して実行時間を計測します。

public static void main(String[] args)は、このプログラムを開始する最初のメソッドです。
拡張for文でTIMESの数だけ繰り返して、メソッドmeasureTimeで実行時間を計測します。

static void measureTime(int n,[e] a)は、実行時間を計測するメソッドです。
System.currentTimeIllis()で現在の時間をミリ単位で取得します。
その後一連の処理をした後、もう一度現在の時間をミリ単位で取得し、その差分で実行時間を計測します。
空欄の[e]には、繰り返し処理をさせる対象のクラスを指定します。
クラスArrayAppedableCharSequenceとクラスListAppedableCharSequenceでしたね。
このふたつは異なるクラスですが、同じ型で指定します。
共通といえば、両者は同じインタフェースを実装しています。
AppendableCharSequenceですね、これでOKです。

■e、ア

【設問2】
問題文にある通り、一番最後のBucketを格納しておくlastを用意します。
コンストラクタはクラスが生成された時に実行されますから、この時点ではBucketは連結されていません。
今あるbucketlistをそのまま代入すれば、すなわち最後のBucketということになります。

■f、ア

[g]の直前のlast.next = new Bucket()で新しいBucketがlastの次に連結されます。
ですが、ここでは連結されただけで、lastが参照しているのは新しいBucketのひとつ手前のままです。
そこで、[g]の行でlast.nextを改めて代入しておきます。

■g、エ
スポンサーサイト

コメント

コメントの投稿

管理者にだけ表示を許可  

トラックバック

http://likep.blog63.fc2.com/tb.php/227-31e81cc4

-

管理人の承認後に表示されます

 | HOME | 

上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。