- 締切済み
基本情報技術者での質問です。
問題 ５００個の要素をもつ配列を線形探索するとき、探索キーと配列中の要素との平均比較回数をAとする。 また、昇順に整列された５００個の要素をもつ配列を2分探索するとき、探索キーと配列中の要素との平均比較回数をBとする。 このとき、AはBの約何倍か。ここで、探索キーと一致する要素が、配列中に必ず存在するものとする。 答えは３１倍なんですが。 自分の解釈としては、まず線形探索の最大比較回数＝n この場合だと500です。 この場合2分探索の最大比較回数＝（ｌｏｇ２Ｎ＋１回） を割れば何倍かがでてくるであっていますか？？ それとバカな質問ですいません高校のときにlogをならっておらず いまさら数学の先生がいなく理解にくるしんでいます。 (logとこの自分が考えてる解き方であっているか)回答おねがいします
- YRKD
- お礼率0% (0/9)
- 数学・算数
- 回答数2
- ありがとう数0
- みんなの回答 （2）
- 専門家の回答
関連するQ&A
- 基本情報技術者での質問です。
問題 ５００個の要素をもつ配列を線形探索するとき、探索キーと配列中の要素との平均比較回数をAとする。 また、昇順に整列された５００個の要素をもつ配列を2分探索するとき、探索キーと配列中の要素との平均比較回数をBとする。 このとき、AはBの約何倍か。ここで、探索キーと一致する要素が、配列中に必ず存在するものとする。 答えは３１倍なんですが。 自分の解釈としては、まず線形探索の最大比較回数＝n この場合だと500です。 この場合2分探索の最大比較回数＝（ｌｏｇ２Ｎ＋１回） を割れば何倍かがでてくるであっていますか？？ それとバカな質問ですいません高校のときにlogをならっておらず いまさら数学の先生がいなく理解にくるしんでいます。 (logとこの自分が考えてる解き方であっているか)回答おねがいします。
- 締切済み
- その他([技術者向] コンピューター)
- 基本情報処理技術者試験問題の解答への質問です。
基本情報処理技術者試験問題の解答への質問です。 現在、基本情報処理技術者試験問題を勉強しています。 平成20年秋期午前問13の問題の答えですが、ネット上で見る解答では11回ですが、私が解くと10回になってしまいます。 キー値の個数 比較回数 1個 0回 2～3個 1回 4～7個 2回 8～15個 3回 16～31個 4回 ・・・・ 1024～2048個 10回 どこがおかしいのか、どなたか教えてください。 なお、問題は 以下の通りです。 2,000 個の相異なる要素が，キーの昇順に整列された表がある。外部から入力したキーによってこの表を２分探索して，該当するキーの要素を取り出す。該当するキーが必ず表中にあることが分かっているとき，キーの比較回数は最大何回か。 ア 9 イ 10 ウ 11 エ 12
- ベストアンサー
- その他([技術者向] コンピューター)
- 二分探索の平均探索回数
こんにちは、 二分探索の最大探索回数がlog2N+1なのは 書籍にある計算式の変換で理解できたのですが、平均探索回数がlog2Nなのが理解できません。 書籍では『平均探索回数の場合、N/2個のデータ探索をすればよいと考えます』と書かれていますが どういう意味なのか判りません。 そこで具体的に考えてみました。 例えば8個のデータの中から探す場合、 a[0]、a[1]、a[2]、a[3]、a[4]、a[5]、a[6]、a[7] とデータが並んでいて、 それぞれの位置に目的の値が入っていた時の探索回数は、 3回、2回、3回、1回、3回、2回、3回、4回 と考えました。 a[1]の場所に目的の数があった場合、 2回目の探索で見つかる、という意味合いです。 最大探索回数はa[7]の時に4回となり、log2N+1になっています。 この考え方でNを増やしていった所、最大探索回数はlog2N+1になりそうです。 そこで上記の場合の平均探索回数の方は、 (3+2+3+1+3+2+3+4)/8 と計算し、2.625と考えました。 この考え方でNを増やしていくと 16コ：3.375 32コ：4.21875 64コ：5.125 128コ：6.0703125 …と、 平均探索回数がlog2Nではなくlog2N-1に近づいていきます。 考え方の間違っている箇所の指摘をお願いします。
- 締切済み
- その他（プログラミング・開発）
- 探索プログラムの速さの計算方法を教えてください。
以下が問題です。 「長さがNの系列に対して3nμ秒で探索を完了する線形プログラムと 4log_2(n)μ秒で探索を完了する二分探索プログラムと 2nlog_2(n)μ秒で整列を完了するプログラムがある。 これらのプログラムを利用して、長さが1024の未整列のデータ系列Sに対し、ある要素が含まれているかどうか探索したい。このとき以下の問いに答えよ。ここでの検索要求とは「系列Sにある要素Xが含まれているかどうか判定すること」とする。」 ・検索要求が1回、5回、10回の場合それぞれの最も速い探索方法とその時間を述べよ。 計算方法と答えを教えてください。
- 締切済み
- 情報処理技術者
- アルゴリズムに関する問題
こんばんわ、いくつかの問題につまってしまったので解答と簡単な解説をお願いします； 【問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）に戻る。 以上になります。
- ベストアンサー
- その他([技術者向] コンピューター)
- 情報処理の問題で、これがよく分からない
相異なるn個のデータが昇順に整列された表がある。この表を1ブロックm個に分割し、各ブロックの最後尾のデータだけ線形探索することによって、目的のデータの存在するブロックを探し出す。次に当該ブロック内を線形探索して目的のデータを探し出す。このときの平均探索回数はどれか。ここで、 m＜nとし、目的のデータは必ず表の中に存在するものとする。 答えは m/2 + n/2m なのですが、 目的のデータが存在したブロックの中での 線形検索の結果でm/2 となるのは分かるのですが、 なぜ、n/2mで目的のブロックを見つけることが できるのかが分かりません。 例えば、 (1,8,9),(10,13,14),(17,19,20) で ３つずつのブロックに分けて各ブロックの最後尾 の数だけで線形検索を行うってことは、 9,14,20 で 検索するってことで 平均2/3 で見つかることは分かります。 けれど、目的の数値が9,14,20 以外の数字 だったら、目的の数値が 含まれるブロックが見つからない気がするのですが。 例えば目的の数値が、8だったら、 最後尾の数だけで、線形検索しても 該当の数がないので、分からないと思うのです。 どなたか、お馬鹿な私に分かりやすく教えてください。 よろしくお願いします。
- ベストアンサー
- 情報処理技術者
- アルゴリズムを勉強していたのですが、線形探索をする
アルゴリズムを勉強していたのですが、線形探索をする時にデータ件数がNの時平均比較回数が(N+1)÷2回となっていたのですが、なぜ+1をしているのでしょうか？普通にN÷2ではダメなんでしょうか 解説お願いします
- 締切済み
- C・C++・C#
- 線形探索について
C言語の線形探索の課題なんですが ５つの整数を入力して その入力した値からみつけたい値を探索する課題なのですが #include <stdio.h> /*--- 要素数nの配列aからkeyと一致する要素を線形探索 ---*/ int search(const int a[], int n, int key) { int i = 0; while (1) { if (i == n) return (-1); /* 探索失敗 */ if (a[i] == key) return (i); /* 探索成功 */ i++; } } int main(void) { int i, ky, idx; int x[4]; int nx = sizeof(x) / sizeof(x[0]); printf("%d個の整数を入力してください。\n", nx); for (i = 0; i < nx; i++) { printf("x[%d]：", i); scanf("%d", &x[i]); } printf("探す値："); scanf("%d", &ky); idx = search(x, nx, ky); /* 配列xから値がkyである要素を線形探索 */ if (idx == -1) puts("探索に失敗しました。"); else printf("%dは%d番目にあります。\n", ky, idx + 1); return (0); } ここまではわかるのですが、 x[0]=99 x[1]=99 x[2]=88 x[3]=99 x[4]=22 と入力したときに 99は 1番目に見つかりました ２番目に見つかりました ４番目に見つかりました と出力したいのですがうまくいきません 線形探索で同じ数値を探索するにはどうすればよいのですか？
- ベストアンサー
- C・C++・C#
- このプログラムの説明合っていますか?
/* 線形探索（for文で実現）*/ #include <stdio.h> /*--- 要素数nの配列aからkeyと一致する要素を線形探索 ---*/ int search(const int a[], int n, int key) { int i; /*iを宣言*/ for (i = 0; i < n; i++) /*iの値を設定し宣言*/ if (a[i] == key) /*iにkeyで入力*/ return (i); /* 探索成功 */ return (-1); /* 探索失敗 */ } int main(void) /*main関数*/ { int i, ky, idx;/*i,ky,idxを宣言*/ int x[7]; /*ｘは配列で７つの数字を入れられる*/ int nx = sizeof(x) / sizeof(x[0]);/*配列を宣言*/ printf("%d個の整数を入力してください。\n", nx); for (i = 0; i < nx; i++) { printf("x[%d]：", i); scanf("%d", &x[i]); }printf("探す値："); scanf("%d", &ky); idx = search(x, nx, ky); /* 配列xから値がkyである要素を線形探索 */ if (idx == -1) puts("探索に失敗しました。"); else printf("%dは%d番目にあります。\n", ky, idx + 1); return (0); /*0の数字で戻る*/ } 1行ずつ理解したいのですが分からない個所多いんです。 分からないの文は説明が書いてないので教えてください。
- ベストアンサー
- C・C++・C#
