アルゴリズムに関する問題
- ハッシュ法を用いた数字の配列に関する問題について解説します。
- 昇順に整列された表をブロックに分割してデータを探す方法について解説します。
- シェルソートによる整列手順を解説し、繰り返し回数を求めます。
- ベストアンサー
アルゴリズムに関する問題
こんばんわ、いくつかの問題につまってしまったので解答と簡単な解説をお願いします； 【問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）に戻る。 以上になります。
- kaisuke1
- お礼率72% (16/22)
- その他([技術者向] コンピューター)
- 回答数2
- ありがとう数0
- みんなの回答 （2）
- 専門家の回答
質問者が選んだベストアンサー
- ベストアンサー
問3についてです。 シェルソートについて思い出そうと、 調べていたところ参考URLのページを見つけました。 どうやら問3は（他もそうかもしれませんが） 情報処理試験の過去問のようですね。 参考URLにまったくおなじ問題と 回答、解説が載っています。 ズバリ、2回です。
その他の回答 (1)
問1についてです。 9+5+7+6=27 これを5で割ったあまりは2ですので、 回答は（ウ）です。 http://club.pep.ne.jp/~yama.ok/FE/H16AutumnFEAM/H16Aq14a.htm 問2は、 nを20とし、mを4としてみます。 データが、次のように並んでいる場合、 ブロック1：１、２、３、４ ブロック2：５，６，７，８ ブロック3：９，１０，１１，１２ ブロック4：１３，１４，１５，１６ ブロック5：１７，１８，１９，２０ まず10を探索すると仮定します。 まず、ブロックの最後尾から見ていきますので、 初めにブロック1の「４」を見ます。 これは、10より小さいので、次のブロック2の最後尾を見ます。 「８」で１０より小さいので、次のブロック3の最後尾を見ます。 「１２」で10より大きいので、次の手順でこのブロック3を 先頭から見ていくと、「９」の次に「１０」がありますね。 この場合、探索回数は、5回です。 ＃ ４、８、１２、９、１０の順に見ていったので。 この手順でもっと早く発見できる数字は「４」です。 ＃ 一回目の探索で見つけられます。 この手順でもっとも遅く発見できる数字は「１９」です。 ＃ 8回目の探索で見つけられます。 平均回数は、この最小の回数と最大の回数を 足して2で割って算出します。 つまり、（１＋９）／２＝4.5です。 nを20とし、mを４として、この4.5が算出できる答えは、 （エ）の式です。 問3についてもこれから考えて見ます。
関連するQ&A
- アルゴリズムによる整列方法について
以下の問題を授業外課題として出されましたがわかりません。身近に分かる人物もいません。 先生も答えてくれません。 解答お待ちしております。 １．以下の文章の空欄を埋めよ．但し，((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の配列変数を整列する場合 主語と述語があって、マル(。)で終わる文を複数書くこと。 キーワードの羅列、体言止めはＮＧ 「解決策」と「うまくいく理由」を説明する。 よろしくおねがいします。
- 締切済み
- その他（学問・教育）
- 宇都宮大学の問題です。お願いします。
表に奇数が並んでいる。上からm行 左からn列にある数をam,nとする。a２，３＝15である。 このとき、次の問いに答えよ。 (1)a1、nをｎを用いて表せ。 (2)上の表のa1,nとan,1を結ぶ直線上にあるすべての数の集合を第n郡と呼ぶ。例えば、第3郡は、{7,8,11}である。このとき、第n群に含まれるすべての数の和を用いて表せ。 (3)251は問2で定めた第何群にあるか？又am,n=251とするとき、ｍとｎを求めよ。 表 1 3 7 13 21 5 9 15 23 11 17 25 19 27 29
- ベストアンサー
- 数学・算数
- 情報処理の問題で、これがよく分からない
相異なる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だったら、 最後尾の数だけで、線形検索しても 該当の数がないので、分からないと思うのです。 どなたか、お馬鹿な私に分かりやすく教えてください。 よろしくお願いします。
- ベストアンサー
- 情報処理技術者
- SW:ハッシュ法によるデータの探索に関する問題
SW受験予定者です。 問題の解法として理解できない点がありましたので、ご理解のある方はご教授のほどお願い致します。 問.ハッシュ法によるデータの探索に関する記述のうち、最も適切なものはどれか。 答.ウ ハッシュ関数h(x)がh(x)=x mod n (xはキー、nはハッシュ表の大きさ)である場合、キー値がaであるデータと、キー値がbであるデータの間にシノニムが発生するときには、a-bがnの倍数であるという関係が成り立つ。 解答 キーaとキーbを a=s・n+c 、 b=t・n+cとする（s、t、cはともに整数） a-b=(s・n+c)-(t・n+c)=(s-t)・nとなり、これはnの倍数となっているので ウ が正解である。 以上の部分で、a=s・n+c 、 b=t・n+c をどのように導いたのかが理解できません。宜しくお願い致します。
- ベストアンサー
- 情報処理技術者
- アルゴリズムの問題です
以下のフローチャートは、基本選択法でデータを昇順（小→大）にソートしたものなのですが、整数の一次元配列に格納されているデータ（１００個）を降順（大→小）にソートするフローチャートを作成するには、どこの部分を変化させればいいのか教えていただけませんか？ 手書きなので見にくいですがよろしくお願いします。 開始 ｌ 整数配列A(100)と整数変数I,J,N,P,MIN,TEMPを宣言 ｌ データの個数N の値を読む ｌ ループ１の開始 I = 1,2,3, ・・・,N ｌ A(I)の値を読む ｌ ループ１の終了 ｌ ループ２の開始 I = 1,2,3, ・・・,N ｌ A(I)の値を出力 ｌ ループ２の終了 ｌ ループ３の開始 I = 1,2,3, ・・・,N-1 ｌ MIN = A(I) ｌ P = I ｌ ループ４の開始 J = I+1,I+2,I+3, ・・・,N ｌ ｌ yes A(J) < MIN ーーーーーー MIN = A(J) ｌ no ｌ ｌ P = J ｌ ｌ ｌ←ーーーーーーーーーーー ｌ ループ４の終了 ｌ TEMP = A(I) ｌ A(I) = A(P) ｌ A(P) = TEMP ｌ ループ３の終了 ｌ ループ５の開始 I = 1,2,3, ・・・,N ｌ A(I)の値を出力 ｌ ループ５の終了 ｌ 終了
- ベストアンサー
- その他([技術者向] コンピューター)
- データ構造とアルゴリズムの問題です
要素数がnである配列aの要素の最大値を求めるアルゴリズムのループ端によるフローチャートを完成せよ(前判定繰返し) max =a[0] i=1; while i<n do{ if(a[i]>max)max=a[i]; i++; } a[0] → max 1 → i 前判定繰返し □ | yes a[i]□max-----| | □ NO i+1 → i 前判定繰返し □の中を埋めるんですが教えてください
- 締切済み
- C・C++・C#
- クイックソートについて
下記のソースプログラムのquick_sort_coreの部分がわかりません。 わかる方助けてください。 あとこのソースを降順にした場合の変更点も教えていただけると助かります。 #include <stdio.h> /* printf()利用のため */ #include <stdlib.h> /* rand()利用のため */ #include <time.h> /* clock()利用のため */ #define N 10 /* 整列対象要素数 */ /** * 配列の中身を表示する関数 * @param a 表示する配列 * @param n 配列の要素数 */ void print_array(const int a[], int n) { int i; for (i = 0; i < n; i++) { printf("%d ", a[i]); } printf("\n"); } /** * 整列されているかどうか確認する関数 * @param a 確認対象配列 * @param n 配列の要素数 */ void is_sorted(const int a[], int n) { int i; for (i = 0; i < n - 1; i++) { if (a[i] > a[i + 1]) { printf("昇順に整列されていません\n"); return; } } printf("昇順に整列されています\n"); } /** * クイックソートの本体 * @param a 整列対象配列 * @param l 対象の最初の要素番号 * @param r 対象の最後の要素番号 */ void quick_sort_core(int a[], int l, int r) { /* ここを実装する */ } /** * これまでの整列関数のインターフェースにあわせるクイックソート呼び出し関数 * @param a 整列対象配列 * @param n 配列の要素数 */ void quick_sort(int a[], int n) { quick_sort_core(a, 0, n - 1); } int main(void) { int i; int n = N; /* 整列対象要素数 */ int a[N]; clock_t start,end; /* 0からRAND_MAXの一様乱数をn個生成し、配列aに格納 */ for (i = 0; i < n; i++) { a[i] = rand(); /* 出力確認(print_array)するときは a[i]=rand()%100 としておくと見やすい */ } /* 昇順にソートされているか確認（デバッグ用） */ is_sorted(a, n); /* 配列の中身を確認（デバッグ用） */ print_array(a, n); /* 開始時刻の取得 */ start = clock(); /* クイックソート関数の呼び出し */ quick_sort(a, n); /* 終了時刻の取得 */ end = clock(); /* 配列の中身を確認（デバッグ用） */ print_array(a, n); /* 昇順にソートされているか確認（デバッグ用） */ is_sorted(a, n); /* 実行時間の表示 */ printf("%d 個の要素のクイックソートの実行に %f [秒]かかりました\n", n, (double)(end - start) / CLOCKS_PER_SEC); return 0; }
- 締切済み
- C・C++・C#
- アルゴリズムが分かりません。
VB2005を使用して、研究をしている学生です。 平均値をｎ、各データの上限をｈとして、 データｄ[ｉ]をランダムにばらつかせるプログラムを考えています。 ｎ,ｈ,ｉ(定数)、ｄ(配列変数) 例えば、平均値＝10、上限＝15、データ数＝3のとき、 ｄ[1]＝9、ｄ[2]=7、ｄ[3]=14 が出力されるような感じです。 稚拙な文章で申し訳ありません。 方法論、具体的なプログラム例、いずれでも構いませんので、 ご回答よろしくお願いします。
- 締切済み
- Visual Basic
補足
ありがとうございます！ 過去門がのってるサイトなんてあったんですね、参考になりました！ また何かあったらよろしくお願いします＾＾；