このアルゴリズムを何回繰り返せばよいのか。

質問

次のようなアルゴリズムＡがある。
Ｐ(ｘ)＝１であるような入力ｘに対しては必ず正しい答え１を出すが、
Ｐ(ｘ)＝０であるような入力ｘに対しては確率0.001で正しい答えを出し、
確率0.999で間違った答えを出す。
この時、どんな入力に対しても確率0.99以上で正しい答えを出すアルゴリズムを構成せよ。

という問題なのです。
答えは　
0.01 ＞ (0.999)**ｎ　　　（　(0.999)**ｎは0.999のｎ乗の意味　）
が成り立つ最小のｎ回アルゴリズムを繰り返せばよいと考えたのですが、
この式を解くとｎが2000以上になると思います。
難しくてきちんとしたｎの値は出てきませんでした。
何かこの式を簡単に解く式変形の仕方ってありますか？？
それともこの問題をこの式で解くのが間違っているのでしょうか？？？
よろしくお願いします！！！

回答No.1

Mr_Holland · ベストアンサー

アルゴリズムについては分かりませんが、
　　0.01 ＞ (0.999)^n
の解き方は、両辺に常用対数をとることで容易に求められます。
　　n＞-2／log(0.999)＝4602.867・・・・・
　したがって、設定された式が正しいとすれば、最小のｎは４６０３になります。

お礼

ありがとうございます。
ふむふむ、常用対数。そんなこと思いつきませんでした。
で、すみません。もう一つ質問させてください↓↓
log(0.999)はどのように直すのですか？？
log(0.999) = log999 - 3
以降できません。
理解力がなくてすみません。

回答No.5

180915

2番の中学生です。
習いませんでしたね。
ネットで調べなくても電卓(Windowsしかわかりませんが、)なら、アクセサリの中にある電卓の設定をちょっと変えてできます。
表示(V)→関数電卓(S)
これでボタンが増えたはず。後は、0.999と入れてlogを押すだけ。
-4.3451177401769130646560069552462e-4
こんな感じになるのかな？
この上の辺りが求めた結果の4桁ずれたものです。
実際は最後の-4だけ桁をずらして、－0.004345です。

お礼

ですよね！！！すごいですね～★☆
アクセサリの電卓ってあまり使ったことなかったんですけど、
そんなことできるんですね！！！！
参考になりました。ありがとうございました。

回答No.4

y_akkie

このアルゴリズムＡの解釈としては、1が正答であれば必ず1が出力され、
0が正答であれば99.99%の確率で1が出力され、0.001の確率で正答である
0が出力されるとみて宜しいでしょうか？
また、P(x)=○の○の部分は、入力値xに対する正答になるような出力値
であると見なしてよいのでしょうか？

そして、質問者さんが考案されているアルゴリズムとしては以下のような形式になるんでしょうか。

(1)何回かのループ回数を定めて、入出力動作を繰り返す。
(2)途中で0が出力された場合は、最終的な出力値を0とする。
(3)各回において出力値が1であればループ終了後に、最終的な
　出力値を1とする。

以上のことから、(3)で１を出力した結果、それが正しい出力値である
確率は正答が得られる確率に相当するわけですよね？
すると、P(x)=0になるような入力値に対して途中で(2)が発生する確率
が99%以上になるように、最小のループ回数を定めるという事になる
のでしょうか。すると、P(x)=0の場合において一度も0が発生しない
確率は(0.99)^n(nはループ回数)となり、(0.99)^n が0.01よりも小さくなれば良い事になるんでしょうか。
すると、(0.999)^n < 0.01が最小になるようなnを求めるには、
n > (log0.01)/(log0.999)になり、これをGoogleの計算機能を用いて
計算してみると、log0.01/log0.999=4 602.86722になるので、
http://www.google.co.jp/search?hl=ja&q=log0.01%2Flog0.999&lr=
n > 4602.8666722を満たす最小の整数nは4603である事が分かります。

お礼

そうです、そうです！！その通りです！！！！
すみません、説明不足で(^^;)
丁寧に説明していただいてありがとうございました。

回答No.3

Mr_Holland

＃１です。
　お礼をいただき、ありがとうございます。

＞log(0.999)はどのように直すのですか？？
＞log(0.999) = log999 - 3

　その変形で構いませんが、関数電卓をお持ちでしたら、0.999のままで計算できます。（Windowsに付属の関数電卓でしたら、0.999と入れた後"log"と押してください。）
　もし関数電卓を使ってはいけないのでしたら、対数表からlog3とlog37の値を読み取って計算しなければなりません。
　　log(0.999)＝log(999) - 3
　　　　　　　＝3log(3)+log(37)-3

お礼

再度ご回答ありがとうございました！！
ご丁寧に回答してくださってありがたかったです(^^)
関数電卓はもっていません。
対数表！！！たぶん昔の教科書の後ろに載っていたはず！！！
あ、ネットで検索したほうが速いですね(^皿^)笑

回答No.2

180915

数学が好きな中学生です。
式の適否はわかりませんが、式変形の仕方はわかります。
この場合、両辺を常用対数で取ればいいでしょう。
0.01>0.999**n
　 log(0.01)>n*log(0.999)←自然対数なので底は10
-2>n*(-0.004345)
n>4602.867217…
という式変形になります。
よって、4603回です。

お礼

ありがとうございます。
中学でlogって習いましたっけ？？
随分前のことで忘れてしまいました(^^;)

で、もう少しおばさんに付き合っていただけるとうれしいです。
log(0.999)はどのようにすれば求めらるんですか？？
う～ん、全く習った記憶がないのですが、私もきちんと習ったんでしょうね★★苦笑