- - PR -
論理的思考力テスト【解答つき】
投稿者 | 投稿内容 | ||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
|
投稿日時: 2006-08-28 09:35
トランプを整列させる時などは、気がつくとバブルソートしてますね^^;
まあ、実際やってみるとすぐわかるのですが、確かに効率は悪いですね。 僕の場合は、覚えたばかりだったので、実際にやってみたかったのです。 一通りのパターンをやってみた後は、先頭の番号で分類するやり方に切り替えました^^; (二人いましたし、間違えてもすぐに修正できますから)
指サックをつけているかどうかで、ループの速度がまるで違います。 それと比較する文字数が1つ増えるだけで比較演算速度が遅くなりますw
リアルで処理する場合は、ワークエリアは広すぎても狭すぎても遅くなる場合が多いです。 | ||||||||||||||||
|
投稿日時: 2006-08-28 20:30
なんかちゃんと伝わってないような気がするので、念のため補足。 #それはわかってる、ということならごめんなさい。 13個で軽重まで判別可、軽重判別不要なら14個までいけるのは、 あくまで「あらかじめ1個正解玉を持ってる」場合です。 持ってない場合軽重まで判別できる上限は12個です。 秤に乗せられるのは偶数個、という条件によって上限は-1され、 さらに軽重判別要否によって±0.5、という解釈が正しいかと。
マジレスすると、バブルソートって連続した二者の比較・入れ替えを繰り返すアルゴリズムですから、リアルでそんなことはまずしないですね。リアルでのソートは、どちらかというと、マージソートに近いのでは?
この場合、ワークエリアが足りなくなって、机の端から書類がどさっと落ちたり、他の書類と混ざったりすることを、バッファオーバーフローというのでしょうか?w | ||||||||||||||||
|
投稿日時: 2006-08-28 23:13
mが3の倍数でない場合は、偶数個制約(というか「右と左に同数の球を載せる」制約)によって、-1されます。 mが3の倍数だった場合は、最初からきれいに3等分できるので、-1する必要はありません。 この問題の場合、(3**n - 1)/2 は決して3の倍数にならないので常に-1になるわけですが、 あっさりと「上限は-1され」と言ってしまっては論理の飛躍でしょう。
ものがトランプのカードだったら、バケットソートするのが普通でしょう。 対象によってバケツの数が多くなりすぎる場合は、再帰的バケットソートというか、 「クイックソートなら2等分する処で10等分する」ような手順を使いませんか? | ||||||||||||||||
|
投稿日時: 2006-08-28 23:24
マジレスすると、そんな事します? バブルソートというと、カードを一枚一枚入れ替えると想像しますが、対象のカードと横のカードを目視で見比べる、その次のカードと見比べる、という風にしませんか?入れ替えるではなく、見比べるです。で対象のカードの番号よりも小さい番号があれば、持ち替えて同じ事をします。あ、でもこれってバブルソートじゃないか。 でも、バブルソートが一番イメージに近いと思ったんですが、違いましたかね。 _________________ 囚人のジレンマな日々 | ||||||||||||||||
|
投稿日時: 2006-08-28 23:55
バブルソートは隣同士入れ替えるだけだけど、カードが1だったら一気に左に置いちゃう。 全種類もってるわけじゃないのでバケットソートはしない。 | ||||||||||||||||
|
投稿日時: 2006-08-28 23:56
学生のころ、証券会社の代行会社で、証券を分類するのに使っていました。 まだ、東証に活きのいい兄ちゃんやおっさんがいたころの話です。 [追加]あ、sort じゃないけど、郵便局の荷わけってもろこれだな。 [ メッセージ編集済み 編集者: ちゃっぴ 編集日時 2006-08-28 23:59 ] | ||||||||||||||||
|
投稿日時: 2006-08-29 00:43
あう、つっこまれてしまった(^^; えーと、私が言及してたのは、n回秤を使って犯人を突き止められる玉数mの上限値、すなわち「決して3の倍数にならない数」でしたので、あっさり-1しました。 飛躍させちゃったところをちゃんと説明すると、(3**n - 1)/2ってゆうのは漸化式を整理して得た式なわけですが、その漸化式を求める根っこのとこでは、「1回目の計測で秤に乗せる玉の数の上限値」と「1回目の計測で秤に乗せない玉の数の上限値」を分けて考えていたわけで。 で、「1回目の計測で秤に乗せる玉の数の上限値」は、論理的には3のべき乗すなわち奇数ですので、偶数個制約による-1が「必ず」発生します。 一方、「1回目の計測で秤に乗せない玉の数の上限値」は、秤がつりあい続けた場合に最後に残る玉が軽重判別不可となるため、軽重判別要の場合は-1になります。 従って、「あらかじめ1個の正解玉を持っている/いない」「軽重まで判別する必要がある/ない」という2つの条件によって、それぞれ別々に-1が発生する、ということが言いたかったのですが、±0.5っていう表現が良くなかったのかもしれません。
確かに実際に指を動かす前に脳内で行う作業まで考えるとどうとでもとれちゃいますね。私の場合、脳内でばらばらに解体してからマージするイメージだったのですが、言われてみると挿入ソートの方が近いかも。でも複数枚1ぺんに比較してるつもりでも潜在意識レベルでは2枚ずつ比較していて、そういう意味ではバブルソートとも言えるかもしれません… #大貧民がやりたくなってきた | ||||||||||||||||
|
投稿日時: 2006-08-29 00:49
確かに脳内作業を入れると何とでも言えてしまいますね。 そして、言われてみると挿入ソートが一番イメージに近いです。 #大富豪やりたくなってきた _________________ 囚人のジレンマな日々 |