以下の問題を授業外課題として出されましたがわかりません。身近に分かる人物もいません。
先生も答えてくれません。
解答お待ちしております。
1.以下の文章の空欄を埋めよ.但し,((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 に対しても実用に耐える
A 回答 (4件)
- 最新から表示
- 回答順に表示
No.4
- 回答日時:
このアルゴリズムはやってないかもしれませんが、他のアルゴリズムや、その「計算量」の考え方はやってますよね?
何の前振りも無しに、こんな問題を出すとは思えません。
他のアルゴリズムだはどんなことやっていたか、復習してみましょう。
n個の整列にかかる時間がT(n)なら、n/2個の整列にかかる時間はT(n/2)です。
(4)は、具体的な計算をするのではなく、T(n/2)や他の値を使って、T(n)との関係だけを求めておきます。
実際の値の計算は、とりあえず、置いておきます。
※ (5)以降が、その具体的な計算をしていくところです。
コンピュータになったつもりで、御自身で具体的にやってみるのもよいでしょう。
トランプを用意します。
全部使ってもよいのですが、わかりにくいので、スペードだけを使います(ハートでもいいですけど)
場に
J
Q
K
と置きます。
1~10のカードを裏返して混ぜ、5枚ずつに分割します。
片方を、小さいカードが上になるように順番に並べて、Jの横に置きます。
もう片方は同様にしてQの横に置きます。
例えば、こういう状態になったとします
J; 4
Q: 1
K;
これが「前段階として,データを半々に二つのグループ I と II に分割し,それぞれを独立に整列する.」の部分です。
JがグループI,QがグループIIです。
ここから、アルゴリズムに従って処理します。
まず最初に。
JもQもあるので、「while (両グループに要素が残っている)」の部分です。
各グループの最小値は、一番上です。 4 と 1 を比べれば 1が小さいです。
従って、 1 を QからKへ移動します。
J; 4
Q: ↓
K; 1
ここまでが「1回」で、時間は a だけかかります。
ここで、 JとQは整列してあるので、最小値を探すには、一番上を見ればいいことになります。
人間だと、5枚くらいなら、全部表にして並べて、一番小さいカードを探しても大して苦ではありません。
ですが、コンピュータにはそんなことはできません。いちいち全部のカードを調べて探さなければなりません。
それを、「整列しておいて、先頭だけを見る」とすることで、コンピュータでも楽に最小値を探すことができます。
これを繰り返していくと、
J; 無し
Q: 9
K; 1 2 3 4 5 6 7 8
のような状態になります。ここからは
「while (グループ I に要素が残っている) do」
「while (グループ II に要素が残っている) do」
に従って、残っているカードを1枚ずつKへ移動します
全部終わると
J; 無し
Q: 無し
K; 1 2 3 4 5 6 7 8 9 10
とKの整列ができあがります。
かかる時間は
T(10)=「Jに並べる時間」+「Qに並べる時間」+ 「Kへ移動させた回数」× a
になるのがわかると思います。
JとQを並べるのに、このアルゴリズムを使えば、「5枚並び換える時間」ですから
T(10)=T(5)+T(5) + 「Kへ移動させた回数」× a
になります。
「Kへ移動させた回数」は....もうわかりますよね?
実はアルゴリズムは有名なもので、名前も付いています。
それで検索すれば解説も「答え」も見つかってしまうのですが....とりあえずは黙っておきます。
あと「バカソート」って何のことだろう?
計算量の話ならバブルソートかな、とも思いますが、「バカ」って意味では、ボゴソート、ボゾソートの方が「バカ」ですし。
No.3
- 回答日時:
学術的には名前があるのかもしれませんが、
ナチュラルマージソートをちょっと非効率にしたようなソートですね。
質問にはありませんが、分割は1個までやってしまうのでしょうね。
#実際にはデータを一度スイープすればどこまで分割が必要か判断できるので
#1個まで分解したりはしないです。
T(2^p)
=2 X T(2^(p-1)) + a x 2^(p)
=2 x (2 x T(2^(p-2)) + a x 2^(p-1)) + a x 2^(p) = 4 x T(2^(p-2)) + 2 x a x 2^(p)
= 2^p x T(1) + pa x 2^p = nT(1) + pan = nT(1) + logn・an
なので a に比例して nlogn のオーダーなのでしょう。
オンラインで書いたので、間違っていたらすいません。
No.2
- 回答日時:
まず、あなたがどこまで埋めることができたのか、教えてくれませんか?
ほとんどは、 T(x),n,p,a を使った式です。
2^p=n より、 p = log n ということも利用しましょう。
データ量n個の時間がT(n)なら、「半分のデータ量」はn/2で、その時間はT(n/2)です。
14,15の選択肢ですが、 14には a~e,15にはf~iが入るのはわかるかと思います。
14が決まれば15が決まります。また、相手の無い選択肢があります。
それはわかりますか?
※ hとiは解釈にちょっと困る
#1さんにもお答えしたとおり、全く分からないのです。最初から、何を言っているのかわかりません。
前段階の話からついていけません。
前段階で整列?が必要なのでしょうか?
何回?それはどのようにすれば求まりますか?(n-2)回とかでしょうか?
14と15の選択肢ですが、選択肢を見た感じ、片方(14)にlogなどが入り、もう片方(15)は言葉だろうな、という漢字のレベルでは認識していました。
No.1
- 回答日時:
「先生も答えてくれません」て, そりゃそうでしょう. そこで簡単に答えてしまうようでは, それこそ「授業外課題」になどなりもしないんだから.
で, なにをどのくらい考えた末の「わからない」ですか?
ありがとうございます。正直「全く分からない」です。
というのも、先生はアルゴリズムに関して全く授業で触れていません。買わされた教科書にも載っていません。なのにもかかわらず、この問題から試験を作成するとおっしゃっていました。「そういえば、こんな問題があるから、解いておいてね、テストに出すから」とのことです。なので、周りの友人たちもわからず、疲弊しきっています。
お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!
似たような質問が見つかりました
- その他(プログラミング・Web制作) pythonにおける単方向リストの実装について 4 2022/07/13 12:34
- 統計学 確率統計の問題です。 3 2022/04/07 04:39
- Ruby 初心者プログラミング 3 2022/10/12 11:31
- Visual Basic(VBA) 【前回の続き続きです、ご教示ください】VBAの記述方法がわかりません。 2 2022/08/24 20:49
- C言語・C++・C# このプログラミングの問題を教えてほしいです。 キーボードからデータ数nとn個のデータを入力し、平均値 3 2022/12/19 22:51
- Excel(エクセル) 【困っています】VBA 追加処理の記述を教えてください。 1 2022/08/25 22:54
- PHP PHPの構文で間違えが分からない 5 2022/07/11 16:38
- C言語・C++・C# このプログラミングの問題を教えて欲しいです。 キーボードから整数kを入力し、kが配列aの中に何個存在 2 2022/12/19 22:50
- Visual Basic(VBA) 【前回の続きです、ご教示ください】VBAの記述方法がわかりません。 2 2022/08/16 16:44
- 大学・短大 C言語線形リストの問題です 3 2022/12/22 00:45
おすすめ情報
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
-
100以下の自然数のうち、次のよ...
-
エクセルで60進法計算の仕方...
-
工事の共通仮設費率の計算がで...
-
エクセル関数で源泉徴収額を計...
-
この産み分けの計算でハズレの...
-
文字を含む三角関数の定積分の...
-
問1.絶対値が3より小さい整数に...
-
エクセルでのシグマ計算
-
整式を整理する・計算する
-
経費率の計算方法を教えて下さい。
-
3桁の自然数の中で、次の個数を...
-
高校時代電離平衡の計算に関し...
-
8進数の765.17を16進数にしたい...
-
勝率50%の事象を100回やって勝...
-
高校の数学1A2Bで難しいと思う...
-
ローン支払いにおける金利の計...
-
ラプラス変換の「s」とは?
-
カルバック・ライブラー擬距離...
-
1億x1億はいくらでしょうか?
-
5進法を10進法への直し方
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
-
エクセル関数で源泉徴収額を計...
-
エクセルで60進法計算の仕方...
-
100以下の自然数のうち、次のよ...
-
工事の共通仮設費率の計算がで...
-
文字を含む三角関数の定積分の...
-
エクセルでのシグマ計算
-
この産み分けの計算でハズレの...
-
経費率の計算方法を教えて下さい。
-
ラプラス変換の「s」とは?
-
Excelで勤務の過不足時間を計算...
-
3桁の自然数の中で、次の個数を...
-
最小公倍数と最大公約数の求め...
-
問1.絶対値が3より小さい整数に...
-
8進数から16進数への変換
-
99の10乗の下位5桁の数を求める...
-
関数電卓の使い方
-
勝率50%の事象を100回やって勝...
-
小学生の割合の問題
-
A÷(B×C)=?
-
高校時代電離平衡の計算に関し...
おすすめ情報