C言語の二分法のプログラムについて

質問

二分法によりルート２の近似値を求めるプログラム、ってどうやって作ったらいいんですか？
ちなみに初期値は２で、収束条件は10^-5です。
収束までの回数も求めなきゃいけません(ニュートン法と比較するため。ちなみにニュートン法はできました。)

似たような質問を見つけたのですが、どれも、難しいプログラムばかりで解読ができません。
関数とかif else文とかwhile文とかfor文とか、そういう簡単なのしか習ってないので、それで作れる範囲で教えてくださる方、
いらっしゃいましたら、よろしくお願いします。

回答No.4

noname#119918 · ベストアンサー

これでどうでしょう。
if文判定、及びwhile文判定を修正しました。

#include <stdio.h>
#include <math.h>
#define f(x)(x*x-2.0)
int main(void)
{
int i=0;
double m,x1=2.0,x2=1.0,eps=1.0e-5;
do{
++i;
m=(x1+x2)/2;
if (f(m)>0)
{
x1 = m;
}
else
{
x2 = m;
}
}
while (fabs(x1-x2)>eps);
printf("%f,%d\n",m,i);
return 0;
}

お礼

うわー、すごい!!

できました!!本当にありがとうございます!!

回答No.3

noname#119918

手抜きですが、こんな感じですか…

#include <stdio.h>

/*
sqrt(2.0) を二分探索法で求める
left 探索範囲左限界
right 探索範囲右限界
conv_cond 収束条件
*/
void solve(double left , double right , double conv_cond)
{
int count; /*試行回数*/
double center; /*中間値*/
for(count=0 ; ; count++)
{
center = (left + right) / 2.0;
/*収束条件を満たしたか*/
if((center - left < conv_cond) &&
(right - center < conv_cond)) break;
/*解は中間値よりも大きいか小さいか*/
if(center*center - 2 < 0)
{
left = center;
}
else
{
right = center;
}
}
printf("%d %f\n" , count , center);
}

int main(void)
{
solve(0 , 2 , 1.0e-5);
return 0;
}

お礼

ありがとうございました。
実行するとうまくいきました。
ちなみに、自力で作ってみました。

#include <stdio.h>
#include <math.h>
#define f(x)(x*x-2.0)
main()
{
int i=0;
double m,x1=2.0,x2=1.0,eps=1e-5;
do{
++i;
m=(x1+x2)/2;
if (f(m)*x1>0){
m=x1;
}
else
m=x2;
}
while (fabs(x1-x2)<eps);
printf("%f,%d\n",m,i);
}

これを実行すると、2.000000，1と出ます。
私はこの程度のプログラムしか習ってません。
つまり、ANo.3の方のプログラムだと、解読できないです。
もしよろしければ、自力でやったプログラムに訂正箇所があればお願いします。

ANO.1の方とお礼がかぶってしまい、申し訳ございません。

回答No.2

Oh-Orange

★リンクの紹介。
＞二分法によりルート２の近似値を求めるプログラム、ってどうやって作ったらいいんですか？
　↑
　次のリンクの『３２ビットの整数の場合でループを展開したもの』をご覧下さい。
　http://ayusya.hp.infoseek.co.jp/ProgramAlgorithm.html#Sqrt
　これがアルゴリズムです。
　実際に組むときはループ処理をさせれば良いです。
　なお、この考え方は数値表現に2進数が使われている事に着目して 8192、4096、2048、1024…と
　二分法で平方根を求めているのです。
＞ちなみに初期値は２で、収束条件は10^-5です。
　↑
　double 型を使うなら初期値の 2、4、8、16、32、…と徐々に大きくしていきチェックします。
　次のリンクも参考にしてみて下さい。
　http://kyutechzemi.hp.infoseek.co.jp/0013/jp0000.html→『平方根を二分法で計算する。』
　ソースもダウンロードできるようです。
　このソースでは10^(-4)乗が収束条件のようです。
・以上。

参考URL：

http://kyutechzemi.hp.infoseek.co.jp/0013/jp0000.html

お礼

ありがとうございました。

そうですか。。。

ちなみに、自力で作ってみました。

#include <stdio.h>
#include <math.h>
#define f(x)(x*x-2.0)
main()
{
int i=0;
double m,x1=2.0,x2=1.0,eps=1e-5;
do{
++i;
m=(x1+x2)/2;
if (f(m)*x1>0){
m=x1;
}
else
m=x2;
}
while (fabs(x1-x2)<eps);
printf("%f,%d\n",m,i);
}

これを実行すると、2.000000，1と出ます。
訂正箇所があればお願いします。

ANO.1の方とお礼がかぶってしまい申し訳ありません。

回答No.1

koko_u_

>関数とかif else文とかwhile文とかfor文とか、そういう簡単なのしか習ってないので
その程度の範囲で書けるはずです。ニュートン法より易しいと思うのですが。

お礼

そうですか。。。

ちなみに、自力で作ってみました。

#include <stdio.h>
#include <math.h>
#define f(x)(x*x-2.0)
main()
{
int i=0;
double m,x1=2.0,x2=1.0,eps=1e-5;
do{
++i;
m=(x1+x2)/2;
if (f(m)*x1>0){
m=x1;
}
else
m=x2;
}
while (fabs(x1-x2)<eps);
printf("%f,%d\n",m,i);
}

これを実行すると、2.000000，1と出ます。
訂正箇所があればお願いします。