平成28年秋期  午前問2(アルゴリズム)

otoさん  
(No.1)
https://www.ap-siken.com/kakomon/28_aki/q2.html
初見でこの問題を解ける人の思考法を想像してみたのですが、以下のような流れでしょうか。

1. まずxに適当な値を選ぶ(解説の場合0.3)
2. 4回程度アルゴリズムの出力値を手計算してみる
3. xの値の誤差に着目して、誤差を手計算してみる
4. 誤差が等比数列であることに気づく
5. 等比数列の式を考案する

3.4.5.の発想というかひらめきが自分にはハードル高いと正直感じました。2.の算出後、(アルゴリズム内の変数には解に直結しそうな値がない)で詰まりそうです。

上記の考え方がそもそもずれているのか、よりシンプルな考え方などあれば教えてください。
2024.01.29 09:19
tinyfinさん 
(No.2)
この問いは初見でしたが解けました。
ただ正直に申し上げますと、このアルゴリズムは二分法と呼ばれており、私の使っている応用情報の参考書(応用情報技術者合格教本)に掲載されています。
従って私の場合ですが、アルゴリズムの概要を知っているからそこまで複雑な思考をせずに解けました。
2024.01.29 09:50
納豆のたれさん 
(No.3)
・問題文やアルゴリズム(1)から全区間は1である。
・アルゴリズム(2)を一回通過(実行)するごとに最大誤差は1/2になる。
・アルゴリズム(3)から、最大誤差が0.001より小さくなれば終了。

これらの条件から
  (1/2)^n<0.001
が立式できます。
あとは、この式を解けばよいです。
逆数をとって
  2^n>1000
n=10のとき、2^10=1024>1000なので答えは10。
※「2^10=1024」は「10^3=1000」とセットで覚えておいたほうがよいですよね。

代入して何回か計算するのは、時間を削られるのでよくないと思います。
代入する方法しか思いつかない場合は、後回しにするのも手段ですが、
その場合は解答欄を間違うリスクや後回しにしたこと自体を忘れるリスクに要注意です。
2024.01.29 17:37
boyonboyonさん 
AP シルバーマイスター
(No.4)
アルゴリズムを順に見てやっていることを解釈します。
(1)変数に範囲の端点を代入か。
(2)xは、範囲の中間だな。
(3)終了条件か。
(4)1回実行するごとに範囲が半分になるな。←これに気付けば後は分かりやすいかも、
1回で半分、2回でまた半分・・・1/2,1/4.1/8・・・
(3)より、範囲が0.001以下になればいいんだな。
0.001=1/1000だな、2^10=1024だったな。
答えは、アかな。

みたいな感じで自分は考えます。
2024.01.29 18:02
otoさん  
(No.5)
皆さま
ありがとうございます。
大変参考になります。
2024.01.29 18:34

返信投稿用フォーム

スパム防止のためにスレッド作成日から30日経過したスレッドへの書込みはできません。

その他のスレッド


Pagetop