HOME»応用情報技術者試験掲示板»平成17年春期  問13【選択肢ランダム】
投稿する

[4816] 平成17年春期  問13【選択肢ランダム】

 makiさん(No.1) 
問題
相異なるn個のデータが昇順に整列された表がある。この表をm個ごとのブロックに分割し,各ブロックの最後尾のデータだけを線形探索することによって,目的のデータの存在するブロックを探し出す。次に,当該ブロック内を線形探索して目的のデータを探し出す。このときの平均比較回数を表す式はどれか。ここで,m<n とし,目的のデータは必ず表の中に存在するものとする。

回答で、1回目の分割階数をn/m回としていますが、なぜ割り切れるとわかったのでしょうか?
割り切れないことを考えた場合はn/m+1回になるかと思うのですが、応用情報処理では基本割り切れると考えるべきなのでしょうか?
2024.02.06 21:01
jjon-comさん(No.2) 
AP プラチナマイスター
H17春の出題では「m<n」としか書かれていませんが、
https://www.ap-siken.com/kakomon/17_haru/q13.html

H18秋以降は「mは十分大きく,nはmの倍数」と問題文が変更されています。
https://www.ap-siken.com/kakomon/18_aki/q11.html
2024.02.06 22:19
 makiさん(No.3) 
jjon-comさん  回答ありがとうございます。
やはり問題に不備があったんですね。ありがとうございました!
2024.02.07 06:39

返信投稿用フォーム

スパム防止のためにスレッド作成日から30日経過したスレッドへの書込みはできません。
© 2010-2024 応用情報技術者試験ドットコム All Rights Reserved.

Pagetop