のんびりやろう！情報処理試験！ 〜１問１問コツコツと〜 |
この記事の発行者<<前の記事
｜
次の記事>>
｜
最新の記事
☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆
★ ★
☆ のんびりやろう！情報処理試験！ 〜１問１問コツコツと〜 ☆
★ ★
☆ 2000.5.26 / vol.355 / mag2:3022 / melma!:2836 / total:5858 ☆
★ ★
☆★☆★☆★☆ 次の試験は、１０月１５日（日）です。 ☆★☆★☆★☆
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
■今日の問題■☆☆（等幅フォントで見てね！）
----------------------------------------------------------------------
挿入法(Straight Insertion) を用いてランダムに並んだデータを整列する。
300 個のデータを整列するための比較演算回数は、100 個のデータを
整列する場合のおよそ何倍になるか。
ア 3
イ 5.2
ウ 9
エ 27
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
■解答■（出典：H10. 1種 問11）
----------------------------------------------------------------------
ウ 9
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
■解説■
----------------------------------------------------------------------
引き続き、ソート関連の問題です。
過去問を見て気づいたのですが、ソートの問題って意外に良く出てますね。
今日は、挿入法(Straight Insertion) でした。
挿入法とは、データ列からデータを１つ取り出し、残りのデータ列が正しい
順序になるように、取り出したデータを挿入します。これを全てのデータに
行い、正しい順番にソートする方法です。
と言っても、よくわからないので、今日もやってみましょう。
次のデータを左から小さい順に並び替えますね。
> ９，７，１３，６，１
まず、一番左からデータを１つ取り出します。９ですね。
残ったデータ列が（７，１３，６，１）になりますね。
最初は、取り出したものを残ったデータ列の先頭（左）に挿入します。
取り出して挿入する所までが１セットです。
> ９，７，１３，６，１
−
９の下に「−」をつけました。
これは、並び替えが終わった部分を表わします。（１セット終了）
次に並び替えが終わっていない部分から、また１つデータを取り出します。
つまり、７を取り出します。（２セット目開始）
この取り出した値を、すでに並び替えの終わった（「−」をつけた）データ
と比べていきます。
よって、９と７を比べます。
９と７は、７の方が小さいので、９の前（左）に７を挿入します。
すると、下のようになりますね。（２セット目終了）
> ７，９，１３，６，１
−−−
後は同じ事の繰り返しです。３セット目は、１３を取り出して、
すでに並び替えの終わった（「−」をつけた）データと比べます。
７と１３を比べると、１３が大きいのでそのまま。
９と１３を比べると、１３が大きいので９の後ろに入れる。
よって、３セット目が終わると下のようになります。
> ７，９，１３，６，１
−−−−−−
同様に、４セット目は
> ６，７，９，１３，１
−−−−−−−−
５セット目が
> １，６，７，９，１３
−−−−−−−−−−
となり、これで並び替えが完了です。
さて、問題は、比較回数なのですが、挿入法では元データの並び方によって
比較回数が変わります。ためしに、トランプを用意して何通りかやってみて
確認しても良いでしょう。
よって、最悪の場合で比較回数が一番大きくなるときと、平均の場合を
考えます。証明は省略しますが。
最悪の場合は、データが n コあったときには、下のような式になります。
> 最悪の場合の比較回数 ＝ n(n-1) / 2
また、平均オーダは
> 挿入法の平均オーダ ＝ n^2
になります。
問題は
> 300 個のデータを整列するための比較演算回数は、100 個のデータを
> 整列する場合のおよそ何倍になるか。
ということなので、平均オーダで考えれば
300 コ = 300^2 = 90000
100 コ = 100^2 = 10000
よって、正解は９倍となります。
ソートのオーダ(order) は一般に下のようになります。
扱うアルゴリズムによって、若干変わることもありますが。
バブルソート n(n−1)/2
選択ソート、挿入ソート n^2
クイックソート、マージソート nlog2 n （底が２です）
線形探索法 n
２分探索法 log2 n （底が２です）
＃オーダとは、演算量がその量に比例するということです。
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
■これ、おしえてっ！■
----------------------------------------------------------------------
このコーナーでは、みなさんからの取り上げてほしい問題を
募集しています。いつの問題なのかわからない方は、具体的に
「○○○についての問題をやってー！」で、構いません。
昔、メールをくれた方でも「まだリクエストに答えてもらってない！」
というのが、たくさんあると思いますので、しつこく送ってもらえれば、
このコーナーで取り上げたいと思います。
----------------------------------------------------------------------
〜お便り、回答をどうもありがとうございました〜
昨日、夜の１時ごろまでにお便りをくれた方には、約束どおり全員に返信
しました(^^; それ以降に送ってくれた方には、今日の夜に返信します。
どうでも良いお便り（？）でも、いつでも待ってます！！
〜次回も待ってまーす〜
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
■選択肢で勉強しよっ！■（答えはこのメールの一番下にあります）
----------------------------------------------------------------------
アルゴリズム(algorithm) って？
＃このコーナーのリクエストは選択肢で勉強する間がないくらいに
たくさん来てます(^^;
順に取り上げていますので、リクエストした方は少しお待ちを。
リクエストは、パソコン関連用語や時事用語でもＯＫ！です。
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
よみものさーちランキング http://ranking.yomimono.com/cgi-bin/count?43
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
のんびりやろう！情報処理試験！ 〜１問１問コツコツと〜
----------------------------------------------------------------------
編集・発行：しゅんぜい shunzei@geocities.co.jp
発送：melma!（旧 clickincome）http://www.melma.com/
：まぐまぐ http://www.mag2.com/
登録・解除：http://www.geocities.co.jp/SiliconValley/2975/
質問用掲示板（自由に使ってね！）
午前：http://www10.cds.ne.jp/~cha/cgi-bin/geo/bbs1/wforum.cgi
Ｃ言語：http://www10.cds.ne.jp/~cha/cgi-bin/geo/bbs2/wforum.cgi
----------------------------------------------------------------------
☆ちょっとした誤字、脱字は目をつぶってくださいね(^^;
☆このメールマガジンは毎週日曜日はお休みです。
☆掲載内容の利用において発生した事故・損害等には一切責任を負いません。
（転載は構いませんが、その旨を明記しておいてくださいね）
☆バックナンバーはホームページにあります。
☆広告掲載については shunzei@geocities.co.jp まで、お願いします。
☆メールマガジンの購読の申込・解除は個人の責任で行ってくださいね。
しゅんぜいは一切代行しません！
----------------------------------------------------------------------
☆答え（読者の方のリクエストです）
ある目的（問題）を解くために、機械的に処理を行う手順のこと。
この手順を文章や流れ図で表わすのが一般的です。
これをプログラミング言語をつかって表現すればプログラムと呼びます。
アルゴリズムってと言うのはよく聞かれるのですが、どうもうまく説明
できないんですよね。誰かうまい説明を送ってくれると助かります。
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
この記事の発行者<<前の記事
｜
次の記事>>
｜
最新の記事
2008年度の受賞メルマガ
