大滝みや子先生 かんたんアルゴリズム解法

質問

試験が近いですが、分かる方いましたらご教授お願いします。
初版版（第一版）のページ番号と内容を記載します。

P,140　(4)部分文字列の検索　TRY (L-1)だけ増えているのL-1はどこから出たか？

P,160　(8)ハッシュ法（オープン）アドレス方式　
　　　a‥Table[i]・key≠kではないのか？
　　　b‥M＝iではないのか？

P,172　実線(5)インデックス　設問２‥解説の＋１が？１９７回ではないのか？
　　　　H１３春　午後問４改　設問３‥問題の処理部一行目の変位が理解不能

P,177　実線(6)クイックソート　設問１‥Ret←k,Ret←Minを入れる理由不明
　　　　H１４春　午後問４改　　設問２‥クイックソートの動作が不明

回答No.3

jjon-com

--------
●K=InData.Key＝空白と考えればいいのでしょうか？　それとも、上記の状態になったら…

意味不明。
問題文で，Table「配列の空き要素には，データとして使わない空白(SPACE)が格納されている」と説明されており，空白が格納されているのは Table[] です。K＝空白にもInData.Key＝空白にもなりません。

--------
●解説に記載してある＋１は最初のΒ（８００）という考えでよいのでしょうか？

はい，よいでしょう。

●800～997の個数は197ではなく198。の方が分かりやすいです。

同じですよ。11～27の範囲に数値はいくつ？と問われて，即座に17個と正解を出せる人は，11の左隣の10をゼロベースにして27－10を計算しているんじゃないですか。それに対して左隣の10を用いずあくまで11を用いるなら 27－11＋１となって，解説文の式の形と同じです。

--------
●問題に合わせると…これでよろしいでしょうか？

はい，よいでしょう。
（要素数と要素を区別して書き分けていないので実に分かりづらい文章でした）

お礼

遅くなりましたが、ありがとうございました。

回答No.2

jjon-com

●L-1はどこから出たか？

内側の二重ループから。
検索対象文字列の検索開始位置から変化する添字がKで，検索文字列の先頭から変化する添字がL。
L＝1のとき検索開始位置からの隔たりは0，
L＝2のとき検索開始位置からの隔たりは1，
よって，内側の二重ループを脱出してLの値が決定したとき，
検索開始位置からの隔たりはL-1。

●a‥Table[i]・key≠kではないのか？

違う。このループを脱出する条件は次のとおり。
「Table[i]＝SPACE で格納のための空き要素が見つかったとき」
　または
「Table[i].Key＝K で同じキーの重複格納が判明したとき」

擬似言語における繰返し処理は，ループ脱出条件ではなくループ継続条件を指定するので，上記の条件式を否定したものを指定すればよい。

■ not (Table[i]＝SPACE or Table[i].Key＝K)

この書籍に登場する ■▽(条件式) という書式は，
情報処理技術者試験における ■not(条件式) に対応する旨，p.76で解説されている。

●b‥M＝iではないのか？

違う。p.161の問題文より，Mはデータの個数である。添字ではない。

●設問２‥解説の＋１が？１９７回ではないのか？

違う。空欄【ａ】の解答「オ 添字2 ← 一次[添字1 －１].ポインタ ＋１」が実行されることで添字2は800を指し，添字2＝997 でdecibelを発見する。800～997の個数は197ではなく198。

●設問３‥問題の処理部一行目の変位が理解不能

「一次インデックスは，二次インデックスからある間隔で英単語を抜粋し」(p.172)たものである。検索する単語の出現確率が均一である場合，探索効率がもっとも良いのは，二次インデックスから均等の間隔で英単語を抜粋して一次インデックスに登録することである。
具体例として，一次要素数＝10，二次要素数＝103の場合を想定すると，均等に抜粋する方法として次の２つの案をすぐに発想できる。

案１）103÷10＝10 なので 10個ごとに抜粋して，一次[1]～一次[9] に登録。ただしp.173図１より，一次[10]は最後の要素を指さねばならないので，一次[10]は二次[103]を指すよう登録。（一次[9]＝90番目，一次[10]＝103番目なのでこの間隔が長い）

案２）103÷９＝11 として 11個ごとに抜粋して，一次[1]～一次[9] に登録。ただしp.173図１より，一次[10]は最後の要素を指さねばならないので，一次[10]は二次[103]を指すよう登録。（一次[9]＝99番目，一次[10]＝103番目なのでこの間隔が短い）

この問題では案２の発想を採用したということ。

●設問１‥Ret←k,Ret←Minを入れる理由不明
●設問２‥クイックソートの動作が不明

クイックソートのアルゴリズムの解説を参照。
http://ja.wikipedia.org/wiki/%E3%82%AF%E3%82%A4%E3%83%83%E3%82%AF%E3%82%BD%E3%83%BC%E3%83%88

お礼

ありがとうございます。お蔭様でほとんど理解できました！
念のために私の理解が正しいかを確認するため、下記に何点か解釈が怪しい点を記載します。

＞●a‥Table[i]・key≠kではないのか？

「Table[i].Key＝K で同じキーの重複格納が判明したとき」

K=InData.Key＝空白と考えればいいのでしょうか？
それとも、上記の状態になったらTable[i]・key≠kのループも何もしないで抜けて
空白aに戻ればいいのでしょうか？

＞●設問２‥解説の＋１が？１９７回ではないのか？

解説に記載してある＋１は最初のΒ（８００）という考えでよいのでしょうか？
800～997の個数は197ではなく198。の方が分かりやすいです。

＞「一次インデックスは，二次インデックスからある間隔で英単語を抜粋し」(p.172)たものである。検索する単語の出現確率が均一である場合，探索効率がもっとも良いのは，二次インデックスから均等の間隔で英単語を抜粋して一次インデックスに登録することである。
具体例として，一次要素数＝10，二次要素数＝103の場合を想定すると，均等に抜粋する方法として次の２つの案をすぐに発想できる。

問題に合わせると、一時要素＝１１（-1で１０になる）　二次要素＝１０３　変位＝１０３÷１０=１０
添字２←９　添字１←１　となり、最終的には一次「１０」のポインタに二次要素-１が入るということになる。

これでよろしいでしょうか？分かりづらくてすいません。急いで書いたので、これで勘弁を‥

回答No.1

ok-kaneto

直接の回答ではないですが念のため。

初版は誤植が多いですが確認はされましたか？

http://www.ric.co.jp/book/error/error605.html

お礼

ありがとうございます。修正完了いたしました！