応用情報技術者 試験情報＆徹底解説

https://www.ap-siken.com/kakomon/28_aki/q2.html

問題文で言う（4）の処理、解説コード4、7、10、13行目について質問です。


連続関数f(x)の値が0以上であればx1、そうでなければx0にxを代入すると言う場面ですが、

解説コードでf(0.5)>=0は真、f(0.25)>=0は偽となっています。
（f(0.375)、f(0.3125)は真でした）

これらの何が違うのか教えていただきたいです。
よろしくお願いいたします。

応用情報 平成28年 秋期 午前 問2
https://www.ap-siken.com/kakomon/28_aki/q2.html

という問題文の意味は次のとおり。

引数の最小値 0 を関数に与えたとき、その出力値 f(0) は負の値であり、
引数の最大値 1 を関数に与えたとき、その出力値 f(1) は正の値である。

単調に増加する、とは、xを 0→1 へと変化させたとき、関数の出力値 f(0)→f(1) は緩やかに変化するかもしれないし急激に変化するかもしれないが、ともかく xを増加させれば f(x)も増加するということ。xを増加させたけれど、f(x)が変化しなかったり f(x)が減少することはないということ。

この出題の区間内における
引数の下限 0 を関数に与えたとき、その出力値 f(0) は負の値であり、
引数の上限 1 を関数に与えたとき、その出力値 f(1) は正の値である。

であるなら、この出題の区間内における
出力値の下限 f(0)…負の数 から始まり、出力値が負である領域を進み、f(x)＝0 となるただ一点が存在し、それ以降は出力値が正の領域を進み、出力値の上限 f(1) に達することになる。
この f(x)＝0 となる x の近似値を求めるアルゴリズムについて出題している。

----
リンク先の解説に登場するトレースの意味は次のとおり。

 1行目：初期状態は xの下限＝0、xの上限＝1
 4行目：f(0.5)が正だと分かったので、xの下限＝0、xの上限＝0.5 に範囲を狭めた
 7行目：f(0.25)が負だと分かったので、xの下限＝0.25、xの上限＝0.5 に範囲を狭めた
10行目：f(0.375)が正だと分かったので、xの下限＝0.25、xの上限＝0.375 に範囲を狭めた
13行目：f(0.3125)が正だと分かったので、xの下限＝0.25、xの上限＝0.3125 に範囲を狭めた

>引数の最小値 0 を関数に与えたとき、その出力値 f(0) は負の値であり、
>引数の最大値 1 を関数に与えたとき、その出力値 f(1) は正の値である。

等号を無視してはいけません。
「であるなら」が成り立たないですね。

IPAの中の人見てますかぁ？
「(2)は何回実行されるか。」
ではなくて
「(2)は最大何回実行されるか。」
ではないでしょうか？

> 等号を無視してはいけません。(No.3)

ご指摘のとおりです、ありがとうございます。
「f(0)≦0≦f(1) を満たすとき」の意味は次のようになりますね。
引数の最小値 0 を関数に与えたとき、その出力値 f(0) は負の値 または 0 であり、
引数の最大値 1 を関数に与えたとき、その出力値 f(1) は 0 または 正の値である。

> 「であるなら」が成り立たないですね。

出力値の下限を f(0)…負の数 または 0
出力値の上限を f(1)…0 または 正の数
に修正すればいいので、私は「成り立たない」とは思いません。
No.2で述べたとおり f(0)＝0＝f(1) なら「単調に増加する」に反すると捉えています。

> 「(2)は最大何回実行されるか。」ではないでしょうか？

はい、私も賛成です。

解説ありがとうございます！

最初の結果がx1に入って0.25はそれ以下だから偽でx0に、0.375はその範囲内だからx1にはいるってことですね！

まだ理解できない点があって、1回目の（4）の比較【f(x)>=0ならば〜】はわかるんですが、2回目以降の比較はどういう意味なのかいまいち理解できません。

最初はf(0.5)>=0ということですよね？
2回目以降はf(0.25)>=0なんでしょうか？
f(x)>=f(x1)であれば理解できるのですが。

1回目の比較でf(0.5)が0以上と確定したからでしょうか？
だからといってf(0.25)が0未満とは言えないですよね。

勘違いというか、何に引っかかっているのか分かってきましたが、言葉にしにくいところです。
解説や下部のJavaScriptに、具体的なf(x)に当たる関数がないのがわかりにくいのかもしれません。
一度、具体的な関数、例えばf(x)=x^3-0.0027として、この2分法のトレースをやってみてはいかがですか？

リンク先の解説に登場するトレースでは、変数を次の意味で使用しています。

x0 は引数の下限
x1 は引数の上限
x  は下限と上限の間の中間点

No.2で回答したのと同じことを、x0, x1, x という変数を用いて書いてみます。

解説の冒頭に書かれているとおり「仮に f(0.3)＝0 として」という前提でトレースが進んでいます。x＝0.3が最終的に求めたい解であることをプログラムは知りません。

----
 1行目: x0←0, x1←1 を初期設定。f(x)＝0となる箇所は範囲0～1のどこかにある。

 2行目: その箇所がどこか不明なので、0～1の中間点 x＝0.5 を調べることにした。
 4行目: f(0.5)の結果は正だった。ならば f(x)＝0となる箇所は範囲0～0.5のどこかにある。そこで引数の上限 x1 を1から0.5に変更して調べる範囲を半分にした。

 5行目: その箇所がどこかまだ不明なので、0～0.5の中間点 x＝0.25 を調べることにした。
 7行目: f(0.25)の結果は負だった。ならば f(x)＝0となる箇所は範囲0.25～0.5のどこかにある。そこで引数の下限 x0 を0から0.25に変更して調べる範囲を半分にした。

 8行目: その箇所がどこかまだ不明なので、0.25～0.5の中間点 x＝0.375 を調べることにした。
10行目: f(0.375)の結果は正だった。ならば f(x)＝0となる箇所は範囲0.25～0.375のどこかにある。そこで引数の上限 x1 を0.5から0.375に変更して調べる範囲を半分にした。

11行目: その箇所がどこかまだ不明なので、0.25～0.375の中間点 x＝0.3125 を調べることにした。
13行目: f(0.3125)の結果は正だった。ならば f(x)＝0となる箇所は範囲0.25～0.3125のどこかにある。そこで引数の上限 x1 を0.375から0.3125に変更して調べる範囲を半分にした。
----

>修正すればいいので、私は「成り立たない」とは思いません。
思わないのは勝手ですが、成り立たないから修正するわけですよね。

>No.2で述べたとおり f(0)＝0＝f(1) なら「単調に増加する」に反する
 f(0)＝0 と f(1)＝0 が同時に成立するのなら「単調に増加する」に反するけど
残念ながら私はそんなことを書いていないということを指摘しておきます。

私の発言 No.3 の最後を訂正します。

問題文のアルゴリズムは、繰り返しの最中で f(x)＝0 の箇所を見つけても、繰り返しを終了していません。
つまりxの上限を狭める方向で調べる範囲を半分にしています。

よって、
> (2)は何回実行されるか。
という問題文は正しく、
> 「(2)は最大何回実行されるか。」ではないでしょうか？
は間違いです。

> 思わないのは勝手ですが、成り立たないから修正するわけですよね。(No.9)

誰に対して回答しているか、についての、あなたと私の意識の違いでしょう。

あなたは、AであるならB、という文に対して、
Aの理解が間違っているなら「であるならB」は成り立たないと「私に」言ったのですよね。

それに対して私は、「…でない」指摘は正しいのだけれど、No.3は質問者が欲する「…である」という「質問者への」回答になっていないと捉えたのです。

> 「であるなら」が成り立たないですね。(No.3)
という発言を目にした私は、この影響で、質問者が「No.2の内容自体が成り立たない」つまり「Bの考え方自体が成り立たない」と短絡的に解釈することを心配したのです。

> 私は「成り立たない」とは思いません。(No.4)
という箇所は、「でも成り立つじゃん！」という「あなたに対する」悔し紛れの発言に見えますが（改めて読み返してみると、そう解釈されても仕方ないなと私にも思えますが…）、

No.4を書いているときの私は、
----
Aに対して「0を含める」という小さな修正をしさえすれば、No.2の「であるなら」以降の Bの主張も小さな修正で理解できますよ。No.3は、No.2の内容自体の否定ではないですよ。
----
と「質問者に」気づいてもらうために、
No.2のような理解はまだ有効ですよと「質問者に」と示したいという意図で
> 私は「成り立たない」とは思いません。(No.4)
と書きました。

----
> f(0)＝0 と f(1)＝0 が同時に成立するのなら「単調に増加する」に反するけど
> 残念ながら私はそんなことを書いていないということを指摘しておきます。

はい、承知しています。なにが「残念ながら」なのかは不明ですが。

> f(0)≦0≦f(1) を満たすとき
であるなら f(0)＝0＝f(1) のときはどうなのだろうと、
質問者や他の回答者が疑問に思ったときのためにこの点を先に指摘してみただけです。

私は No.2 と No.8 で同じような回答を書いたのですけれど。

質問者が「まだ理解できない」とおっしゃっている点はぜんぜん別のことかもしれない、
と、HimaJinJPさんの No.7 を読ませていただいてちょっと心配になってきました。

HimaJinJPさん(No.7) からいただいた関数でトレースしてみました！
符号があったのでx0とx1へ振り分けているラインがわかりましたが、仰る通り言葉にするのが難しい部分で理解できていないと思います。

x0より大きくx1より小さかったら比較の上置き換えが発生することはわかるんですが、それをどちらに置き換えるのか（例 0.25 <= x <= 0.5 の時、0.375はなぜ0.5と置き換えるのか）
元問題だとやはり比較の部分がどうしても引っ掛かります。

たくさん解説してくださったのに申し訳ないですが、今年春受験予定なので一旦この問題はスルーしようと思います。

しっかりと理解できたらご報告させていただきます。
皆様ありがとうございました。

この投稿は投稿者により削除されました。(2025.02.19 18:57)

投稿を書いている間に、スレ主様の投稿がありましたが、せっかくなので投稿させていただきます。

横から失礼します。

この問題、二分探索と似ていますね。
出てくる数が、飛び飛びではなく連続という点では違いますが・・・
スレ主様、二分探索について調べてみるとこの問題理解しやすいと思います。

アルゴリズムについてですが、f(x)≧0ならば、x1←x ということは、
もしf(0.5)=0であっても、(2)に戻るので処理が継続されるということになります。
ようするに、f(x)=0になるxが見つかっても処理は続き、わざわざx1-x<0.001 になるxを求めると言うことです。

xが範囲内のいかなる数でもf(x)=0になるxを探索する幅は、解説の後半のとおり
1/2,1/4,1/8,1/16,・・・,1/1024
と狭くなっていくので、１０回目の1/1024で0.001より小さくなります。