サラリーマンの３大資格は、
英語・会計・IT
です。
そこで、ここではITの基礎知識を身に付けるための情報をお届けします。
基本情報技術者は、４０台から目指す試験ではないのですが、開発者の基本知識です。
コンピュータが動く仕組みを理解することは、コンピュータを利用する上でも役立ちます。
コンピュータ利用者にとってはワンランク上の知識ですが、勉強してみましょう。
基本情報技術者試験平成19年秋午後問3
システムの開発者を目指す人にとっても、基本的な知識とはいえ専門家の入り口です。
やはり、皆さん、悩んでいる人が多いです。
基本情報処理のアルゴリズム問題です。下記問題が解ける方よろしくお願いいたしま...
基本情報処理のアルゴリズム問題です。下記問題が解ける方よろしくお願いいたします。
[ﾌﾟﾛｸﾞﾗﾑの説明]
与えられた文字列内に、ある文字ﾊﾟﾀｰﾝpが含まれているかどうかを検索する副ﾌﾟﾛｸﾞﾗﾑKENSAKU
である。文字列Tとﾊﾟﾀｰﾝpは大文字のｱﾙﾌｧﾍﾞｯﾄのみからなる文字型の配列で書く文字列の添字は1から始まる
ex)文字列Tが"TICTTACTOC",ﾊﾟﾀｰﾝpが"TAC"であった場合、まずは"TIC"と"TAC"を照合。
→2文字目で不一致検出
→"TIC"の末尾文字である"C"は、"TAC"の末尾以外どこにも含まれていない
→次の照合は、3文字分ずらした"TTA"から開始すればよい
というように、次の照合開始位置を状況に応じて複数文字分ずらしていく。このﾙｰﾙに従うと以降は
"TTA"と"TAC"を照合
→2文字目で不一致検出
→"TTA"の末尾文字である"A"は"TAC"の2文字目に含まれている
→"A"の位置を合わせるように、次の照合開始位置を1文字分ずらす
→"TAC"と"TAC"の照合
→一致検出
となる
このずらす文字数の情報は予め配列CTABLE及び配列STABLEに用意しておく
CTABKEとSTABLEは、添字が等しい要素どうしが対応しており、CTABLEには「ﾊﾟﾀｰﾝpに登場する各文字」
を登録する
また、STABLEには、「文字列T中の照合範囲右端の文字に応じて次の照合文字位置を何文字分ずらすか」
を登録する（CTABLEの文字列の終了は"#"で表す）
[ﾌﾟﾛｸﾞﾗﾑ]
01 ○大域:文字型:CTABLE[26],整数型:STABLE[26]
02 ○KENSAKU(文字型:T[],文字型:P[],整数型:M,整数型:N,整数型:R)
03 ○整数型:I,J,K
04
05 ･I ← 1
06 ･R ← -1
07 ■I≦M-N+1 and R=-1
08 ｜･J←1
06 ｜■【 ａ 】
07 ｜｜･J←J+1
08 ｜■
09 ｜▲J>N
10 ｜｜･R←1
11 ｜--------
12 ｜｜･K←1
13 ｜｜■【 ｂ 】
14 ｜｜｜･K←K+1
15 ｜｜■
16 ｜｜･I←I+STABLE[K]
17 ｜▼
18 ■
【ａ】に関する回答群
ア J≦I and T[I+J-1] = P[J-1]
イ J≦N and T[I+J-1] = P[J-1]
ウ J＜I or T[I+J] = P[J]
エ J＜N or T[I+J] = P[J]
オ J≦I and T[I+J-1] = P[J]
カ J≦N and T[I+J-1] = P[J]
キ J＜I or T[I+J-1] = P[J]
ク J＜N or T[I+J-1] = P[J]
【ｂ】に関する回答群
ア CTABLE[K] = T[I]
イ CTABLE[K] ≠ T[I]
ウ CTABLE[K] = T[I+N-1]
エ CTABLE[K] ≠ T[I+N-1]
オ STABLE[K] = I+N-1
カ STABLE[K] ≠ I+N-1
以上、よろしくお願いいたします。
- 回答 -
基本はバブルソートですよ。
あんまりややこしく考えないように、それにこれができても、基本情報の午後で出題されるとは限りません。
J＝Pのカウントアップ添え字
I＝Tのカウントアップ添え字
N＝Pの最終No（要素数いわばPの全事象です）
M＝Ｔの最終No（要素数いわばTの全事象です）
と考えると、バブルソートと組み合わせてご理解できますね＾＾
バブルソートと異なるのは、合った場所を次回のPの初めの場所となるわけです。
かみ合った場合はJ←J+1を実行しますので、この【a】には合う場合を入れればよいわけです。
えらそうな事言ってはずしたらごめんなさい。
【a】=「カ」ではないでしょうか。
それと、この擬似言語の文中に、CTABLEが使われていません。よって、【b】にはCTABLEが使われた条件が入ってきます。（笑）
作った人はアホかと思うくらいかなりヒント与えちゃってますね＾＾
IはSTABLEで位置を格納しています。
【b】=「ウ」or「ア」
のどちらかとなるでしょうね。
多分【b】=「ウ」でしょう。
解答を見ないで答えたので、誤っているかもしれませんが、考え方は以上の様になると思われます。
N（Pの要素数）が使われている理由がよくわかりませんが、こういうの見たことあります。
第一テーブルは文字シフト用
第二テーブルはパターンシフト用でしょう。
一度やって間違えたことがありますね。むつかしいですね。
多分「＃」がある以上、使うでしょうね。ですので、【b】は終端文字比較ではないでしょうか？
出題は相手の戦術より戦略を気にしてください。
それと30分で解けないと、別の問題に負荷がかかります。
（この記事は「Yahoo知恵袋」より引用させて頂きました）
すぐに分からなくても、がんばりましょうね！！
今回は以上です。
では、また次回まで。