HSPTV!掲示板

こちらのサイトで、二分探索アルゴリズムについての説明がありました。
http://gakuen.gifu-net.ed.jp/~contents/museum/golden/page62.html
（ページ一番下です。）

黄金比(1:1.618)で分割すると最も効率がいいと書いてありますが、
中心で分割するほうが効率がいいのではないでしょうか？

試しに、プログラムを組んでみました。
ですがやはり、中心で分割したほうが効率がいいという結果が出ました。
皆さんの意見を聞かせていただけないでしょうか？

Screen 0,1100,150
randomize
repeat//繰り返し行う為にルームを二重に
	ct = double(cnt+1)//試行回数を記録する
	目標点 = rnd(1000)//探索するポイントを設定
	地点A = 0//探索開始地点
	地点B = 1000//探索終了地点

	repeat 20
		//中心点=( double(地点B-地点A) *0.382)+地点A//地点AとBの"黄金比"を計算
		中心点=( double(地点B-地点A) /2.0)+地点A//地点AとBの中心点を計算
		gosub*描画:await 500//描画
		if 中心点<目標点 : { 地点A=中心点 } else{ 地点B=中心点 }//中心点より左or右に目標点があるのか判定
		gosub*描画:await 500//描画

		if (地点B-地点A) <= 10 : { 合計cnt + cnt:title "平均探索回数(cnt)="+(double(合計cnt)/ct)+"":await 500:break }//地点AとBの範囲が一定の値以下になったら終了
	loop

await
loop

*描画//なんやかんや描画
	color 150,150,150 : boxf
	color 255,0,200 : pos 中心点,100 : mes "P"
	color 255,255,0 : pos 目標点,120 : mes"★"
	color 255,0,0 : pos 地点A,120 : mes "●"
	color 0,0,255 : pos 地点B,120 : mes "●"
	color 0,0,0 : pos 10,10 : mes "地点A="+int(地点A)+"\n地点B="+int(地点B)+"\n中心点="+int(中心点)+"\n目標点="+int(目標点)+""//左上に情報を表示
	return

「黄金分割法」についてはちょっと調べただけなので、トンチンカンな事を言ってたら申し訳ないのですが、
そのページに載っているたとえ話は、「黄金分割法」のたとえ話としては不適切なのではないでしょうか？

どうも、そのページは古いページのようで、同じ「岐阜県まるごと学園」のサイト内で
新しいページを見つけたのですが、こちらはたとえ話の内容がより適切なものになっているようです。
http://gakuen.gifu-net.ed.jp/~contents/museum/golden/page62_5.html

二分法の説明に「この方法のポイントは、『目標物がそのどちらに属するかが判断できるとき』に
大変有効な方法であり」とありますので、古いページに載っているような例(水道管云々)の場合は、
やはり二分法の方が適切なのではないでしょうか。

>沢渡さん
やはりページの例えの問題でしたか。
新しいページの方もあったとは知りませんでした・・・
色々と調べていただき、本当にありがとうございますｍ（＿＿）ｍ