- C言語なら俺に聞け（入門編）Part 125
684 ：デフォルトの名無しさん[sage]：2014/03/24(月) 19:02:46.76 ID:5KtS3atQ - 今、縦3横6計18セルある長方形に１〜18までの要素を1個ずついれて、
下の状態が整列されている状態とする。
1 2 3 4 5 6
7 8 9 10 11 12
13 14 15 16 17 18
整列されていない状態の例は以下である。
9 18 3 4 5 13
7 8 1 10 11 6
12 14 15 16 17 2
|
- C言語なら俺に聞け（入門編）Part 125
685 ：デフォルトの名無しさん[sage]：2014/03/24(月) 19:05:01.32 ID:5KtS3atQ - 任意の整列されていない状態に対して、縦横隣同士を交換して
整列されている状態にする場合、どういうアルゴリズムが最適か？
という問題なんんですがどういうアルゴリズムがいいですか？
プログラムで書けるならそれも教えて下さい。
ソートを使うのがいいですが、隣同士なので体系的なソートの場合
バブルソートしか使えません。
僕の考えは横でバブルソート、縦でバブルソートしか思いつきません。
|
- C言語なら俺に聞け（入門編）Part 125
697 ：デフォルトの名無しさん[sage]：2014/03/24(月) 19:32:28.70 ID:5KtS3atQ - >>688
走査の数ですよ
元々整列されている配列ほど走査数は少ないような方法も欲張るなら
求めたいです
|
- C言語なら俺に聞け（入門編）Part 125
698 ：デフォルトの名無しさん[sage]：2014/03/24(月) 19:35:36.37 ID:5KtS3atQ - >>692
回答ありがとうございます
なんで6で割った余りなんですか？
直接要素同士を比較しないんですか？
|
- C言語なら俺に聞け（入門編）Part 125
701 ：デフォルトの名無しさん[sage]：2014/03/24(月) 19:40:04.26 ID:5KtS3atQ - 全く分からない…
18と6を比較するのに何故18mod6と6mod6を比較するのでしょうか？
|
- C言語なら俺に聞け（入門編）Part 125
703 ：デフォルトの名無しさん[sage]：2014/03/24(月) 19:42:36.82 ID:5KtS3atQ - アルゴリズムまじで頭の良し悪しが分かる…
全く思いつかない
|
- C言語なら俺に聞け（入門編）Part 125
705 ：デフォルトの名無しさん[sage]：2014/03/24(月) 19:45:33.50 ID:5KtS3atQ - 行でソートの場合
6
3
1
をソートしたら
1
3
6
になって6は1行目最終列なのに、遠のく事にならないでしょうか？
|
- C言語なら俺に聞け（入門編）Part 125
708 ：デフォルトの名無しさん[sage]：2014/03/24(月) 19:50:16.45 ID:5KtS3atQ - そもそも整列された状態から交換を繰り返さないとダメですね
適当に配置した標本だと元通りできないですね…
>>706
全く分かりません、余りだと詰むんでしょうか？
|
- C言語なら俺に聞け（入門編）Part 125
711 ：デフォルトの名無しさん[sage]：2014/03/24(月) 19:52:28.14 ID:5KtS3atQ - とりあえず、最初にあまりで比較して最後は要素同士を比較ってことですか？
|
- C言語なら俺に聞け（入門編）Part 125
712 ：デフォルトの名無しさん[sage]：2014/03/24(月) 19:55:26.67 ID:5KtS3atQ - >>709
整列可能という前提です、問題に不備がありすいませんでした。
確実に整列できる方法です。
例えばバブルソートの場合どんなパターンでもO(n(n-1)/4)回で整列可能です。
この場合もO(?)回で完全に整列できるのか知りたいです。
元々整列されていた場合早くするというのは最適化問題になりますので
そういう問題ではなくMAXオーダーを求めたいという事です。
|
- C言語なら俺に聞け（入門編）Part 125
714 ：デフォルトの名無しさん[sage]：2014/03/24(月) 20:11:31.94 ID:5KtS3atQ - 分かりません…
|
- C言語なら俺に聞け（入門編）Part 125
716 ：デフォルトの名無しさん[sage]：2014/03/24(月) 20:15:38.42 ID:5KtS3atQ - そもそも横 縦とも大小の矛盾が無いけど解は無い例なんて
存在するんでしょうか？
3 4 8 9 10
2 5 12....
..........
こういう事ですよね？
無いと思うのですが
|
- C言語なら俺に聞け（入門編）Part 125
719 ：デフォルトの名無しさん[sage]：2014/03/24(月) 20:27:54.88 ID:5KtS3atQ - 結局オーダー回数は理論的に求められないってことでＯＫですか？
そうなるど最適化問題に帰着するんでしょうか
|
- C言語なら俺に聞け（入門編）Part 125
721 ：デフォルトの名無しさん[sage]：2014/03/24(月) 20:32:21.66 ID:5KtS3atQ - >>720
この問題はオーダー何回でしょうか？
後最適化問題じゃないけど、早くする方法みたいなのもあれば
例えばバブルソートを双方向バブルソートにするみたいな
最適化ではないですが強化バージョンなので…
|
- C言語なら俺に聞け（入門編）Part 125
725 ：デフォルトの名無しさん[sage]：2014/03/24(月) 20:43:19.67 ID:5KtS3atQ - >>723
背景ですが、頭脳王という番組を見て9マスの正方形の中にある8個の数字の
書いたパズルを並び替えるという問題があってそこから感銘を受けて18マス
ではどうかという問題を思いつきました。
最初は最適化問題でどうしたら最短で解けるかという事を考えましたが
それ以前に少なくとも何回やれば、つまり最大何回やればどんなパターンで
も整列できるのかすら分からないのでそっちから考えたいと思いました。
|
- C言語なら俺に聞け（入門編）Part 125
728 ：アルゴリズム ◆MWZMauNNLxfX [sage]：2014/03/24(月) 20:55:37.87 ID:5KtS3atQ - >>727
実名は勘弁してください
|
- C言語なら俺に聞け（入門編）Part 125
732 ：アルゴリズム ◆MWZMauNNLxfX [sage]：2014/03/24(月) 21:02:10.15 ID:5KtS3atQ - >>729
縦をソートした後に横をソートしたら、縦でソートしたことが
台無しになってしまい躓いています
|
- C言語なら俺に聞け（入門編）Part 125
736 ：アルゴリズム ◆MWZMauNNLxfX [sage]：2014/03/24(月) 21:19:06.85 ID:5KtS3atQ - >>734
一つの要素を移動して最終的な位置に移動しても別の要素に影響与えるのは
どうしたらいいですか？
|
- C言語なら俺に聞け（入門編）Part 125
738 ：アルゴリズム ◆MWZMauNNLxfX [sage]：2014/03/24(月) 21:40:07.75 ID:5KtS3atQ - うん？やっぱり要素数18のバブルソートなのかな…
|
- C言語なら俺に聞け（入門編）Part 125
740 ：アルゴリズム ◆MWZMauNNLxfX [sage]：2014/03/24(月) 21:48:49.36 ID:5KtS3atQ - 結論出ました。上限回数はバブルソートの回数ですね。
長方形を一列とみなすという事ですが、縦も交換できるから
強化バージョンが作れると思うのですが無理でしょうか？
|
- C言語なら俺に聞け（入門編）Part 125
741 ：アルゴリズム ◆MWZMauNNLxfX [sage]：2014/03/24(月) 21:55:37.89 ID:5KtS3atQ - 誰か教えて下さい…
>>739
解決したら一瞬で去ります、一日中この事考えています
|
- C言語なら俺に聞け（入門編）Part 125
744 ：アルゴリズム ◆MWZMauNNLxfX [sage]：2014/03/24(月) 22:18:58.11 ID:5KtS3atQ - 使える変数はa[17]だけとします
つまり好きな要素を選んだり、選択ソートみたいに最小要素を選んだり
する事はできない。
|