- 締切済み
アルゴリズム
1,2,3, …14,15 と昇順に整列された 15個のデータに対して二分探索法を行うこと考える。4を 探索するとき何回の査で見つか理由も含めて述べよ。ただし、理由は150文字から180文字で記述する。 教えていただけませんか。
- mizingiridabesa
- お礼率0% (0/30)
- Java
- 回答数1
- ありがとう数0
- みんなの回答 （1）
- 専門家の回答
みんなの回答
- kmee
- ベストアンサー率55% (1857/3366)
「二分探索法」がどんな物か知っていれば、簡単な問題ですが、どのあたりがわからないのでしょうか? 走査回数は、実際に手でやってみれば、簡単にわかります。 その理由も、参考書等を読めば、大抵は書いてあります。こういうアルゴリズムのお手本みたいな方法ですから。
関連するQ&A
- 探索・整列アルゴリズムのメリット・デメリットについ
「コンピューターはなぜ動くのか？」の第５章の「アルゴリズムと仲良くなる7つのポイント」のところにて、主な定番アルゴリズムとして、 表5.1 主な定番アルゴリズム (1)ユーグリットの互除去 (2)エラトステネスのふるい (3)線型探索 (4)2分探索 (5)ハッシュ法 (6)バブル・ソート (7)クイック・ソート 上記のアルゴリズムがあり、そのアルゴリズムの用途には (1)最大公約数のアルゴリズム (2)素数のアルゴリズム (3)データ探索のアルゴリズム (4)整列のアルゴリズム 上記のアルゴリズムがありますが、(3)～(4)のアルゴリズムの用途においてのメリット・デメリット ・データ探索のアルゴリズム (3)線型探索 (4)2分探索 (5)ハッシュ法 についてのメリット・デメリット ・整列のアルゴリズム (6)バブル・ソート (7)クイック・ソート についてのメリット・デメリット これらを教えて頂けばと思っております。 よろしくお願いたします。
- 締切済み
- その他([技術者向] コンピューター)
- アルゴリズムに関する問題
こんばんわ、いくつかの問題につまってしまったので解答と簡単な解説をお願いします； 【問1】 4桁の数字( a1a2a3a4 )をハッシュ法を用いて配列に格納したい。 ハッシュ関数をmod（ a1 +a2 +a3 +a4 ,5 ）とし、求めたハッシュ関数値に対応する位置の配列要素に格納する場合、９５７６は（ア）～（オ）のどこに入るか。 ここでmod（x，5）の値は、xを5で割った余りとする。 位置 配列 ０ （ア） １ （イ） ２ （ウ） ３ （エ） ４ （オ） 【問２】 相違なるｎ個のデータが昇順に整列された表がある。この表を１ブロックｍ個に分割し、各ブロックの最後尾のデータだけ線形検索することによって、目的のデータを探し出す。 次に当該ブロック内を線形検索して目的のデータを探し出す。 このときの平均探索（比較）回数は（ア）～（エ）のうちどれか。 ここでｍ＜ｎとし、目的のデータは必ず表の中に存在するものとする。 （ア） （イ） （ウ） （エ） ｎ ｎ ｎ ｍ ｎ ─ ─ ｍ ＋ ─ ─＋─ ｍ ２ｍ ｍ ２ ２ｍ 【問3】 次の手順はシェルソートによる整列を示している。 データ列”7，2，8，3，1，9，4，5，6”を手順（１）～（４）に従って整列すると手順（３）を何回繰り返して完了するか。 ここで、〔〕は小数点以下を切り捨てる。 ＜手順＞ （1）〔データ数÷3〕→Ｈとする。 （2）データ列を互いにＨ要素分だけ離れた要素の集まりからなる部分列とし、それぞれの部分列を挿入方を用いて整列する。 （3）〔Ｈ÷3〕→Ｈとする （4）Ｈが0であればデータ列の整列は完了し、0でなければ（2）に戻る。 以上になります。
- ベストアンサー
- その他([技術者向] コンピューター)
- pascalでの二分探索（バイナリサーチ）
ファイルからデータを読み込み，それを整列し，入力された値をデータの中から二分探索によって探索することを繰り返すプログラムが作りたいのですが，どのように記述すればよいのか分かりません。教えてください。
- ベストアンサー
- その他（プログラミング・開発）
- なぜ通りがけをすると昇順に整列されるのか？
2分探索木で通りがけをすると中身が昇順に整列されて出てくる、それは覚えたのですが、なぜそうなるかがわかりません。 試験に「整列されて出ることを帰納法で証明せよ」という問題が出ることを予告されているのですが、なぜかが理論的に理解できていないので出来る気がしません。 どなたか理論をお教えください。
- ベストアンサー
- その他（プログラミング・開発）
- データ構造とアルゴリズムの問題が分かりません。
データ構造とアルゴリズムの問題が分かりません。 以下の問題で悩んでいます。 索引は書籍中の単語が書籍の何ページ目に出現するかを表す。もちろん、索引に含まれるある単語が複数のページに出現する場合や、索引に含まれる複数の単語が同一のページに出現する場合もある。 この索引で対象とする単語は、その書籍の中で重要な意味をもつものとして、また、特定の単語はたかだか数ページにのみ出現すると仮定する。 （1）単方向リストを用いてこのようなデータ構造を実現する場合、Ｃ言語ではどのように宣言をすれば適切か、struct宣言を用いて示しなさい。 （2）単方向リストを用いてデータ構造の場合、特定の単語が何ページ目に現れるか探すにはどのようなアルゴリズムを適用すれば適切か、探索に必要な時間計算量とともに示しなさい。 （3）二分探索木を用いてこのようなデータ構造を実現する場合、Ｃ言語ではどのように宣言をすれば適切か、struct宣言を用いて示しなさい。 （4）二分探索木を用いたデータ構の場合、特定の単語が何ページ目に現れるか探すにはどのようなアルゴリズムを適用すれば適切か、探索に必要な時間計算量とともに示しなさい。 （5）二分探索木を用いたデータ構の場合、アルファベット順の索引を出力するたねには、どのような整列アルゴリズムを適用すれば適切か、整列に必要な時間計算量とともに示しなさい。 テストに類題を出すと先生はおっしゃってたので、どうしてもすぐに回答が必要です。先生にも質問したのですが、テストに類題を出すから教えられない。自力で頑張れと言われ困っています。 どなたか御助力よろしくお願いいたします。
- 締切済み
- 科学
- データ構造とアルゴリズムの問題が分かりません。
以下の問題で悩んでいます。 １ 配列とリストでデータを末尾に追加する場合の時間計算量をO記法で表せ。 ２ 配列とリスト、それぞれの時間計算量以外の利点と欠点をなるべく多く挙げよ。 ３ データ構造「スタック」、「キュー」を配列もしくはリストで実現した場合、それぞれの利点と欠点を挙げよ。 ４ アルゴリズム「線形探索」、「二分探索」で特定のデータを検索するための時間計算量をO記法で表し、またその理由も記述せよ。 ５ データを検索する操作のほうが多い場合と、データを追加する操作が多い場 合、 「線形探索」と「二分探索」どちらが有利か理由をつけて述べよ。 １は、挿入と削除はO記法で表せたのですが、追加が分かりませんでした。 ２は配列の利点はランダムアクセス可能な点と任意のデータをすぐに扱える点の２点 リストの利点は扱うデータを自由に変えられる点の１点しか思いつかず、欠点はよく分かりませんでした。 ３、４、５も理由をつけて説明しろと言われたら無理です。 テストに類題を出すと先生はおっしゃってたので、どうしてもすぐに回答が必要です。先生にも質問したのですが、テストに類題を出すから教えられない。自力で頑張れと言われ困っています。 どなたか御助力よろしくお願いいたします。
- ベストアンサー
- C・C++・C#
- 二分探索のアルゴリズム
分からない問題があります。 ・２分探索における計算量を答えなさい。また、なぜそのようになるのかについてわかりやすく説明しなさい。 ・線形探索の計算量と２分探索の計算量を比べるとどちらの方が計算量が大きいか。理由をつけて説明しなさい。 ２分探索の計算量が O(logn) 線形探索の計算量が O(n)となるのはわかりますが そのようになる説明をどのようにしたらいいか。また logn<n となるのは わかるのですが理由をどう説明したらいいのか分かりません。 どなたかお教え下さい。
- ベストアンサー
- 科学
- アルゴリズムによる整列方法について
以下の問題を授業外課題として出されましたがわかりません。身近に分かる人物もいません。 先生も答えてくれません。 解答お待ちしております。 １．以下の文章の空欄を埋めよ．但し，((14)),((15)) については，選択肢から最も適切なものを選び，記号で答えよ．加えて，解答の過程を詳しく述べよ。 高速な整列として以下のアルゴリズムによる方法を考える．以下では，整数データを昇順に配列するも のとする． 前段階として，データを半々に二つのグループ I と II に分割し，それぞれを独立に整列する． while (両グループに要素が残っている) do if (グループ I の最小要素 < グループ II の最小要素) then グループ I の最小要素を出力場所に移し，グループ I からは削除する else グループ II の最小要素を出力場所に移し，グループ II からは削除する endif done while (グループ I に要素が残っている) do グループ I の要素を出力場所に移し，グループ I からは削除する done while (グループ II に要素が残っている) do グループ II の要素を出力場所に移し，グループ II からは削除する done この整列に要する計算量 T(n) を求める．但し，n は整列するデータの量である．前段階の整列では，半分のデータ量の整列を 2 回行うので ((1)) だけの計算を要する．次に，3 個の while 反復のいずれについても， 「反復を 1 回行うごとに要素が一つだけ出力場所に移動する」 ことから，3 個を合計すると反復の中身は正確に ((2)) 回実行されることが分かる．1 回の実行に a だけの時間がかかるものとすれば，全体で ((3)) となる．従って次の関係式が成り立つ． T(n) = ((4)) 簡単のため，n = 2^p であるとすると， T(n) = ((5))×T(2^((6)) ) + ((7)) = ((8)) × T(2^((9)) ) + 2 × ((7)) ・ ・ ・ = ((10)) × T(2^0) + ((11)) T(2^0) = ((12)) なので，T(n) を a と n のみを用いて表すと， T(n) = ((13)) であり，これは， ((14)) に比例し，計算量のオーダーは ((15)) といえる． ((14)),((15)) の選択肢 a. n b. n^2 c. 2^n d. n log n e. log n f. いわゆる「指数オーダー」であり，アルゴリズムとして全く実用に耐えない g. いわゆる「バカソート」と同じであり，n がごく小さい場合を除いて実用には適さない h. 経験上最速とされるソート法には及ばないが，それほど大きくない n に対しては実用に耐える i. 経験上最速とされるソート法と同じであり，十分大きい n に対しても実用に耐える
- 締切済み
- 数学・算数
- 探索プログラムの速さの計算方法を教えてください。
以下が問題です。 「長さがNの系列に対して3nμ秒で探索を完了する線形プログラムと 4log_2(n)μ秒で探索を完了する二分探索プログラムと 2nlog_2(n)μ秒で整列を完了するプログラムがある。 これらのプログラムを利用して、長さが1024の未整列のデータ系列Sに対し、ある要素が含まれているかどうか探索したい。このとき以下の問いに答えよ。ここでの検索要求とは「系列Sにある要素Xが含まれているかどうか判定すること」とする。」 ・検索要求が1回、5回、10回の場合それぞれの最も速い探索方法とその時間を述べよ。 計算方法と答えを教えてください。
- 締切済み
- 情報処理技術者
- アルゴリズムでわからない問題があります。（C言語）
問題１：探索アルゴリズムであるハッシュ法について正しいものを選べ。 (1)ハッシュ関数の出力によりデータを格納した配列の先頭から順番に調べる． (2) 入力データを，ハッシュ関数の出力により求めた格納場所に基づいて，あらかじめ木構造に格納しておく． (4) 入力データを格納した配列を繰り返し２つに分割し，それぞれを順番に調べていく． (3) 入力データから格納場所の位置に変換する関数（ハッシュ関数）の出力により，データの探索場所を決定する。 (5) 入力データを，ハッシュ関数の出力により求めた格納場所に基づいて，あらかじめヒープに格納しておく 問題２：探索アルゴリズムであるハッシュ法について正しくないものを選べ。 (1)入力データはハッシュ値で決められる場所に格納される． (2) ハッシュ関数には，異なる入力の値に対し異なる値を出力することが求められる． (3) ハッシュ関数の時間計算量は，入力データのサイズに比例する． (4) データの格納場所が大きい方が効率がよい． (5) 一般に２分探索法より高速に動作する． どなたかアルゴリズムに詳しい方回答お願いします
- 締切済み
- C・C++・C#
