HOME»応用情報技術者試験掲示板»平成17年春期 問13【選択肢ランダム】
投稿する
»[4814] 単純な計算問題の質問です 投稿数:12
»[4813] 管理人さんへ改善要望_午後の過去問の学習履歴 投稿数:1
平成17年春期 問13【選択肢ランダム】 [4816]
makiさん(No.1)
問題
相異なるn個のデータが昇順に整列された表がある。この表をm個ごとのブロックに分割し,各ブロックの最後尾のデータだけを線形探索することによって,目的のデータの存在するブロックを探し出す。次に,当該ブロック内を線形探索して目的のデータを探し出す。このときの平均比較回数を表す式はどれか。ここで,m<n とし,目的のデータは必ず表の中に存在するものとする。
回答で、1回目の分割階数をn/m回としていますが、なぜ割り切れるとわかったのでしょうか?
割り切れないことを考えた場合はn/m+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
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
その他のスレッド
»[4815] アドレス指定あたりのイメージが全く付かない 投稿数:7»[4814] 単純な計算問題の質問です 投稿数:12
»[4813] 管理人さんへ改善要望_午後の過去問の学習履歴 投稿数:1