基本情報技術者 試験情報＆徹底解説 -新制度に完全対応-

大域:整数型の二次元配列:hash

○整数型:searchHash(整数型:code)
  整数型:i,tmp,cnt
  i←0
  tmp←code
  for(cnt,1～3,1)
  i←i+(tmp mod 10)×cnt(a)
  tmp← tmp÷10
  endfor
  while((i≠-1)and(code≠hash[1,i])
  i←hash[3,i](b)
  endwhile
  if(i≠(-1))
  return hash[2,i]
  else
  return (-1)
  endif

hash ……28 29 30…55 56 57     コード
1 650 384 -1  465 183 708    整数データ
2 37 92 -1  22 54 85    シノニムレコード
3 -1 55 -1  57 -1 -1      の要素番号


例  465の場合  4*3+6*2+5*1=29 
    384        3*3+8*2+4*1=29
例  384の場合には(b)を入れた時に、
値が同じ29で衝突してしまうのですが何故ですか

ハッシュ値は衝突しないのが理想的ですが、どうしても衝突は発生してしまいます。そのため、衝突を解決する方法としてチェーン法やオープンアドレス法などがあります。

掲示板だけでは、これくらいしか分かりませんが,
解釈が合っているかどうか？

与えられている表が
      i     28   29   30  ・・・ 55   56   57
hash[1,i]  650  384   -1  ・・・465  183  708
hash[2,i]   37   92   -1  ・・・ 22   54   85
hash[3,i]   -1   55   -1  ・・・ 57   -1   -1
として考えます。

code=465の場合、i=29になります。
hash[1,29]は、384≠465なので
i←hash[3,29]=55
hash[1,55]=465
return  hash[2,55]=22

code=384の場合、i=29になります。
hash[1,29]は、384なので
return  hash[2,29]=92
になります。

ちなみに残りの数では、
code=708の時、i=29
return hash[2,57]=85

code=650の時、i=28
return hash[2,28]=37

などになります。

＞まーぼさん、boyonboyonさん
解説ありがとうございます。
もう少し聞きたいことがあります
(b)のi←hash[3,i]が入るのですが・・・

code=465を処理した後に

>code=384を格納する場合、i=29に入ります
hash[1,29]は、384なので
return  hash[2,29]=92
とありますが、シノニムレコードはhash[3,29]=55です

またcode=465の時にも
hash[3,29]＝55となり上書きするという意味で
(b)のi←hash[3,i]入るのですか。

何か解釈が違うのでしょうか、解説お願い致します。

この投稿は投稿者により削除されました。(2024.08.27 23:02)

整数型の変数codeが3桁の十進数である場合，
を実行後のiの値は
(codeの百の位×3)＋(codeの十の位×2)＋(codeの一の位×1)
です。

実行後のiの最小値は，code＝000のとき，
(0×3)＋(0×2)＋(0×1)＝ 0 です。

実行後のiの最大値は，code＝999のとき，
(9×3)＋(9×2)＋(9×1)＝54 です。

あり得るcodeの値の範囲 000～999 に対して
iの値の範囲は 0～54 しかありませんから，
当然，衝突（シノニム）が発生します。

No.3 で指摘のあったように，
465の場合  4*3+6*2+5*1=29
384の場合  3*3+8*2+4*1=29
だけでなく，
708の場合  7*3+0*2+8*1=29
もシノニムレコードです。


No.2で指摘のあったように，
上の表では，シノニムレコードをチェーン法で格納しています。

上の表の i＝0～54 までが
ハッシュ値に対応した最初のcodeが格納された領域。
上の表の i＝55 以降が
シノニムレコードが格納された領域だと予想できます。

のように hash[3,i] が
同じハッシュ値である次のシノニムレコードの位置を指していることが確認できます。

すこし質問とは脱線してしまいますがコメントします。

コードを理解しようとするのは良いのですが少し疑問に思っています。

質問者さんが疑問に思って聞かれている部分って、コードの上部に説明として仕様が提示されていると思うのですが違いますでしょうか？

そこを読んでもなおコードから問題を解く上で情報が欠如しているのであればその書籍の提示不足だとおもってますし、パズルのように足りない仕様は想像で完成させろという事まで基本情報では求めていない気がしています。

IPA:https://www.ipa.go.jp/shiken/kubun/fe.html
6.上位者の指導の下に、ソフトウェアを設計できる。
7.上位者の方針を理解し、自らプログラムを作成できる。 
上位者の意志を読み取って作ってね。
というのは裏を返せば勝手な解釈をしてやるなとも読み取れますのでコードから仕様を理解しようとする事はキケンな行為だと思ってます。

いきなりコード読もうとせず、まず何をしようとしているのか？を理解してからするようにしたほうが良いと思いました。

No.4のご質問の下記の所ですが、補足します。
code=384の場合
hash[1,29]は、384なので
code=hash[1,29]になり、whileループには入らずに
 if(i≠(-1))
  return hash[2,i]
  else
  return (-1)
  endif
を実行します。
結果、return  hash[2,29]=92  になります。

＞皆様
解説ありがとうございました。
別途ご返信しますのでよろしくお願いいたします。

＞電タックさん
いつもご指摘ありがとうございます。

＞質問者さんが疑問に思って聞かれている部分って、コードの上部に説明として仕様が提示されていると思うのですが違いますでしょうか？

問題を解くときに問題文は理解しました。
しかし、プログラムになった時に問題と該当する部分が分からないことがかなりあって、問題の大目的は分かるのですが(例  変数を入力したら価格が返ってくるとか)けれども細かい部分で何をしているのかがわからないです

また経験不足という問題なれもあるかもしれません。
すみません上手く言えなくて

私は基本情報には不向きなのかな？

問題文から

またこのハッシュ表ではシノニムにチェーン法で対応する。シノニムレコードは二次元配列hashの要素番号55以降に格納され、hash[1,i]のシノニムレコードの要素番号番号はhash[3,i]に格納される。なお二次元配列hashの未使用要素、及びシノニムをつないだリストの最後尾となる要素jのhash[3,i]には（-1）が格納されている。

このあたりが(b)該当するのかなと思うのですが、
問題文から解答の(b)のi←hash[3,i]が確実に入るのか確証できないです。

やっと分かりました。
流れ的に、465を探したい場合
①格納場所計算で求める(4*3+6*2+5*1＝29)
②hash[1,29]=384が格納されているのでhash[3,29]=55
ここが
while((i≠-1)and(code≠hash[1,i])
  i←hash[3,i]
ということなんですね

＞皆様
57というのは次のアドレスなんですね

＞皆様
解説ありがとうございました。
問題集があってないかもしれませんが続けます。
もうほとんどの参考書をやりきってしまって・・・

基本情報に向いてるか向いていないかは、2択じゃなくて％かなーと思うのが前提で。
B試験で合格ライン目の前まで到達してる人は、間違いなく向いている側かと思われます。
FEはCBTでかつ平均受験年齢が約24歳だから、やたら合格率高いというのが私の見立てです。
日本人の平均年齢は50歳以上な訳ですが、仮に全国民にある程度ITの勉強(仮に200hくらい)をしてもらってFE試験やったら、本当に私見ですけど合格率10％未満になるんじゃないですかね…。

＞adkさん
お言葉ありがとうございました。
アドバイスありがとうございます。これからも励みます

すごく私事ですが、10月にまたFE受ける事にしました。
2月に受かったとはいえ、ギリギリだったし色々忘れてるし、APの模擬試験代わりにしようかな～と。
お互い頑張りましょう。