• ベストアンサー
  • 困ってます

二分探索プログラムの添削願い

  • 質問No.8370853
  • 閲覧数470
  • ありがとう数9
  • 気になる数0
  • 回答数3
  • コメント数0

お礼率 88% (81/92)

方程式の解を求める以下のプログラムの添削やアドバイスをお願いします。プログラムが行う処理手順の概要は、以下の通りです。解くべき方程式はmainの2行目に(i)と示されています。
(1)方程式を表示し、ユーザーに関数fのパラメーターを入力させる。
(2)関数の次数に応じて処理が分岐し、fが”定数項が0でない三次式”の場合は(4)へ飛ぶ。それ以外は(3)へ。
(3)解の公式などを用いて虚数解を含むすべての解を求めて表示し、終了。
(4)二分法を用いて解を求める。二分法の区間を入力するようユーザーを誘導する。
(5)設定された区間をさらに1000等分してそれぞれの区間に対して(上限値に近いほうから順番に)二分法を用い、見つけられるだけの実数解を探索し、結果を表示して終了。

・・・以上です。載せているソースコードは前文ではなく抜粋です。本当はソースコードを全部載せたかったのですが、字数制限の都合上かなり省略があります。
実際には、*には方程式のパラメータ入力への誘導部が、**には二分法の区間設定への誘導が省略されています。これらの部分で、関数のパラメータをa,b,c,dに、二分法の区間をupper,lowerに格納します。
 また、ユーザーを誘導するメッセージ、求めた方程式の解を表示するメッセージなども全て省略しています。途中に出てくるメソッドですが、
・checkDegree(コードは省略されています。)
fのパラメータを渡すと、fの次数をdegreeに返す。

・soluteEq(コードは省略されています。)
fの次数とパラメータを渡すと、a=0かつd=0の場合を除き(i)の解を全て表示し、終了フラグを立てる。

・foo(省略されています。)
変数xと、方程式のパラメータを与えると、fの値を返す。

・doBisection
二分法の区間と方程式のパラメータを渡すとその区間を1000等分して新たな区間を
1000個作成し、それぞれの区間に(上限値に近いほうから)二分法を実行。見つけられた解の個数を返す。

となっています。
自分が作成したプログラムをEclipse上で動かしてみると、一応正確な答えは帰ってきました。
ただ自分の作ったプログラムの問題として、doBisectionの処理において、たまたまn番目の区間の下限値が方程式(i)の解だった場合、n+1番目の区間に対して二分法処理が行われないことです。
これはn番目の区間の下限値が、n+1番目の区間の上限値になってしまうためなのですが、何か良い解決策をご提示願えないでしょうか。

また他にも、ソースコードをより可読的にするための改善点などありましたら、
ご提案願えないでしょうか。プログラミング初学者なのですが、独学でやっていますので
変な癖がついたりするのが結構不安です。
以下ソースコード抜粋を貼ります。皆様のお言葉、お待ちしております・・・
(自分は返信をスルーすることはありません。ベストアンサーも必ず指定して質問を完結させます。)

//以下main methodの中身
double a = 0, b = 0, c = 0, d = 0, upper = 1, lower = 0;
System.out.println("f(x) = a * x^3 + b * x^2 + c * x + d = 0 ・・・(i).");//*
int degree = checkDegree(a,b,c,d);
int endflag = soluteEq(degree,a,b,c,d);
if(endflag == 1){return;}//**
if(upper == lower){return;}
if(upper < lower){
double change = lower;
lower = upper;
upper = change;
}
int find = doBisection(upper,lower,a,b,c,d);
}//main以上

//以下doBisection
int i = 0, find = 0;
while(true){
double u = (1 - 0.001*i)*upper + 0.001*i*lower;
double l = (1 - 0.001*(i+1))*upper + 0.001*(i+1)*lower;
if(find == 3){break;}
if(i == 999){break;}
while(true){
double fl = foo(l,a,b,c,d);
double fu = foo(u,a,b,c,d);
if(fu*fl > 0){
i++;
break;}
if(fl == 0){
find++;
i++;
break;}
if(fu == 0){
System.out.println("x = "+ u +"\r\nは方程式(i)の解です。");
find++;
i++;
break;}
if(u - l < 10E-10){
i++;
find++;
break;}
double m = (u + l) / 2;
double fm = foo(m,a,b,c,d);
if(fm == 0){
find++;
i++;
break;}
if(fu*fm > 0){u = m;}
if(fl*fm > 0){l = m;}
}
}
return find;
}//doBisection以上。

質問者が選んだベストアンサー

  • 回答No.3
  • ベストアンサー

ベストアンサー率 44% (4492/10098)

他カテゴリのカテゴリマスター
> 危険というのは、区間の境界値が実数解の十分な近似である場合に、==0の判定文ではそれを捉え損ねるという理解で間違いないでしょうか。

そういうことだ。

> whileをforに変えれば「n番目の下限値がn+1番目の上限値になってしまう」という問題も解決するのでしょうか。

そんなわけないでしょ。epsを小さい正数として
1区間の2分探索に与える上限uと下限lに関してfu*fl<-epsとなっていれば2分探索は簡単に書けるよね。この場合には必ずこの範囲に1個または3個の解が存在するのだけれど,あなたの与えられた課題では,3個の解がある場合でも1個だけ発見して残りの2個は見逃してもいいのだから簡単でしょ。
fu*fl>=epsであればこの範囲には解がないとして次の範囲に行く。
それ以外の場合にはuかlのどちらか,または両方が解になるけど,例えばuだけを判定するようにしても,lは次回で判定されるから見逃すことはないでしょう。


でも,もう一度言うけど,方程式の解を求めるのが目的ならこんな下手くそなアルゴリズムは捨てたほうがマシだと思うぞ。
お礼コメント
moguraduka

お礼率 88% (81/92)

ありがとうございます、わかりやすかったです。

方程式の解を求めたいわけでなく、単に課題の内容がそうなっていただけなので、ひとまずこのまま進める予定です。
投稿日時:2013/12/04 11:46

その他の回答 (全2件)

  • 回答No.2

ベストアンサー率 44% (4492/10098)

他カテゴリのカテゴリマスター
if(fl == 0){
とか
if(fu == 0){
を==0で判定するのは危険でしょう。
判定したい数の絶対値<小さい数
で判定すべきです。

しかし,それ以前にどうして区間を1000等分するのか?
それでは解が区間の1000分の1未満の差しかないときに対応できません。
ちゃんとそれぞれの解を挟むようにアルゴリズムを考えてください。
お礼コメント
moguraduka

お礼率 88% (81/92)

ありがとうございます。

危険というのは、区間の境界値が実数解の十分な近似である場合に、==0の判定文ではそれを捉え損ねるという理解で間違いないでしょうか。

今回作成するアルゴリズムの内容の問題点私も承知していますが、ひとまずそのようなプログラムを作る課題を与えられたということで、そこは問題にしないということでお願いします。
投稿日時:2013/12/03 11:05
  • 回答No.1

ベストアンサー率 55% (1857/3366)

1つのwhileで全部やろうとして、こんがらがってるだけではないでしょうか?

for(1000 区間分 ) {
1区間の2分探索
}
と考えてコーディングしてみては?


構造化プログラミングといった、プログラミングの考え方を勉強していくとよいでしょう。
お礼コメント
moguraduka

お礼率 88% (81/92)

ありがとうございます。
構造化プログラミングというキーワードで自学します。

for文を使って二分法をせよとのことですが、
whileをforに変えれば「n番目の下限値がn+1番目の上限値になってしまう」という問題も解決するのでしょうか。
投稿日時:2013/12/03 11:00
結果を報告する
このQ&Aにはまだコメントがありません。
あなたの思ったこと、知っていることをここにコメントしてみましょう。
AIエージェント「あい」

こんにちは。AIエージェントの「あい」です。
あなたの悩みに、OKWAVE 3,600万件のQ&Aを分析して最適な回答をご提案します。

関連するQ&A

その他の関連するQ&Aをキーワードで探す

ピックアップ

ページ先頭へ