C言語なら俺に聞け（入門編）Part 125 [sc](★0)
-
- 1
- 2014/02/16(日) 01:49:14.42
-
C言語の入門者向け解説スレッドです。
★前スレ
C言語なら俺に聞け（入門編）Part 124
http://toro.2ch.net/test/read.cgi/tech/1389096769/
★過去スレ
ttp://makimo.to:8000/cgi-bin/search/search.cgi?q=%82b%8C%BE%8C%EA%82%C8%82%E7%89%B4%82%C9%95%B7%82%AF&andor=AND&sf=0&H=&view=table&D=tech&shw=5000
★教えて欲しいのではなく宿題を丸投げしたいだけなら
↓宿題スレ↓へ行ってください。
C/C++の宿題片付けます 166代目
http://toro.2ch.net/test/read.cgi/tech/1381909900/
★C++言語については避けてください。C++対応明記スレへどうぞ。
★分からない事をなるべく詳しく書いて下さい。
★ソースコードを晒すと答えやすくなるかもしれません。
# 抜粋／整形厳禁、コンパイラに渡したソースをそのまま貼ること。
# サイズが大きい場合はアップローダ等を利用してください。
ttp://codepad.org/
ttp://ideone.com/
★開発環境や動作環境も晒すと答えが早いかもしれません。
★質問者は最初にその質問をした時のレス番号を名前欄に書いて下さい。
【重要】
当たり前の事ですが、2chではコピペ荒らしは禁止されています
-
- 704
- 2014/03/24(月) 19:44:38.07
-
「縦3横6計18セルある長方形に１〜18までの要素を1個ずついれて」
なんだから、最適化された処理は
const static ans[3][6] = { { 1,2,3,4,5,6},{7,8,9,10,11,12},{13,14,15,16,17,18}};
だと思うんだけど。固定値だよね？
-
- 705
- 2014/03/24(月) 19:45:33.50
-
行でソートの場合
6
3
1
をソートしたら
1
3
6
になって6は1行目最終列なのに、遠のく事にならないでしょうか？
-
- 706
- 2014/03/24(月) 19:45:34.95
-
>>701
整列されている状態を6で割った余りにしてみろ
縦横バブルソートだと
12...
34...
56...
ってなったら積む
-
- 707
- 2014/03/24(月) 19:47:18.04
-
>>704
与えられた要素をその整列された状態にするのに「上下左右の交換」が最低何回必要かって問題だから
ソートした結果を答えろという問題ではない
-
- 708
- 2014/03/24(月) 19:50:16.45
-
そもそも整列された状態から交換を繰り返さないとダメですね
適当に配置した標本だと元通りできないですね…
>>706
全く分かりません、余りだと詰むんでしょうか？
-
- 709
- 2014/03/24(月) 19:51:49.13
-
「どういうアルゴリズムが最適か」だから整列不能も含めて判断しろってことじゃないの
いずれにしろ問題が曖昧すぎる
-
- 710
- 2014/03/24(月) 19:51:58.70
-
馬鹿には無理
-
- 711
- 2014/03/24(月) 19:52:28.14
-
とりあえず、最初にあまりで比較して最後は要素同士を比較ってことですか？
-
- 712
- 2014/03/24(月) 19:55:26.67
-
>>709
整列可能という前提です、問題に不備がありすいませんでした。
確実に整列できる方法です。
例えばバブルソートの場合どんなパターンでもO(n(n-1)/4)回で整列可能です。
この場合もO(?)回で完全に整列できるのか知りたいです。
元々整列されていた場合早くするというのは最適化問題になりますので
そういう問題ではなくMAXオーダーを求めたいという事です。
-
- 713
- 2014/03/24(月) 20:07:30.14
-
>>708
１ ４ ７ 10 13 16
２ ５ ８ 11 14 17
３ ６ ９ 12 15 18
"縦だけ""横だけ"で値の大小による比較ではソート済み（これ以上の比較は不要で収束している）
が、解の並びではない
-
- 714
- 2014/03/24(月) 20:11:31.94
-
分かりません…
-
- 715
- 2014/03/24(月) 20:15:11.99
-
ID:5KtS3atQ
こいつに何言ってもわかんないだろ
NGに入れとけクズども
-
- 716
- 2014/03/24(月) 20:15:38.42
-
そもそも横 縦とも大小の矛盾が無いけど解は無い例なんて
存在するんでしょうか？
3 4 8 9 10
2 5 12....
..........
こういう事ですよね？
無いと思うのですが
-
- 717
- 2014/03/24(月) 20:16:33.50
-
>>715
おまえは毎日ハロワ通いと転職サイト最低３カ所チェックする
日課を終わらせること。
-
- 718
- 2014/03/24(月) 20:21:10.20
-
ルービックキューブを可能なパターン全てこなしてから、最短手順を求めるやつはいない。
最短に近い攻略法で攻めるだろ。
-
- 719
- 2014/03/24(月) 20:27:54.88
-
結局オーダー回数は理論的に求められないってことでＯＫですか？
そうなるど最適化問題に帰着するんでしょうか
-
- 720
- 2014/03/24(月) 20:29:59.92
-
>>719
なんでそんな結論になったのか・・・
何処にもランダム要素なんて発生し無いのに論理的に求められない理由は無いぞ？
-
- 721
- 2014/03/24(月) 20:32:21.66
-
>>720
この問題はオーダー何回でしょうか？
後最適化問題じゃないけど、早くする方法みたいなのもあれば
例えばバブルソートを双方向バブルソートにするみたいな
最適化ではないですが強化バージョンなので…
-
- 722
- 2014/03/24(月) 20:34:15.30
-
ゴミニートことQZが大発狂中！大発狂中！
ム板を腐らせるゴミは出ていけ！！
-
- 723
- 2014/03/24(月) 20:37:04.61
-
>>721
まず基本的な事から。名前書け。
質問を小出しにするな体系立てて、自分で考えて
わからないことだけ背景含めて説明しながら質問しろ。
-
- 724
- 2014/03/24(月) 20:37:19.07
-
素朴な疑問
ビッグオー表記で O(n^2) ならまだしも O(n(n-1)/4) って意味あるの？
-
- 725
- 2014/03/24(月) 20:43:19.67
-
>>723
背景ですが、頭脳王という番組を見て9マスの正方形の中にある8個の数字の
書いたパズルを並び替えるという問題があってそこから感銘を受けて18マス
ではどうかという問題を思いつきました。
最初は最適化問題でどうしたら最短で解けるかという事を考えましたが
それ以前に少なくとも何回やれば、つまり最大何回やればどんなパターンで
も整列できるのかすら分からないのでそっちから考えたいと思いました。
-
- 726
- 2014/03/24(月) 20:49:27.98
-
>>717
わろたｗｗｗ
-
- 727
- 2014/03/24(月) 20:53:52.27
-
>>725
いや、まずは名前書けよ・・・
-
- 729
- 2014/03/24(月) 20:57:15.33
-
>>725
名前は次から書けばいいとして話を進めるか。
大まかな背景は解った。
で、どこまで考えて結果はどうなって、いまは何に躓いてるんだ？
-
- 730
- 2014/03/24(月) 20:59:09.34
-
ほらみろゴミ（質問者）が調子に乗り出した
もう目も当てられないよこのスレ
-
- 731
- 2014/03/24(月) 21:00:03.14
-
>>728
あれ。2chは初めて？
流石に実名は求めてない。
他人とかぶらなければ全く問題無し。
質問とかの連続した話題の時は、他の人が話題追いやすいように
一番初めに質問したときの番号を埋め込んどくのが正解。
-
- 733
- 2014/03/24(月) 21:09:33.12
-
ゴミ回答するなQZ
お前は不要な存在
-
- 734
- 2014/03/24(月) 21:13:06.28
-
>>732
縦をソートする意図がわかんない
最終的に移動完了させるかたちは一つしかないだろ？
すべての移動は、最終的な位置に近づく用に移動させるべきだ。
ここまでは解るよな。後は考えたら見えるはずだ。
-
- 735
- 2014/03/24(月) 21:18:49.54
-
ろくにCできないゴミが発狂していいスレじゃねえだろ
マジで消えろゴミクズうんこ馬鹿ども
-
- 737
- 2014/03/24(月) 21:29:18.09
-
お前はID真っ赤だ
これ以上質問するなゴミすれになるぞ
-
- 738
- アルゴリズム
- 2014/03/24(月) 21:40:07.75
-
うん？やっぱり要素数18のバブルソートなのかな…
-
- 739
- 2014/03/24(月) 21:48:00.78
-
お前調子のるな
質問者だからって許されることじゃない
-
- 740
- アルゴリズム
- 2014/03/24(月) 21:48:49.36
-
結論出ました。上限回数はバブルソートの回数ですね。
長方形を一列とみなすという事ですが、縦も交換できるから
強化バージョンが作れると思うのですが無理でしょうか？
-
- 742
- 2014/03/24(月) 22:08:40.60
-
これだけレスついて回答しないとか馬鹿だろ
スレを私物化するな、出ていけ
-
- 743
- 2014/03/24(月) 22:09:53.03
-
自分の頭で考えるってことができないんじゃプログラミングは無理
クレクレで出来ることなんてたかが知れてるぞおい
-
- 744
- アルゴリズム
- 2014/03/24(月) 22:18:58.11
-
使える変数はa[17]だけとします
つまり好きな要素を選んだり、選択ソートみたいに最小要素を選んだり
する事はできない。
-
- 745
- 2014/03/24(月) 22:30:34.53
-
チョンの脳なんじゃね？本国に帰れよ
-
- 746
- 2014/03/25(火) 00:11:31.10
-
愚直に1から順番に移動してみた例 :
https://ideone.com/5EgKA2
各値を線形探索しているため遅い。
-
- 747
- 2014/03/25(火) 00:20:15.28
-
>>746
96行も…ありがとうございます
それってバブルソートのアルゴリズム使ってないですか？
-
- 748
- 2014/03/25(火) 00:25:10.02
-
マナーすら守れない奴はこないでね。
回答なんて誰もできないから。
マナーの無い奴に回答すると調子乗って暴れまくるし
ほかの馬鹿がマナー守らなくていいと勘違いするからね。
だから、お前には誰も回答しないんじゃなくて、 "誰も回答できない" んだよ。
-
- 749
- 2014/03/25(火) 00:33:14.10
-
>>747
バブルソートに当たるかどうかは分かりませんが、かなり近い操作はしています。
1. n = 1とする
2. nと一致する横x番目, 縦y番目を検索する
3. nが位置すべきなのは横correct_x番目縦correct_y番目である
4. xがcorrect_xに近づくように隣同士交換する
5. yがcorrect_yに近づくように隣同士交換する
6. n = n + 1して2.へ(n = 18まで繰り返す)
左上から確定していき、初めにxで並び替えるため、左上を絶対に通りません。
従って必ず並び替えられます。
-
- 750
- 2014/03/25(火) 00:37:56.95
-
>>749
なるほど、変数は使ってるものの思いつかなかった…
整列されてる要素に影響はないでしょうか？
-
- 751
- 2014/03/25(火) 00:42:57.89
-
なるほどー
123と並んでる時、4がどこかにあるはずですが、yを先に選ぶと
重なる可能性ありますからね、よくできたアルゴリズムですね！
感動しました
-
- 752
- アルゴリズム
- 2014/03/25(火) 00:46:01.81
-
選択ソートとバブルソートの組み合わせみたいな感じですね
とても良い勉強になりました、ありがとうございます
満足しました^o^
-
- 753
- 2014/03/25(火) 07:35:56.55
-
可能な操作が、一対一のスワップではなく、４つの正方形で右・左まわりとかだと超絶難しくなりそうですね
そもそももっと一般化すると、状態を表すパラメータと、それを変化させる操作が定義された時に、
ある状態からある状態への移動が可能なのか（言い換えると、状態のグループ化）、また最速な操作の仕方はわかるのかというん問題に帰結しますね
前者の問題は、操作をずっと繰り返してすべての状態をメモリ確保して調べていけば、すべての問題で回答可能ですね
後者の問題はわかりません！誰か偉い人教えてください
ルービックキューブだと、最小手順数の最大値とかまでもうわかってるんでしたっけ確か
-
- 754
- アルゴリズム
- 2014/03/25(火) 08:21:30.02
-
中々この問題は面白いですね
移動が可能かどうかという問題は解決可能なんですか？
全ての状態を割り出して、その中に移動可能かどうか調べたい状態が無ければ移動不可能
という事になると思いますが、全ての状態を割り出したかどうかどうやって判断するんでしょうか？
-
- 755
- 2014/03/25(火) 08:31:00.39
-
>>754
まず前提として初期値が設定されています。ある状態に対する操作は有限個であるので、はじめの状態から一回操作した状態がわかるので
それを記録します。以下繰り返していき、すでに記録された状態に辿り着いたらその分岐はおしまい。
すべての状態の数は有限なので、操作していった時の状態の分岐はいつか終了するので、初期値から変化可能な状態が全て割り出せます。
状態Aから状態Bへたどり着けるかはわかりませんが、状態Aからたどり着けるすべての状態をグループ化できます
そのグループに状態Bが含まれていれば到達可能であり、
そうでないならば先のグループとは別の、状態のグループが存在しているということになります
このページを共有する
おすすめワード