これは、困っての質問ではありません。
>基本的な判定は、各段階で x が中央の要素 v[mid] より小さいか、
>より大きいか、あるいは等しいかである。
>われわれの二分探索では、ループの中で二つのテストを行っている。
>これは本来1回で十分である(外側でもっとテストが必要になるという第小はあるが。)
ごく基礎的なところを学習しているVB.NETの初学者です。
今、Else If まで進んだところです。
上記の引用は二分検索に関するもの。
「一回のテストでOKな二分検索を書け」が演習テーマ。
それで、回答はありません。
回答自体は、設問の中に書かれていますのでさほど難しいものではありません。
ですから、回答自体は欲していません。
欲しているのは回答が書かれているサイト。
Wikpedia や入門サイトを検索しましたが、2つのテスト版しかヒットしません。
どなたか、「一回のテストでOKな二分検索」が掲載されているサイトを知りませんか?
No.4ベストアンサー
- 回答日時:
「基本的な判定は、各段階で x が中央の要素 v[mid] より小さいか、より大きいか、あるいは等しいかである。
」という文章をキーワードにGoogle検索すると,検索結果の2番目に次のPDFファイルがヒットします。
http://www.robotics.jp/download/tools/pdf/sh-man …
これが「ループの中で二つのテストを行っている」コード例でしょう。
----------------------------------------
low = 0;
high = n - 1;
while (low <= high)
mid = low + high SHR 1;
if (x < v[mid]) {
high = mid - 1;
else if (x > v[mid])
low =mid + 1;
else /* 一致した
return(mid);
}
return(-1); /* 一致するものがなかった
}
----------------------------------------
次に,
「われわれの二分探索では、ループの中で二つのテストを行っている。これは本来1回で十分である」
でGoogle検索すると,検索結果の2番目に次のWebページがヒットします。
http://codeforzion.seesaa.net/article/47059843.h …
これが「一回のテストでOKな二分検索(外側でもっとテストが必要になるという代償はあるが)」というコード例でしょう。
----------------------------------------
low = 0;
high = n - 1;
while (high > low) {
mid = (high + low) / 2;
if (x <= v[mid]) {
high = mid;
} else {
low = mid + 1;
}
}
return (v[low] == x) ? low : -1; /* 三項演算子 */
----------------------------------------
どちらもVisual Basic系のソースコードでありませんが,アルゴリズムは表現されています。
Function BS(ByVal aGoods As String, ByVal aAttachs() As String) As String
Dim S As Integer
Dim L As Integer = aAttachs.Count - 1
Dim M As Integer
Dim aEntryGoods As String = ""
Do While S < L
M = (S + L) / 2
aEntryGoods = aAttachs(M).Split(",")(0)
If aEntryGoods < aGoods Then
S = M + 1
Else
L = M - 1
End If
Loop
Return If(aEntryGoods = aGoods, aAttachs(M), "")
End Function
Low = 0;
high = n - 1;
while (high > low) {
mid = (high + low) / 2;
if (x <= v[mid]) {
high = mid;
} else {
low = mid + 1;
}
}
return (v[low] == x) ? low : -1; /* 三項演算子 */
上で正解だと思っていたのですが・・・。
とんでもない勘違いをしていました。
L = M
で、書いて失敗。
まあ、いいかで L = M - 1 で逃げを打っていました。
正直に質問したが良かったですね。
ともかく、疑問が氷解しました。
ありがとうございます。
No.3
- 回答日時:
他の回答者が仰ってる通り、です。
これじゃ全く何の事やらサッパリです。不明瞭にも程がある、んですが……。Googleでフレーズ検索したところ、元ネタが分かりました。
K&R(プログラミング言語C:共立出版)の演習3-1ってのがその元ネタですね。
演習3-1 われわれの二分探索では、ループの中で二つのテストを行っている。これは本来1回で十分である(外側でもっとテストが必要になるという代償はあるが)。ループの中で1回しかテストをしないようなプログラムを書き、実行時間の差を測定せよ。
まさしくK&R持ってない人にとっては何の事やらサッパリ、です。質問の仕方もなってませんし。要するに、単にK&Rの演習問題の解答が知りたい、ってそれだけでしょう。
んで実はK&Rの解答集なんかも発売されてるんで、それを素直に買い求めた方が良いのでは、とか思います。
プログラミング言語
Cアンサー・ブック 第2版
http://www.kyoritsu-pub.co.jp/
No.2
- 回答日時:
文章は多いですが肝心なところの説明が足らなさすぎると思います。
>二つのテストを行っている。
テストってなんでしょうか?
1つ目の引用で言われている、基本的な判定のことでしょうか?
>今、Else If まで進んだところです。
教科書によって教える順番が違うので何の説明にもなりません。
>二分検索
二分探索ですよね?
>「一回のテストでOKな二分検索を書け」
これを他人に伝わる形で説明することがこの質問で最も重要かと思いますが
まったく書かれていません。
>設問の中に書かれていますのでさほど難しいものではありません。
設問の一部しか読んでいない人にとってはそれなりに難解な設問ですが?
>Wikpedia や入門サイトを検索しましたが、2つのテスト版しかヒットしません。
ヒットしたページのURLをここにかいてそれのどの部分が「2つのテスト」なのかを説明した方が良いのでは?
とまぁ、全体的に説明不足です。
テストとは何か、1回のテストとはどのような状況であるか、というのを例にとって述べて
それのアルゴリズムが書かれているサイトがないのかということを聞けば良いかと思います。
お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!
関連するカテゴリからQ&Aを探す
おすすめ情報
- ・漫画をレンタルでお得に読める!
- ・人生のプチ美学を教えてください!!
- ・10秒目をつむったら…
- ・あなたの習慣について教えてください!!
- ・牛、豚、鶏、どれか一つ食べられなくなるとしたら?
- ・【大喜利】【投稿~9/18】 おとぎ話『桃太郎』の知られざるエピソード
- ・街中で見かけて「グッときた人」の思い出
- ・「一気に最後まで読んだ」本、教えて下さい!
- ・幼稚園時代「何組」でしたか?
- ・激凹みから立ち直る方法
- ・1つだけ過去を変えられるとしたら?
- ・【あるあるbot連動企画】あるあるbotに投稿したけど採用されなかったあるある募集
- ・【あるあるbot連動企画】フォロワー20万人のアカウントであなたのあるあるを披露してみませんか?
- ・映画のエンドロール観る派?観ない派?
- ・海外旅行から帰ってきたら、まず何を食べる?
- ・誕生日にもらった意外なもの
- ・天使と悪魔選手権
- ・ちょっと先の未来クイズ第2問
- ・【大喜利】【投稿~9/7】 ロボットの住む世界で流行ってる罰ゲームとは?
- ・推しミネラルウォーターはありますか?
- ・都道府県穴埋めゲーム
- ・この人頭いいなと思ったエピソード
- ・準・究極の選択
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
-
texに関する初歩的な質問
-
ハノイ塔の非再帰について
-
Visial C++におけるプログラミング
-
VB6 コードでメニュー作成
-
PL/SQLのカーソルについて
-
納品 vs ご納品 どちらが正し...
-
納入日と納品日について
-
「スポット受注」はどういう意...
-
長さ0の文字列を格納できません...
-
formで送信したPOSTデータの削...
-
営業職をやってます。先月発注...
-
電子納品 CDへの捺印について
-
Windows server 2022 CALとSQL ...
-
ナショナル NE-1401F の業...
-
契約期間内における値上げ等に...
-
Windows 2000 とWindows XPの違い
-
見積書と発注書を兼用できるの...
-
インプットとアウトプット
-
敬語チェックお願いします!
-
テストについて
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
-
texに関する初歩的な質問
-
VBからBeckyを使用したメール送...
-
Excel-VBA コンテンツの作成日時
-
C#単体テストで同クラス内の呼...
-
JUnit結果出力をファイルに書き...
-
VB6 コードでメニュー作成
-
P2P地震速報のEEW APIの仕様書...
-
C#の単体テストでローカル変数...
-
Visial C++におけるプログラミング
-
UNIX:テキストファイルのNULL...
-
HWNDへの変換
-
web制作について
-
テスト仕様書について
-
仕様とはなんですかよろしくお...
-
ショッピングカートを作るには?
-
テスト仕様書作成って初心者(...
-
開発後のテスト方法の勉強について
-
自作ゲームについて・・・
-
外部仕様書の書き方
-
テスト仕様書の著作権について
おすすめ情報