![](http://oshiete.xgoo.jp/images/v2/pc/qa/question_title.png?e8efa67b6d)
A 回答 (7件)
- 最新から表示
- 回答順に表示
No.7
- 回答日時:
#5,6です。
クイックソートにこだわって回答して参りましたが、重大な欠点が見つかったので、撤回させていただきます。まことに申し訳ありません。
クイックソートは、実務上は極めて優秀な方法で、通常は他の追従を許さないのですが、理論的には弱みを抱えています。すなわち、わざと意地悪をして、クイックソートにとって不都合なデータを作ってやると、他の方法に負けてしまいます。試みに「41523」から始めると、比較回数が8回になってしまいます。これでは回答になりません。
カードが2~4枚の場合は、(カード数×2)-3ですから、もし5枚で7回ということであれば、この式はそこまで成り立ちます。高々5枚であれば、根気よくあらゆる場合を想定すれば、解は簡単に求められると思います。例えば、トーナメント式の図を書きます。決勝までやって、比較回数は4です。2位の候補がどこにあるか、次いで3位の候補がどこにあるかを、順々に解決して行く方法が考えられます。ですが、一般に、数学好きな人は、そういう作業をやりたくないものです。
しかしポリアという人の『帰納と類比』という本に「そのような作業から法則を発見することがあるので、単純作業だからといって軽視してはいけない」という意味の教訓がありました。面白くない仕事ですが、そこから着手してはどうでしょうか。そのうちに、何か成果が得られるかもしれません。
No.6
- 回答日時:
#5です。
クイックソートの原理を「再帰呼び出し」に触れないで説明しようとして、かえって論理的な破綻を起こしてしまいました。すみませんが、#5を破棄してください。
次の手順を、ぜひトランプなどでお確かめください。
左から小さい順に並べることを最終目的とします。
(1)最初に左端札を「基準札」、右端札を「対象札」とします。この手順の目的は、基準札の位置を確定することです。
(2)基準札と対象札を比較し、
--大小関係が正しければ(つまり左のほうが小さければ)対象札の隣(基準札に近いほう)を新しい対象札として続行します。
--大小関係が逆ならば、基準札と対象札の位置を交換して続行します。
(3)こうしていつかは、基準札と対象札が隣接して、対象札の移動ができなくなります。このとき基準札の位置は確定します。
(4)確定札を含まない札から成る2枚以上のストリング(列)に対して、この手順を適用します。こうして、基準札の位置が一つずつ確定していきます。
以下の説明は特に理解しなくても、この方法は使えます。
「再帰呼び出し」というのは、呼び出すプログラムと、呼び出されるプログラムが同一である場合の手続きを指します。実行が終了していないのに、未完了の部分に対してプログラムを再適用しようとするものです。会社が1つしかないのに、下請け発注をして、その注文書を自分自身が受け取って「下請け会社になりすまし」をするという、プログラミング上のテクニックです。クイックソートは、再帰呼び出しが可能なコンピューターでのみ実行できます(現在は、すべてのパソコンンで可能ですが)。
No.5
- 回答日時:
「並び替え」ではありません。
「並べ替え」です。並べ替え問題は、コンピューターの世界で詳しく研究されています。キーワード「クイックソート」で調べてみてください。これなら7回以内でできると思います。
クイックソートの原理:
(1)左端を「基準札」、右端を「対象札」とする。
(2)2つの札の大小関係が正しければ、対象札の隣(基準札寄り)を次の対象札とする。
(3)基準札と対象札が隣り合ってしまえば、この2つについては完成なので、未完成部分について(1)に戻る。
(4)もし(2)で大小関係が逆であれば、両札を交換して(2)から再実行する。ただし、この交換では「基準札」「対象札」の資格は各札が背負ったまま移動するので、両札の左右関係は反転する。
No.4
- 回答日時:
この問題に関して別のアプローチを試みました。
Jリーグなどで使われるリーグ対戦表(総当り戦形式)を用いて、比較すべき数字の組み合わせを表に○印してみるというものです。
この表を大きい数字から数字順に並べ替えて作図しますときわめて特徴的な図形が現れます。
具体的には表の斜線部分に規則的に印される結果になります。
現在ANo3さんによりますと12枚のカードを大きい順に並べ替えるのに必要な手順数は29手順ということですが、このリーグ対戦表からは13枚以上のカードを並べ替える場合の手順数が感覚的に類推できそうな図表が得られます。
数学的に証明しうるのかどうかは解りませんが、専門家の方または詳しい方がありましたらご教示願えるとありがたく思います。
質問者さまの提起された質問に触発されてこの場をお借りして質問させていただきましたがご了承ください。
なお質問者さまは見たところ受験勉強中のかたとお見受けしました。
この問題には深入りなさらずに、気分転換程度になさってください。見当違いでしたらお許しください。
No.3
- 回答日時:
お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!
おすすめ情報
- ・漫画をレンタルでお得に読める!
- ・【あるあるbot連動企画】あるあるbotに投稿したけど採用されなかったあるある募集
- ・【あるあるbot連動企画】フォロワー20万人のアカウントであなたのあるあるを披露してみませんか?
- ・映画のエンドロール観る派?観ない派?
- ・海外旅行から帰ってきたら、まず何を食べる?
- ・誕生日にもらった意外なもの
- ・天使と悪魔選手権
- ・ちょっと先の未来クイズ第2問
- ・【大喜利】【投稿~9/7】 ロボットの住む世界で流行ってる罰ゲームとは?
- ・推しミネラルウォーターはありますか?
- ・都道府県穴埋めゲーム
- ・この人頭いいなと思ったエピソード
- ・準・究極の選択
- ・ゆるやかでぃべーと タイムマシンを破壊すべきか。
- ・「I love you」 をかっこよく翻訳してみてください
- ・歩いた自慢大会
- ・許せない心理テスト
- ・字面がカッコいい英単語
- ・昔のあなたへのアドバイス
- ・かっこよく答えてください!!
- ・あなたが好きな本屋さんを教えてください
- ・これ何て呼びますか Part2
- ・人生で一番思い出に残ってる靴
- ・ゆるやかでぃべーと すべての高校生はアルバイトをするべきだ。
- ・初めて自分の家と他人の家が違う、と意識した時
- ・単二電池
- ・チョコミントアイス
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
-
EDATE関数で末日を正確に表示さ...
-
オルカンを8月1日付けで購入...
-
自分は自分が得をするかどうか...
-
友達ってどういう基準で選んで...
-
BMI は日本と世界で基準が違う...
-
あなたに回答して欲しい質問 の...
-
まだ積立nisaを初めて2ヶ月程な...
-
毎月決算型の投資信託で基準価...
-
楽天アプリ iSPEED
-
インベスコ 世界厳選株式オープ...
-
ニーサ始めたばかりです。 月3...
-
「個別元本単価」と「基準金額...
-
来年からの新nisaでの運用について
-
雪だるま投信
-
投信始めたいのですが
-
積立分譲???
-
インド株について
-
ほったらかしで初心者でも簡単...
-
新NISAでオルカンの積立を検討...
-
ワールド・ソブリンインカム ...
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
-
オルカンを8月1日付けで購入...
-
ウォータースライダーなどの身...
-
回答常連者にはベストアンサー...
-
将来、AIでも出来ないものはあ...
-
あなたに回答して欲しい質問 の...
-
スクールカーストって何!何が...
-
100×1.2と100÷0.8 どちらも20%...
-
EXCEL
-
EDATE関数で末日を正確に表示さ...
-
絶対値と相対値の違い
-
「普通に~」という言葉について。
-
低身長イケメン、中身長フツメ...
-
X〜N(409.1, 0.9^2)のとき、 P(...
-
幸せって何が基準なのかな?
-
オームの法則で数値オーバーで...
-
イワシの開きは何グラムぐらい...
-
投信の購入価格
-
Webカメラの選び方
-
特別分配金を再投資する意味
-
エクセルで時間を計算する場合...
おすすめ情報