これは、困っての質問ではありません。
>基本的な判定は、各段階で 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で質問しましょう!
似たような質問が見つかりました
- その他(プログラミング・Web制作) ロボットの作り方を教えて下さい! なにも知らない素人です。 全て自作する場合、どうすればよいでしょう 6 2022/12/18 01:25
- その他(悩み相談・人生相談) 過去に知恵袋で同じような質問を何回もしていて、Google検索に出てくることで悩んでいます。 相談内 2 2022/09/05 22:57
- 邦楽 思い出せない歌のタイトル/歌詞について 質問が埋もれてしまったので二度目失礼します 学生時代(かなり 1 2022/04/08 23:21
- モニター・ディスプレイ Dell G2422HSのディスプレイの入力信号の切替器やリモコンを教えてください 4 2023/05/30 17:56
- 歴史学 米国における女性の歴史についての記事があるサイト 2 2023/02/21 14:02
- その他(ブラウザ) 教えて!gooなのですが、投稿者名で検索されたら過去の質問が出てきてしまいますか? 3 2023/03/13 02:51
- 教えて!goo 教えて!goo以外の質問サイトを含め、回答がつく順番を教えて下さい。 2 2022/05/10 13:43
- その他(インターネット接続・インフラ) 電話番号についてわかる方 1 2022/05/30 20:59
- ヘアケア・ヘアアレンジ・ヘアスタイル 自分に合った上手な美容師さんが見付けられません 3 2022/09/08 23:31
- 教えて!goo 指摘されたので質問です 1 2022/04/17 14:11
関連するカテゴリからQ&Aを探す
おすすめ情報
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
-
texに関する初歩的な質問
-
C#単体テストで同クラス内の呼...
-
C#の単体テストでローカル変数...
-
仕様書に書かれていないこと
-
納品 vs ご納品 どちらが正し...
-
「スポット受注」はどういう意...
-
Zと2とか紛らわしいのがあるか...
-
営業職をやってます。先月発注...
-
敬語チェックお願いします!
-
スーパー発注し始めて3週間たち...
-
グーグルの障害者訓練プログラ...
-
三菱製PLC:ファイルレジスタ(...
-
納期の前倒しを依頼する場合 ...
-
契約書の「重大な背信行為」は...
-
中小企業に対しての分割検収
-
初心者です。プログラムを作り...
-
access 今月のデータを抽出するVBA
-
納入日と納品日について
-
PostgreSQL+DataGridView
-
Windows server 2022 CALとSQL ...
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
-
texに関する初歩的な質問
-
P2P地震速報のEEW APIの仕様書...
-
VBからBeckyを使用したメール送...
-
JUnit結果出力をファイルに書き...
-
Excel-VBA コンテンツの作成日時
-
C#の単体テストでローカル変数...
-
C#単体テストで同クラス内の呼...
-
ホームページ・ビルダーで「e...
-
テスト仕様書作成って初心者(...
-
UNIX:テキストファイルのNULL...
-
Visial C++におけるプログラミング
-
テスト仕様書
-
AtomPubでlivedoorブログに記事...
-
仕様書に書かれていないこと
-
VB6 コードでメニュー作成
-
EXCEL_VBAでOracleにADO接続し...
-
Verilogの参考書のお勧めを教え...
-
ハノイ塔の非再帰について
-
納品の定義,システムの動作の常...
-
HWNDへの変換
おすすめ情報