実際に二分探索を使うとして

フォーラム(掲示板)ルール
フォーラム(掲示板)ルールはこちら  ※コードを貼り付ける場合は [code][/code] で囲って下さい。詳しくはこちら
dic
記事: 657
登録日時: 13年前
住所: 宮崎県
連絡を取る:

実際に二分探索を使うとして

#1

投稿記事 by dic » 1年前

失礼します。ちょっとモヤモヤしたので質問します。

 C/C++でSTLを自由に使ってよいという条件のもと「二分探索を実装してくれ」と
頼まれて、STLを使うことにし、以下のコードを作った場合は、いいのでしょうか?

コード:

例
// ただxがvに含まれているかどうかを探す単純な例
bool lookup(vector<T>& v, const T& x)
{
	// ソートするのを忘れない
	sort(v.begin(), v.end());
	// 検索
	return binary_search(v.begin(), v.end(), x);
}
STLを使えば一行で済むので、ほかの人が苦労して何行もかけてつくっている
C言語での実装を見ると、かわいそうに思えてきます。

基本情報処理の試験テストでも、C言語での実装アルゴリズムを見かけます。
個人的にはSTLで安全な処理がいいのですが、C言語を勉強する必要はあるのでしょうか?

box
記事: 2002
登録日時: 13年前

Re: 実際に二分探索を使うとして

#2

投稿記事 by box » 1年前

実行結果さえ正しければ実装の方法は自由と思いますが、いかがですか?
バグのないプログラムはない。
プログラムは思ったとおりには動かない。書いたとおりに動く。

dic
記事: 657
登録日時: 13年前
住所: 宮崎県
連絡を取る:

Re: 実際に二分探索を使うとして

#3

投稿記事 by dic » 1年前

STLを使える人は使って、使えない人は苦労して実装するということに
落ち着きました。
角度を求める atan2(y,x) のような感じでしょうか
実行結果さえ正しければ、途中はプログラマの力量次第で
色々変化するのは、特に問題ないということですね。
モヤモヤが少しとれました。ありがとうございました。

アバター
usao
記事: 1887
登録日時: 11年前

Re: 実際に二分探索を使うとして

#4

投稿記事 by usao » 1年前

状況がわからん.

仕事か何かで(?),「実装してくれ」っていう話なら何を使ってもまともな処理時間でまともな結果が得られる物ならOKじゃないかな.
(実装された機能を利用する側は,その内側の具体実装コードを知りたいわけじゃない,ふつうは見ない.)

そうじゃなくて,「実装してみせてみろよw(できればな)」とかいう話だと自前で実装しろっていう話であろう.

---

で,それはそれとして,

> ただxがvに含まれているかどうかを探す

っていうだけの機能なのに,元のコンテナの中身が変更されてしまうってのは仕様としてOKなのか?
という話の方が気がかりな感じ.

アバター
usao
記事: 1887
登録日時: 11年前

Re: 実際に二分探索を使うとして

#5

投稿記事 by usao » 1年前

しかし,C++で今現在実装作業に従事している者が

> C言語を勉強する必要

とか言っている状況が謎なのだが……
他にも「ほかの人が苦労して何行もかけてつくっている」「基本情報処理の試験テストでも」とか謎めいた記述が散見されることから想像するに,
二分探索というものを「自前で実装できること」を求められている場面でありそうな予感もする.
(仮にそういう場面だとしたら,binary_search って1行書いてドヤってるのはマズイよね.「ほかの人」がやれていることをあなたもやれること,が求められているのでは?)

まぁ,どんな場面なのかはわからんけども,
「二分探索って何なのか全然わかんねぇけど,STLに何かそれっぽいのがあるからコレ呼んどけばいいんでしょ?」
みたいな奴とは正直一緒に仕事したくないよね(個人の感想です),とかならないように,勉強が必要だと思うなら裏でやっとけばよいのでは.

---

> STLを自由に使ってよいという条件のもと「二分探索を実装してくれ」

とか言われたら,「二分探索はSTLに存在するのですが?」と問うべきであろう.
(そのコードを書いちゃう前に)

返信

“C言語何でも質問掲示板” へ戻る